Reading maps from .map files

[alexti]

Arralen said:
Alexti, I think you're missing the point. Someone who is an experienced programmer, maybe software engineer or with an degree in computer science or something, will have little trouble understanding what those libraries do, and how to use them.

Then think of a novice:

He isn't exactly a novice. Didn't he wrote some tools for Dom2? Anyway, if the primary idea is to learn some basics of the language and not to solve the problem of finding the "areas", it doesn't matter which algorithm to use.

Arralen said:
The concept of OO-programming (C++, Java) is new to him,

I think that concept of OO-programming can be new only to old-school programmers Meaning that C++ (and Java, to some extent) concepts match modelling languages almost exactly, so the step of converting the model into procedures is effectively removed.

Arralen said:
And we're talking about a real thin sheet of paper: 100-300 provinces (nodes) at best, with less than 750 interconnects.
A short script will really do.

I wouldn't be so optimistic. For example, check http://domino.research.ibm.com/Comm/...arch2005.html. Just 6x6x6 cube with 2 possible values in a cell and its way beyond the computing power of modern computers.

Getting back to our particular task, the simple algorithm that would check for chokepoints would apparently have to verify if the graph is connected for each single and pair of nodes, which for province with N=200 nodes gives you about O(N^2)=40000 verifications for graph connectivity. And checking graph connectivity is not particularly fast operation. It may or may not be a problem, it's kind of estimation, where you can't say for sure without actual test. So to avoid frustration of discovering that your nicely written program can't handle large maps in reasonable time it may be better to look up for more efficient solutions from the start.

Of course, all this doesn't matter if the primary goal is to learn programming.

[Huzurdaddi]

Actually I would figure that validating whether a graph is connected or not would be an O(n) operation since you simply walk the graph from any randomly selected node and if the number of nodes in the walk is equal to the number of nodes in the graph then it is connected.

So the whole operation you described would be O(n^3).

[alexti]

Imagine graph:
Code:

---

x-x-x-x-x-x-x-x-x-x

---

If you start your walk from any node in the middle you'll reach dead-end without passing through all the nodes, even though the graph is connected. So you need to retrace your steps to walk through all graph. I think that establishing if the graph is connected or not is O(m), where m is number of edges (neighbour connections). However it is somewhat bigger O, in sense that each operation is more costly than iterating through the node. We start from random node, mark is as "visited", select any edge outgoing from "visited" node and mark it as "travelled", mark the node it leads to as "visited" and repeat procedure selecting the next "non-travelled" edge outgoing from "visited" node. If all nodes are "visited" at the end, the graph is connected. In this method we need no more that number of edges iterations, but the most efficient implementation of it will probably involve 2 copy of list of edges and list of nodes and moving elements from one to another, which is more costly than just iterations.

[Huzurdaddi]

When you walk the graph you simply do a BFS on the graph and then color each node as you visit it and never revisit a node which is colored.

One easy method of programming this is to take a random node and push all of it's neighbors onto a stack. Then for each element on the stack check to see if the node is colored if so then ignore if not then push all of it's neighbors on the stack, bump the global count and color the node. Repeat. If at the end the global count is equal to the number of nodes in the graph then it is fully connected. A decent interview question.

The order of this is O(m) ( where m is the number of edges ). When I said the order was O(n^3) I was assuming that n~m this may not be a valid assumption. Clearly in a fully connected graph m = n^2. But most maps in dominions do not match that profile.

PS: I used the word "walk" in my 1st post which was incorrect. I should have defined what I meant which I did in this post sorry about being unclear.

[alexti]

Yeah, it makes sense. I was thinking more, probably my original chokepoint finding approach is bad. On most real Dom2 maps, chokepoints are not of 1st or 2nd order, but 3rd or 4th or higher, which means that they are much harder to calculate. Besides huge extra drain on performance, for chokepoints with higher order a lot of various "mega-area" splits will start to appear and it is unclear how to pick "right" ones.

Thus I came up with yet another rectangular wheel (oops, I meant "mega-area" finding algorithm )

For each node we can introduce a sequence of metrics, 1st metric equal to number of provinces that can be reached in no more than 1 hop, 2nd metric equal to number of provinces that can be reached in no more than 2 hop etc. In practice, we will choose only one of those metrics (depending on the map size, probably). Let's say it will be 7-metric. For this metric there's an area around the node which can be reached within 7 hops. Then we can find the "core" of the mega-areas by the following procedure:
- introduce function f() for pair of the nodes, equal to the number of diffirent provinces they have in their areas.
- find where minimum of f() is loosely reached (for example where f() is different from the exact minimum by no more than 2). Those nodes are considered to be in the "cores". Obviously, nodes that are connected with each other by path that stays within "core" nodes.
- Now we can grow "mega-areas" from the cores by incrementing the range by 1. At some point "mega-areas" will start to clash, those equally remote nodes can be marked as "neutral").
- After every attempt to "grow" leads to clash, the procedure is completed. Now we can review "mega areas" and assign neutral nodes to the "mega areas" in a way to make the density of "mega-areas" most uniform.

[Huzurdaddi]

Whoa. I would need to see the results in a visualizer to see if it makes sense. That is a wacked algorithim!