Class: GRATR::Digraph

Inherits:
Object
  • Object
show all
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

DirectedMultiGraph, DirectedPseudoGraph

Instance Method Summary collapse

Methods included from Graph::ChinesePostman

#closed_chinese_postman_tour

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

#initialize(*params) ⇒ Digraph

Returns a new instance of Digraph.

Raises:

  • (ArgumentError) 


55
56
57
58
59
60
 
# File 'lib/gratr/digraph.rb', line 55

def initialize(*params)
  raise ArgumentError if params.any? do |p| 
   !(p.kind_of? GRATR::Graph or p.kind_of? Array)
  end if self.class == GRATR::Digraph
  super(*params)
end

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

Returns:

  • (Boolean) 


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

Returns:

  • (Boolean) 


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.

Returns:

  • (Boolean) 


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