Archived

This topic is now archived and is closed to further replies.

Kylotan

Generating optimal graphs from node connections

Recommended Posts

Kylotan    9983
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]

Share this post


Link to post
Share on other sites
GrinningGator    122
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.

Share this post


Link to post
Share on other sites