module RGL::Graph

In BGL terminology the module Graph defines the graph concept (see www.boost.org/libs/graph/doc/graph_concepts.html). We however do not distinguish between the IncidenceGraph, EdgeListGraph and VertexListGraph concepts, which would complicate the interface too much. These concepts are defined in BGL to differentiate between efficient access to edges and vertices.

The RGL Graph concept contains only a few requirements that are common to all the graph concepts. These include, especially, the iterators defining the sets of vertices and edges (see #each_vertex and #each_adjacent). Most other functions are derived from these fundamental iterators, i.e. #num_vertices or num_edges.

Each graph is an enumerable of vertices.

Public Instance Methods

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

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

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

Returns an array of vertices adjacent to vertex v.

# File lib/rgl/base.rb, line 217
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)) click to toggle source

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

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

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

Raises ArgumentError if an edge weight is undefined.

Raises ArgumentError or the graph has negative-weight cycles. This behavior can be overridden my a custom handler for visitor's edge_not_minimized event.

# File lib/rgl/bellman_ford.rb, line 108
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 }) click to toggle source

Returns a BFSIterator, starting at vertex v.

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

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.

# File lib/rgl/traversal.rb, line 111
def bfs_search_tree_from(v)
  require 'rgl/adjacency'
  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?() click to toggle source

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

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

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

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

# 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 { @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() click to toggle source

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.

# 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_visit(u, vis = DFSVisitor.new(self), &b) click to toggle source

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

# File lib/rgl/traversal.rb, line 188
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
      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
  end

  vis.color_map[u] = :BLACK
  vis.handle_finish_vertex(u) # finish vertex
  b.call(u)
end
dfs_iterator(v = self.detect { |x| true }) click to toggle source

Returns a DFSIterator staring at vertex v.

# File lib/rgl/traversal.rb, line 164
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)) click to toggle source

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

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

Raises ArgumentError if edge weight is negative or undefined.

# File lib/rgl/dijkstra.rb, line 114
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)) click to toggle source

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

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

Raises ArgumentError if edge weight is negative or undefined.

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

Is the graph directed? The default returns false.

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

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

# File lib/rgl/dot.rb, line 62
def dotty(params = {})
  dotfile = "graph.dot"
  File.open(dotfile, "w") do |f|
    print_dotted_on(params, f)
  end
  system("dotty", dotfile)
end
each(&block) click to toggle source

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

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

The #each_adjacent iterator defines the out edges of vertex v. This method must be defined by concrete graph classes. Its defines the BGL IncidenceGraph concept.

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

Compute the connected components of an undirected graph, using a DFS (Depth-first search)-based approach. A _connected component_ of an undirected graph is a set of vertices that are all reachable from each other.

The function is implemented as an iterator which calls the client with an array of vertices for each component.

It raises an exception if the graph is directed.

# File lib/rgl/connected_components.rb, 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() { |u, v| ... } click to toggle source

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

# File lib/rgl/base.rb, line 158
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() { |v| ... } click to toggle source

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

# File lib/rgl/base.rb, line 138
def each_vertex() # :yields: v
  raise NotImplementedError
end
edge_class() click to toggle source

Returns the class for edges: DirectedEdge or UnDirectedEdge.

# File lib/rgl/base.rb, line 202
def edge_class
  directed? ? DirectedEdge : UnDirectedEdge
end
edges() click to toggle source

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

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

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]
# File lib/rgl/implicit.rb, line 145
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?() click to toggle source

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

# File lib/rgl/base.rb, line 190
def empty?
  num_vertices.zero?
end
eql?(other) click to toggle source

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

# File lib/rgl/base.rb, line 256
def eql?(other)
  equal?(other) || eql_graph?(other)
end
Also aliased as: ==
has_vertex?(v) click to toggle source

Returns true if v is a vertex of the graph. Same as include? inherited from Enumerable. Complexity is O(num_vertices) by default. Concrete graph may be better here (see AdjacencyGraph).

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

Return a new ImplicitGraph which is isomorphic (i.e. has same edges and vertices) to the receiver. It is a shortcut, also used by #edges_filtered_by and vertices_filtered_by.

# File lib/rgl/implicit.rb, line 163
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) click to toggle source

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

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

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

Raises ArgumentError if the graph is not directed.

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

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

Returns the number of edges.

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

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

# File lib/rgl/base.rb, line 226
def out_degree(v)
  r = 0
  each_adjacent(v) { |u| r += 1 }
  r
end
prim_minimum_spanning_tree(edge_weights_map, start_vertex = nil, visitor = DijkstraVisitor.new(self)) click to toggle source

Finds the minimum spanning tree of the graph.

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

Raises ArgumentError if edge weight is undefined.

# File lib/rgl/prim.rb, line 46
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) click to toggle source

Output the DOT-graph to stream s.

reverse() click to toggle source

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

If the graph is undirected, the result is self.

# File lib/rgl/adjacency.rb, line 189
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() click to toggle source

Returns the number of vertices.

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

This is Tarjan's algorithm for strongly connected components, from his paper “Depth first search and linear graph algorithms”. It calculates the components in a single application of DFS. We implement the algorithm with the help of the DFSVisitor TarjanSccVisitor.

Definition

A _strongly connected component_ of a directed graph G=(V,E) is a maximal set of vertices U which is in V, such that for every pair of vertices u and v in U, we have both a path from u to v and a path from v to u. That is to say, u and v are reachable from each other.

@Article!{Tarjan:1972:DFS,

author =       "R. E. Tarjan",
key =          "Tarjan",
title =        "Depth First Search and Linear Graph Algorithms",
journal =      "SIAM Journal on Computing",
volume =       "1",
number =       "2",
pages =        "146--160",
month =        jun,
year =         "1972",
CODEN =        "SMJCAT",
ISSN =         "0097-5397 (print), 1095-7111 (electronic)",
bibdate =      "Thu Jan 23 09:56:44 1997",
bibsource =    "Parallel/Multi.bib, Misc/Reverse.eng.bib",

}

The output of the algorithm is recorded in a TarjanSccVisitor vis. vis.comp_map will contain numbers giving the component ID assigned to each vertex. The number of components is vis.num_comp.

# 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() click to toggle source

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

# File lib/rgl/adjacency.rb, line 177
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 = {}) click to toggle source

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

# File lib/rgl/dot.rb, line 28
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|
    graph << DOT::Node.new(
        'name'     => vertex_id(v),
        'fontsize' => fontsize,
        'label'    => vertex_label(v)
    )
  end

  each_edge do |u, v|
    graph << edge_class.new(
        'from'     => vertex_id(u),
        'to'       => vertex_id(v),
        'fontsize' => fontsize
    )
  end

  graph
end
to_s() click to toggle source

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

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

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

If the graph is undirected, the result is self.

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

Returns a TopsortIterator.

# File lib/rgl/topsort.rb, line 66
def topsort_iterator
  TopsortIterator.new(self)
end
transitive_closure() click to toggle source

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.

# 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() click to toggle source

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.

# 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) click to toggle source
# File lib/rgl/dot.rb, line 20
def vertex_id(v)
  v
end
vertex_label(v) click to toggle source

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

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

Return the array of vertices. Synonym for to_a inherited by Enumerable.

# File lib/rgl/base.rb, line 196
def vertices
  to_a
end
vertices_filtered_by(&filter) click to toggle source

Graph adaptors

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

The methods provides similar functionality 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 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)"
# File lib/rgl/implicit.rb, line 124
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") click to toggle source

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

# File lib/rgl/dot.rb, line 73
def write_to_graphic_file(fmt='png', dotfile="graph")
  src = dotfile + ".dot"
  dot = dotfile + "." + fmt

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

  system("dot -T#{fmt} #{src} -o #{dot}")
  dot
end

Private Instance Methods

each_edge_aux() { |u, v| ... } click to toggle source
# File lib/rgl/base.rb, line 296
def each_edge_aux
  # needed in each_edge
  visited = Hash.new

  each_vertex do |u|
    each_adjacent(u) do |v|
      edge = UnDirectedEdge.new(u, v)

      unless visited.has_key?(edge)
        visited[edge] = true
        yield u, v
      end
    end
  end
end
eql_edges_set?(other) click to toggle source
# File lib/rgl/base.rb, line 282
def eql_edges_set?(other)
  other_num_edges = 0

  other.each_edge do |u, v|
    if has_edge?(u, v)
      other_num_edges += 1
    else
      return false
    end
  end

  other_num_edges == num_edges
end
eql_graph?(other) click to toggle source
# File lib/rgl/base.rb, line 264
def eql_graph?(other)
  other.is_a?(Graph) && directed? == other.directed? && eql_vertices_set?(other) && eql_edges_set?(other)
end
eql_vertices_set?(other) click to toggle source
# File lib/rgl/base.rb, line 268
def eql_vertices_set?(other)
  other_num_vertices = 0

  other.each_vertex do |v|
    if has_vertex?(v)
      other_num_vertices += 1
    else
      return false
    end
  end

  other_num_vertices == num_vertices
end