Graph property predicates

Provides functions to test structural properties of graphs: isTree, isForest, isRegular, isComplete, etc.

Imports

../types, ../graph, ../digraph

Procs

proc flowHierarchy[N](g: DiGraph[N]): float: Compute the flow hierarchy of a directed graph. The fraction of edges not in a cycle.
func girth[N](g: Graph[N]): int: Return the length of the shortest cycle in the graph. Returns -1 if the graph is acyclic.
func isArborescence[N](g: DiGraph[N]): bool: Return true if the digraph is an arborescence (rooted directed tree). An arborescence is a directed tree where every node (except the root) has exactly one predecessor, and the root has zero predecessors.
func isBranching[N](g: DiGraph[N]): bool: Return true if the digraph is a branching (forest of arborescences). Every node has in-degree 0 or 1, and there are no cycles.
func isComplete[N](g: Graph[N]): bool: Return true if the graph is complete (every pair connected).
func isConnected[N](g: Graph[N]): bool: Return true if the undirected graph is connected.
func isDAG[N](g: DiGraph[N]): bool: Return true if the directed graph is a DAG (no cycles).
proc isDistanceRegular[N](g: Graph[N]): bool: Check if the graph is distance-regular. A graph is distance-regular if for any vertices u, v at distance i, the number of neighbors of v at distance i-1, i, i+1 from u depends only on i and not on the specific choice of u and v.
func isForest[N](g: Graph[N]): bool: Return true if the undirected graph is a forest (acyclic). A forest has no cycles; equivalently each connected component is a tree.
func isKRegular[N](g: Graph[N]; k: int): bool: Check if every node has degree exactly k.
func isRegular[N](g: Graph[N]): bool: Return true if every node has the same degree.
func isStronglyConnected[N](g: DiGraph[N]): bool: Return true if the directed graph is strongly connected.
proc isStronglyRegular[N](g: Graph[N]): bool: Check if the graph is strongly regular. A graph is strongly regular with parameters (n, k, λ, μ) if it is k-regular and every pair of adjacent vertices has λ common neighbors and every pair of non-adjacent vertices has μ common neighbors.
proc isThresholdGraph[N](g: Graph[N]): bool: Check if the graph is a threshold graph. A threshold graph can be constructed by repeated addition of isolated nodes or nodes connected to all existing nodes.
func isTree[N](g: Graph[N]): bool: Return true if the undirected graph is a tree. A tree is a connected graph with exactly n-1 edges.
func isWeaklyConnected[N](g: DiGraph[N]): bool: Return true if the directed graph is weakly connected.
proc moralGraph[N](g: DiGraph[N]): Graph[N]: Compute the moral graph of a DAG (marry parents + drop orientation).
proc treeCentroid[N](g: Graph[N]): seq[N]: Return the centroid of a tree (1 or 2 nodes). The centroid minimizes the maximum distance to any other node. Uses leaf-peeling algorithm.

nimnet/algorithms/properties

Imports

Procs