| | |
- astar_search(...)
- astar_search(graph, root_vertex, heuristic, visitor = None,
predecessor_map = None, cost_map = None,
distance_map = None, weight_map = None, color_map = None)
Searches a weight, directed or undirected graph using an heuristic
function as guidance.
Parameters:
graph the graph to search. It may be either a directed or
undirected graph.
root_vertex the starting vertex for the search.
heuristic an heuristic function that maps a vertex to a
floating-point value that estimates the distance from
the source to that vertex.
visitor a visitor that will receive events as the search
progresses. Typically this visitor should be derived
from boost.graph.astar_visitor.
predecessor_map a vertex -> vertex map that stores the predecessor of
each vertex in the search tree. From a given vertex,
one can follow the predecessor_map back to the
root_vertex to reconstruct the path taken.
cost_map a vertex -> float map that stores the distance from
the root_vertex to each vertex in the tree plus the
estimated cost to reach the goal.
distance_map a vertex -> float map that stores the distance from
the root_vertex to each vertex in the tree.
weight_map an edge -> float map that stores the weight of each
edge in the graph. Negative edge weights are not
permitted. If no weight map is provided, each edge
will be assumed to have a weight of 1.0.
color_map a vertex property map that stores the "color" of each
vertex, which indicates whether is has not been seen
(white), has been seen but not visited (grey), or has
been visited (black).
See also:
astar_visitor
bellman_ford_shortest_paths
dag_shortest_paths
dijkstra_shortest_paths
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/astar_search.html
- bellman_ford_shortest_paths(...)
- bellman_ford_shortest_paths(graph, root_vertex, predecessor_map = None,
distance_map = None, weight_map = None,
visitor = None) -> bool
Computes the shortest paths from the root vertex to every other vertex
in the graph. Edge weights may be either positive or negative, but if a
negative weight cycle is found the algorithm will return False to
indicate failure. Otherwise, the algorithm returns True on success.
Parameters:
graph the graph on which to compute shortest paths will
run. It may be either a directed or undirected graph.
root_vertex the starting vertex for the shortest-path search.
predecessor_map a vertex -> vertex map that stores the predecessor of
each vertex in the shortest paths tree. From a given
vertex, one can follow the predecessor_map back to
the root_vertex to reconstruct the shortest path.
distance_map a vertex -> float map that stores the distance from
the root_vertex to each vertex in the tree. A
distance of infinity in this property map indicates
that the vertex is unreachable from the root_vertex.
weight_map an edge -> float map that stores the weight of each
edge in the graph. Negative edge weights are
permitted. If no weight map is provided, each edge
will be assumed to have a weight of 1.0.
visitor a visitor that will receive events as the
shortest-paths computation progresses. Typically this
visitor should be derived from
boost.graph.bellman_ford_visitor.
See also:
bellman_ford_visitor
dag_shortest_paths
dijkstra_shortest_paths
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/bellman_ford_shortest.html
- betweenness_centrality_clustering(...)
- betweenness_centrality_clustering(graph, done,
edge_centrality_map = None)
Clusters the graph by repeatedly removing the edge with the largest
betweenness centrality until a certain stopping criteria is reached.
This is a rather inefficient clustering algorithm and should only be
used for small graphs.
Parameters:
graph the graph that will be clustered.
done A Python function (or callable object) that
determines when betweenness centrality clustering
should terminate. It receives three parameters
during each iteration: the maximum centrality,
the edge descriptor that has that centrality, and
the graph itself, and should return True when
clustering is complete.
edge_centrality_map an edge -> float map that stores the centrality
of each edge in the graph.
See also:
brandes_betweenness_centrality
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/bc_clustering.html
- biconnected_components(...)
- biconnected_components(graph, component_map = None) -> list
Computes the biconnected components and articulation points in an
undirected graph, assigning component numbers in the range [0, n) (where
n is the number of biconnected components) to the edges in the graph.
The set of articulation points, i.e., those vertices that separate
biconnected components, will be returned.
Parameters:
graph the graph on which to compute biconnected components.
The graph must be undirected.
component_map an edge -> int map that stores the component number for
each edge in the graph. Edges with the same component
number are in the same biconnected component.
See also:
connected_components
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/biconnected_components.html
- brandes_betweenness_centrality(...)
- brandes_betweenness_centrality(graph, vertex_centrality_map = None,
edge_centrality_map = None,
weight_map = None)
Computes the betweenness centrality of the vertices and/or edges in the
graph. The betweenness centrality of a vertex or edge is the ratio of
shortest paths in the graph that pass through the vertex or edge.
Parameters:
graph the graph on which centrality should be
computed.
vertex_centrality_map a vertex -> float map that stores the
centrality of each vertex in the graph.
edge_centrality_map an edge -> float map that stores the centrality
of each edge in the graph.
weight_map an edge -> float map that stores the weight of
each edge in the graph. If no weight map is
provided, each edge will be assumed to have a
weight of 1.0.
See also:
betweenness_centrality_clustering
central_point_dominance
relative_betweenness_centrality
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/betweenness_centrality.html
- breadth_first_search(...)
- breadth_first_search(graph, root_vertex, buffer = None, visitor = None,
color_map = None)
Performs a breadth-first search on the given graph starting at a
particular vertex.
Parameters:
graph the graph on which the breadth-first search will run. It
may be either a directed or undirected graph.
root_vertex the vertex where the breadth-first search will originate.
buffer the queue used by the breadth-first search. If not
supplied, a simple FIFO queue will be used.
visitor a visitor that will receive events as the breadth-first
search progresses. Typically this visitor should be
derived from boost.graph.bfs_visitor.
color_map a vertex property map that stores the "color" of each
vertex, which indicates whether is has not been seen
(white), has been seen but not visited (grey), or has
been visited (black).
See also:
bfs_visitor
breadth_first_visit
depth_first_search
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/breadth_first_search.html
- central_point_dominance(...)
- central_point_dominance(graph, vertex_centrality_map = None) -> float
Computes the central point dominance of a graph based on the relative
betweeness centrality of the vertices. Returns a value between 0 and 1,
where larger numbers indicate more star-like graphs with a single
central node and 0 indicates a very decentralized graph.
Parameters:
graph the graph on which the relative vertex
centrality has been computed.
vertex_centrality_map a vertex -> float map that stores the relative
centrality of each vertex in the graph.
See also:
betweenness_centrality_clustering
brandes_betweenness_centrality
relative_betweenness_centrality
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/betweenness_centrality.html
- circle_graph_layout(...)
- circle_graph_layout(graph, position_map, radius = 0.5)
Lays out the vertices of the graph along a circle of given radius.
Parameters:
graph the graph on which to perform the layout.
position_map a vertex -> Point2D map that stores the position of each
vertex.
radius the radius of the circle.
See also:
fruchterman_reingold_force_directed_layout
kamada_kawai_spring_layout
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/circle_graph_layout.html
- connected_components(...)
- connected_components(graph, component_map = None) -> int
Computes the connected components in an undirected graph, assigning
component numbers in the range [0, n) (where n is the number of
connected components) to the vertices in the graph. Returns the number
of connected components.
Parameters:
graph the graph on which to compute connected components. The
graph must be undirected.
component_map a vertex -> int map that stores the component number
for each vertex in the graph. Vertices with the same
component number are in the same connected component.
See also:
biconnected_components
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/connected_components.html
- cuthill_mckee_ordering(...)
- cuthill_mckee_ordering(graph, comp = None) -> list
Computes a new ordering for the vertices in the graph that reduces the
bandwidth in a sparse matrix.
Parameters:
graph the graph to be ordered.
comp the comparison function that determines the order the neighbors
are visited.
See also:
king_ordering
minimum_degree_ordering
sloan_ordering
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/cuthill_mckee_ordering.html
- dag_shortest_paths(...)
- dag_shortest_paths(graph, root_vertex, predecessor_map = None,
distance_map = None, weight_map = None,
visitor = None)
Computes the shortest paths from the root vertex to every other vertex
in a directed acyclic graph.
Parameters:
graph the graph on which to compute shortest paths will
run. It may be either a directed or undirected graph.
root_vertex the starting vertex for the shortest-path search.
predecessor_map a vertex -> vertex map that stores the predecessor of
each vertex in the shortest paths tree. From a given
vertex, one can follow the predecessor_map back to
the root_vertex to reconstruct the shortest path.
distance_map a vertex -> float map that stores the distance from
the root_vertex to each vertex in the tree. A
distance of infinity in this property map indicates
that the vertex is unreachable from the root_vertex.
weight_map an edge -> float map that stores the weight of each
edge in the graph. Negative edge weights are
permitted. If no weight map is provided, each edge
will be assumed to have a weight of 1.0.
visitor a visitor that will receive events as the
shortest-paths computation progresses. Typically this
visitor should be derived from
boost.graph.dijkstra_visitor.
See also:
bellman_ford_shortest_paths
dijkstra_visitor
dijkstra_shortest_paths
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/dag_shortest_paths.html
- depth_first_search(...)
- depth_first_search(graph, root_vertex = None, visitor = None,
color_map = None)
Performs a depth-first search on the given graph, optionally starting at
a particular vertex.
Parameters:
graph the graph on which the depth-first search will run. It
may be either a directed or undirected graph.
root_vertex the vertex where the depth-first search will originate.
If none is provided, the depth-first search will cover
all vertices in the graph
visitor a visitor that will receive events as the depth-first
search progresses. Typically this visitor should be
derived from boost.graph.dfs_visitor.
color_map a vertex property map that stores the "color" of each
vertex, which indicates whether is has not been seen
(white), has been seen but not visited (grey), or has
been visited (black).
See also:
breadth_first_search
dfs_visitor
depth_first_visit
undirected_dfs
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/depth_first_search.html
- depth_first_visit(...)
- depth_first_visit(graph, root_vertex, visitor = None, color_map = None)
Performs a depth-first search on the given graph starting at a
particular vertex. Unless depth_first_search, the root_vertex parameter
is mandatory and the color_map, if provided, will NOT be reinitialized.
Parameters:
graph the graph on which the depth-first search will run. It
may be either a directed or undirected graph.
root_vertex the vertex where the depth-first search will originate.
visitor a visitor that will receive events as the depth-first
search progresses. Typically this visitor should be
derived from boost.graph.dfs_visitor.
color_map a vertex property map that stores the "color" of each
vertex, which indicates whether is has not been seen
(white), has been seen but not visited (grey), or has
been visited (black).
See also:
breadth_first_search
dfs_visitor
depth_first_search
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/depth_first_visit.html
- dijkstra_shortest_paths(...)
- dijkstra_shortest_paths(graph, root_vertex, predecessor_map = None,
distance_map = None, weight_map = None,
visitor = None)
Computes the shortest paths from the root vertex to every other vertex
in a graph.
Parameters:
graph the graph on which to compute shortest paths will
run. It may be either a directed or undirected graph.
root_vertex the starting vertex for the shortest-path search.
predecessor_map a vertex -> vertex map that stores the predecessor of
each vertex in the shortest paths tree. From a given
vertex, one can follow the predecessor_map back to
the root_vertex to reconstruct the shortest path.
distance_map a vertex -> float map that stores the distance from
the root_vertex to each vertex in the tree. A
distance of infinity in this property map indicates
that the vertex is unreachable from the root_vertex.
weight_map an edge -> float map that stores the weight of each
edge in the graph. Negative edge weights are not
permitted. If no weight map is provided, each edge
will be assumed to have a weight of 1.0.
visitor a visitor that will receive events as the
shortest-paths computation progresses. Typically this
visitor should be derived from
boost.graph.dijkstra_visitor.
See also:
bellman_ford_shortest_paths
dag_shortest_paths
dijkstra_visitor
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
- fruchterman_reingold_force_directed_layout(...)
- fruchterman_reingold_force_directed_layout(graph, position,
origin = Point2D()/Point3D(),
extent = Point2D(500, 500)/Point3D(500, 500, 500),
attractive_force = None,
repulsive_force = None,
force_pairs = None,
cooling = None,
progressive = False)
Performs Fruchterman-Reingold force-directed layout in either two or
three dimensions. This is a good general-purpose graph layout routine
that handles both directed and undirected, connected and disconnected
graphs.
Parameters:
graph the graph on which to perform the layout.
position a vertex -> Point2D map or vertex -> Point3D that
stores the position of each vertex.
origin the origin of the bounding box in which layout will
occur
extent the extent (size) of the bounding box in which
layout will occur
attractive_force A Python function (or callable object) that computes
the attractive force along an edge. The function
should accept four parameters: the edge descriptor,
the parameter k = sqrt(bounding box
volume/graph.num_vertices()), the distance between
the two endpoints of the edge, and the graph g. If
no attractive force is provided, the default of
dist*dist/k will be used.
repulsive_force A Python function (or callable object) that computes
the repulsive force between two vertices. The
function should accept five parameters: the two
vertex descriptors, followed by the parameter k =
sqrt(bounding box volume/graph.num_vertices()), the
distance between the two endpoints of the edge, and
the graph g. If no repulsive force is provided, the
default of k*k/dist will be used.
force_pairs A Python function (or callable object) that
enumerates the pairs of vertices that should repulse
each other. This function must accept two arguments:
the graph and the apply_force function. It will
traverse the graph and, for each pair of vertices
(u, v) that should repulse each other, execute
apply_force(u, v). If no force_pairs function is
provided, the algorithm will use a 2k x 2k grid to
provide a reasonably performance and accuracy
tradeoff.
cooling A Python function (or callable object) that provides
the maximm displacement (i.e., the "temperature")
for any vertex in each iteration, and terminates the
algorithm by returning a temperature of 0.
progressive when False, vertex positions are randomized before
the algorithm is executed. Otherwise, the positions
stored in the position property map are used as the
starting positions.
See also:
circle_graph_layout
kamada_kawai_spring_layout
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/fruchterman_reingold.html
- isomorphism(...)
- isomorphism(graph1, graph2, isomorphism_map = None,
vertex_invariant = None) -> bool
Determines if the two input graphs are isomorphic. If so, returns True
and fills in the isomorphism_map (if provided). Otherwise, it returns
false.
Parameters:
graph1 the first graph
graph2 the second graph
isomorphism_map a vertex -> vertex map that will store the mapping
from vertices in graph1 to vertices in graph2, if
the graphs are indeed isomorphic.
vertex_invariant A Python function (or callable object) that produces
a hash value given a vertex and its owning graph.
This function must work for both vertices in graph1
and graph2, such that isomorphic vertices have the
same hash value. If no vertex_invariant is provided,
the degree of vertices will be used to aid matching.
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/isomorphism.html
- kamada_kawai_spring_layout(...)
- kamada_kawai_spring_layout(graph, position, weight = None,
side_length = 500.0, done = None,
spring_constant = 1.0, progressive = False)
Performs Kamada-Kawai spring embedding layout in two dimensions on an
undirected, connected, possibly weighted graph. While this algorithm is
considerably more expensive and limited than Fruchterman-Reingold, it
tends to produce much better layouts.
Parameters:
graph the graph on which to perform the layout, which must
be undirected.
position a vertex -> Point2D map that stores the position of
each vertex.
weight an edge -> float map that stores the weight of each
edge in the graph. If no weight map is provided, each
edge will be assumed to have a weight of 1.0.
side_length the length of a side in the 2D bounding box in which
layout will occur
done A Python function (or callable object) that
determines when the local and global phases of the
algorithm will terminate. The function must take four
arguments: delta_p, a measure of how far the point
"p" has moved; "p" the vertex that has been moved
most recently; the graph; and a boolean value that
indicates whether the movement is local (True) or
global (False). If omitted, the algorithm will
terminate will it reaches a local minimum.
spring_constant A constant multiplied by each spring's strength.
Larger values create more pleasing layouts (but take
longer), smaller values produce layouts more rapidly
(but they may not look as good).
progressive when False, vertex positions are randomized before
the algorithm is executed. Otherwise, the positions
stored in the position property map are used as the
starting positions.
See also:
circle_graph_layout
fruchterman_reingold_force_directed_layout
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/kamada_kawai_spring_layout.html
- king_ordering(...)
- king_ordering(graph) -> list
Computes a new ordering for the vertices in the graph that reduces the
bandwidth of a sparse matrix.
Parameters:
graph the graph to be ordered.
See also:
cuthill_mckee_ordering
minimum_degree_ordering
sloan_ordering
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/king_ordering.html
- kruskal_minimum_spanning_tree(...)
- kruskal_minimum_spanning_tree(graph, weight_map) -> list
Computes a minimum spanning forest for the given undirected graph. The
edges in the spanning forest will be returned as a list.
Parameters:
graph the graph whose spanning tree will be computed.
weight_map an edge -> float map that stores the weight of each edge
in the graph.
See also:
prim_minimum_spanning_tree
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/kruskal_min_spanning_tree.html
- minimum_degree_ordering(...)
- minimum_degree_ordering(graph, supernode_size = None, delta = 0) -> list
Computes a new ordering for the vertices in the graph that reduces the
fill-in of sparse matrices.
Parameters:
graph the graph to be ordered.
supernode_size a vertex -> int that provides the supernode size of
each vertex. If omitted, the supernode size of each
vertex will be initialized to 1.
delta the minimum difference between the minimum degree and
the degree of vertices that will be eliminated by
multiple elimination
See also:
cuthill_mckee_ordering
king_ordering
sloan_ordering
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/minimum_degree_ordering.html
- page_rank(...)
- page_rank(graph, rank_map, done_or_iterations = 20)
Computes the PageRank of each vertex in a directed graph. For optimal
results, the graph should be strongly connected.
Parameters:
graph the directed graph whose vertices will be ranked.
rank_map a vertex -> float that will contain the ranks of
each vertex in the graph
done_or_iterations this can either be an integer number of iterations
to run or a Python function (or callable object)
that accepts the rank map and the graph as
arguments and returns True when the algorithm
should terminate
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/page_rank.html
- prim_minimum_spanning_tree(...)
- prim_minimum_spanning_tree(graph, predecessor_map = None,
distance_map = None, weight_map = None,
visitor = None, root_vertex = None,
color_map = None)
Computes the minimum spanning tree from the root vertex, if provided;
otherwise, computes a minimum spanning forest.
Parameters:
graph the graph for which the minimum spanning tree will be
computed.
predecessor_map a vertex -> vertex map that stores the predecessor of
each vertex in the minimum spanning tree. From a
given vertex, one can follow the predecessor_map back
to the root_vertex to reconstruct the shortest path.
distance_map a vertex -> float map that stores the distance from
the root_vertex to each vertex in the tree. A
distance of infinity in this property map indicates
that the vertex is unreachable from the root_vertex.
weight_map an edge -> float map that stores the weight of each
edge in the graph. Negative edge weights are not
permitted. If no weight map is provided, each edge
will be assumed to have a weight of 1.0.
visitor a visitor that will receive events as the
shortest-paths computation progresses. Typically this
visitor should be derived from
boost.graph.dijkstra_visitor.
root_vertex the starting vertex for the minimum spanning tree. If
omitted a minimum spanning forest will be computed.
color_map a vertex property map that stores the "color" of each
vertex, which indicates whether is has not been seen
(white), has been seen but not visited (grey), or has
been visited (black).
See also:
dfs_visitor
kruskal_minimum_spanning_tree
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/prim_minimum_spanning_tree.html
- relative_betweenness_centrality(...)
- relative_betweenness_centrality(graph, vertex_centrality_map = None)
Transforms the raw vertex betweenness centrality produced by
brandes_betweenness_centrality into a relative betweenness centrality
that can be used by central_point_dominance or for comparison with other
graphs.
Parameters:
graph the graph on which the vertex centrality has
been computed.
vertex_centrality_map a vertex -> float map that stores the relative
centrality of each vertex in the graph.
See also:
betweenness_centrality_clustering
brandes_betweenness_centrality
central_point_dominance
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/betweenness_centrality.html
- sequential_vertex_coloring(...)
- sequential_vertex_coloring(graph, color_map = None) -> int
Colors the vertices of the graph using a simple but relatively efficient
algorithm. Returns the number "n" of colors used, and the color_map will
contain colors for each vertex in the range [0, n).
Parameters:
graph the graph whose vertices will be colored
color_map a vertex -> int map that will contain the color of each
vertex
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/sequential_vertex_coloring.html
- sloan_ordering(...)
- sloan_ordering(graph, start, end, color_map = None,
priority_map = None, weight1 = 1.0,
weight2 = 2.0) -> list
sloan_ordering(graph, color_map = None, priority_map = None,
weight1 = 1.0, weight2 = 2.0) -> list
Computes a new ordering for the vertices in the graph that reduces the
profile and wavefront of sparse matrices. The start and end vertices are
optional, but providing them can have a large (positive or negative)
effect on the resulting ordering.
Parameters:
graph the graph to be ordered.
start the vertex from which ordering should start
end the vertex at which ordering should end
color_map a vertex property map that stores the "color" of each
vertex, which indicates whether is has not been seen
(white), has been seen but not visited (grey), or has
been visited (black).
priority_map a vertex -> float map used internally that tracks the
priority of each vertex.
weight1 Relative weight applied to the global "degree".
weight2 Relative weight applied to the global "degree".
See also:
cuthill_mckee_ordering
king_ordering
minimum_degree_ordering
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/sloan_ordering.html
- strong_components(...)
- strong_components(graph, component_map = None) -> int
Computes the strongly connected components in a directed graph,
assigning component numbers in the range [0, n) (where n is the number
of strongly connected components) to the vertices in the graph. Returns
the number of strongly connected components.
Parameters:
graph the graph on which to compute strongly connected
components. The graph must be directed.
component_map a vertex -> int map that stores the component number
for each vertex in the graph. Vertices with the same
component number are in the same strongly connected
component.
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/strong_components.html
- topological_sort(...)
- topological_sort(graph, color_map = None) -> list
Computes a reverse topological ordering of the vertices in the graph.
Returns the list of vertices in their new order.
Parameters:
graph the graph to be ordered.
color_map a vertex property map that stores the "color" of each
vertex, which indicates whether is has not been seen
(white), has been seen but not visited (grey), or has been
visited (black).
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/topological_sort.html
- transitive_closure(...)
- transitive_closure(graph, orig_to_copy = None) -> Digraph
Computes the transitive closure of a directed graph and returns the
resulting graph. The input graph is not modified.
Parameters:
graph the directed graph from which the transition closure
will be computed.
orig_to_copy a vertex -> vertex map that maps from the vertices of
the input graph to the vertices of the resulting graph.
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/transitive_closure.html
- undirected_dfs(...)
- undirected_dfs(graph, visitor = None, color_map = None,
edge_color_map = None)
Performs an undirected depth-first search on the given graph.
Parameters:
graph the undirected graph on which the depth-first search
will run.
visitor a visitor that will receive events as the depth-first
search progresses. Typically this visitor should be
derived from boost.graph.dfs_visitor.
color_map a vertex property map that stores the "color" of each
vertex, which indicates whether is has not been seen
(white), has been seen but not visited (grey), or has
been visited (black).
edge_color_map an edge property map that stores the "color" of each
edge, allowing the algorithm to distinguish between
tree and back edges in an undirected graph
See also:
dfs_visitor
depth_first_search
depth_first_visit
Complete C++ documentation is available at:
http://www.boost.org/libs/graph/doc/undirected_dfs.html
|