Module: Plexus::DirectedGraphBuilder::Algorithms

Includes:
ChinesePostman, Distance, Search, StrongComponents
Defined in:
lib/plexus/directed_graph/algorithms.rb

Instance Method Summary collapse

Methods included from ChinesePostman

#closed_chinese_postman_tour

Methods included from Distance

#bellman_ford_moore, #dijkstras_algorithm, #floyd_warshall, #shortest_path

Methods included from StrongComponents

#condensation, #plexus_inner_transitive_closure!, #strong_components, #transitive_closure, #transitive_closure!

Methods included from 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, #sort, #spanning_forest, #topsort, #tree_from_vertex

Dynamic Method Handling

This class handles dynamic methods through the method_missing method in the class Plexus::Search

Instance Method Details

#ancestors(node, options = {:recursive => true}) ⇒ Object 



86
87
88
 
# File 'lib/plexus/directed_graph/algorithms.rb', line 86

def ancestors(node, options = {:recursive => true})
  community(node, :in)
end

#balanced?(v) ⇒ Boolean

Balanced is the state when the out edges count is equal to the in edges count.

Returns:

  • (Boolean) 


61
62
63
 
# File 'lib/plexus/directed_graph/algorithms.rb', line 61

def balanced?(v)
  out_degree(v) == in_degree(v)
end

#community(node, direction, options = {:recursive => true}) ⇒ Object 



71
72
73
74
75
76
77
78
79
80
 
# File 'lib/plexus/directed_graph/algorithms.rb', line 71

def community(node, direction, options = {:recursive => true})
  nodes, stack = {}, adjacent(node, :direction => direction)
  while n = stack.pop
    unless nodes[n.object_id] || node == n
      nodes[n.object_id] = n
      stack += adjacent(n, :direction => direction) if options[:recursive]
    end
  end
  nodes.values
end

#delta(v) ⇒ Object

Returns out_degree(v) - in_degree(v).



67
68
69
 
# File 'lib/plexus/directed_graph/algorithms.rb', line 67

def delta(v)
  out_degree(v) - in_degree(v)
end

#descendants(node, options = {:recursive => true}) ⇒ Object 



82
83
84
 
# File 'lib/plexus/directed_graph/algorithms.rb', line 82

def descendants(node, options = {:recursive => true})
  community(node, :out)
end

#directed? ⇒ Boolean

A directed graph is directed by definition.

Returns:

  • (Boolean) —

    always true



22
23
24
 
# File 'lib/plexus/directed_graph/algorithms.rb', line 22

def directed?
  true
end

#edge_class ⇒ Plexus::MultiArc, Plexus::Arc

A digraph uses the Arc class for edges.

Returns:



31
32
33
 
# File 'lib/plexus/directed_graph/algorithms.rb', line 31

def edge_class
  @parallel_edges ? Plexus::MultiArc : Plexus::Arc
end

#family(node, options = {:recursive => true}) ⇒ Object 



90
91
92
 
# File 'lib/plexus/directed_graph/algorithms.rb', line 90

def family(node, options = {:recursive => true})
  community(node, :all)
end

#oriented? ⇒ Boolean

Check whether the graph is oriented or not.

Returns:

  • (Boolean) 


51
52
53
54
55
 
# File 'lib/plexus/directed_graph/algorithms.rb', line 51

def oriented?
  e = edges
  re = e.map { |x| x.reverse}
  not e.any? { |x| re.include?(x)}
end

#reversal ⇒ DirectedGraph

Reverse all edges in a graph.

Returns:

  • (DirectedGraph) —

    a copy of the receiver for which the direction of edges has been inverted.



40
41
42
43
44
45
 
# File 'lib/plexus/directed_graph/algorithms.rb', line 40

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