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.

Bipartiteness test

type OddCycle a = [a]

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

detectParts :: Ord a => AdjacencyMap a -> 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

data 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')]"

Instances

(Eq a, Eq b) => Eq (Matching a b)

Defined in Algebra.Graph.Bipartite.AdjacencyMap.Algorithm

Methods

(==) :: Matching a b -> Matching a b -> Bool

(/=) :: Matching a b -> Matching a b -> Bool

(Ord a, Ord b) => Ord (Matching a b)

Defined in Algebra.Graph.Bipartite.AdjacencyMap.Algorithm

Methods

compare :: Matching a b -> Matching a b -> Ordering

(<) :: Matching a b -> Matching a b -> Bool

(<=) :: Matching a b -> Matching a b -> Bool

(>) :: Matching a b -> Matching a b -> Bool

(>=) :: Matching a b -> Matching a b -> Bool

max :: Matching a b -> Matching a b -> Matching a b

min :: Matching a b -> Matching a b -> Matching a b

(Show a, Show b) => Show (Matching a b)

Defined in Algebra.Graph.Bipartite.AdjacencyMap.Algorithm

Methods

showsPrec :: Int -> Matching a b -> ShowS

show :: Matching a b -> String

showList :: [Matching a b] -> ShowS

Generic (Matching a b)

Defined in Algebra.Graph.Bipartite.AdjacencyMap.Algorithm

Associated Types

type Rep (Matching a b) :: Type -> Type

Methods

from :: Matching a b -> Rep (Matching a b) x

to :: Rep (Matching a b) x -> Matching a b

type Rep (Matching a b)

Defined in Algebra.Graph.Bipartite.AdjacencyMap.Algorithm

type Rep (Matching a b) = D1 ('MetaData "Matching" "Algebra.Graph.Bipartite.AdjacencyMap.Algorithm" "algebraic-graphs-0.6-31pq0b3ITnUItSsb9kEuq8" 'False) (C1 ('MetaCons "Matching" 'PrefixI 'True) (S1 ('MetaSel ('Just "pairOfLeft") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Map a b)) :*: S1 ('MetaSel ('Just "pairOfRight") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Map b a))))

pairOfLeft :: 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

pairOfRight :: 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

matching :: (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')]

isMatchingOf :: (Ord a, Ord b) => Matching a b -> AdjacencyMap a b -> Bool

Check if a given Matching is a valid matching of a bipartite graph. Complexity: O(S * log(n)), where S is the size of the matching.

isMatchingOf (matching []) x               == True
isMatchingOf (matching xs) empty           == null xs
isMatchingOf (matching [(x,y)]) (edge x y) == True
isMatchingOf (matching [(1,2)]) (edge 2 1) == False

matchingSize :: Matching a b -> Int

The number of edges in a matching. Complexity: O(1) time.

matchingSize (matching [])                 == 0
matchingSize (matching [(2,'a'), (1,'b')]) == 2
matchingSize (matching [(1,'a'), (1,'b')]) == 1
matchingSize (matching xs)                 <= length xs
matchingSize                               == Map.size . pairOfLeft

maxMatching :: (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

type 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).

isVertexCoverOf :: (Ord a, Ord b) => (Set a, Set b) -> AdjacencyMap a b -> 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)

vertexCoverSize :: VertexCover a b -> Int

The number of vertices in a vertex cover. Complexity: O(1) time.

minVertexCover :: (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

type 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).

isIndependentSetOf :: (Ord a, Ord b) => (Set a, Set b) -> AdjacencyMap a b -> 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

independentSetSize :: IndependentSet a b -> Int

The number of vertices in an independent set. Complexity: O(1) time.

maxIndependentSet :: (Ord a, Ord b) => AdjacencyMap a b -> 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

augmentingPath :: (Ord a, Ord b) => Matching a b -> AdjacencyMap a b -> 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

consistentMatching :: (Ord a, Ord b) => Matching a b -> Bool

Check if the internal representation of a matching is consistent, i.e. that every edge that is present in pairOfLeft is also present in pairOfRight. Complexity: O(S * log(S)), where S is the size of the matching.

consistentMatching (matching xs)   == True
consistentMatching (maxMatching x) == True