Class: GRATR::Digraph
 Inherits:

Object
 Object
 GRATR::Digraph
 Includes:
 AdjacencyGraph, Graph::ChinesePostman, Graph::Distance, Graph::Search, Graph::StrongComponents
 Defined in:
 lib/gratr/digraph.rb
Overview
Digraph is a directed graph which is a finite set of vertices and a finite set of edges connecting vertices. It cannot contain parallel edges going from the same source vertex to the same target. It also cannot contain loops, i.e. edges that go have the same vertex for source and target.
DirectedPseudoGraph is a class that allows for parallel edges, and a DirectedMultiGraph is a class that allows for parallel edges and loops as well.
Direct Known Subclasses
Instance Method Summary collapse

#balanced?(v) ⇒ Boolean
Balanced is when the out edge count is equal to the in edge count.

#delta(v) ⇒ Object
Returns out_degree(v)  in_degree(v).

#directed? ⇒ Boolean
A directed graph is directed by definition.

#edge_class ⇒ Object
A digraph uses the Arc class for edges.

#initialize(*params) ⇒ Digraph
constructor
A new instance of Digraph.

#oriented? ⇒ Boolean
Return true if the Graph is oriented.

#reversal ⇒ Object
Reverse all edges in a graph.
Methods included from Graph::ChinesePostman
Methods included from Graph::Distance
#bellman_ford_moore, #dijkstras_algorithm, #floyd_warshall, #shortest_path
Methods included from Graph::StrongComponents
#condensation, #strong_components, #transitive_closure, #transitive_closure!
Methods included from Graph::Search
#acyclic?, #astar, #best_first, #bfs, #bfs_spanning_forest, #bfs_tree_from_vertex, #cyclic?, #dfs, #dfs_spanning_forest, #dfs_tree_from_vertex, #lexicograph_bfs, #method_missing, #pre_search_method_missing, #spanning_forest, #topsort, #tree_from_vertex
Methods included from AdjacencyGraph
#add_edge!, #add_vertex!, #adjacent, #edge?, #edges, #graph_adjacent, included, #remove_edge!, #remove_vertex!, #vertex?, #vertices
Methods included from Graph
#dotty, #to_dot, #to_dot_graph, #write_to_graphic_file
Constructor Details
Dynamic Method Handling
This class handles dynamic methods through the method_missing method in the class GRATR::Graph::Search
Instance Method Details
#balanced?(v) ⇒ Boolean
Balanced is when the out edge count is equal to the in edge count
84 
# File 'lib/gratr/digraph.rb', line 84 def balanced?(v) out_degree(v) == in_degree(v); end 
#delta(v) ⇒ Object
Returns out_degree(v)  in_degree(v)
87 
# File 'lib/gratr/digraph.rb', line 87 def delta(v) out_degree(v)  in_degree(v); end 
#directed? ⇒ Boolean
A directed graph is directed by definition
63 
# File 'lib/gratr/digraph.rb', line 63 def directed?() true; end 
#edge_class ⇒ Object
A digraph uses the Arc class for edges
66 
# File 'lib/gratr/digraph.rb', line 66 def edge_class() @parallel_edges ? GRATR::MultiArc : GRATR::Arc; end 
#oriented? ⇒ Boolean
Return true if the Graph is oriented.
77 78 79 80 81 
# File 'lib/gratr/digraph.rb', line 77 def oriented? e = edges re = e.map {x x.reverse} not e.any? {x re.include?(x)} end 
#reversal ⇒ Object
Reverse all edges in a graph
69 70 71 72 73 74 
# File 'lib/gratr/digraph.rb', line 69 def reversal result = self.class.new edges.inject(result) {a,e a << e.reverse} vertices.each { v result.add_vertex!(v) unless result.vertex?(v) } result end 