Ok, I''m not sure of all the terminology here, so bear with me.
I have a set of nodes, each of which has a link to other nodes... basically, a graph structure. The main problem is that I need a 2D representation of this structure, with the following constraints:
- all links are of a roughly equal weighting and should attempt to reflect this in the 2D distance as far as possible.
- where possible, links should not cross.
I''m especially looking for a system that can fulfill both criteria, although separate algorithms for each one - even if mutually exclusive - may still be useful.
One application of this is in producing an auto-mapper for text-based adventures, where the nodes are rooms connected by north/south/east/west links. This application needs both the constraints above in order to produce a reasonable-looking map. I expect the direction of the exit could be fed into the algorithm as well.
I''m also interested in more abstract graphs, such as plotting links between websites or whatever. In this case I expect that initial node positioning might be random, and adjusted later.
My first thought is to go with some sort of genetic algorithm, where I try a few random graphs, look at how well it fits the constraints, and then use that as the fitness for the genetic algorithm, eventually breeding the best graph. But I think there might be a more guaranteed way to achieve this.
[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]
Generating optimal graphs from node connections
I''ve seen a method, often called "force-directed layout", where you insert springs between each connected node and then simmulate the forces on the nodes until they reach an equilibrium. Here''s a web site with some Java applets (with source) that use this method. It results in pleasing results some of the time.
I''ve also seen refernce to heuristic algorithms being applied to this problem (simmulated anealing, genetic algorithms, etc.), but I have no experience along those lines.
I''ve also seen refernce to heuristic algorithms being applied to this problem (simmulated anealing, genetic algorithms, etc.), but I have no experience along those lines.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement