Bipartite (yog-fsharp)

Bipartite Module

Namespace: Yog.Properties
Assembly: Yog.FSharp.dll

Bipartite graph analysis and matching algorithms.

A graph is bipartite (2-colorable) if its vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. Equivalently, a bipartite graph contains no odd-length cycles.

Algorithms

Problem	Algorithm	Function	Complexity
Bipartite check	BFS 2-coloring	isBipartite, partition	O(V + E)
Maximum matching	Augmenting paths	maximumMatching	O(VE)
Stable matching	Gale-Shapley	stableMarriage	O(V²)

Use Cases

Job assignment: Workers to tasks they can perform
Scheduling: Time slots to events without conflicts
Recommendation systems: Users to items they might like
Stable marriage: Matching medical residents to hospitals

Types

Type	Description
Partition	Represents a partition of a bipartite graph into two independent sets.
StableMarriage

Functions and values

Function or value	Description
`getPartner person marriage` Full Usage: `getPartner person marriage` Parameters: person : `NodeId` marriage : `StableMarriage` Returns: `NodeId option`	person : `NodeId` marriage : `StableMarriage` Returns: `NodeId option`
`isBipartite graph` Full Usage: `isBipartite graph` Parameters: graph : `Graph<'n, 'e>` Returns: `bool`	Checks if a graph is bipartite (2-colorable). graph : `Graph<'n, 'e>` Returns: `bool`
`maximumMatching partition graph` Full Usage: `maximumMatching partition graph` Parameters: partition : `Partition` graph : `Graph<'n, 'e>` Returns: `(NodeId * NodeId) list`	Finds a maximum matching in a bipartite graph. partition : `Partition` graph : `Graph<'n, 'e>` Returns: `(NodeId * NodeId) list`
`partition graph` Full Usage: `partition graph` Parameters: graph : `Graph<'n, 'e>` Returns: `Partition option`	Returns the two partitions of a bipartite graph, or None if the graph is not bipartite. graph : `Graph<'n, 'e>` Returns: `Partition option`
`stableMarriage leftPrefs rightPrefs` Full Usage: `stableMarriage leftPrefs rightPrefs` Parameters: leftPrefs : `Map<NodeId, NodeId list>` rightPrefs : `Map<NodeId, NodeId list>` Returns: `StableMarriage`	Finds a stable matching using the Gale-Shapley algorithm. leftPrefs : `Map<NodeId, NodeId list>` rightPrefs : `Map<NodeId, NodeId list>` Returns: `StableMarriage`