# Module: Plexus::DirectedGraphBuilder::Algorithms

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

## Instance Method Summary collapse

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

• Returns out_degree(v) - in_degree(v).

• A directed graph is directed by definition.

• A digraph uses the Arc class for edges.

• Check whether the graph is oriented or not.

• Reverse all edges in a graph.

### Methods included from ChinesePostman

#closed_chinese_postman_tour

## 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:

• `Plexus::MultiArc` if the graph allows for parallel edges, `Plexus::Arc` otherwise.

 ``` 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:

• 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```