HORIZON HASKELLDocslts/ghc-9.14.xd82dee82026-10-12Search names, modules, packages, or :: a typeCtrl K

GHC 9.14.1 · lts/ghc-9.14.x · d82dee8 · 2026-10-12

Modulealgebraic-graphs-0.8Haskell2010

Algebra.Graph.Bipartite.AdjacencyMap.Algorithm

Alga is a library for algebraic construction and manipulation of graphs in Haskell. See this paper for the motivation behind the library, the underlying theory, and implementation details.

This module provides several basic algorithms on undirected bipartite graphs.

  • 4 types
  • 15 values

Bipartiteness test

2 declarations
typetype OddCycle a = [a]
#

A cycle of odd length. For example, [1,2,3] represents the cycle 1 -> 2 -> 3 -> 1.

valuedetectParts
  1. :: Ord a
  2. => AdjacencyMap a
  3. -> Either (OddCycle a) (AdjacencyMap a a)
#

Test the bipartiteness of a given Algebra.Graph.AdjacencyMap. In case of success, return an AdjacencyMap with the same set of edges and each vertex marked with the part it belongs to. In case of failure, return any cycle of odd length in the graph.

The returned partition is lexicographically smallest, assuming that vertices of the left part precede all the vertices of the right part.

The returned cycle is optimal in the following sense: there exists a path that is either empty or ends in a vertex adjacent to the first vertex in the cycle, such that all vertices in path ++ cycle are distinct and path ++ cycle is lexicographically smallest among all such pairs of paths and cycles.

Note: since AdjacencyMap represents undirected bipartite graphs, all edges in the input graph are treated as undirected. See the examples and the correctness property for a clarification.

Complexity: O((n + m) * log(n)) time and O(n + m) memory.

detectParts empty                                       == Right empty
detectParts (vertex x)                                  == Right (leftVertex x)
detectParts (edge x x)                                  == Left [x]
detectParts (edge 1 2)                                  == Right (edge 1 2)
detectParts (1 * (2 + 3))                               == Right (edges [(1,2), (1,3)])
detectParts (1 * 2 * 3)                                 == Left [1, 2, 3]
detectParts ((1 + 3) * (2 + 4) + 6 * 5)                 == Right (swap (1 + 3) * (2 + 4) + swap 5 * 6)
detectParts ((1 * 3 * 4) + 2 * (1 + 2))                 == Left [2]
detectParts (clique [1..10])                            == Left [1, 2, 3]
detectParts (circuit [1..10])                           == Right (circuit [(x, x + 1) | x <- [1,3,5,7,9]])
detectParts (circuit [1..11])                           == Left [1..11]
detectParts (biclique [] xs)                            == Right (vertices xs [])
detectParts (biclique (map Left (x:xs)) (map Right ys)) == Right (biclique (map Left (x:xs)) (map Right ys))
isRight (detectParts (star x ys))                       == notElem x ys
isRight (detectParts (fromBipartite (toBipartite x)))   == True

The correctness of detectParts can be expressed by the following property:

let undirected = symmetricClosure input in
case detectParts input of
    Left cycle -> mod (length cycle) 2 == 1 && isSubgraphOf (circuit cycle) undirected
    Right result -> gmap fromEither (fromBipartite result) == undirected

Matchings

7 declarations
datadata Matching a b
#

A matching is a set of pairwise non-adjacent edges between the two parts of a bipartite graph.

The Show instance is defined using the matching function, with the edges listed in the ascending order of left vertices.

show (matching [])                 == "matching []"
show (matching [(2,'a'), (1,'b')]) == "matching [(1,'b'),(2,'a')]"
Instances5Eq, Ord, Show, Generic, Rep
valuepairOfLeft :: Matching a b -> Map a b
#

The map of vertices covered by the matching in the left part to their neighbours in the right part. Complexity: O(1) time.

pairOfLeft (matching [])                 == Map.empty
pairOfLeft (matching [(2,'a'), (1,'b')]) == Map.fromList [(1,'b'), (2,'a')]
Map.size . pairOfLeft                    == Map.size . pairOfRight
valuepairOfRight :: Matching a b -> Map b a
#

The map of vertices covered by the matching in the right part to their neighbours in the left part. Complexity: O(1).

pairOfRight (matching [])                 == Map.empty
pairOfRight (matching [(2,'a'), (1,'b')]) == Map.fromList [('a',2), ('b',1)]
Map.size . pairOfRight                    == Map.size . pairOfLeft
valuematching :: (Ord a, Ord b) => [(a, b)] -> Matching a b
#

Construct a Matching from a list of edges. Complexity: O(L * log(L)) time, where L is the length of the given list.

Edges that appear closer to the end of the list supersede all previous edges. That is, if two edges from the list share a vertex, the one that appears closer to the beginning is ignored.

pairOfLeft  (matching [])                     == Map.empty
pairOfRight (matching [])                     == Map.empty
pairOfLeft  (matching [(2,'a'), (1,'b')])     == Map.fromList [(2,'a'), (1,'b')]
pairOfLeft  (matching [(1,'a'), (1,'b')])     == Map.singleton 1 'b'
matching [(1,'a'), (1,'b'), (2,'b'), (2,'a')] == matching [(2,'a')]
valuemaxMatching :: (Ord a, Ord b) => AdjacencyMap a b -> Matching a b
#

Find a maximum matching in a bipartite graph. A matching is maximum if it has the largest possible size. Complexity: O(m * sqrt(n) * log(n)) time.

maxMatching empty                                          == matching []
maxMatching (vertices xs ys)                               == matching []
maxMatching (path [1,2,3,4])                               == matching [(1,2), (3,4)]
matchingSize (maxMatching (circuit [(1,2), (3,4), (5,6)])) == 3
matchingSize (maxMatching (star x (y:ys)))                 == 1
matchingSize (maxMatching (biclique xs ys))                == min (length (nub xs)) (length (nub ys))
isMatchingOf (maxMatching x) x                             == True

Vertex covers

4 declarations
typetype VertexCover a b = (Set a, Set b)
#

A vertex cover of a bipartite graph.

A vertex cover is a subset of vertices such that every edge is incident to some vertex in the subset. We represent vertex covers by storing two sets of vertices, one for each part. An equivalent representation, which is slightly less memory efficient, is Set (Either a b).

valueisVertexCoverOf
  1. :: (Ord a, Ord b)
  2. => (Set a, Set b)
  3. -> AdjacencyMap a b
  4. -> Bool
#

Check if a given pair of sets is a vertex cover of a bipartite graph. Complexity: O(m * log(n)).

isVertexCoverOf (xs             , ys             ) empty          == Set.null xs && Set.null ys
isVertexCoverOf (xs             , ys             ) (leftVertex x) == Set.isSubsetOf xs (Set.singleton x) && Set.null ys
isVertexCoverOf (Set.empty      , Set.empty      ) (edge x y)     == False
isVertexCoverOf (Set.singleton x, ys             ) (edge x y)     == Set.isSubsetOf ys (Set.singleton y)
isVertexCoverOf (xs             , Set.singleton y) (edge x y)     == Set.isSubsetOf xs (Set.singleton x)
valueminVertexCover :: (Ord a, Ord b) => AdjacencyMap a b -> VertexCover a b
#

Find a minimum vertex cover in a bipartite graph. A vertex cover is minimum if it has the smallest possible size. Complexity: O(m * sqrt(n) * log(n)).

minVertexCover empty                              == (Set.empty, Set.empty)
minVertexCover (vertices xs ys)                   == (Set.empty, Set.empty)
minVertexCover (path [1,2,3])                     == (Set.empty, Set.singleton 2)
minVertexCover (star x (1:2:ys))                  == (Set.singleton x, Set.empty)
vertexCoverSize (minVertexCover (biclique xs ys)) == min (length (nub xs)) (length (nub ys))
vertexCoverSize . minVertexCover                  == matchingSize . maxMatching
isVertexCoverOf (minVertexCover x) x              == True

Independent sets

4 declarations
typetype IndependentSet a b = (Set a, Set b)
#

An independent set of a bipartite graph.

An independent set is a subset of vertices such that no two of them are adjacent. We represent independent sets by storing two sets of vertices, one for each part. An equivalent representation, which is slightly less memory efficient, is Set (Either a b).

valueisIndependentSetOf
  1. :: (Ord a, Ord b)
  2. => (Set a, Set b)
  3. -> AdjacencyMap a b
  4. -> Bool
#

Check if a given pair of sets is an independent set of a bipartite graph. Complexity: O(m * log(n)).

isIndependentSetOf (xs             , ys             ) empty          == Set.null xs && Set.null ys
isIndependentSetOf (xs             , ys             ) (leftVertex x) == Set.isSubsetOf xs (Set.singleton x) && Set.null ys
isIndependentSetOf (Set.empty      , Set.empty      ) (edge x y)     == True
isIndependentSetOf (Set.singleton x, ys             ) (edge x y)     == Set.null ys
isIndependentSetOf (xs             , Set.singleton y) (edge x y)     == Set.null xs
valuemaxIndependentSet
  1. :: (Ord a, Ord b)
  2. => AdjacencyMap a b
  3. -> IndependentSet a b
#

Find a maximum independent set in a bipartite graph. An independent set is maximum if it has the largest possible size. Complexity: O(m * sqrt(n) * log(n)).

maxIndependentSet empty                                 == (Set.empty, Set.empty)
maxIndependentSet (vertices xs ys)                      == (Set.fromList xs, Set.fromList ys)
maxIndependentSet (path [1,2,3])                        == (Set.fromList [1,3], Set.empty)
maxIndependentSet (star x (1:2:ys))                     == (Set.empty, Set.fromList (1:2:ys))
independentSetSize (maxIndependentSet (biclique xs ys)) == max (length (nub xs)) (length (nub ys))
independentSetSize (maxIndependentSet x)                == vertexCount x - vertexCoverSize (minVertexCover x)
isIndependentSetOf (maxIndependentSet x) x              == True

Miscellaneous

2 declarations
valueaugmentingPath
  1. :: (Ord a, Ord b)
  2. => Matching a b
  3. -> AdjacencyMap a b
  4. -> Either (VertexCover a b) (List a b)
#

Given a matching in a bipartite graph, find either a vertex cover of the same size or an augmenting path with respect to the matching, thereby demonstrating that the matching is not maximum. Complexity: O((m + n) * log(n)).

An alternating path is a path whose edges belong alternately to the matching and not to the matching. An augmenting path is an alternating path that starts from and ends on the vertices that are not covered by the matching. A matching is maximum if and only if there is no augmenting path with respect to it.

augmentingPath (matching [])      empty            == Left (Set.empty, Set.empty)
augmentingPath (matching [])      (edge 1 2)       == Right [1,2]
augmentingPath (matching [(1,2)]) (path [1,2,3])   == Left (Set.empty, Set.singleton 2)
augmentingPath (matching [(3,2)]) (path [1,2,3,4]) == Right [1,2,3,4]
isLeft (augmentingPath (maxMatching x) x)          == True