Reading maps from .map files

[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!