numConnectedComponents -- returns the number of connected components in a (hyper)graph

This function returns the number of connected components of a hypergraph. A connected component of a hypergraph is any maximal set of vertices which are pairwise connected by a non-trivial path. Isolated vertices, which are those not appearing in any edge, do not count as connected components. This is in contrast to numConnectedGraphComponents in which isolated vertices are counted as connected components. See the Connected Components Tutorial for more information.

The algorithm used by numConnectedComponents turns H into a simplicial complex, and then computes the rank of the 0^{th} reduced homology group. This number plus 1 gives the number of connected components of H.

We depart from this method in two cases: We define the hypergraph with only the empty edge (corresponding to the irrelevant simplicial complex) and the hypergraph with empty edge set (corresponding to the void simplicial complex) to have 0 connected components.

Although this method can be applied to graphs, its output does not match the most common meaning for the number of connected components of a graph. Instead, one should use numConnectedGraphComponents.

i1 : S = QQ[a..e];

i2 : g = graph {a*b,b*c,c*d,d*e,a*e} -- the 5-cycle (connected)

o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}
           "ring" => S
           "vertices" => {a, b, c, d, e}

o2 : Graph

i3 : h = graph {a*b,b*c,c*a,d*e} -- a 3-cycle and a disjoint edge (not connected)

o3 = Graph{"edges" => {{a, b}, {a, c}, {b, c}, {d, e}}}
           "ring" => S
           "vertices" => {a, b, c, d, e}

o3 : Graph

i4 : numConnectedComponents g

o4 = 1

i5 : numConnectedComponents h

o5 = 2

The following example contains a hypergraph with an edge of size one. The vertex in this edge is not considered isolated and does count as a connected component.

i6 : S = QQ[a..d];

i7 : H = hyperGraph {a*b,c}

o7 = HyperGraph{"edges" => {{a, b}, {c}}  }
                "ring" => S
                "vertices" => {a, b, c, d}

o7 : HyperGraph

i8 : isolatedVertices H

o8 = {d}

o8 : List

i9 : connectedComponents H

o9 = {{a, b}, {c}}

o9 : List

i10 : numConnectedComponents H

o10 = 2