Gryphon
API
Generated with
Gryphon/com.phasmidsoftware.gryphon/com.phasmidsoftware.gryphon.traverse/ConnectedComponents

ConnectedComponents

com.phasmidsoftware.gryphon.traverse.ConnectedComponents
object ConnectedComponents

Computes connected components of an undirected graph.

Uses getConnexions (the manual parent-tracking DFS on Traversable) to explore each component in turn, labelling vertices with a monotonically increasing component ID.

NOTE: this implementation is intended for undirected graphs only. For strongly connected components of a directed graph, see StronglyConnectedComponents (Kosaraju's algorithm) — to be implemented.

Attributes

Graph
Supertypes
class Object
trait Matchable
class Any
Self type

Members list

Value members

Concrete methods

def components[V, E](graph: Traversable[V])(using random: Random = ...): ConnectedResult[V, E]

Identifies all connected components of graph, returning both the DFS discovery tree (as Connexions) and a component-ID map for every vertex.

Identifies all connected components of graph, returning both the DFS discovery tree (as Connexions) and a component-ID map for every vertex.

Type parameters

E

the edge-attribute type.

V

the vertex type.

Value parameters

graph

the graph to analyse; must be a Graph[V] to allow key enumeration.

random

controls adjacency ordering during traversal.

Attributes

Returns

a ConnectedResult[V, E] — a pair of (Connexions, componentMap).

Throws
GraphException

if graph is not a Graph[V].

Generated with