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
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_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