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/traversal.rb,
lib/laser/third_party/rgl/traversal.rb,
lib/laser/third_party/rgl/adjacency.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)

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

- (Boolean) acyclic?

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

Returns:

  • (Boolean) 


67
68
69
 
# File 'lib/laser/third_party/rgl/topsort.rb', line 67

def acyclic?
  topsort_iterator.count == num_vertices
end

- (Object) adjacent_vertices(v)

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

- (Object) bfs_iterator(v = self.detect { |x| true})

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

- (Object) bfs_search_tree_from(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.



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

- (Object) build_dfst(tree, node, visited)

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

- (Object) condensation_graph

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.

Raises:



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

- (Object) depth_first_search(vis = DFSVisitor.new(self), &b)

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

- (Object) depth_first_spanning_tree(start_node)

Computes the depth first spanning tree of the CFG, and also attaches the depth-first ordering to the basic blocks in the CFG. O(|V| + |E|), just like DFS.

Raises:



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

- (Object) depth_first_visit(u, vis = DFSVisitor.new(self), &b)

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

- (Object) dfs_iterator(v = self.detect { |x| true })

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

- (Boolean) directed?

Is the graph directed? The default returns false.

Returns:

  • (Boolean) 


139
 
# File 'lib/laser/third_party/rgl/base.rb', line 139

def directed?; false; end

- (Object) dominance_frontier(start_node = self.enter, dom_tree)

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

- (Object) dominator_tree(start_node = self.enter)

Returns the dominator tree of the graph. O(V^2), but performs better than or close to Lengauer-Tarjan on real-world 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

- (Object) dotty(params = {})

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

- (Object) each(&block)

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

- (Object) each_adjacent(v)

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.

Raises:



112
113
114
 
# File 'lib/laser/third_party/rgl/base.rb', line 112

def each_adjacent (v) # :yields: v
  raise NotImplementedError
end

- (Object) each_connected_component {|comp| ... }

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.

Yields:

  • (comp)

Raises:



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

- (Object) each_edge(&block)

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

- (Object) each_vertex

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

Raises:



105
106
107
 
# File 'lib/laser/third_party/rgl/base.rb', line 105

def each_vertex () # :yields: v
  raise NotImplementedError
end

- (Object) edge_class

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

- (Object) edges

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

- (Object) edges_filtered_by(&filter)

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

- (Boolean) empty?

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

accessing vertices and edges

Returns:

  • (Boolean) 


149
 
# File 'lib/laser/third_party/rgl/base.rb', line 149

def empty?; num_vertices.zero?; end

- (Boolean) eql?(g) Also known as: ==

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

Returns:

  • (Boolean) 


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

- (Boolean) has_vertex?(v)

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

Returns:

  • (Boolean) 


144
 
# File 'lib/laser/third_party/rgl/base.rb', line 144

def has_vertex?(v); include?(v); end

- (Object) implicit_graph {|result| ... }

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.

Yields:

  • (result) 


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

- (Object) iterated_dominance_frontier(set, dom_tree)

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

- (Object) num_edges

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

- (Object) out_degree(v)

Returns the number of out-edges (for directed graphs) or the number of



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

- (Object) print_dotted_on(params = {}, s = $stdout)

Output the DOT-graph 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

- (Object) reverse

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

- (Object) size 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

- (Object) strongly_connected_components

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 =        "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.

Raises:



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

- (Object) to_adjacency

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

- (Object) to_dot_graph(params = {})

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'] || 'Times-Roman'
  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

- (Object) to_s

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

- (Object) to_undirected

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

- (Object) topsort_iterator

Returns a TopsortIterator.



60
61
62
 
# File 'lib/laser/third_party/rgl/topsort.rb', line 60

def topsort_iterator
  TopsortIterator.new(self)
end

- (Object) transitive_closure

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.

Raises:



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 NON-trivial 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 non-trivial 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

- (Object) transitive_reduction

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.

Raises:



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 NON-trivial 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 non-trivial 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

- (Object) vertices

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

- (Object) vertices_filtered_by(&filter)

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

- (Object) write_to_graphic_file(fmt = 'png', dotfile = 'graph', params = {})

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