Class: RGL::DFSVisitor

Inherits:

Object

• Object
• RGL::DFSVisitor

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:

• DFSIterator

Direct Known Subclasses

Graph::TarjanSccVisitor

Instance Attribute Summary

• #color_map ⇒ Hash included from GraphVisitor readonly

  A map which store the colors for each vertex.

• #graph ⇒ Graph included from GraphWrapper

  The wrapped graph.

Instance Method Summary

• #attach_distance_map(map = Hash.new(0)) ⇒ Object included from GraphVisitor

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

• #finished_vertex?(v) ⇒ Boolean included from GraphVisitor

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

• #follow_edge?(u, v) ⇒ Boolean included from GraphVisitor

  Shall we follow the edge (u,v); i.e.

• #initialize(graph) ⇒ Object included from GraphVisitor

  Create a new GraphVisitor on graph.

• #reset ⇒ Object included from GraphVisitor

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

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:

• graph (Graph)

#reset ⇒ Object Originally defined in module GraphVisitor

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