class Tangle::Undirected::Graph

Undirected graph

Public Instance Methods

adjacent(vertex) click to toggle source

Return the set of adjacent vertices

# File lib/tangle/undirected/graph.rb, line 18
def adjacent(vertex)
  Set.new(edges(vertex).map { |edge| edge.walk(vertex) })
end
adjacent?(vertex, other) click to toggle source

Two vertices are adjacent if there is an edge between them

# File lib/tangle/undirected/graph.rb, line 13
def adjacent?(vertex, other)
  edges(vertex).any? { |edge| edge[vertex] == other }
end
component(vertex)
Alias for: connected_subgraph
connected?(*tested_vertices) click to toggle source

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

# 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_component(vertex)
Alias for: connected_subgraph
connected_subgraph(vertex) click to toggle source

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

connected_subgraph(vertex) => Graph

# File lib/tangle/undirected/graph.rb, line 27
def connected_subgraph(vertex)
  subgraph { |other| connected?(vertex, other) }
end
Also aliased as: component, connected_component
disconnected?(*tested_vertices) click to toggle source

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

# File lib/tangle/undirected/graph.rb, line 56
def disconnected?(*tested_vertices)
  !connected?(*tested_vertices)
end
disconnected_subgraph(vertex) click to toggle source

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

# File lib/tangle/undirected/graph.rb, line 36
def disconnected_subgraph(vertex)
  subgraph { |other| !connected?(vertex, other) }
end
reachable(start_vertex) click to toggle source

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

# File lib/tangle/undirected/graph.rb, line 62
def reachable(start_vertex)
  vertex_enumerator(start_vertex, :adjacent)
end

Private Instance Methods

new_edge(*args, **kwargs) click to toggle source
# File lib/tangle/undirected/graph.rb, line 68
def new_edge(*args, **kwargs)
  Edge.new(*args, **kwargs)
end