...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

// named parameter versiontemplate<typename Graph, typename PositionMap, typename Dim, typename Param, typename Tag, typename Rest> void fruchterman_reingold_force_directed_layout (const Graph& g, PositionMap position, Dim width, Dim height, const bgl_named_params<Param, Tag, Rest>& params);// non-named parameter versiontemplate<typename Graph, typename PositionMap, typename Dim, typename AttractiveForce, typename RepulsiveForce, typename ForcePairs, typename DisplacementMap, typename Cooling> void fruchterman_reingold_force_directed_layout (const Graph& g, PositionMap position, Dim width, Dim height, AttractiveForce fa, RepulsiveForce fr, ForcePairs fp, Cooling cool, DisplacementMap displacement); template<typename Graph, typename PositionMap, typename Dim> void fruchterman_reingold_force_directed_layout(const Graph& g, PositionMap position, Dim width, Dim height);

This algorithm [58] performs layout of
unweighted, undirected graphs. Unlike the Kamada-Kawai layout
algorithm, this algorithm directly supports the layout of disconnected
graphs (but see the `force_pairs` named parameter). It is a
*force-directed* algorithm, meaning that vertex layout is
determined by the forces pulling vertices together and pushing them
apart. Attractive forces occur between adjacent vertices only, whereas
repulsive forces occur between every pair of vertices. Each iteration
computes the sum of the forces on each vertex, then moves the vertices
to their new positions. The movement of vertices is mitigated by the
*temperature* of the system for that iteration: as the algorithm
progresses through successive iterations, the temperature should
decrease so that vertices settle in place. The cooling schedule,
attractive forces, and repulsive forces can be provided by the user.

The vertices are often placed randomly prior to execution of this algorithm via `random_graph_layout`.

The graph object on which the algorithm will be applied. The typeIN/OUT:Graphmust be a model of Vertex And Edge List Graph.

Python: This parameter is namedgraphin Python.

The property map that stores the position of each vertex. It should typically be initialized with the vertices at random locations (useIN:random_graph_layout). The typePositionMapmust be a model of Lvalue Property Map such that the vertex descriptor type ofGraphis convertible to its key type. Its value type must be a structure with fieldsxandy, representing the coordinates of the vertex.

Python: The position map must be avertex_point2d_mapfor the graph.

Python default:graph.get_vertex_point2d_map("position")

The width of the display area in which layout should occur. On termination of the algorithm, theIN:xcoordinates of all vertices will fall in[-width/2, width/2].

The height of the display area in which layout should occur. On termination of the algorithm, theycoordinates of all vertices will fall in[-height/2, height/2].

Computes the magnitude of the attractive force between two adjacent vertices. The function objectIN:famust accept four parameters: the edge descriptor,k, the distance between the vertices, and the graph.kis the square root of the ratio of the display area to the number of vertices.

Default:square_distance_attractive_force(), which computes the attractive force as`dist`

.^{2}/k

Python: Any callable Python object that matches the signature will suffice.

Computes the magnitude of the repulsive force between any two vertices. The function objectIN:famust accept five parameters: the two vertex descriptors,k, the distance between the vertices, and the graph.kis the square root of the ratio of the display area to the number of vertices.

Default:square_distance_repsulsive_force(), which computes the repulsive force as`k`

.^{2}/dist

Python: Any callable Python object that matches the signature will suffice.

Enumerates the pairs of vertices on which the repulsive force should be applied.IN:fpis a function object taking two parameters: the graphgand a binary function object that should be passed each pair of vertices to be considered. The basic formulation of the Fruchterman-Reingold algorithm computes repulsive forces between all pairs of vertices (passall_force_pairs()for this parameter), which is functional for disconnected graphs but tends to push the connected components toward the edges of the display area. The grid variant of the algorithm places a grid over the display area and only computes repulsive forces among vertices within each rectangle in the grid. The grid variant can be more efficient than the basic formulation and tends to produce better layouts for disconnected graphs, but is not better overall: passmake_grid_force_pairs(width, height, position, g)as this parameter to use the grid variant. Other enumeration strategies may yield better results for particular graphs.

Default:make_grid_force_pairs(width, height, position, g)

Python: Unsupported parameter.

Determines the cooling schedule for the algorithm, which affects the rate of movement of vertices and termination of the algorithm. TheUTIL:coolparameter is a nullary function object (i.e., one that takes no arguments) and returns the temperature for the current iteration. When the returned temperature is zero, the algorithm terminates. Cooling schedules should begin with some initial temperature and gradually reduce the temperature to zero.

Default:linear_cooling<double>(100)

Python: Any callable Python object that matches the signature will suffice.

The displacement map is used to compute the amount by which each vertex will move in each step. TheIN:DisplacementMaptype carries the same requirements as thePositionMaptype.

Default:Aniterator_property_mapwith a value type ofsimple_point<double>and using the given vertex index map.

Python:Unsupported parameter.

This maps each vertex to an integer in the range[0, num_vertices(g)). This is only necessary when no displacement map is provided. The typeVertexIndexMapmust be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Default:get(vertex_index, g)Note: if you use this default, make sure your graph has an internalvertex_indexproperty. For example,adjacenty_listwithVertexList=listSdoes not have an internalvertex_indexproperty.

Python:Unsupported parameter.

Whenfalse, performs a random layout of the graph before running the Fruchterman-Reingold algorithm. Iftrue, the algorithm is executing starting with the vertex configuration in thepositionmap.

Default:False.

The time complexity is *O(|V| ^{2} + |E|)* for each
iteration of the algorithm in the worse case. The average case for the
grid variant is

Copyright © 2004 | Doug Gregor, Indiana University |