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

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

The RGL Graph concept contains only few requirements that are common to all the graph concepts. These include especially the iterators defining the set 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

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.

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 be 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 be 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 may 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 be 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 vertex, i.e. num_vertices == 0.


accessing vertices and edges

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 bee 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.

Synonym 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 DOT::DOTDigraph for directed graphs or a DOT::DOTSubgraph 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.

transitive_closure()

Floyd-Warshal algorithm which should be O(n^3), where n is the number of nodes. We can probably work a bit on the constant factors!

In BGL, there is an algorithm with time complexity (worst-case) O(|V||E|) (see BOOST_DOC/transitive_closure.html), based on the detection of strong components.

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 do to create a graphical representation of the graph. Returns the filename of the graphics file.

[Validate]