# Class: RGL::ImplicitGraph

Inherits:
Object
• Object
show all
Includes:
Graph
Defined in:
lib/rgl/implicit.rb

## Overview

An ImplicitGraph provides a handy way to define graphs on the fly, using two blocks for the two iterators defining a graph. Other examples are given by the methods Graph#vertices_filtered_by and Graph#edges_filtered_by, which can be applied to any graph.

Examples:

# A directed cyclic graph, with five vertices can be created as follows:
g = RGL::ImplicitGraph.new do |g|
g.vertex_iterator { |b| 0.upto(4,&b) }
g.adjacent_iterator { |x, b| b.call((x+1)%5) }
g.directed = true
end

g.to_s # => "(0-1)(1-2)(2-3)(3-4)(4-0)"

## Constant Summary collapse

EMPTY_VERTEX_ITERATOR =
proc { |b| }
EMPTY_NEIGHBOR_ITERATOR =
proc { |x, b| }

## Instance Attribute Summary collapse

• writeonly

Sets the attribute directed.

## Instance Method Summary collapse

• included from Graph

Returns true if the graph contains no cycles.

• Sets the adjacent_iterator to block, which must be a block of two parameters:.

• included from Graph

Of vertices adjacent to vertex v.

• included from Graph

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

• included from Graph

Starting at vertex v.

• included from Graph

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

• included from Graph

Returns true if the graph is bipartite.

• included from Graph

Separates graph’s vertices into two disjoint sets so that every edge of the graph connects vertices from different sets.

• included from Graph

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.

• included from Graph

Do a recursive DFS search on the whole graph.

• included from Graph

Start a depth first search at vertex u.

• included from Graph

Staring at vertex v.

• included from Graph

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

• included from Graph

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

• Returns the value of @directed.

• included from Graph

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

• included from Graph

Vertices get enumerated.

• included from Graph

Compute the connected components of an undirected graph, using a DFS (Depth-first search)-based approach.

• included from Graph

The class for edges: Edge::DirectedEdge or Edge::UnDirectedEdge.

• Sets the edge_iterator to block, which must be a block of two parameters: The first parameter is the source of the edges; the second is the target of the edge.

• included from Graph

It uses #each_edge to compute the edges.

• included from Graph

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

• included from Graph

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

• #eql?(other) ⇒ Boolean (also: #==) included from Graph

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

• included from Graph

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

• included from Graph

Returns true if v is a vertex of the graph.

• included from Graph

Return a new ImplicitGraph which is isomorphic (i.e. has same edges and vertices) to the receiver.

• constructor

Create a new ImplicitGraph, which is empty by default.

• included from Graph

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

• included from Graph

The number of edges.

• included from Graph

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

• included from Graph

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

• included from Graph

Finds the minimum spanning tree of the graph.

• included from Graph

Output the DOT-graph to stream s.

• included from Graph

Return a new DirectedAdjacencyGraph which has the same set of vertices.

• included from Graph

Set the configuration values for the given edge.

• included from Graph

Set the configuration values for the given vertex.

• #size ⇒ int (also: #num_vertices) included from Graph

The number of vertices.

• included from Graph

This is Tarjan’s algorithm for strongly connected components, from his paper “Depth first search and linear graph algorithms”.

• included from Graph

Convert a general graph to an AdjacencyGraph.

• included from Graph

Return a DOT::Digraph for directed graphs or a DOT::Graph for an undirected Graph.

• included from Graph

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

• included from Graph

Return a new AdjacencyGraph which has the same set of vertices.

• included from Graph

For the graph.

• included from Graph

Returns an DirectedAdjacencyGraph which is the transitive closure of this graph.

• included from Graph

Returns an DirectedAdjacencyGraph which is the transitive reduction of this graph.

• included from Graph
• Sets the vertex_iterator to block, which must be a block of one parameter which again is the block called by #each_vertex.

• included from Graph

Returns a label for vertex v.

• included from Graph

Synonym for #to_a inherited by Enumerable.

• included from Graph

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

• included from Graph

Use dot to create a graphical representation of the graph.

## Constructor Details

### #initialize {|_self| ... } ⇒ ImplicitGraph

Create a new RGL::ImplicitGraph, which is empty by default. The caller should configure the graph using vertex and neighbor iterators. If the graph is directed, the client should set @directed to true. The default value for @directed is false.

Yields:

• (_self)

Yield Parameters:

• _self

the object that the method was called on

 40 41 42 43 44 45 # File 'lib/rgl/implicit.rb', line 40 def initialize @directed = false @vertex_iterator = EMPTY_VERTEX_ITERATOR @adjacent_iterator = EMPTY_NEIGHBOR_ITERATOR yield self if block_given? # Let client overwrite defaults. end

## Instance Attribute Details

### #directed=(value) ⇒ Object(writeonly)

Sets the attribute directed

Parameters:

• value

the value to set the attribute directed to.

 30 31 32 # File 'lib/rgl/implicit.rb', line 30 def directed=(value) @directed = value end

## Instance Method Details

### #acyclic? ⇒ Boolean Originally defined in module Graph

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

Returns:

• (Boolean)

Sets the adjacent_iterator to block, which must be a block of two parameters:

The first parameter is the vertex the neighbors of which are to be
traversed.

The second is the block which will be called for each neighbor
of this vertex.
 86 87 88 # File 'lib/rgl/implicit.rb', line 86 def adjacent_iterator(&block) @adjacent_iterator = block end

### #adjacent_vertices(v) ⇒ Array Originally defined in module Graph

Returns of vertices adjacent to vertex v.

Parameters:

• v

a vertex of the graph

Returns:

• (Array)

of vertices adjacent to vertex v.

### #bellman_ford_shortest_paths(edge_weights_map, source, visitor = BellmanFordVisitor.new(self)) ⇒ Hash[Object,Array] Originally defined in module Graph

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

### #bfs_iterator(v = self.detect { |x| true }) ⇒ BFSIterator Originally defined in module Graph

Returns starting at vertex v.

Returns:

• starting at vertex v.

### #bfs_search_tree_from(v) ⇒ DirectedAdjacencyGraph Originally defined in module Graph

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

Returns:

• which represents a BFS search tree starting at v.

### #bipartite? ⇒ Boolean Originally defined in module Graph

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

Returns:

• (Boolean)

### #bipartite_sets ⇒ Array Originally defined in module Graph

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:

### #condensation_graph ⇒ Object Originally defined in module Graph

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:

### #depth_first_search(vis = DFSVisitor.new(self), &b) ⇒ Object Originally defined in module Graph

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

### #depth_first_visit(u, vis = DFSVisitor.new(self), &b) ⇒ Object Originally defined in module Graph

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

### #dfs_iterator(v = self.detect { |x| true }) ⇒ DFSIterator Originally defined in module Graph

Returns staring at vertex v.

Returns:

• staring at vertex v.

### #dijkstra_shortest_path(edge_weights_map, source, target, visitor = DijkstraVisitor.new(self)) ⇒ Object Originally defined in module Graph

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.

### #dijkstra_shortest_paths(edge_weights_map, source, visitor = DijkstraVisitor.new(self)) ⇒ Object Originally defined in module Graph

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.

### #directed? ⇒ Boolean

Returns the value of @directed.

Returns:

• (Boolean)
 49 50 51 # File 'lib/rgl/implicit.rb', line 49 def directed? @directed end

### #dotty(params = {}) ⇒ Object Originally defined in module Graph

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

### #each(&block) ⇒ Object Originally defined in module Graph

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

 57 58 59 # File 'lib/rgl/implicit.rb', line 57 def each_adjacent(v, &block) @adjacent_iterator.call(v, block) end

### #each_connected_component {|comp| ... } ⇒ Object Originally defined in module Graph

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:

### #each_edge(&block) ⇒ Object

 61 62 63 64 65 66 67 # File 'lib/rgl/implicit.rb', line 61 def each_edge(&block) if defined? @edge_iterator @edge_iterator.call(block) else super # use default implementation end end

### #each_vertex(&block) ⇒ Object

 53 54 55 # File 'lib/rgl/implicit.rb', line 53 def each_vertex(&block) @vertex_iterator.call(block) end

### #edge_class ⇒ Class Originally defined in module Graph

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

Returns:

### #edge_iterator(&block) ⇒ Object

Sets the edge_iterator to block, which must be a block of two parameters: The first parameter is the source of the edges; the second is the target of the edge.

 94 95 96 # File 'lib/rgl/implicit.rb', line 94 def edge_iterator(&block) @edge_iterator = block end

### #edges ⇒ Array Originally defined in module Graph

It uses #each_edge to compute the edges

Returns:

• (Array)

of edges (DirectedEdge or UnDirectedEdge) of the graph

### #edges_filtered_by(&filter) ⇒ ImplicitGraph Originally defined in module Graph

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:

### #empty? ⇒ Boolean Originally defined in module Graph

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

Returns:

• (Boolean)

### #eql?(other) ⇒ BooleanAlso known as: == Originally defined in module Graph

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

Parameters:

Returns:

• (Boolean)

### #has_edge?(u, v) ⇒ Boolean Originally defined in module Graph

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

Returns:

• (Boolean)

### #has_vertex?(v) ⇒ Boolean Originally defined in module Graph

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)

### #implicit_graph {|result| ... } ⇒ ImplicitGraph Originally defined in module Graph

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:

### #maximum_flow(edge_capacities_map, source, sink) ⇒ Hash Originally defined in module Graph

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)

### #num_edges ⇒ int Originally defined in module Graph

Returns the number of edges.

Returns:

• (int)

the number of edges

### #out_degree(v) ⇒ int Originally defined in module Graph

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)

### #path?(source, target) ⇒ Boolean Originally defined in module Graph

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

Returns:

• (Boolean)

### #prim_minimum_spanning_tree(edge_weights_map, start_vertex = nil, visitor = DijkstraVisitor.new(self)) ⇒ Object Originally defined in module Graph

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.

Output the DOT-graph to stream s.

### #reverse ⇒ DirectedAdjacencyGraph Originally defined in module Graph

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:

### #set_edge_options(u, v, **options) ⇒ Object Originally defined in module Graph

Set the configuration values for the given edge

### #set_vertex_options(vertex, **options) ⇒ Object Originally defined in module Graph

Set the configuration values for the given vertex

### #size ⇒ intAlso known as: num_vertices Originally defined in module Graph

Returns the number of vertices.

Returns:

• (int)

the number of vertices

### #strongly_connected_components ⇒ TarjanSccVisitor Originally defined in module Graph

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:

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

Returns:

### #to_dot_graph(params = {}) ⇒ Object Originally defined in module Graph

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.

### #to_s ⇒ String Originally defined in module Graph

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

Returns:

• (String)

### #to_undirected ⇒ AdjacencyGraph Originally defined in module Graph

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:

### #topsort_iterator ⇒ TopsortIterator Originally defined in module Graph

Returns for the graph.

Returns:

• for the graph.

### #transitive_closure ⇒ Object Originally defined in module Graph

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:

Raises:

### #transitive_reduction ⇒ Object Originally defined in module Graph

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:

Raises:

### #vertex_iterator(&block) ⇒ Object

Sets the vertex_iterator to block, which must be a block of one parameter which again is the block called by #each_vertex.

 73 74 75 # File 'lib/rgl/implicit.rb', line 73 def vertex_iterator(&block) @vertex_iterator = block end

### #vertex_label(v) ⇒ Object Originally defined in module Graph

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

### #vertices ⇒ Array Originally defined in module Graph

Synonym for #to_a inherited by Enumerable.

Returns:

• (Array)

of vertices

### #vertices_filtered_by(&filter) ⇒ ImplicitGraph Originally defined in module Graph

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) }
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:

### #write_to_graphic_file(fmt = 'png', dotfile = "graph", options = {}) ⇒ Object Originally defined in module Graph

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