yog - v1.2.3

yog/bipartite

Types

Partition

</>

Represents a partition of a bipartite graph into two independent sets. In a bipartite graph, all edges connect vertices from left to right, with no edges within left or within right.

pub type Partition {
  Partition(left: set.Set(Int), right: set.Set(Int))
}

Constructors

Values

is_bipartite

</> 
pub fn is_bipartite(graph: model.Graph(n, e)) -> Bool

Checks if a graph is bipartite (2-colorable).

A graph is bipartite 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.

Example

let graph =
  yog.undirected()
  |> yog.add_node(1, Nil)
  |> yog.add_node(2, Nil)
  |> yog.add_node(3, Nil)
  |> yog.add_node(4, Nil)
  |> yog.add_edge(from: 1, to: 2, with: 1)
  |> yog.add_edge(from: 2, to: 3, with: 1)
  |> yog.add_edge(from: 3, to: 4, with: 1)

bipartite.is_bipartite(graph)  // => True (can color as: 1,3 vs 2,4)

Time Complexity: O(V + E)

maximum_matching

</> 
pub fn maximum_matching(
  graph: model.Graph(n, e),
  partition: Partition,
) -> List(#(Int, Int))

Finds a maximum matching in a bipartite graph.

A matching is a set of edges with no common vertices. A maximum matching has the largest possible number of edges.

Uses the augmenting path algorithm (also known as the Hungarian algorithm for unweighted bipartite matching).

Returns a list of matched pairs #(left_node, right_node).

Example

let graph =
  yog.undirected()
  |> yog.add_node(1, Nil)  // left
  |> yog.add_node(2, Nil)  // left
  |> yog.add_node(3, Nil)  // right
  |> yog.add_node(4, Nil)  // right
  |> yog.add_edge(from: 1, to: 3, with: 1)
  |> yog.add_edge(from: 1, to: 4, with: 1)
  |> yog.add_edge(from: 2, to: 3, with: 1)

case bipartite.partition(graph) {
  Some(p) -> {
    let matching = bipartite.maximum_matching(graph, p)
    // => [#(1, 3), #(2, 4)] or [#(1, 4), #(2, 3)]
  }
  None -> panic as "Not bipartite"
}

Time Complexity: O(V * E)

partition

</> 
pub fn partition(
  graph: model.Graph(n, e),
) -> option.Option(Partition)

Returns the two partitions of a bipartite graph, or None if the graph is not bipartite.

Uses BFS with 2-coloring to detect bipartiteness and construct the partitions. Handles disconnected graphs by checking all components.

Example

case bipartite.partition(graph) {
  Some(Partition(left, right)) -> {
    // left and right are the two independent sets
    io.println("Graph is bipartite!")
  }
  None -> io.println("Graph is not bipartite")
}

Time Complexity: O(V + E)

✨ Search Document