| Force-based Algorithms |
Website Links For Algorithms |
Information AboutForce-based Algorithms |
| CATEGORIES ABOUT FORCE-BASED ALGORITHMS | |
| graph algorithms | |
| articles with example pseudocode | |
|
The force-directed algorithms achieve this by assigning forces amongst the set of edges and the set of nodes; the most straightforward method is to assign forces as if the edges were Springs (see Hooke's Law ) and the nodes were Electrically Charged particles (see Coulomb's Law ). The entire graph is then simulated as if it were a physical system. The forces are applied to the nodes, pulling them closer together or pushing them further apart. This is repeated iteratively until the system comes to an equilibrium state; i.e., their relative positions do not change anymore from one iteration to the next. At that moment, the graph is drawn. The physical interpretation of this equilibrium state is that all the forces are in Mechanical Equilibrium . A force-directed graph can involve forces other than mechanical springs and electrical repulsion; examples include logarithmic springs (as opposed to linear springs) and magnetic or gravitational fields. The results of this class of algorithm often look very good. In the case of spring-and-charged-particle graphs, the edges tend to have uniform length (because of the spring forces), and nodes that are not connected by an edge tend to be drawn further apart (because of the electrical repulsion). While graph drawing is a difficult problem, force-directed algorithms, being physical simulations, usually require no special knowledge about graph theory such as Planarity . Another advantage of this class of algorithm is the interactive aspect. By drawing the intermediate stages of the graph, the user can follow how the graph evolves, seeing it unfold from a tangled mess into a good-looking configuration. In some interactive graph drawing tools, the user can pull one or more nodes out of their equilibrium state and watch them migrate back into position.
Due to the physical simulation aspect, such as with masses and springs, it is easy to see that force-directed algorithms produce a graph with minimal total energy, or at least one whose total energy is a ''local'' minimum. It is also possible to employ mechanisms that search more directly for energy minima, either instead of or in conjunction with physical simulation. Such mechanisms, which are examples of general Global Optimization methods, include Simulated Annealing and Genetic Algorithms . EXTERNAL LINKS
|
|
|