Module RGL::Graph
In: lib/rgl/topsort.rb
lib/rgl/dot.rb
lib/rgl/traversal.rb
lib/rgl/adjacency.rb
lib/rgl/transitivity.rb
lib/rgl/implicit.rb
lib/rgl/connected_components.rb
lib/rgl/condensation.rb
lib/rgl/base.rb

In BGL terminology the module Graph defines the graph concept (see www.boost.org/libs/graph/doc/graph_concepts.html). We however do not distinguish between the IncidenceGraph, EdgeListGraph and VertexListGraph concepts, which would complicate the interface too much. These concepts are defined in BGL to differentiate between efficient access to edges and vertices.

The RGL Graph concept contains only a few requirements that are common to all the graph concepts. These include, especially, the iterators defining the sets of vertices and edges (see each_vertex and each_adjacent). Most other functions are derived from these fundamental iterators, i.e. num_vertices or num_edges.

Each graph is an enumerable of vertices.

Methods

Included Modules

Enumerable Edge

Classes and Modules

Class RGL::Graph::TarjanSccVisitor

Public Instance methods

==(g)

Alias for eql?

Returns true if the graph contains no cycles. This is only meaningful for directed graphs. Returns false for undirected graphs.

Returns an array of vertices adjacent to vertex v.

Returns a DirectedAdjacencyGraph, which represents a BFS search tree starting at v. This method uses the tree_edge_event of BFSIterator to record all tree edges of the search tree in the result.

Returns an RGL::ImplicitGraph where the strongly connected components of this graph are condensed into single nodes represented by Set instances containing the members of each strongly connected component. Edges between the different strongly connected components are preserved while edges within strongly connected components are omitted.

Raises RGL::NotDirectedError if run on an undirected graph.

Do a recursive DFS search on the whole graph. If a block is passed, it is called on each finish_vertex event. See strongly_connected_components for an example usage.

Start a depth first search at vertex u. The block b is called on each finish_vertex event.

Is the graph directed? The default returns false.

Call dotty for the graph which is written to the file ‘graph.dot’ in the # current directory.

Vertices get enumerated. A graph is thus an enumerable of vertices.


Testing

The each_adjacent iterator defines the out edges of vertex v. This method must be defined by concrete graph classes. Its defines the BGL IncidenceGraph concept.

Compute the connected components of an undirected graph, using a DFS (Depth-first search)-based approach. A _connected component_ of an undirected graph is a set of vertices that are all reachable from each other.

The function is implemented as an iterator which calls the client with an array of vertices for each component.

It raises an exception if the graph is directed.

The each_edge iterator should provide efficient access to all edges of the graph. Its defines the EdgeListGraph concept.

This method must not be defined by concrete graph classes, because it can be implemented using each_vertex and each_adjacent. However for undirected graph the function is inefficient because we must not yield (v,u) if we already visited edge (u,v).

The each_vertex iterator defines the set of vertices. This method must be defined by concrete graph classes. It defines the BGL VertexListGraph concept.

Returns the class for edges: DirectedEdge or UnDirectedEdge.

Return the array of edges (DirectedEdge or UnDirectedEdge) of the graph using each_edge, depending whether the graph is directed or not.

Return a new ImplicitGraph which has as edges all edges of the receiver which satisfy the predicate filter (a block with two parameters).

Example

      g = complete(7).edges_filtered_by {|u,v| u+v == 7}
      g.to_s     => "(1=6)(2=5)(3=4)"
      g.vertices => [1, 2, 3, 4, 5, 6, 7]

Returns true if the graph has no vertices, i.e. num_vertices == 0.


accessing vertices and edges

Equality is defined to be same set of edges and directed?

Returns true if v is a vertex of the graph. Same as include? inherited from Enumerable. Complexity is O(num_vertices) by default. Concrete graph may be better here (see AdjacencyGraph).

Return a new ImplicitGraph which is isomorphic (i.e. has same edges and vertices) to the receiver. It is a shortcut, also used by edges_filtered_by and vertices_filtered_by.

Returns the number of edges.

num_vertices()

Alias for size

Returns the number of out-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v.

Output the DOT-graph to stream s.

Return a new DirectedAdjacencyGraph which has the same set of vertices. If (u,v) is an edge of the graph, then (v,u) is an edge of the result.

If the graph is undirected, the result is self.

Returns the number of vertices.

This is Tarjan‘s algorithm for strongly connected components, from his paper "Depth first search and linear graph algorithms". It calculates the components in a single application of DFS. We implement the algorithm with the help of the DFSVisitor TarjanSccVisitor.

Definition

A _strongly connected component_ of a directed graph G=(V,E) is a maximal set of vertices U which is in V, such that for every pair of vertices u and v in U, we have both a path from u to v and a path from v to u. That is to say, u and v are reachable from each other.

@Article{Tarjan:1972:DFS,

  author =       "R. E. Tarjan",
  key =          "Tarjan",
  title =        "Depth First Search and Linear Graph Algorithms",
  journal =      "SIAM Journal on Computing",
  volume =       "1",
  number =       "2",
  pages =        "146--160",
  month =        jun,
  year =         "1972",
  CODEN =        "SMJCAT",
  ISSN =         "0097-5397 (print), 1095-7111 (electronic)",
  bibdate =      "Thu Jan 23 09:56:44 1997",
  bibsource =    "Parallel/Multi.bib, Misc/Reverse.eng.bib",

}

The output of the algorithm is recorded in a TarjanSccVisitor vis. vis.comp_map will contain numbers giving the component ID assigned to each vertex. The number of components is vis.num_comp.

Convert a general graph to an AdjacencyGraph. If the graph is directed, returns a DirectedAdjacencyGraph; otherwise, returns an AdjacencyGraph.

Return a RGL::DOT::Digraph for directed graphs or a DOT::Subgraph for an undirected Graph. params can contain any graph property specified in rdot.rb.

Utility method to show a string representation of the edges of the graph.

Return a new AdjacencyGraph which has the same set of vertices. If (u,v) is an edge of the graph, then (u,v) and (v,u) (which are the same edges) are edges of the result.

If the graph is undirected, the result is self.

Returns an RGL::DirectedAdjacencyGraph which is the transitive closure of this graph. Meaning, for each path u -> … -> v in this graph, the path is copied and the edge u -> v is added. This method supports working with cyclic graphs by ensuring that edges are created between every pair of vertices in the cycle, including self-referencing edges.

This method should run in O(|V||E|) time, where |V| and |E| are the number of vertices and edges respectively.

Raises RGL::NotDirectedError if run on an undirected graph.

Returns an RGL::DirectedAdjacencyGraph which is the transitive reduction of this graph. Meaning, that each edge u -> v is omitted if path u -> … -> v exists. This method supports working with cyclic graphs; however, cycles are arbitrarily simplified which may lead to variant, although equally valid, results on equivalent graphs.

This method should run in O(|V||E|) time, where |V| and |E| are the number of vertices and edges respectively.

Raises RGL::NotDirectedError if run on an undirected graph.

Return the array of vertices. Synonym for to_a inherited by Enumerable.


Graph adaptors

Return a new ImplicitGraph which has as vertices all vertices of the receiver which satisfy the predicate filter.

The methods provides similar functionaty as the BGL graph adapter filtered_graph (see BOOST_DOC/filtered_graph.html).

Example

  def complete (n)
    set = n.integer? ? (1..n) : n
    RGL::ImplicitGraph.new { |g|
          g.vertex_iterator { |b| set.each(&b) }
          g.adjacent_iterator { |x, b|
            set.each { |y| b.call(y) unless x == y }
          }
    }
  end

  complete(4).to_s =>     "(1=2)(1=3)(1=4)(2=3)(2=4)(3=4)"
  complete(4).vertices_filtered_by {|v| v != 4}.to_s => "(1=2)(1=3)(2=3)"

Use dot to create a graphical representation of the graph. Returns the filename of the graphics file.

[Validate]