Class: Tangle::Undirected::Graph

Inherits:
BaseGraph show all
Defined in:
lib/tangle/undirected/graph.rb

Overview

Undirected graph

Direct Known Subclasses

Simple::Graph

Instance Attribute Summary

Attributes included from Mixin::Initialize

#mixins

Instance Method Summary collapse

Methods inherited from BaseGraph

[], #[], #add_edge, #add_vertex, #clone, #edges, #fetch, #initialize, #remove_edge, #remove_vertex, #select, #subgraph, #to_s, #vertices

Methods included from Currify

included

Constructor Details

This class inherits a constructor from Tangle::BaseGraph

Instance Method Details

#adjacent(vertex) ⇒ Object

Return the set of adjacent vertices



18
19
20
 
# File 'lib/tangle/undirected/graph.rb', line 18

def adjacent(vertex)
  Set.new(edges(vertex).map { |edge| edge.walk(vertex) })
end

#adjacent?(vertex, other) ⇒ Boolean

Two vertices are adjacent if there is an edge between them

Returns:

  • (Boolean) 


13
14
15
 
# File 'lib/tangle/undirected/graph.rb', line 13

def adjacent?(vertex, other)
  edges(vertex).any? { |edge| edge[vertex] == other }
end

#connected?(*tested_vertices) ⇒ Boolean

A graph is connected if all vertices are connected to all vertices An empty graph is disconnected.

Returns:

  • (Boolean) 


43
44
45
46
47
48
49
50
51
 
# File 'lib/tangle/undirected/graph.rb', line 43

def connected?(*tested_vertices)
  tested_vertices = vertices if tested_vertices.empty?
  return false if tested_vertices.empty?

  tested_vertices.combination(2).all? do |pair|
    this, that = pair.to_a
    reachable(this).any? { |other| other == that }
  end
end

#connected_subgraph(vertex) ⇒ Object Also known as: component, connected_component

Get the largest connected subgraph for a vertex. Also aliased as :component and :connected_component

connected_subgraph(vertex) => Graph



27
28
29
 
# File 'lib/tangle/undirected/graph.rb', line 27

def connected_subgraph(vertex)
  subgraph { |other| connected?(vertex, other) }
end

#disconnected?(*tested_vertices) ⇒ Boolean

A graph is disconnected if any vertex is not connected to all other. An empty graph is disconnected.

Returns:

  • (Boolean) 


56
57
58
 
# File 'lib/tangle/undirected/graph.rb', line 56

def disconnected?(*tested_vertices)
  !connected?(*tested_vertices)
end

#disconnected_subgraph(vertex) ⇒ Object

Get the largest subgraph that is not connected to a vertex, or what’s left after removing the connected subgraph.



36
37
38
 
# File 'lib/tangle/undirected/graph.rb', line 36

def disconnected_subgraph(vertex)
  subgraph { |other| !connected?(vertex, other) }
end

#reachable(start_vertex) ⇒ Object

Return a breadth-first Enumerator for all reachable vertices, by transitive adjacency.



62
63
64
 
# File 'lib/tangle/undirected/graph.rb', line 62

def reachable(start_vertex)
  vertex_enumerator(start_vertex, :adjacent)
end