Class: RGL::DFSVisitor

Inherits:
Object
  • Object
show all
Includes:
GraphVisitor
Defined in:
lib/rgl/traversal.rb

Overview

A DFSVisitor is needed by the Graph#depth_first_search and Graph#depth_first_visit methods of a graph. Besides the eventpoints of GraphVisitor, it provides an additional eventpoint start_vertex, which is called when a depth_first_search starts a new subtree of the depth first forest that is defined by the search.

See Also:

Direct Known Subclasses

Graph::TarjanSccVisitor

Instance Attribute Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#color_map ⇒ Hash (readonly) Originally defined in module GraphVisitor

Returns a map which store the colors for each vertex.

Returns:

  • (Hash) —

    a map which store the colors for each vertex

#graph ⇒ Graph Originally defined in module GraphWrapper

Returns the wrapped graph.

Returns:

  • (Graph) —

    the wrapped graph

Instance Method Details

#attach_distance_map(map = Hash.new(0)) ⇒ Object Originally defined in module GraphVisitor

Attach a map to the visitor which records the distance of a visited vertex to the start vertex.

This is similar to BGLs distance_recorder.

After the distance_map is attached, the visitor has a new method distance_to_root, which answers the distance to the start vertex.

#finished_vertex?(v) ⇒ Boolean Originally defined in module GraphVisitor

Returns true if vertex v is colored :BLACK (i.e. finished).

Returns:

  • (Boolean)

#follow_edge?(u, v) ⇒ Boolean Originally defined in module GraphVisitor

Shall we follow the edge (u,v); i.e. v has color :WHITE

Returns:

  • (Boolean)

#initialize(graph) ⇒ Object Originally defined in module GraphVisitor

Create a new GraphVisitor on graph.

Parameters:

#reset ⇒ Object Originally defined in module GraphVisitor

Mark each vertex unvisited (i.e. :WHITE)