Module | RGL::Graph |
In: |
lib/rgl/adjacency.rb
lib/rgl/base.rb lib/rgl/dot.rb lib/rgl/connected_components.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 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.
Returns true if the graph contains no cycles. This is only meaningful for directed graphs. Returns false for undirected graphs.
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.
Call dotty for the graph which is written to the file ‘graph.dot’ in the # current directory.
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.
Return a new ImplicitGraph which has as edges all edges of the receiver which satisfy the predicate filter (a block with two parameters).
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 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.
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.
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.
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.
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.
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 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).
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.