Module: RGL::Graph
 Includes:
 Enumerable, Edge
 Included in:
 BidirectionalGraph, ImplicitGraph, MutableGraph
 Defined in:
 lib/laser/third_party/rgl/base.rb,
lib/laser/third_party/rgl/dot.rb,
lib/laser/third_party/rgl/topsort.rb,
lib/laser/third_party/rgl/implicit.rb,
lib/laser/third_party/rgl/adjacency.rb,
lib/laser/third_party/rgl/traversal.rb,
lib/laser/third_party/rgl/traversal.rb,
lib/laser/third_party/rgl/dominators.rb,
lib/laser/third_party/rgl/condensation.rb,
lib/laser/third_party/rgl/transitivity.rb,
lib/laser/third_party/rgl/connected_components.rb,
lib/laser/third_party/rgl/depth_first_spanning_tree.rb
Overview
class AdjacencyGraph
Defined Under Namespace
Classes: TarjanSccVisitor
Instance Method Summary collapse

#acyclic? ⇒ Boolean
Returns true if the graph contains no cycles.

#adjacent_vertices(v) ⇒ Object
Returns an array of vertices adjacent to vertex v.

#bfs_iterator(v = self.detect { x true}) ⇒ Object
Returns a BFSIterator, starting at vertex v.

#bfs_search_tree_from(v) ⇒ Object
Returns a DirectedAdjacencyGraph, which represents a BFS search tree starting at v.

#build_dfst(tree, node, visited) ⇒ Object
builds the dfst from the start node.

#condensation_graph ⇒ Object
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.

#depth_first_search(vis = DFSVisitor.new(self), &b) ⇒ Object
Do a recursive DFS search on the whole graph.

#depth_first_spanning_tree(start_node) ⇒ Object
Computes the depth first spanning tree of the CFG, and also attaches the depthfirst ordering to the basic blocks in the CFG.

#depth_first_visit(u, vis = DFSVisitor.new(self), &b) ⇒ Object
Start a depth first search at vertex u.

#dfs_iterator(v = self.detect { x true }) ⇒ Object
Returns a DFSIterator staring at vertex v.

#directed? ⇒ Boolean
Is the graph directed? The default returns false.

#dominance_frontier(start_node = self.enter, dom_tree) ⇒ Object
Returns the dominance frontier of the graph.

#dominator_tree(start_node = self.enter) ⇒ Object
Returns the dominator tree of the graph.

#dotty(params = {}) ⇒ Object
Call dotty for the graph which is written to the file 'graph.dot' in the # current directory.

#each(&block) ⇒ Object
Vertices get enumerated.

#each_adjacent(v) ⇒ Object
The each_adjacent iterator defines the out edges of vertex v.

#each_connected_component {comp ... } ⇒ Object
Compute the connected components of an undirected graph, using a DFS (Depthfirst search)based approach.

#each_edge(&block) ⇒ Object
The each_edge iterator should provide efficient access to all edges of the graph.

#each_vertex ⇒ Object
The each_vertex iterator defines the set of vertices.

#edge_class ⇒ Object
Returns the class for edges: DirectedEdge or UnDirectedEdge.

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

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

#empty? ⇒ Boolean
Returns true if the graph has no vertices, i.e.

#eql?(g) ⇒ Boolean
(also: #==)
Equality is defined to be same set of edges and directed?.

#has_vertex?(v) ⇒ Boolean
Returns true if v is a vertex of the graph.

#implicit_graph {result ... } ⇒ Object
Return a new ImplicitGraph which is isomorphic (i.e. has same edges and vertices) to the receiver.

#iterated_dominance_frontier(set, dom_tree) ⇒ Object
Computes DF^+: the iterated dominance frontier of a set of blocks.

#num_edges ⇒ Object
Returns the number of edges.

#out_degree(v) ⇒ Object
incident edges (for undirected graphs) of vertex v.

#print_dotted_on(params = {}, s = $stdout) ⇒ Object
Output the DOTgraph to stream s.

#reverse ⇒ Object
Return a new DirectedAdjacencyGraph which has the same set of vertices.

#size ⇒ Object
(also: #num_vertices)
Returns the number of vertices.

#strongly_connected_components ⇒ Object
This is Tarjan's algorithm for strongly connected components, from his paper “Depth first search and linear graph algorithms”.

#to_adjacency ⇒ Object
Convert a general graph to an AdjacencyGraph.

#to_dot_graph(params = {}) ⇒ Object
Return a RGL::DOT::Digraph for directed graphs or a DOT::Subgraph for an undirected Graph.

#to_s ⇒ Object
Utility method to show a string representation of the edges of the graph.

#to_undirected ⇒ Object
Return a new AdjacencyGraph which has the same set of vertices.

#topsort_iterator ⇒ Object
Returns a TopsortIterator.

#transitive_closure ⇒ Object
Returns an RGL::DirectedAdjacencyGraph which is the transitive closure of this graph.

#transitive_reduction ⇒ Object
Returns an RGL::DirectedAdjacencyGraph which is the transitive reduction of this graph.

#vertices ⇒ Object
Return the array of vertices.

#vertices_filtered_by(&filter) ⇒ Object
— === Graph adaptors.

#write_to_graphic_file(fmt = 'png', dotfile = 'graph', params = {}) ⇒ Object
Use dot to create a graphical representation of the graph.
Methods included from Enumerable
#all?, #any?, #chunk, #collect, #collect_concat, #count, #cycle, #detect, #drop, #drop_while, #each_cons, #each_entry, #each_slice, #each_with_index, #each_with_object, #entries, #find_index, #first, #flat_map, #grep, #group_by, #include?, #inject, #map, #max, #max_by, #min, #min_by, #minmax, #minmax_by, #none?, #one?, #partition, #reject, #reverse_each, #select, #slice_before, #sort, #sort_by, #take, #take_while, #to_a, #to_set, #zip
Instance Method Details
#acyclic? ⇒ Boolean
Returns true if the graph contains no cycles. This is only meaningful for directed graphs. Returns false for undirected graphs.
67 68 69 
# File 'lib/laser/third_party/rgl/topsort.rb', line 67 def acyclic? topsort_iterator.count == num_vertices end 
#adjacent_vertices(v) ⇒ Object
Returns an array of vertices adjacent to vertex v.
167 168 169 170 171 
# File 'lib/laser/third_party/rgl/base.rb', line 167 def adjacent_vertices (v) r = [] each_adjacent(v) { u r << u } r end 
#bfs_iterator(v = self.detect { x true}) ⇒ Object
Returns a BFSIterator, starting at vertex v.
229 230 231 
# File 'lib/laser/third_party/rgl/traversal.rb', line 229 def bfs_iterator (v = self.detect { x true}) BFSIterator.new(self, v) end 
#bfs_search_tree_from(v) ⇒ Object
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.
237 238 239 240 241 242 243 244 245 246 
# File 'lib/laser/third_party/rgl/traversal.rb', line 237 def bfs_search_tree_from (v) require 'laser/third_party/rgl/adjacency' bfs = bfs_iterator(v) tree = DirectedAdjacencyGraph.new bfs.set_tree_edge_event_handler { from, to tree.add_edge(from, to) } bfs.set_to_end # does the search tree end 
#build_dfst(tree, node, visited) ⇒ Object
builds the dfst from the start node. O(V + E), just like DFS.
27 28 29 30 31 32 33 34 35 
# File 'lib/laser/third_party/rgl/depth_first_spanning_tree.rb', line 27 def build_dfst(tree, node, visited) visited << node node.real_successors.each do other if !visited.include?(other) tree.add_edge(node, other) build_dfst(tree, other, visited) end end end 
#condensation_graph ⇒ Object
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.
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 
# File 'lib/laser/third_party/rgl/condensation.rb', line 13 def condensation_graph raise NotDirectedError, "condensation_graph only supported for directed graphs" unless directed? # Get the component map for the strongly connected components. comp_map = strongly_connected_components.comp_map # Invert the map such that for any number, n, in the component map a Set # instance is created containing all of the nodes which map to n. The Set # instances will be used to map to the number, n, with which the elements # of the set are associated. inv_comp_map = {} comp_map.each { v, n (inv_comp_map[n] = Set.new) << v } # Create an ImplicitGraph where the nodes are the strongly connected # components of this graph and the edges are the edges of this graph which # cross between the strongly connected components. ImplicitGraph.new do g g.vertex_iterator do b inv_comp_map.each_value(&b) end g.adjacent_iterator do scc, b scc.each do v each_adjacent(v) do w # Do not make the cluster reference itself in the graph. if comp_map[v] != comp_map[w] then b.call(inv_comp_map[comp_map[w]]) end end end end g.directed = true end end 
#depth_first_search(vis = DFSVisitor.new(self), &b) ⇒ Object
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.
299 300 301 302 303 304 305 306 
# File 'lib/laser/third_party/rgl/traversal.rb', line 299 def depth_first_search (vis = DFSVisitor.new(self), &b) each_vertex do u unless vis.finished_vertex?(u) vis.handle_start_vertex(u) depth_first_visit(u, vis, &b) end end end 
#depth_first_spanning_tree(start_node) ⇒ Object
Computes the depth first spanning tree of the CFG, and also attaches the depthfirst ordering to the basic blocks in the CFG. O(V + E), just like DFS.
17 18 19 20 21 22 23 
# File 'lib/laser/third_party/rgl/depth_first_spanning_tree.rb', line 17 def depth_first_spanning_tree(start_node) raise ArgumentError unless vertices.include?(start_node) tree = DirectedAdjacencyGraph.new visited = Set.new build_dfst(tree, start_node, visited) tree end 
#depth_first_visit(u, vis = DFSVisitor.new(self), &b) ⇒ Object
Start a depth first search at vertex u. The block b is called on each finish_vertex event.
311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 
# File 'lib/laser/third_party/rgl/traversal.rb', line 311 def depth_first_visit (u, vis = DFSVisitor.new(self), &b) vis.color_map[u] = :GRAY vis.handle_examine_vertex(u) each_adjacent(u) { v vis.handle_examine_edge(u, v) if vis.follow_edge?(u, v) # (u,v) is a tree edge vis.handle_tree_edge(u, v) # also discovers v vis.color_map[v] = :GRAY # color of v was :WHITE depth_first_visit(v, vis, &b) else # (u,v) is a non tree edge if vis.color_map[v] == :GRAY vis.handle_back_edge(u, v) # (u,v) has gray target else vis.handle_forward_edge(u, v) # (u,v) is a cross or forward edge end end } vis.color_map[u] = :BLACK vis.handle_finish_vertex(u) # finish vertex b.call(u) end 
#dfs_iterator(v = self.detect { x true }) ⇒ Object
Returns a DFSIterator staring at vertex v.
291 292 293 
# File 'lib/laser/third_party/rgl/traversal.rb', line 291 def dfs_iterator (v = self.detect { x true }) DFSIterator.new(self, v) end 
#directed? ⇒ Boolean
Is the graph directed? The default returns false.
139 
# File 'lib/laser/third_party/rgl/base.rb', line 139 def directed?; false; end 
#dominance_frontier(start_node = self.enter, dom_tree) ⇒ Object
Returns the dominance frontier of the graph.
If the start node is not provided, it is assumed the receiver is a ControlFlowGraph and has an #enter method.
return: Node => Set<Node>
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 
# File 'lib/laser/third_party/rgl/dominators.rb', line 55 def dominance_frontier(start_node = self.enter, dom_tree) vertices.inject(Hash.new { h, k h[k] = Set.new }) do result, b preds = b.real_predecessors if preds.size >= 2 preds.each do p b_dominator = dom_tree[b].successors.first break unless b_dominator runner = dom_tree[p] while runner && runner != b_dominator result[runner] << b runner = runner.successors.first end end end result end end 
#dominator_tree(start_node = self.enter) ⇒ Object
Returns the dominator tree of the graph. O(V^2), but performs better than or close to LengauerTarjan on realworld ASTs.
If the start node is not provided, it is assumed the receiver is a ControlFlowGraph and has an #enter method.
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 
# File 'lib/laser/third_party/rgl/dominators.rb', line 16 def dominator_tree(start_node = self.enter) doms = {start_node => start_node} changed = true reverse_postorder = compute_post_order(self, start_node) while changed changed = false reverse_postorder.each do b if (original = b.each_real_predecessors.find { node doms[node] }) new_idom = original b.each_real_predecessors do p if doms[p] && p != original new_idom = dominator_set_intersect(p, new_idom, doms) end end if doms[b] != new_idom doms[b] = new_idom changed = true end end end end # doms is IDOM. All outward edges connect an IDom to its dominee. d_tree = self.class.new (vertices  [enter, exit]).each do b copy = Laser::Analysis::ControlFlow::BasicBlock.new(b.name) copy.instructions = b.instructions d_tree.add_vertex(copy) end doms.each { src, dest d_tree.add_edge(d_tree[src], d_tree[dest]) unless src == enter && dest == enter } d_tree end 
#dotty(params = {}) ⇒ Object
Call dotty for the graph which is written to the file 'graph.dot' in the # current directory.
69 70 71 72 73 74 75 
# File 'lib/laser/third_party/rgl/dot.rb', line 69 def dotty (params = {}) dotfile = "graph.dot" File.open(dotfile, "w") {f print_dotted_on(params, f) } system("dotty", dotfile) end 
#each(&block) ⇒ Object
Vertices get enumerated. A graph is thus an enumerable of vertices.
Testing
136 
# File 'lib/laser/third_party/rgl/base.rb', line 136 def each(&block); each_vertex(&block); end 
#each_adjacent(v) ⇒ Object
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.
112 113 114 
# File 'lib/laser/third_party/rgl/base.rb', line 112 def each_adjacent (v) # :yields: v raise NotImplementedError end 
#each_connected_component {comp ... } ⇒ Object
Compute the connected components of an undirected graph, using a DFS (Depthfirst 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.
23 24 25 26 27 28 29 30 31 32 33 34 35 36 
# File 'lib/laser/third_party/rgl/connected_components.rb', line 23 def each_connected_component raise NotUndirectedError, "each_connected_component only works " + "for undirected graphs." if directed? comp = [] vis = DFSVisitor.new(self) vis.set_finish_vertex_event_handler { v comp << v } vis.set_start_vertex_event_handler { v yield comp unless comp.empty? comp = [] } depth_first_search(vis) { v } yield comp unless comp.empty? end 
#each_edge(&block) ⇒ Object
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).
123 124 125 126 127 128 129 130 131 
# File 'lib/laser/third_party/rgl/base.rb', line 123 def each_edge (&block) if directed? each_vertex { u each_adjacent(u) { v yield u,v } } else each_edge_aux(&block) # concrete graphs should to this better end end 
#each_vertex ⇒ Object
The each_vertex iterator defines the set of vertices. This method must be defined by concrete graph classes. It defines the BGL VertexListGraph concept.
105 106 107 
# File 'lib/laser/third_party/rgl/base.rb', line 105 def each_vertex () # :yields: v raise NotImplementedError end 
#edge_class ⇒ Object
Returns the class for edges: DirectedEdge or UnDirectedEdge.
155 
# File 'lib/laser/third_party/rgl/base.rb', line 155 def edge_class; directed? ? DirectedEdge : UnDirectedEdge; end 
#edges ⇒ Object
Return the array of edges (DirectedEdge or UnDirectedEdge) of the graph using each_edge, depending whether the graph is directed or not.
159 160 161 162 163 164 
# File 'lib/laser/third_party/rgl/base.rb', line 159 def edges result = [] c = edge_class each_edge { u,v result << c.new(u,v) } result end 
#edges_filtered_by(&filter) ⇒ Object
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]
146 147 148 149 150 151 152 153 154 155 156 157 
# File 'lib/laser/third_party/rgl/implicit.rb', line 146 def edges_filtered_by (&filter) implicit_graph { g g.adjacent_iterator { v, b self.each_adjacent(v) { u b.call(u) if filter.call(v, u) } } g.edge_iterator { b self.each_edge { u,v b.call(u, v) if filter.call(u, v) } } } end 
#empty? ⇒ Boolean
Returns true if the graph has no vertices, i.e. num_vertices == 0.
accessing vertices and edges
149 
# File 'lib/laser/third_party/rgl/base.rb', line 149 def empty?; num_vertices.zero?; end 
#eql?(g) ⇒ Boolean Also known as: ==
Equality is defined to be same set of edges and directed?
196 197 198 199 200 201 202 203 204 205 206 207 
# File 'lib/laser/third_party/rgl/base.rb', line 196 def eql?(g) equal?(g) or begin g.is_a?(Graph) and directed? == g.directed? and g.inject(0) { n, v has_vertex?(v) or return false; n+1} == num_vertices and begin ng = 0 g.each_edge { u,v has_edge? u,v or return false; ng += 1 } ng == num_edges end end end 
#has_vertex?(v) ⇒ Boolean
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).
144 
# File 'lib/laser/third_party/rgl/base.rb', line 144 def has_vertex?(v); include?(v); end 
#implicit_graph {result ... } ⇒ Object
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.
163 164 165 166 167 168 169 170 171 
# File 'lib/laser/third_party/rgl/implicit.rb', line 163 def implicit_graph result = ImplicitGraph.new { g g.vertex_iterator { b self.each_vertex(&b) } g.adjacent_iterator { v, b self.each_adjacent(v, &b) } g.directed = self.directed? } yield result if block_given? # let client overwrite defaults result end 
#iterated_dominance_frontier(set, dom_tree) ⇒ Object
Computes DF^+: the iterated dominance frontier of a set of blocks. Used in SSA conversion.
75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 
# File 'lib/laser/third_party/rgl/dominators.rb', line 75 def iterated_dominance_frontier(set, dom_tree) worklist = Set.new(set) result = Set.new(set) frontier = dominance_frontier(dom_tree) until worklist.empty? block = worklist.pop frontier[dom_tree[block]].each do candidate candidate_in_full_graph = self[candidate] unless result.include?(candidate_in_full_graph) result << candidate_in_full_graph worklist << candidate_in_full_graph end end end result end 
#num_edges ⇒ Object
Returns the number of edges.
188 
# File 'lib/laser/third_party/rgl/base.rb', line 188 def num_edges; r = 0; each_edge {u,v r +=1}; r; end 
#out_degree(v) ⇒ Object
incident edges (for undirected graphs) of vertex v.
175 176 177 178 179 
# File 'lib/laser/third_party/rgl/base.rb', line 175 def out_degree (v) r = 0 each_adjacent(v) { u r += 1} r end 
#print_dotted_on(params = {}, s = $stdout) ⇒ Object
Output the DOTgraph to stream s.
62 63 64 
# File 'lib/laser/third_party/rgl/dot.rb', line 62 def print_dotted_on (params = {}, s = $stdout) s << to_dot_graph(params).to_s << "\n" end 
#reverse ⇒ Object
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.
201 202 203 204 205 206 207 
# File 'lib/laser/third_party/rgl/adjacency.rb', line 201 def reverse return self unless directed? result = DirectedAdjacencyGraph.new each_vertex { v result.add_vertex v } each_edge { u,v result.add_edge(v, u) } result end 
#size ⇒ Object Also known as: num_vertices
Returns the number of vertices.
182 183 184 
# File 'lib/laser/third_party/rgl/base.rb', line 182 def size() # Why not in Enumerable? inject(0) { n, v n + 1 } end 
#strongly_connected_components ⇒ Object
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
author = "R. E. Tarjan",
key = "Tarjan",
title = "Depth First Search and Linear Graph Algorithms",
journal = "SIAM Journal on Computing",
volume = "1",
number = "2",
pages = "146160",
month = jun,
year = "1972",
CODEN = "SMJCAT",
ISSN = "00975397 (print), 10957111 (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.
129 130 131 132 133 134 135 
# File 'lib/laser/third_party/rgl/connected_components.rb', line 129 def strongly_connected_components raise NotDirectedError, "strong_components only works for directed graphs." unless directed? vis = TarjanSccVisitor.new(self) depth_first_search(vis) { v } vis end 
#to_adjacency ⇒ Object
Convert a general graph to an AdjacencyGraph. If the graph is directed, returns a DirectedAdjacencyGraph; otherwise, returns an AdjacencyGraph.
189 190 191 192 193 194 
# File 'lib/laser/third_party/rgl/adjacency.rb', line 189 def to_adjacency result = (directed? ? DirectedAdjacencyGraph : AdjacencyGraph).new each_vertex { v result.add_vertex(v) } each_edge { u,v result.add_edge(u, v) } result end 
#to_dot_graph(params = {}) ⇒ Object
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.
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 
# File 'lib/laser/third_party/rgl/dot.rb', line 19 def to_dot_graph (params = {}) params['name'] = self.class.name.gsub(/:/,'_') fontsize = params['fontsize']  '8' fontname = params['fontname']  'TimesRoman' graph = (directed? ? DOT::Digraph : DOT::Subgraph).new(params) edge_class = directed? ? DOT::DirectedEdge : DOT::Edge shape = params['shape']  'ellipse' each_vertex do v name = v.to_s graph << DOT::Node.new('name' => name, 'fontsize' => fontsize, 'label' => name, 'shape' => shape, 'fontname' => fontname) end each_edge do u,v if respond_to?(:is_abnormal?) if is_abnormal?(u, v) && is_block_taken?(u, v) color = 'blue' elsif is_abnormal?(u, v) color = 'red' elsif is_fake?(u, v) color = '#bbbbbb' else color = 'black' end style = (is_fake?(u, v)  !is_executable?(u, v)) ? 'dashed' : 'solid' else color = 'black' style = 'solid' end graph << edge_class.new('from' => u.to_s, 'to' => v.to_s, 'fontsize' => fontsize, 'fontname' => fontname, 'color' => color, 'style' => style) end graph end 
#to_s ⇒ Object
Utility method to show a string representation of the edges of the graph.
191 192 193 
# File 'lib/laser/third_party/rgl/base.rb', line 191 def to_s edges.sort.to_s end 
#to_undirected ⇒ Object
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.
215 216 217 218 
# File 'lib/laser/third_party/rgl/adjacency.rb', line 215 def to_undirected return self unless directed? AdjacencyGraph.new(Set, self) end 
#topsort_iterator ⇒ Object
Returns a TopsortIterator.
60 61 62 
# File 'lib/laser/third_party/rgl/topsort.rb', line 60 def topsort_iterator TopsortIterator.new(self) end 
#transitive_closure ⇒ Object
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 selfreferencing edges.
This method should run in O(VE) time, where V and E are the number of vertices and edges respectively.
Raises RGL::NotDirectedError if run on an undirected graph.
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 
# File 'lib/laser/third_party/rgl/transitivity.rb', line 20 def transitive_closure raise NotDirectedError, "transitive_closure only supported for directed graphs" unless directed? # Compute a condensation graph in order to hide cycles. cg = condensation_graph # Use a depth first search to calculate the transitive closure over the # condensation graph. This ensures that as we traverse up the graph we # know the transitive closure of each subgraph rooted at each node # starting at the leaves. Subsequent root nodes which consume these # subgraphs by way of the nodes' immediate successors can then immediately # add edges to the roots of the subgraphs and to every successor of those # roots. tc_cg = DirectedAdjacencyGraph.new cg.depth_first_search do v # For each vertex v, w, and x where the edges v > w and w > x exist in # the source graph, add edges v > w and v > x to the target graph. cg.each_adjacent(v) do w tc_cg.add_edge(v, w) tc_cg.each_adjacent(w) do x tc_cg.add_edge(v, x) end end # Ensure that a vertex with no in or out edges is added to the graph. tc_cg.add_vertex(v) end # Expand the condensed transitive closure. # # For each trivial strongly connected component in the condensed graph, # add the single node it contains to the new graph and add edges for each # edge the node begins in the original graph. # For each NONtrivial strongly connected component in the condensed # graph, add each node it contains to the new graph and add edges to # every node in the strongly connected component, including self # referential edges. Then for each edge of the original graph from any # of the contained nodes, add edges from each of the contained nodes to # all the edge targets. g = DirectedAdjacencyGraph.new tc_cg.each_vertex do scc scc.each do v # Add edges between all members of nontrivial strongly connected # components (size > 1) and ensure that self referential edges are # added when necessary for trivial strongly connected components. if scc.size > 1  has_edge?(v, v) then scc.each do w g.add_edge(v, w) end end # Ensure that a vertex with no in or out edges is added to the graph. g.add_vertex(v) end # Add an edge from every member of a strongly connected component to # every member of each strongly connected component to which the former # points. tc_cg.each_adjacent(scc) do scc2 scc.each do v scc2.each do w g.add_edge(v, w) end end end end # Finally, the transitive closure... g end 
#transitive_reduction ⇒ Object
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(VE) time, where V and E are the number of vertices and edges respectively.
Raises RGL::NotDirectedError if run on an undirected graph.
99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 
# File 'lib/laser/third_party/rgl/transitivity.rb', line 99 def transitive_reduction raise NotDirectedError, "transitive_reduction only supported for directed graphs" unless directed? # Compute a condensation graph in order to hide cycles. cg = condensation_graph # Use a depth first search to compute the transitive reduction over the # condensed graph. This is similar to the computation of the transitive # closure over the graph in that for any node of the graph all nodes # reachable from the node are tracked. Using a depth first search ensures # that all nodes reachable from a target node are known when considering # whether or not to add an edge pointing to that target. tr_cg = DirectedAdjacencyGraph.new paths_from = {} cg.depth_first_search do v paths_from[v] = Set.new cg.each_adjacent(v) do w # Only add the edge v > w if there is no other edge v > x such that # w is reachable from x. Make sure to completely skip the case where # x == w. unless Enumerator.new(cg, :each_adjacent, v).any? do x x != w && paths_from[x].include?(w) end then tr_cg.add_edge(v, w) # For each vertex v, track all nodes reachable from v by adding node # w to the list as well as all the nodes readable from w. paths_from[v] << w paths_from[v].merge(paths_from[w]) end end # Ensure that a vertex with no in or out edges is added to the graph. tr_cg.add_vertex(v) end # Expand the condensed transitive reduction. # # For each trivial strongly connected component in the condensed graph, # add the single node it contains to the new graph and add edges for each # edge the node begins in the original graph. # For each NONtrivial strongly connected component in the condensed # graph, add each node it contains to the new graph and add arbitrary # edges between the nodes to form a simple cycle. Then for each strongly # connected component adjacent to the current one, find and add the first # edge which exists in the original graph, starts in the first strongly # connected component, and ends in the second strongly connected # component. g = DirectedAdjacencyGraph.new tr_cg.each_vertex do scc # Make a cycle of the contents of nontrivial strongly connected # components. scc_arr = scc.to_a if scc.size > 1  has_edge?(scc_arr.first, scc_arr.first) then 0.upto(scc_arr.size  2) do idx g.add_edge(scc_arr[idx], scc_arr[idx + 1]) end g.add_edge(scc_arr.last, scc_arr.first) end # Choose a single edge between the members of two different strongly # connected component to add to the graph. edges = Enumerator.new(self, :each_edge) tr_cg.each_adjacent(scc) do scc2 g.add_edge( *edges.find do v, w scc.member?(v) && scc2.member?(w) end ) end # Ensure that a vertex with no in or out edges is added to the graph. scc.each do v g.add_vertex(v) end end # Finally, the transitive reduction... g end 
#vertices ⇒ Object
Return the array of vertices. Synonym for #to_a inherited by Enumerable.
152 
# File 'lib/laser/third_party/rgl/base.rb', line 152 def vertices; to_a; end 
#vertices_filtered_by(&filter) ⇒ Object
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)"
126 127 128 129 130 131 132 133 134 135 
# File 'lib/laser/third_party/rgl/implicit.rb', line 126 def vertices_filtered_by (&filter) implicit_graph { g g.vertex_iterator { b self.each_vertex { v b.call(v) if filter.call(v) } } g.adjacent_iterator { v, b self.each_adjacent(v) { u b.call(u) if filter.call(u) } } } end 
#write_to_graphic_file(fmt = 'png', dotfile = 'graph', params = {}) ⇒ Object
Use dot to create a graphical representation of the graph. Returns the filename of the graphics file.
80 81 82 83 84 85 86 87 88 89 90 
# File 'lib/laser/third_party/rgl/dot.rb', line 80 def write_to_graphic_file (fmt='png', dotfile='graph', params = {}) src = dotfile + ".dot" dot = dotfile + "." + fmt File.open(src, 'w') do f f << self.to_dot_graph(params).to_s << "\n" end system( "dot T#{fmt} o #{dot} #{src}" ) dot end 