module RGL::Graph

In BGL terminology the module Graph defines the graph concept (see Graph Concepts). 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. {#each_edge}, {#num_vertices} or {#num_edges}.

Each graph is an enumerable of vertices.

Public Instance Methods

==(other)
Alias for: eql?
acyclic?() click to toggle source

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

   # File lib/rgl/topsort.rb
75 def acyclic?
76   topsort_iterator.length == num_vertices
77 end
adjacent_vertices(v) click to toggle source

@return [Array] of vertices adjacent to vertex v. @param (see each_adjacent)

    # File lib/rgl/base.rb
230 def adjacent_vertices(v)
231   r = []
232   each_adjacent(v) { |u| r << u }
233   r
234 end
bellman_ford_shortest_paths(edge_weights_map, source, visitor = BellmanFordVisitor.new(self)) click to toggle source

Finds the shortest paths from the source to each vertex of the graph.

Returns a Hash that maps each vertex of the graph to an Array of vertices that represents the shortest path from the source to the vertex. If the path doesn’t exist, the corresponding hash value is nil. For the source vertex returned hash contains a trivial one-vertex path - [source].

Unlike Dijkstra algorithm, Bellman-Ford shortest paths algorithm works with negative edge weights.

Raises ArgumentError if an edge weight is undefined.

Raises ArgumentError or the graph has negative-weight cycles. This behavior can be overridden my a custom handler for visitor’s edge_not_minimized event. @return [Hash]

    # File lib/rgl/bellman_ford.rb
109 def bellman_ford_shortest_paths(edge_weights_map, source, visitor = BellmanFordVisitor.new(self))
110   BellmanFordAlgorithm.new(self, edge_weights_map, visitor).shortest_paths(source)
111 end
bfs_iterator(v = self.detect { |x| true }) click to toggle source

@return [BFSIterator] starting at vertex v.

    # File lib/rgl/traversal.rb
111 def bfs_iterator(v = self.detect { |x| true })
112   BFSIterator.new(self, v)
113 end
bfs_search_tree_from(v) click to toggle source

This method uses the tree_edge_event of BFSIterator to record all tree edges of the search tree in the result.

@return [DirectedAdjacencyGraph] which represents a BFS search tree starting at v.

    # File lib/rgl/traversal.rb
119 def bfs_search_tree_from(v)
120   unless defined?(DirectedAdjacencyGraph)
121     require 'rgl/adjacency'
122   end
123   bfs  = bfs_iterator(v)
124   tree = DirectedAdjacencyGraph.new
125 
126   bfs.set_tree_edge_event_handler do |from, to|
127     tree.add_edge(from, to)
128   end
129 
130   bfs.set_to_end # does the search
131   tree
132 end
bipartite?() click to toggle source

Returns true if the graph is bipartite. Otherwise returns false.

   # File lib/rgl/bipartite.rb
38 def bipartite?
39   !bipartite_sets.nil?
40 end
bipartite_sets() click to toggle source

Separates graph’s vertices into two disjoint sets so that every edge of the graph connects vertices from different sets. If it’s possible, the graph is bipartite.

Returns an array of two disjoint vertices sets (represented as arrays) if the graph is bipartite. Otherwise, returns nil. @return [Array]

   # File lib/rgl/bipartite.rb
14 def bipartite_sets
15   raise NotUndirectedError.new('bipartite sets can only be found for an undirected graph') if directed?
16 
17   bfs = BipartiteBFSIterator.new(self)
18 
19   # if necessary, we start BFS from each vertex to make sure
20   # that all connected components of the graph are processed
21   each_vertex do |u|
22     next if bfs.finished_vertex?(u)
23 
24     bfs.reset_start(u)
25     bfs.move_forward_until { bfs.found_odd_cycle }
26 
27     return if bfs.found_odd_cycle
28   end
29 
30   bfs.bipartite_sets_map.inject([[], []]) do |sets, (vertex, set)|
31     sets[set] << vertex
32     sets
33   end
34 end
condensation_graph() click to toggle source

Returns an {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 {NotDirectedError} if run on an undirected graph. @return ImplicitGraph

   # File lib/rgl/condensation.rb
17 def condensation_graph
18   raise NotDirectedError,
19         "condensation_graph only supported for directed graphs" unless directed?
20 
21   # Get the component map for the strongly connected components.
22   comp_map = strongly_connected_components.comp_map
23 
24   # Invert the map such that for any number, n, in the component map a Set
25   # instance is created containing all of the nodes which map to n. The Set
26   # instances will be used to map to the number, n, with which the elements
27   # of the set are associated.
28   inv_comp_map = {}
29   comp_map.each { |v, n| (inv_comp_map[n] ||= Set.new) << v }
30 
31   # Create an ImplicitGraph where the nodes are the strongly connected
32   # components of this graph and the edges are the edges of this graph which
33   # cross between the strongly connected components.
34   ImplicitGraph.new do |g|
35     g.vertex_iterator do |b|
36       inv_comp_map.each_value(&b)
37     end
38 
39     g.adjacent_iterator do |scc, b|
40       scc.each do |v|
41         each_adjacent(v) do |w|
42           # Do not make the cluster reference itself in the graph.
43           if comp_map[v] != comp_map[w]
44             b.call(inv_comp_map[comp_map[w]])
45           end
46         end
47       end
48     end
49 
50     g.directed = true
51   end
52 end
depth_first_visit(u, vis = DFSVisitor.new(self), &b) click to toggle source

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

    # File lib/rgl/traversal.rb
195 def depth_first_visit(u, vis = DFSVisitor.new(self), &b)
196   vis.color_map[u] = :GRAY
197   vis.handle_examine_vertex(u)
198 
199   each_adjacent(u) do |v|
200     vis.handle_examine_edge(u, v)
201 
202     if vis.follow_edge?(u, v)          # (u,v) is a tree edge
203       vis.handle_tree_edge(u, v)       # also discovers v
204       # color of v was :WHITE. Will be marked :GRAY in recursion
205       depth_first_visit(v, vis, &b)
206     else                               # (u,v) is a non tree edge
207       if vis.color_map[v] == :GRAY
208         vis.handle_back_edge(u, v)     # (u,v) has gray target
209       else
210         vis.handle_forward_edge(u, v)  # (u,v) is a cross or forward edge
211       end
212     end
213   end
214 
215   vis.color_map[u] = :BLACK
216   vis.handle_finish_vertex(u) # finish vertex
217   b.call(u)
218 end
dfs_iterator(v = self.detect { |x| true }) click to toggle source

@return [DFSIterator] staring at vertex v.

    # File lib/rgl/traversal.rb
171 def dfs_iterator(v = self.detect { |x| true })
172   DFSIterator.new(self, v)
173 end
dijkstra_shortest_path(edge_weights_map, source, target, visitor = DijkstraVisitor.new(self)) click to toggle source

Finds the shortest path from the source to the target in the graph.

If the path exists, returns it as an Array of vertices. Otherwise, returns nil.

Raises ArgumentError if edge weight is negative or undefined.

    # File lib/rgl/dijkstra.rb
116 def dijkstra_shortest_path(edge_weights_map, source, target, visitor = DijkstraVisitor.new(self))
117   DijkstraAlgorithm.new(self, edge_weights_map, visitor).shortest_path(source, target)
118 end
dijkstra_shortest_paths(edge_weights_map, source, visitor = DijkstraVisitor.new(self)) click to toggle source

Finds the shortest paths from the source to each vertex of the graph.

Returns a Hash that maps each vertex of the graph to an Array of vertices that represents the shortest path from the source to the vertex. If the path doesn’t exist, the corresponding hash value is nil. For the source vertex returned hash contains a trivial one-vertex path - [source].

Raises ArgumentError if edge weight is negative or undefined.

    # File lib/rgl/dijkstra.rb
128 def dijkstra_shortest_paths(edge_weights_map, source, visitor = DijkstraVisitor.new(self))
129   DijkstraAlgorithm.new(self, edge_weights_map, visitor).shortest_paths(source)
130 end
directed?() click to toggle source

Is the graph directed? The default returns false.

    # File lib/rgl/base.rb
180 def directed?
181   false
182 end
dotty(params = {}) click to toggle source

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

    # File lib/rgl/dot.rb
103 def dotty(params = {})
104   dotfile = "graph.dot"
105   File.open(dotfile, "w") do |f|
106     print_dotted_on(params, f)
107   end
108   unless system("dotty", dotfile)
109     raise "Error executing dotty. Did you install GraphViz?"
110   end
111 end
each(&block) click to toggle source

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

    # File lib/rgl/base.rb
175 def each(&block)
176   each_vertex(&block)
177 end
each_adjacent(v) { |v| ... } click to toggle source

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. @param v a vertex of the graph

    # File lib/rgl/base.rb
152 def each_adjacent(v, &block) # :yields: v
153   raise NotImplementedError
154 end
each_connected_component() { |comp| ... } click to toggle source

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.

   # File lib/rgl/connected_components.rb
23 def each_connected_component
24   raise NotUndirectedError,
25         "each_connected_component only works " +
26             "for undirected graphs." if directed?
27 
28   comp = []
29   vis  = DFSVisitor.new(self)
30   vis.set_finish_vertex_event_handler { |v| comp << v }
31 
32   vis.set_start_vertex_event_handler do |v|
33     yield comp unless comp.empty?
34     comp = []
35   end
36 
37   depth_first_search(vis) { |v| }
38   yield comp unless comp.empty?
39 end
each_edge() { |u, v| ... } click to toggle source

The each_edge iterator should provide efficient access to all edges of the graph. Its defines the BGL 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 graphs the function is inefficient because we must not yield (v,u) if we already visited edge (u,v).

    # File lib/rgl/base.rb
163 def each_edge(&block)
164   if directed?
165     each_vertex do |u|
166       each_adjacent(u) { |v| yield u, v }
167     end
168   else
169     each_edge_aux(&block) # concrete graphs should to this better
170   end
171 end
each_vertex() { |v| ... } click to toggle source

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

    # File lib/rgl/base.rb
143 def each_vertex(&block) # :yields: v
144   raise NotImplementedError
145 end
edge_class() click to toggle source

@return [Class] the class for edges: {Edge::DirectedEdge} or {Edge::UnDirectedEdge}.

    # File lib/rgl/base.rb
215 def edge_class
216   directed? ? DirectedEdge : UnDirectedEdge
217 end
edges() click to toggle source

@return [Array] of edges (DirectedEdge or UnDirectedEdge) of the graph It uses {#each_edge} to compute the edges

    # File lib/rgl/base.rb
221 def edges
222   result = []
223   c = edge_class
224   each_edge { |u, v| result << c.new(u, v) }
225   result
226 end
edges_filtered_by(&filter) click to toggle source

Returns 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]

@return [ImplicitGraph]

    # File lib/rgl/implicit.rb
146 def edges_filtered_by(&filter)
147   implicit_graph do |g|
148     g.adjacent_iterator do |v, b|
149       self.each_adjacent(v) do |u|
150         b.call(u) if filter.call(v, u)
151       end
152     end
153 
154     g.edge_iterator do |b|
155       self.each_edge { |u, v| b.call(u, v) if filter.call(u, v) }
156     end
157   end
158 end
empty?() click to toggle source

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

    # File lib/rgl/base.rb
203 def empty?
204   num_vertices.zero?
205 end
eql?(other) click to toggle source

Two graphs are equal iff they have equal directed? property as well as vertices and edges sets. @param [Graph] other

    # File lib/rgl/base.rb
271 def eql?(other)
272   equal?(other) || eql_graph?(other)
273 end
Also aliased as: ==
has_edge?(u, v) click to toggle source

Returns true if +(u, v)+ is an edge of the graph. @param (see each_edge)

    # File lib/rgl/base.rb
194 def has_edge?(u, v)
195   each_adjacent(u) do |w|
196     return true if v == w
197   end
198   return false
199 end
has_vertex?(v) click to toggle source

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). @param (see each_adjacent)

    # File lib/rgl/base.rb
188 def has_vertex?(v)
189   include?(v) # inherited from enumerable
190 end
implicit_graph() { |result| ... } click to toggle source

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 [ImplicitGraph]

    # File lib/rgl/implicit.rb
164 def implicit_graph
165   result = ImplicitGraph.new do |g|
166     g.vertex_iterator { |b| self.each_vertex(&b) }
167     g.adjacent_iterator { |v, b| self.each_adjacent(v, &b) }
168     g.directed = self.directed?
169   end
170 
171   yield result if block_given? # let client overwrite defaults
172   result
173 end
maximum_flow(edge_capacities_map, source, sink) click to toggle source

Finds the maximum flow from the source to the sink in the graph.

Returns flows map as a hash that maps each edge of the graph to a flow through that edge that is required to reach the maximum total flow.

For the method to work, the graph should be first altered so that for each directed edge (u, v) it contains reverse edge (u, v). Capacities of the primary edges should be non-negative, while reverse edges should have zero capacity.

Raises ArgumentError if the graph is not directed.

Raises ArgumentError if a reverse edge is missing, edge capacity is missing, an edge has negative capacity, or a reverse edge has positive capacity.

@return [Hash]

    # File lib/rgl/edmonds_karp.rb
136 def maximum_flow(edge_capacities_map, source, sink)
137   EdmondsKarpAlgorithm.new(self, edge_capacities_map).maximum_flow(source, sink)
138 end
num_edges() click to toggle source

@return [int] the number of edges

    # File lib/rgl/base.rb
256 def num_edges
257   r = 0
258   each_edge { |u, v| r +=1 }
259   r
260 end
num_vertices()
Alias for: size
out_degree(v) click to toggle source

Returns the number of out-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v. @return [int] @param (see each_adjacent)

    # File lib/rgl/base.rb
240 def out_degree(v)
241   r = 0
242   each_adjacent(v) { |u| r += 1 }
243   r
244 end
path?(source, target) click to toggle source

Checks whether a path exists between source and target vertices in the graph.

   # File lib/rgl/path.rb
10 def path?(source, target)
11   return false unless has_vertex?(source)
12 
13   bfs_iterator = bfs_iterator(source)
14   bfs_iterator.include?(target)
15 end
prim_minimum_spanning_tree(edge_weights_map, start_vertex = nil, visitor = DijkstraVisitor.new(self)) click to toggle source

Finds the minimum spanning tree of the graph.

Returns an {AdjacencyGraph} that represents the minimum spanning tree of the graph’s connectivity component that contains the starting vertex. The algorithm starts from an arbitrary vertex if the start_vertex is not given. Since the implementation relies on the Dijkstra’s algorithm, Prim’s algorithm uses the same visitor class and emits the same events.

Raises ArgumentError if edge weight is undefined.

   # File lib/rgl/prim.rb
49 def prim_minimum_spanning_tree(edge_weights_map, start_vertex = nil, visitor = DijkstraVisitor.new(self))
50   PrimAlgorithm.new(self, edge_weights_map, visitor).minimum_spanning_tree(start_vertex)
51 end
print_dotted_on(params = {}, s = $stdout) click to toggle source

Output the DOT-graph to stream s.

reverse() click to toggle source

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. @return [DirectedAdjacencyGraph]

    # File lib/rgl/adjacency.rb
182 def reverse
183   return self unless directed?
184   result = DirectedAdjacencyGraph.new
185   each_vertex { |v| result.add_vertex v }
186   each_edge { |u, v| result.add_edge(v, u) }
187   result
188 end
set_edge_options(u, v, **options) click to toggle source

Set the configuration values for the given edge

   # File lib/rgl/dot.rb
34 def set_edge_options(u, v, **options)
35   edge = edge_class.new(u, v)
36   @edge_options ||= {}
37   @edge_options[edge] ||= {}
38 
39   RGL::DOT::EDGE_OPTS.each do |opt|
40     @edge_options[edge][:"#{opt}"] = options[:"#{opt}"] if options.key?(:"#{opt}")
41   end
42 end
set_vertex_options(vertex, **options) click to toggle source

Set the configuration values for the given vertex

   # File lib/rgl/dot.rb
24 def set_vertex_options(vertex, **options)
25   @vertex_options ||= {}
26   @vertex_options[vertex] ||= {}
27 
28   RGL::DOT::NODE_OPTS.each do |opt|
29     @vertex_options[vertex][:"#{opt}"] = options[:"#{opt}"] if options.key?(:"#{opt}")
30   end
31 end
size() click to toggle source

@return [int] the number of vertices

    # File lib/rgl/base.rb
248 def size # Why not in Enumerable?
249   inject(0) { |n, v| n + 1 }
250 end
Also aliased as: num_vertices
strongly_connected_components() click to toggle source

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. @return [TarjanSccVisitor]

    # File lib/rgl/connected_components.rb
135 def strongly_connected_components
136   raise NotDirectedError,
137         "strong_components only works for directed graphs." unless directed?
138 
139   vis = TarjanSccVisitor.new(self)
140   depth_first_search(vis) { |v| }
141   vis
142 end
to_adjacency() click to toggle source

Convert a general graph to an AdjacencyGraph. If the graph is directed, returns a {DirectedAdjacencyGraph}; otherwise, returns an {AdjacencyGraph}. @return {DirectedAdjacencyGraph} or {AdjacencyGraph}

    # File lib/rgl/adjacency.rb
170 def to_adjacency
171   result = (directed? ? DirectedAdjacencyGraph : AdjacencyGraph).new
172   each_vertex { |v| result.add_vertex(v) }
173   each_edge { |u, v| result.add_edge(u, v) }
174   result
175 end
to_dot_graph(params = {}) click to toggle source

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

   # File lib/rgl/dot.rb
48 def to_dot_graph(params = {})
49   params['name'] ||= self.class.name.gsub(/:/, '_')
50   fontsize       = params['fontsize'] ? params['fontsize'] : '8'
51   graph          = (directed? ? DOT::Digraph : DOT::Graph).new(params)
52   edge_class     = directed? ? DOT::DirectedEdge : DOT::Edge
53 
54   each_vertex do |v|
55     default_vertex_options = {
56       'name'     => vertex_id(v),
57       'fontsize' => fontsize,
58       'label'    => vertex_label(v)
59     }
60     each_vertex_options = default_vertex_options
61 
62     if @vertex_options && @vertex_options[v]
63       RGL::DOT::NODE_OPTS.each do |opt|
64         if @vertex_options[v].key?(:"#{opt}")
65           each_vertex_options["#{opt}"] = @vertex_options[v].fetch(:"#{opt}")
66         end
67       end
68     end
69     graph << DOT::Node.new(each_vertex_options)
70   end
71 
72   edges.each do |edge|
73     default_edge_options = {
74       'from'     => edge.source,
75       'to'       => edge.target,
76       'fontsize' => fontsize
77     }
78 
79     each_edge_options = default_edge_options
80 
81     if @edge_options && @edge_options[edge]
82       RGL::DOT::EDGE_OPTS.each do |opt|
83         if @edge_options[edge].key?(:"#{opt}")
84           each_edge_options["#{opt}"] = @edge_options[edge].fetch(:"#{opt}")
85         end
86       end
87     end
88     graph << edge_class.new(each_edge_options)
89     end
90 
91   graph
92 end
to_s() click to toggle source

Utility method to show a string representation of the edges of the graph. @return [String]

    # File lib/rgl/base.rb
264 def to_s
265   edges.collect {|e| e.to_s}.sort.join
266 end
to_undirected() click to toggle source

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. @return [AdjacencyGraph]

    # File lib/rgl/adjacency.rb
196 def to_undirected
197   return self unless directed?
198   AdjacencyGraph.new(Set, self)
199 end
topsort_iterator() click to toggle source

@return [TopsortIterator] for the graph.

   # File lib/rgl/topsort.rb
68 def topsort_iterator
69   TopsortIterator.new(self)
70 end
transitive_closure() click to toggle source

Returns an {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 {NotDirectedError} if run on an undirected graph. @return DirectedAdjacencyGraph

   # File lib/rgl/transitivity.rb
20 def transitive_closure
21   raise NotDirectedError,
22         "transitive_closure only supported for directed graphs" unless directed?
23 
24   # Compute a condensation graph in order to hide cycles.
25   cg = condensation_graph
26 
27   # Use a depth first search to calculate the transitive closure over the
28   # condensation graph. This ensures that as we traverse up the graph we
29   # know the transitive closure of each subgraph rooted at each node
30   # starting at the leaves. Subsequent root nodes which consume these
31   # subgraphs by way of the nodes' immediate successors can then immediately
32   # add edges to the roots of the subgraphs and to every successor of those
33   # roots.
34   tc_cg = DirectedAdjacencyGraph.new
35   cg.depth_first_search do |v|
36     # For each vertex v, w, and x where the edges v -> w and w -> x exist in
37     # the source graph, add edges v -> w and v -> x to the target graph.
38     cg.each_adjacent(v) do |w|
39       tc_cg.add_edge(v, w)
40       tc_cg.each_adjacent(w) do |x|
41         tc_cg.add_edge(v, x)
42       end
43     end
44     # Ensure that a vertex with no in or out edges is added to the graph.
45     tc_cg.add_vertex(v)
46   end
47 
48   # Expand the condensed transitive closure.
49   #
50   # For each trivial strongly connected component in the condensed graph,
51   # add the single node it contains to the new graph and add edges for each
52   # edge the node begins in the original graph.
53   # For each NON-trivial strongly connected component in the condensed
54   # graph, add each node it contains to the new graph and add edges to
55   # every node in the strongly connected component, including self
56   # referential edges. Then for each edge of the original graph from any
57   # of the contained nodes, add edges from each of the contained nodes to
58   # all the edge targets.
59   g = DirectedAdjacencyGraph.new
60   tc_cg.each_vertex do |scc|
61     scc.each do |v|
62       # Add edges between all members of non-trivial strongly connected
63       # components (size > 1) and ensure that self referential edges are
64       # added when necessary for trivial strongly connected components.
65       if scc.size > 1 || has_edge?(v, v)
66         scc.each do |w|
67           g.add_edge(v, w)
68         end
69       end
70       # Ensure that a vertex with no in or out edges is added to the graph.
71       g.add_vertex(v)
72     end
73     # Add an edge from every member of a strongly connected component to
74     # every member of each strongly connected component to which the former
75     # points.
76     tc_cg.each_adjacent(scc) do |scc2|
77       scc.each do |v|
78         scc2.each do |w|
79           g.add_edge(v, w)
80         end
81       end
82     end
83   end
84 
85   # Finally, the transitive closure...
86   g
87 end
transitive_reduction() click to toggle source

Returns an {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 {NotDirectedError} if run on an undirected graph. @return DirectedAdjacencyGraph

    # File lib/rgl/transitivity.rb
100 def transitive_reduction
101   raise NotDirectedError,
102         "transitive_reduction only supported for directed graphs" unless directed?
103 
104   # Compute a condensation graph in order to hide cycles.
105   cg = condensation_graph
106 
107   # Use a depth first search to compute the transitive reduction over the
108   # condensed graph. This is similar to the computation of the transitive
109   # closure over the graph in that for any node of the graph all nodes
110   # reachable from the node are tracked. Using a depth first search ensures
111   # that all nodes reachable from a target node are known when considering
112   # whether or not to add an edge pointing to that target.
113   tr_cg = DirectedAdjacencyGraph.new
114   paths_from = {}
115   cg.depth_first_search do |v|
116     paths_from[v] = Set.new
117     cg.each_adjacent(v) do |w|
118       # Only add the edge v -> w if there is no other edge v -> x such that
119       # w is reachable from x. Make sure to completely skip the case where
120       # x == w.
121       unless cg.to_enum(:each_adjacent, v).any? { |x| x != w && paths_from[x].include?(w) }
122         tr_cg.add_edge(v, w)
123 
124         # For each vertex v, track all nodes reachable from v by adding node
125         # w to the list as well as all the nodes readable from w.
126         paths_from[v] << w
127         paths_from[v].merge(paths_from[w])
128       end
129     end
130     # Ensure that a vertex with no in or out edges is added to the graph.
131     tr_cg.add_vertex(v)
132   end
133 
134   # Expand the condensed transitive reduction.
135   #
136   # For each trivial strongly connected component in the condensed graph,
137   # add the single node it contains to the new graph and add edges for each
138   # edge the node begins in the original graph.
139   # For each NON-trivial strongly connected component in the condensed
140   # graph, add each node it contains to the new graph and add arbitrary
141   # edges between the nodes to form a simple cycle. Then for each strongly
142   # connected component adjacent to the current one, find and add the first
143   # edge which exists in the original graph, starts in the first strongly
144   # connected component, and ends in the second strongly connected
145   # component.
146   g = DirectedAdjacencyGraph.new
147   tr_cg.each_vertex do |scc|
148     # Make a cycle of the contents of non-trivial strongly connected
149     # components.
150     scc_arr = scc.to_a
151     if scc.size > 1 || has_edge?(scc_arr.first, scc_arr.first)
152       0.upto(scc_arr.size - 2) do |idx|
153         g.add_edge(scc_arr[idx], scc_arr[idx + 1])
154       end
155       g.add_edge(scc_arr.last, scc_arr.first)
156     end
157 
158     # Choose a single edge between the members of two different strongly
159     # connected component to add to the graph.
160     edges = self.to_enum(:each_edge)
161     tr_cg.each_adjacent(scc) do |scc2|
162       g.add_edge(
163           *edges.find do |v, w|
164             scc.member?(v) && scc2.member?(w)
165           end
166       )
167     end
168 
169     # Ensure that a vertex with no in or out edges is added to the graph.
170     scc.each do |v|
171       g.add_vertex(v)
172     end
173   end
174 
175   # Finally, the transitive reduction...
176   g
177 end
vertex_id(v) click to toggle source
   # File lib/rgl/dot.rb
19 def vertex_id(v)
20   v
21 end
vertex_label(v) click to toggle source

Returns a label for vertex v. Default is v.to_s

   # File lib/rgl/dot.rb
15 def vertex_label(v)
16   v.to_s
17 end
vertices() click to toggle source

Synonym for to_a inherited by Enumerable. @return [Array] of vertices

    # File lib/rgl/base.rb
209 def vertices
210   to_a
211 end
vertices_filtered_by(&filter) click to toggle source

Returns a new {ImplicitGraph} which has as vertices all vertices of the receiver which satisfy the predicate filter.

The methods provides similar functionality as {www.boost.org/doc/libs/1_36_0/libs/graph/doc/filtered_graph.html BGLs Filtered Graph}

@example

def complete (n)
  set = n.integer? ? (1..n) : n
  RGL::ImplicitGraph.new do |g|
    g.vertex_iterator { |b| set.each(&b) }
    g.adjacent_iterator do |x, b|
      set.each { |y| b.call(y) unless x == y }
    end
  end
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)"

@return [ImplicitGraph]

    # File lib/rgl/implicit.rb
125 def vertices_filtered_by(&filter)
126   implicit_graph do |g|
127     g.vertex_iterator do |b|
128       self.each_vertex { |v| b.call(v) if filter.call(v) }
129     end
130 
131     g.adjacent_iterator do |v, b|
132       self.each_adjacent(v) { |u| b.call(u) if filter.call(u) }
133     end
134   end
135 end
write_to_graphic_file(fmt = 'png', dotfile = "graph", options = {}) click to toggle source

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

    # File lib/rgl/dot.rb
116 def write_to_graphic_file(fmt = 'png', dotfile = "graph", options = {})
117   src = dotfile + ".dot"
118   dot = dotfile + "." + fmt
119 
120   File.open(src, 'w') do |f|
121     f << self.to_dot_graph(options).to_s << "\n"
122   end
123 
124   unless system("dot -T#{fmt} #{src} -o #{dot}")
125     raise "Error executing dot. Did you install GraphViz?"
126   end
127   dot
128 end

Private Instance Methods

each_edge_aux() { |u, v| ... } click to toggle source
    # File lib/rgl/base.rb
311 def each_edge_aux
312   # needed in each_edge
313   visited = Hash.new
314 
315   each_vertex do |u|
316     each_adjacent(u) do |v|
317       edge = UnDirectedEdge.new(u, v)
318 
319       unless visited.has_key?(edge)
320         visited[edge] = true
321         yield u, v
322       end
323     end
324   end
325 end
eql_edges_set?(other) click to toggle source
    # File lib/rgl/base.rb
297 def eql_edges_set?(other)
298   other_num_edges = 0
299 
300   other.each_edge do |u, v|
301     if has_edge?(u, v)
302       other_num_edges += 1
303     else
304       return false
305     end
306   end
307 
308   other_num_edges == num_edges
309 end
eql_graph?(other) click to toggle source
    # File lib/rgl/base.rb
279 def eql_graph?(other)
280   other.is_a?(Graph) && directed? == other.directed? && eql_vertices_set?(other) && eql_edges_set?(other)
281 end
eql_vertices_set?(other) click to toggle source
    # File lib/rgl/base.rb
283 def eql_vertices_set?(other)
284   other_num_vertices = 0
285 
286   other.each_vertex do |v|
287     if has_vertex?(v)
288       other_num_vertices += 1
289     else
290       return false
291     end
292   end
293 
294   other_num_vertices == num_vertices
295 end