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)]
- Find a maximum matching using augmenting paths. Returns a list of matched edge pairs. Requires the graph to be bipartite.
proc minimumVertexCover[N](g: Graph[N]): HashSet[N]
- Find minimum vertex cover for bipartite graph using König's theorem.|minimum vertex cover| = |maximum matching|