Module: RGL::Graph

Includes:
Enumerable, Edge
Included in:
BidirectionalGraph, ImplicitGraph, MutableGraph
Defined in:
lib/rgl/base.rb,
lib/rgl/dot.rb,
lib/rgl/path.rb,
lib/rgl/prim.rb,
lib/rgl/topsort.rb,
lib/rgl/dijkstra.rb,
lib/rgl/implicit.rb,
lib/rgl/adjacency.rb,
lib/rgl/bipartite.rb,
lib/rgl/traversal.rb,
lib/rgl/traversal.rb,
lib/rgl/bellman_ford.rb,
lib/rgl/condensation.rb,
lib/rgl/edmonds_karp.rb,
lib/rgl/transitivity.rb,
lib/rgl/connected_components.rb

Overview

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.

Defined Under Namespace

Classes: TarjanSccVisitor

Instance Method Summary collapse

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.

Returns:

  • (Boolean) 


75
76
77
 
# File 'lib/rgl/topsort.rb', line 75

def acyclic?
  topsort_iterator.length == num_vertices
end

#adjacent_vertices(v) ⇒ Array

Returns of vertices adjacent to vertex v.

Parameters:

  • v —

    a vertex of the graph

Returns:

  • (Array) —

    of vertices adjacent to vertex v.



230
231
232
233
234
 
# File 'lib/rgl/base.rb', line 230

def adjacent_vertices(v)
  r = []
  each_adjacent(v) { |u| r << u }
  r
end

#bellman_ford_shortest_paths(edge_weights_map, source, visitor = BellmanFordVisitor.new(self)) ⇒ Hash[Object,Array]

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.

Returns:

  • (Hash[Object,Array]) 


109
110
111
 
# File 'lib/rgl/bellman_ford.rb', line 109

def bellman_ford_shortest_paths(edge_weights_map, source, visitor = BellmanFordVisitor.new(self))
  BellmanFordAlgorithm.new(self, edge_weights_map, visitor).shortest_paths(source)
end

#bfs_iterator(v = self.detect { |x| true }) ⇒ BFSIterator

Returns starting at vertex v.

Returns:



111
112
113
 
# File 'lib/rgl/traversal.rb', line 111

def bfs_iterator(v = self.detect { |x| true })
  BFSIterator.new(self, v)
end

#bfs_search_tree_from(v) ⇒ DirectedAdjacencyGraph

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

Returns:



119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/rgl/traversal.rb', line 119

def bfs_search_tree_from(v)
  unless defined?(DirectedAdjacencyGraph)
    require 'rgl/adjacency'
  end
  bfs  = bfs_iterator(v)
  tree = DirectedAdjacencyGraph.new

  bfs.set_tree_edge_event_handler do |from, to|
    tree.add_edge(from, to)
  end

  bfs.set_to_end # does the search
  tree
end

#bipartite? ⇒ Boolean

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

Returns:

  • (Boolean) 


38
39
40
 
# File 'lib/rgl/bipartite.rb', line 38

def bipartite?
  !bipartite_sets.nil?
end

#bipartite_sets ⇒ Array

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.

Returns:

  • (Array)

Raises:



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/rgl/bipartite.rb', line 14

def bipartite_sets
  raise NotUndirectedError.new('bipartite sets can only be found for an undirected graph') if directed?

  bfs = BipartiteBFSIterator.new(self)

  # if necessary, we start BFS from each vertex to make sure
  # that all connected components of the graph are processed
  each_vertex do |u|
    next if bfs.finished_vertex?(u)

    bfs.reset_start(u)
    bfs.move_forward_until { bfs.found_odd_cycle }

    return if bfs.found_odd_cycle
  end

  bfs.bipartite_sets_map.inject([[], []]) do |sets, (vertex, set)|
    sets[set] << vertex
    sets
  end
end

#condensation_graph ⇒ Object

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.

Returns:

  • ImplicitGraph

Raises:



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
48
49
50
51
52
 
# File 'lib/rgl/condensation.rb', line 17

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

Note that this traversal does not garantee, that roots are at the top of each spanning subtree induced by the DFS search on a directed graph (see also the discussion in issue #20).

See Also:



183
184
185
186
187
188
189
190
 
# File 'lib/rgl/traversal.rb', line 183

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

See Also:



195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
 
# File 'lib/rgl/traversal.rb', line 195

def depth_first_visit(u, vis = DFSVisitor.new(self), &b)
  vis.color_map[u] = :GRAY
  vis.handle_examine_vertex(u)

  each_adjacent(u) do |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
      # color of v was :WHITE. Will be marked :GRAY in recursion
      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
  end

  vis.color_map[u] = :BLACK
  vis.handle_finish_vertex(u) # finish vertex
  b.call(u)
end

#dfs_iterator(v = self.detect { |x| true }) ⇒ DFSIterator

Returns staring at vertex v.

Returns:



171
172
173
 
# File 'lib/rgl/traversal.rb', line 171

def dfs_iterator(v = self.detect { |x| true })
  DFSIterator.new(self, v)
end

#dijkstra_shortest_path(edge_weights_map, source, target, visitor = DijkstraVisitor.new(self)) ⇒ Object

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.



116
117
118
 
# File 'lib/rgl/dijkstra.rb', line 116

def dijkstra_shortest_path(edge_weights_map, source, target, visitor = DijkstraVisitor.new(self))
  DijkstraAlgorithm.new(self, edge_weights_map, visitor).shortest_path(source, target)
end

#dijkstra_shortest_paths(edge_weights_map, source, visitor = DijkstraVisitor.new(self)) ⇒ Object

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.



128
129
130
 
# File 'lib/rgl/dijkstra.rb', line 128

def dijkstra_shortest_paths(edge_weights_map, source, visitor = DijkstraVisitor.new(self))
  DijkstraAlgorithm.new(self, edge_weights_map, visitor).shortest_paths(source)
end

#directed? ⇒ Boolean

Is the graph directed? The default returns false.

Returns:

  • (Boolean) 


180
181
182
 
# File 'lib/rgl/base.rb', line 180

def directed?
  false
end

#dotty(params = {}) ⇒ Object

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



103
104
105
106
107
108
109
110
111
 
# File 'lib/rgl/dot.rb', line 103

def dotty(params = {})
  dotfile = "graph.dot"
  File.open(dotfile, "w") do |f|
    print_dotted_on(params, f)
  end
  unless system("dotty", dotfile)
    raise "Error executing dotty. Did you install GraphViz?"
  end
end

#each(&block) ⇒ Object

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



175
176
177
 
# File 'lib/rgl/base.rb', line 175

def each(&block)
  each_vertex(&block)
end

#each_adjacent(v, &block) ⇒ 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.

Parameters:

  • v —

    a vertex of the graph

Raises:

  • (NotImplementedError) 


152
153
154
 
# File 'lib/rgl/base.rb', line 152

def each_adjacent(v, &block) # :yields: v
  raise NotImplementedError
end

#each_connected_component {|comp| ... } ⇒ Object

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
37
38
39
 
# File 'lib/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 do |v|
    yield comp unless comp.empty?
    comp = []
  end

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



163
164
165
166
167
168
169
170
171
 
# File 'lib/rgl/base.rb', line 163

def each_edge(&block)
  if directed?
    each_vertex do |u|
      each_adjacent(u) { |v| yield u, v }
    end
  else
    each_edge_aux(&block) # concrete graphs should to this better
  end
end

#each_vertex(&block) ⇒ Object

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.

Raises:

  • (NotImplementedError) 


143
144
145
 
# File 'lib/rgl/base.rb', line 143

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

#edge_class ⇒ Class

Returns the class for edges: Edge::DirectedEdge or Edge::UnDirectedEdge.

Returns:



215
216
217
 
# File 'lib/rgl/base.rb', line 215

def edge_class
  directed? ? DirectedEdge : UnDirectedEdge
end

#edges ⇒ Array

It uses #each_edge to compute the edges

Returns:

  • (Array) —

    of edges (DirectedEdge or UnDirectedEdge) of the graph



221
222
223
224
225
226
 
# File 'lib/rgl/base.rb', line 221

def edges
  result = []
  c = edge_class
  each_edge { |u, v| result << c.new(u, v) }
  result
end

#edges_filtered_by(&filter) ⇒ ImplicitGraph

Returns a new ImplicitGraph which has as edges all edges of the receiver which satisfy the predicate filter (a block with two parameters).

Examples:


g = complete(7).edges_filtered_by { |u,v| u+v == 7 }
g.to_s     => "(1=6)(2=5)(3=4)"
g.vertices => [1, 2, 3, 4, 5, 6, 7]

Returns:



146
147
148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/rgl/implicit.rb', line 146

def edges_filtered_by(&filter)
  implicit_graph do |g|
    g.adjacent_iterator do |v, b|
      self.each_adjacent(v) do |u|
        b.call(u) if filter.call(v, u)
      end
    end

    g.edge_iterator do |b|
      self.each_edge { |u, v| b.call(u, v) if filter.call(u, v) }
    end
  end
end

#empty? ⇒ Boolean

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

Returns:

  • (Boolean) 


203
204
205
 
# File 'lib/rgl/base.rb', line 203

def empty?
  num_vertices.zero?
end

#eql?(other) ⇒ Boolean Also known as: ==

Two graphs are equal iff they have equal directed? property as well as vertices and edges sets.

Parameters:

Returns:

  • (Boolean) 


271
272
273
 
# File 'lib/rgl/base.rb', line 271

def eql?(other)
  equal?(other) || eql_graph?(other)
end

#has_edge?(u, v) ⇒ Boolean

Returns true if (u, v) is an edge of the graph.

Returns:

  • (Boolean) 


194
195
196
197
198
199
 
# File 'lib/rgl/base.rb', line 194

def has_edge?(u, v)
  each_adjacent(u) do |w|
    return true if v == w
  end
  return false
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).

Parameters:

  • v —

    a vertex of the graph

Returns:

  • (Boolean) 


188
189
190
 
# File 'lib/rgl/base.rb', line 188

def has_vertex?(v)
  include?(v) # inherited from enumerable
end

#implicit_graph {|result| ... } ⇒ ImplicitGraph

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)

Returns:



164
165
166
167
168
169
170
171
172
173
 
# File 'lib/rgl/implicit.rb', line 164

def implicit_graph
  result = ImplicitGraph.new do |g|
    g.vertex_iterator { |b| self.each_vertex(&b) }
    g.adjacent_iterator { |v, b| self.each_adjacent(v, &b) }
    g.directed = self.directed?
  end

  yield result if block_given? # let client overwrite defaults
  result
end

#maximum_flow(edge_capacities_map, source, sink) ⇒ Hash

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.

Returns:

  • (Hash) 


136
137
138
 
# File 'lib/rgl/edmonds_karp.rb', line 136

def maximum_flow(edge_capacities_map, source, sink)
  EdmondsKarpAlgorithm.new(self, edge_capacities_map).maximum_flow(source, sink)
end

#num_edges ⇒ int

Returns the number of edges.

Returns:

  • (int) —

    the number of edges



256
257
258
259
260
 
# File 'lib/rgl/base.rb', line 256

def num_edges
  r = 0
  each_edge { |u, v| r +=1 }
  r
end

#out_degree(v) ⇒ int

Returns the number of out-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v.

Parameters:

  • v —

    a vertex of the graph

Returns:

  • (int) 


240
241
242
243
244
 
# File 'lib/rgl/base.rb', line 240

def out_degree(v)
  r = 0
  each_adjacent(v) { |u| r += 1 }
  r
end

#path?(source, target) ⇒ Boolean

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

Returns:

  • (Boolean) 


10
11
12
13
14
15
 
# File 'lib/rgl/path.rb', line 10

def path?(source, target)
  return false unless has_vertex?(source)

  bfs_iterator = bfs_iterator(source)
  bfs_iterator.include?(target)
end

#prim_minimum_spanning_tree(edge_weights_map, start_vertex = nil, visitor = DijkstraVisitor.new(self)) ⇒ Object

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.



49
50
51
 
# File 'lib/rgl/prim.rb', line 49

def prim_minimum_spanning_tree(edge_weights_map, start_vertex = nil, visitor = DijkstraVisitor.new(self))
  PrimAlgorithm.new(self, edge_weights_map, visitor).minimum_spanning_tree(start_vertex)
end

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

Output the DOT-graph to stream s.



96
97
98
 
# File 'lib/rgl/dot.rb', line 96

def print_dotted_on(params = {}, s = $stdout)
  s << to_dot_graph(params).to_s << "\n"
end

#reverse ⇒ DirectedAdjacencyGraph

Return a new DirectedAdjacencyGraph which has the same set of vertices. If (u,v) is an edge of the graph, then (v,u) is an edge of the result.

If the graph is undirected, the result is self.

Returns:



182
183
184
185
186
187
188
 
# File 'lib/rgl/adjacency.rb', line 182

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

#set_edge_options(u, v, **options) ⇒ Object

Set the configuration values for the given edge



34
35
36
37
38
39
40
41
42
 
# File 'lib/rgl/dot.rb', line 34

def set_edge_options(u, v, **options)
  edge = edge_class.new(u, v)
  @edge_options ||= {}
  @edge_options[edge] ||= {}

  RGL::DOT::EDGE_OPTS.each do |opt|
    @edge_options[edge][:"#{opt}"] = options[:"#{opt}"] if options.key?(:"#{opt}")
  end
end

#set_vertex_options(vertex, **options) ⇒ Object

Set the configuration values for the given vertex



24
25
26
27
28
29
30
31
 
# File 'lib/rgl/dot.rb', line 24

def set_vertex_options(vertex, **options)
  @vertex_options ||= {}
  @vertex_options[vertex] ||= {}

  RGL::DOT::NODE_OPTS.each do |opt|
    @vertex_options[vertex][:"#{opt}"] = options[:"#{opt}"] if options.key?(:"#{opt}")
  end
end

#size ⇒ int Also known as: num_vertices

Returns the number of vertices.

Returns:

  • (int) —

    the number of vertices



248
249
250
 
# File 'lib/rgl/base.rb', line 248

def size # Why not in Enumerable?
  inject(0) { |n, v| n + 1 }
end

#strongly_connected_components ⇒ TarjanSccVisitor

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.

Returns:

Raises:



135
136
137
138
139
140
141
142
 
# File 'lib/rgl/connected_components.rb', line 135

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 ⇒ DirectedAdjacencyGraph

Convert a general graph to an AdjacencyGraph. If the graph is directed, returns a DirectedAdjacencyGraph; otherwise, returns an AdjacencyGraph.

Returns:



170
171
172
173
174
175
 
# File 'lib/rgl/adjacency.rb', line 170

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 DOT::Digraph for directed graphs or a DOT::Graph for an undirected RGL::Graph. params can contain any graph property specified in rdot.rb.



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
88
89
90
91
92
 
# File 'lib/rgl/dot.rb', line 48

def to_dot_graph(params = {})
  params['name'] ||= self.class.name.gsub(/:/, '_')
  fontsize       = params['fontsize'] ? params['fontsize'] : '8'
  graph          = (directed? ? DOT::Digraph : DOT::Graph).new(params)
  edge_class     = directed? ? DOT::DirectedEdge : DOT::Edge

  each_vertex do |v|
    default_vertex_options = {
      'name'     => vertex_id(v),
      'fontsize' => fontsize,
      'label'    => vertex_label(v)
    }
    each_vertex_options = default_vertex_options

    if @vertex_options && @vertex_options[v]
      RGL::DOT::NODE_OPTS.each do |opt|
        if @vertex_options[v].key?(:"#{opt}")
          each_vertex_options["#{opt}"] = @vertex_options[v].fetch(:"#{opt}")
        end
      end
    end
    graph << DOT::Node.new(each_vertex_options)
  end

  edges.each do |edge|
    default_edge_options = {
      'from'     => edge.source,
      'to'       => edge.target,
      'fontsize' => fontsize
    }

    each_edge_options = default_edge_options

    if @edge_options && @edge_options[edge]
      RGL::DOT::EDGE_OPTS.each do |opt|
        if @edge_options[edge].key?(:"#{opt}")
          each_edge_options["#{opt}"] = @edge_options[edge].fetch(:"#{opt}")
        end
      end
    end
    graph << edge_class.new(each_edge_options)
    end

  graph
end

#to_s ⇒ String

Utility method to show a string representation of the edges of the graph.

Returns:

  • (String) 


264
265
266
 
# File 'lib/rgl/base.rb', line 264

def to_s
  edges.collect {|e| e.to_s}.sort.join
end

#to_undirected ⇒ AdjacencyGraph

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.

Returns:



196
197
198
199
 
# File 'lib/rgl/adjacency.rb', line 196

def to_undirected
  return self unless directed?
  AdjacencyGraph.new(Set, self)
end

#topsort_iterator ⇒ TopsortIterator

Returns for the graph.

Returns:



68
69
70
 
# File 'lib/rgl/topsort.rb', line 68

def topsort_iterator
  TopsortIterator.new(self)
end

#transitive_closure ⇒ Object

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.

Returns:

  • DirectedAdjacencyGraph

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

Returns:

  • DirectedAdjacencyGraph

Raises:



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
 
# File 'lib/rgl/transitivity.rb', line 100

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 cg.to_enum(:each_adjacent, v).any? { |x| x != w && paths_from[x].include?(w) }
        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)
      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 = self.to_enum(: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

#vertex_id(v) ⇒ Object 



19
20
21
 
# File 'lib/rgl/dot.rb', line 19

def vertex_id(v)
  v
end

#vertex_label(v) ⇒ Object

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



15
16
17
 
# File 'lib/rgl/dot.rb', line 15

def vertex_label(v)
  v.to_s
end

#vertices ⇒ Array

Synonym for #to_a inherited by Enumerable.

Returns:

  • (Array) —

    of vertices



209
210
211
 
# File 'lib/rgl/base.rb', line 209

def vertices
  to_a
end

#vertices_filtered_by(&filter) ⇒ ImplicitGraph

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

The methods provides similar functionality as BGLs Filtered Graph

Examples:


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

Returns:



125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/rgl/implicit.rb', line 125

def vertices_filtered_by(&filter)
  implicit_graph do |g|
    g.vertex_iterator do |b|
      self.each_vertex { |v| b.call(v) if filter.call(v) }
    end

    g.adjacent_iterator do |v, b|
      self.each_adjacent(v) { |u| b.call(u) if filter.call(u) }
    end
  end
end

#write_to_graphic_file(fmt = 'png', dotfile = "graph", options = {}) ⇒ Object

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



116
117
118
119
120
121
122
123
124
125
126
127
128
 
# File 'lib/rgl/dot.rb', line 116

def write_to_graphic_file(fmt = 'png', dotfile = "graph", options = {})
  src = dotfile + ".dot"
  dot = dotfile + "." + fmt

  File.open(src, 'w') do |f|
    f << self.to_dot_graph(options).to_s << "\n"
  end

  unless system("dot -T#{fmt} #{src} -o #{dot}")
    raise "Error executing dot. Did you install GraphViz?"
  end
  dot
end