Bipartite graph algorithms
Bipartiteness check, 2-coloring, maximum matching (Hopcroft-Karp).
Procs
proc bipartiteClustering[N](g: Graph[N]): Table[N, float]
- Compute the bipartite clustering coefficient for each node. CC(v) = number of 4-cycles through v / (deg(v) * (deg(v)-1) / 2)
proc bipartiteProjection[N](g: Graph[N]; nodes: HashSet[N]): Graph[N]
- Project a bipartite graph onto one set of nodes. Two nodes in the projection are connected if they share a neighbor in the other partition.
proc bipartiteRedundancy[N](g: Graph[N]): Table[N, float]
- Compute the redundancy coefficient for each node. RC(v) = fraction of neighbor pairs that share more than one neighbor.
proc bipartiteSets[N](g: Graph[N]): (HashSet[N], HashSet[N])
- Return the two partitions of a bipartite graph. Raises NimNetError if the graph is not bipartite.
proc bipartiteWeightedProjection[N](g: Graph[N]; nodes: HashSet[N]): Graph[N]
- Project with weights equal to number of shared neighbors.
proc isBipartite[N](g: Graph[N]): bool
- Check if the graph is bipartite using 2-coloring BFS.
proc maximumMatching[N](g: Graph[N]): seq[(N, N)]
- Return an exact maximum-cardinality bipartite matching using layered Hopcroft-Karp, with indexed data and iterative, stack-safe augmentation. Time is O((V + E) sqrt(V)); auxiliary space is O(V + E). Each matched edge occurs once, oriented from an inferred first partition. Disconnected components and isolates are supported; weights are ignored. Raises NimNetError for odd cycles or self-loops.
proc maximumMatching[N](g: Graph[N]; topNodes: HashSet[N]): seq[(N, N)]
- Return an exact maximum-cardinality matching using the supplied partition. Each pair is (node in topNodes, node outside topNodes), occurring once. topNodes and its complement must cover the two sides of every edge; disconnected components may be oriented independently and isolates may be on either side. The partition is validated once, without inference. Raises NodeNotFound for unknown topNodes and NimNetError for intra-part edges (including self-loops). No node ordering is required. Uses stack-safe Hopcroft-Karp in O((V + E) sqrt(V)) time, O(V + E) space.
proc minimumVertexCover[N](g: Graph[N]): HashSet[N]
- Return an exact minimum vertex cover of a bipartite graph. By König's theorem its size equals the maximum matching cardinality. Infers and validates the partition once, reusing indexed Hopcroft-Karp data. Disconnected graphs and isolates are supported. Raises NimNetError for odd cycles or self-loops. Time is O((V + E) sqrt(V)); auxiliary space is O(V + E).
proc minimumVertexCover[N](g: Graph[N]; topNodes: HashSet[N]): HashSet[N]
- Return an exact minimum vertex cover using the supplied bipartition. Partition rules and exceptions are the same as for maximumMatching(g, topNodes). Validation occurs once, with no hidden inference. Isolates are never needed in the cover. Time is O((V + E) sqrt(V)); auxiliary space is O(V + E).