Class: RGL::DirectedAdjacencyGraph
 Inherits:

Object
 Object
 RGL::DirectedAdjacencyGraph
 Includes:
 MutableGraph
 Defined in:
 lib/rgl/adjacency.rb
Overview
The DirectedAdjacencyGraph
class implements a generalized adjacency list graph structure. An AdjacencyGraph is basically a twodimensional structure (ie, a list of lists). Each element of the first dimension represents a vertex. Each of the vertices contains a onedimensional structure that is the list of all adjacent vertices.
The class for representing the adjacency list of a vertex is, by default, a Set
. This can be configured by the client, however, when an AdjacencyGraph is created.
Direct Known Subclasses
Class Method Summary collapse

.[](*a) ⇒ Object
Shortcut for creating a DirectedAdjacencyGraph.
Instance Method Summary collapse

#acyclic? ⇒ Boolean
included
from Graph
Returns true if the graph contains no cycles.
 #add_edge(u, v) ⇒ Object

#add_edges(*edges) ⇒ Object
included
from MutableGraph
Add all edges in the edges array to the edge set.

#add_vertex(v) ⇒ Object
If the vertex is already in the graph (using
eql?
), the method does nothing. 
#add_vertices(*a) ⇒ Object
included
from MutableGraph
Add all objects in a to the vertex set.

#adjacent_vertices(v) ⇒ Array
included
from Graph
Of vertices adjacent to vertex
v
. 
#bellman_ford_shortest_paths(edge_weights_map, source, visitor = BellmanFordVisitor.new(self)) ⇒ Hash[Object,Array]
included
from Graph
Finds the shortest paths from the source to each vertex of the graph.

#bfs_iterator(v = self.detect { x true }) ⇒ BFSIterator
included
from Graph
Starting at vertex v.

#bfs_search_tree_from(v) ⇒ DirectedAdjacencyGraph
included
from Graph
This method uses the
tree_edge_event
of BFSIterator to record all tree edges of the search tree in the result. 
#bipartite? ⇒ Boolean
included
from Graph
Returns true if the graph is bipartite.

#bipartite_sets ⇒ Array
included
from Graph
Separates graph’s vertices into two disjoint sets so that every edge of the graph connects vertices from different sets.

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

#cycles ⇒ Array
included
from MutableGraph
This is not an efficient implementation O(n^4) and could be done using Minimum Spanning Trees.

#cycles_with_vertex(vertex) ⇒ Array[Array]
included
from MutableGraph
Returns all minimum cycles that pass through a give vertex.

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

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

#dfs_iterator(v = self.detect { x true }) ⇒ DFSIterator
included
from Graph
Staring at vertex v.

#dijkstra_shortest_path(edge_weights_map, source, target, visitor = DijkstraVisitor.new(self)) ⇒ Object
included
from Graph
Finds the shortest path from the source to the target in the graph.

#dijkstra_shortest_paths(edge_weights_map, source, visitor = DijkstraVisitor.new(self)) ⇒ Object
included
from Graph
Finds the shortest paths from the source to each vertex of the graph.

#directed? ⇒ Boolean
True.

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

#each(&block) ⇒ Object
included
from Graph
Vertices get enumerated.
 #each_adjacent(v, &b) ⇒ Object

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

#each_edge(&block) ⇒ Object
included
from Graph
The
each_edge
iterator should provide efficient access to all edges of the graph. 
#each_vertex(&b) ⇒ Object
Iterator for the keys of the vertices list hash.

#edge_class ⇒ Class
included
from Graph
The class for edges: Edge::DirectedEdge or Edge::UnDirectedEdge.

#edgelist_class=(klass) ⇒ Object
Converts the adjacency list of each vertex to be of type
klass
. 
#edges ⇒ Array
included
from Graph
It uses Graph#each_edge to compute the edges.

#edges_filtered_by(&filter) ⇒ ImplicitGraph
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).

#empty? ⇒ Boolean
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.

#from_graphxml(source) ⇒ Object
included
from MutableGraph
Initializes an RGL graph from a subset of the GraphML format given in
source
(see graphml.graphdrawing.org/). 
#has_edge?(u, v) ⇒ Boolean
Complexity is O(1), if a Set is used as adjacency list.

#has_vertex?(v) ⇒ Boolean
Complexity is O(1), because the vertices are kept in a
Hash
containing as values the lists of adjacent vertices of v. 
#implicit_graph {result ... } ⇒ ImplicitGraph
included
from Graph
Return a new ImplicitGraph which is isomorphic (i.e. has same edges and vertices) to the receiver.

#initialize(edgelist_class = Set, *other_graphs) ⇒ DirectedAdjacencyGraph
constructor
The new empty graph has as its edgelist class the given class.

#initialize_copy(orig) ⇒ Object
Copy internal vertices_dict.

#maximum_flow(edge_capacities_map, source, sink) ⇒ Hash
included
from Graph
Finds the maximum flow from the source to the sink in the graph.

#num_edges ⇒ int
included
from Graph
The number of edges.

#out_degree(v) ⇒ int
included
from Graph
Returns the number of outedges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex
v
. 
#path?(source, target) ⇒ Boolean
included
from Graph
Checks whether a path exists between source and target vertices in the graph.

#prim_minimum_spanning_tree(edge_weights_map, start_vertex = nil, visitor = DijkstraVisitor.new(self)) ⇒ Object
included
from Graph
Finds the minimum spanning tree of the graph.

#print_dotted_on(params = {}, s = $stdout) ⇒ Object
included
from Graph
Output the DOTgraph to stream s.
 #remove_edge(u, v) ⇒ Object
 #remove_vertex(v) ⇒ Object

#remove_vertices(*a) ⇒ Object
included
from MutableGraph
Remove all vertices specified by the array a from the graph by calling #remove_vertex.

#reverse ⇒ DirectedAdjacencyGraph
included
from Graph
Return a new DirectedAdjacencyGraph which has the same set of vertices.

#set_edge_options(u, v, **options) ⇒ Object
included
from Graph
Set the configuration values for the given edge.

#set_vertex_options(vertex, **options) ⇒ Object
included
from Graph
Set the configuration values for the given vertex.

#size ⇒ int
(also: #num_vertices)
included
from Graph
The number of vertices.

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

#to_adjacency ⇒ DirectedAdjacencyGraph
included
from Graph
Convert a general graph to an AdjacencyGraph.

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

#to_s ⇒ String
included
from Graph
Utility method to show a string representation of the edges of the graph.

#to_undirected ⇒ AdjacencyGraph
included
from Graph
Return a new AdjacencyGraph which has the same set of vertices.

#topsort_iterator ⇒ TopsortIterator
included
from Graph
For the graph.

#transitive_closure ⇒ Object
included
from Graph
Returns an DirectedAdjacencyGraph which is the transitive closure of this graph.

#transitive_reduction ⇒ Object
included
from Graph
Returns an DirectedAdjacencyGraph which is the transitive reduction of this graph.
 #vertex_id(v) ⇒ Object included from Graph

#vertex_label(v) ⇒ Object
included
from Graph
Returns a label for vertex v.

#vertices ⇒ Array
included
from Graph
Synonym for #to_a inherited by Enumerable.

#vertices_filtered_by(&filter) ⇒ ImplicitGraph
included
from Graph
Returns a new ImplicitGraph which has as vertices all vertices of the receiver which satisfy the predicate filter.

#write_to_graphic_file(fmt = 'png', dotfile = "graph", options = {}) ⇒ Object
included
from Graph
Use dot to create a graphical representation of the graph.
Constructor Details
#initialize(edgelist_class = Set, *other_graphs) ⇒ DirectedAdjacencyGraph
The new empty graph has as its edgelist class the given class. The default edgelist class is Set, to ensure set semantics for edges and vertices.
If other graphs are passed as parameters their vertices and edges are added to the new graph.
39 40 41 42 43 44 45 46 
# File 'lib/rgl/adjacency.rb', line 39 def initialize(edgelist_class = Set, *other_graphs) @edgelist_class = edgelist_class @vertices_dict = Hash.new other_graphs.each do g g.each_vertex { v add_vertex v } g.each_edge { v, w add_edge v, w } end end 
Class Method Details
.[](*a) ⇒ Object
Shortcut for creating a DirectedAdjacencyGraph
26 27 28 29 30 
# File 'lib/rgl/adjacency.rb', line 26 def self.[](*a) result = new 0.step(a.size  1, 2) { i result.add_edge(a[i], a[i + 1]) } result 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.
#add_edge(u, v) ⇒ Object
98 99 100 101 102 
# File 'lib/rgl/adjacency.rb', line 98 def add_edge(u, v) add_vertex(u) # ensure key add_vertex(v) # ensure key basic_add_edge(u, v) end 
#add_edges(*edges) ⇒ Object Originally defined in module MutableGraph
Add all edges in the edges array to the edge set. Elements of the array can be both twoelement arrays or instances of Edge::DirectedEdge or Edge::UnDirectedEdge.
#add_vertex(v) ⇒ Object
If the vertex is already in the graph (using eql?
), the method does nothing.
93 94 95 
# File 'lib/rgl/adjacency.rb', line 93 def add_vertex(v) @vertices_dict[v] = @edgelist_class.new end 
#add_vertices(*a) ⇒ Object Originally defined in module MutableGraph
Add all objects in a to the vertex set.
#adjacent_vertices(v) ⇒ Array Originally defined in module Graph
Returns 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 onevertex path  [source].
Unlike Dijkstra algorithm, BellmanFord shortest paths algorithm works with negative edge weights.
Raises ArgumentError if an edge weight is undefined.
Raises ArgumentError or the graph has negativeweight cycles. This behavior can be overridden my a custom handler for visitor’s edge_not_minimized event.
#bfs_iterator(v = self.detect { x true }) ⇒ BFSIterator Originally defined in module Graph
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.
#bipartite? ⇒ Boolean Originally defined in module Graph
Returns true if the graph is bipartite. Otherwise returns false.
#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.
#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.
#cycles ⇒ Array Originally defined in module MutableGraph
This is not an efficient implementation O(n^4) and could be done using Minimum Spanning Trees. Hint. Hint.
#cycles_with_vertex(vertex) ⇒ Array[Array] Originally defined in module MutableGraph
Returns all minimum cycles that pass through a give vertex. The format is an Array of cycles, with each cycle being an Array of vertices in the cycle.
#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.
#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 onevertex path  [source].
Raises ArgumentError if edge weight is negative or undefined.
#directed? ⇒ Boolean
Returns true.
71 72 73 
# File 'lib/rgl/adjacency.rb', line 71 def directed? true 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.
#each_adjacent(v, &b) ⇒ Object
64 65 66 67 
# File 'lib/rgl/adjacency.rb', line 64 def each_adjacent(v, &b) adjacency_list = (@vertices_dict[v] or raise NoVertexError, "No vertex #{v}.") adjacency_list.each(&b) end 
#each_connected_component {comp ... } ⇒ Object Originally defined in module Graph
Compute the connected components of an undirected graph, using a DFS (Depthfirst search)based approach. A _connected component_ of an undirected graph is a set of vertices that are all reachable from each other.
The function is implemented as an iterator which calls the client with an array of vertices for each component.
It raises an exception if the graph is directed.
#each_edge(&block) ⇒ Object Originally defined in module Graph
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).
#each_vertex(&b) ⇒ Object
Iterator for the keys of the vertices list hash.
59 60 61 
# File 'lib/rgl/adjacency.rb', line 59 def each_vertex(&b) @vertices_dict.each_key(&b) end 
#edge_class ⇒ Class Originally defined in module Graph
Returns the class for edges: Edge::DirectedEdge or Edge::UnDirectedEdge.
#edgelist_class=(klass) ⇒ Object
Converts the adjacency list of each vertex to be of type klass
. The class is expected to have a new constructor which accepts an enumerable as parameter.
121 122 123 124 125 
# File 'lib/rgl/adjacency.rb', line 121 def edgelist_class=(klass) @vertices_dict.keys.each do v @vertices_dict[v] = klass.new @vertices_dict[v].to_a end end 
#edges ⇒ Array Originally defined in module Graph
It uses #each_edge to compute the edges
#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).
#empty? ⇒ Boolean Originally defined in module Graph
Returns true if the graph has no vertices, i.e. num_vertices == 0.
#eql?(other) ⇒ Boolean Also known as: == Originally defined in module Graph
Two graphs are equal iff they have equal directed? property as well as vertices and edges sets.
#from_graphxml(source) ⇒ Object Originally defined in module MutableGraph
Initializes an RGL graph from a subset of the GraphML format given in source
(see graphml.graphdrawing.org/).
#has_edge?(u, v) ⇒ Boolean
Complexity is O(1), if a Set is used as adjacency list. Otherwise, complexity is O(out_degree(v)).
86 87 88 
# File 'lib/rgl/adjacency.rb', line 86 def has_edge?(u, v) has_vertex?(u) && @vertices_dict[u].include?(v) end 
#has_vertex?(v) ⇒ Boolean
Complexity is O(1), because the vertices are kept in a Hash
containing as values the lists of adjacent vertices of v.
79 80 81 
# File 'lib/rgl/adjacency.rb', line 79 def has_vertex?(v) @vertices_dict.has_key?(v) end 
#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.
#initialize_copy(orig) ⇒ Object
Copy internal vertices_dict
50 51 52 53 54 55 
# File 'lib/rgl/adjacency.rb', line 50 def initialize_copy(orig) @vertices_dict = orig.instance_eval { @vertices_dict }.dup @vertices_dict.keys.each do v @vertices_dict[v] = @vertices_dict[v].dup end end 
#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 nonnegative, 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.
#num_edges ⇒ int Originally defined in module Graph
Returns the number of edges.
#out_degree(v) ⇒ int Originally defined in module Graph
Returns the number of outedges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v
.
#path?(source, target) ⇒ Boolean Originally defined in module Graph
Checks whether a path exists between source and target vertices in the graph.
#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.
#print_dotted_on(params = {}, s = $stdout) ⇒ Object Originally defined in module Graph
Output the DOTgraph to stream s.
#remove_edge(u, v) ⇒ Object
113 114 115 
# File 'lib/rgl/adjacency.rb', line 113 def remove_edge(u, v) @vertices_dict[u].delete(v) unless @vertices_dict[u].nil? end 
#remove_vertex(v) ⇒ Object
105 106 107 108 109 110 
# File 'lib/rgl/adjacency.rb', line 105 def remove_vertex(v) @vertices_dict.delete(v) # remove v from all adjacency lists @vertices_dict.each_value { adjList adjList.delete(v) } end 
#remove_vertices(*a) ⇒ Object Originally defined in module MutableGraph
Remove all vertices specified by the array a from the graph by calling #remove_vertex.
#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.
#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 ⇒ int Also known as: num_vertices Originally defined in module Graph
Returns 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 = "146160",
month = jun,
year = "1972",
CODEN = "SMJCAT",
ISSN = "00975397 (print), 10957111 (electronic)",
bibdate = "Thu Jan 23 09:56:44 1997",
bibsource = "Parallel/Multi.bib, Misc/Reverse.eng.bib",
}
The output of the algorithm is recorded in a TarjanSccVisitor vis. vis.comp_map
will contain numbers giving the component ID assigned to each vertex. The number of components is vis.num_comp
.
#to_adjacency ⇒ DirectedAdjacencyGraph Originally defined in module Graph
Convert a general graph to an AdjacencyGraph. If the graph is directed, returns a DirectedAdjacencyGraph; otherwise, returns an AdjacencyGraph.
#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.
#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
.
#topsort_iterator ⇒ TopsortIterator Originally defined in module 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 selfreferencing edges.
This method should run in O(VE) time, where V and E are the number of vertices and edges respectively.
Raises NotDirectedError if run on an undirected graph.
#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(VE) time, where V and E are the number of vertices and edges respectively.
Raises NotDirectedError if run on an undirected graph.
#vertex_id(v) ⇒ Object Originally defined in module Graph
#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.
#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