Copyright | (c) Andrey Mokhov 2016-2022 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
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.
Synopsis
- type OddCycle a = [a]
- detectParts :: Ord a => AdjacencyMap a -> Either (OddCycle a) (AdjacencyMap a a)
- data Matching a b
- pairOfLeft :: Matching a b -> Map a b
- pairOfRight :: Matching a b -> Map b a
- matching :: (Ord a, Ord b) => [(a, b)] -> Matching a b
- isMatchingOf :: (Ord a, Ord b) => Matching a b -> AdjacencyMap a b -> Bool
- matchingSize :: Matching a b -> Int
- maxMatching :: (Ord a, Ord b) => AdjacencyMap a b -> Matching a b
- type VertexCover a b = (Set a, Set b)
- isVertexCoverOf :: (Ord a, Ord b) => (Set a, Set b) -> AdjacencyMap a b -> Bool
- vertexCoverSize :: VertexCover a b -> Int
- minVertexCover :: (Ord a, Ord b) => AdjacencyMap a b -> VertexCover a b
- type IndependentSet a b = (Set a, Set b)
- isIndependentSetOf :: (Ord a, Ord b) => (Set a, Set b) -> AdjacencyMap a b -> Bool
- independentSetSize :: IndependentSet a b -> Int
- maxIndependentSet :: (Ord a, Ord b) => AdjacencyMap a b -> IndependentSet a b
- augmentingPath :: (Ord a, Ord b) => Matching a b -> AdjacencyMap a b -> Either (VertexCover a b) (List a b)
- consistentMatching :: (Ord a, Ord b) => Matching a b -> Bool
Bipartiteness test
type OddCycle a = [a] Source #
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) Source #
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.
detectPartsempty
== Rightempty
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 ysisRight
(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
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) Source # | |
(Ord a, Ord b) => Ord (Matching a b) Source # | |
(Show a, Show b) => Show (Matching a b) Source # | |
Generic (Matching a b) Source # | |
type Rep (Matching a b) Source # | |
Defined in Algebra.Graph.Bipartite.AdjacencyMap.Algorithm type Rep (Matching a b) = D1 ('MetaData "Matching" "Algebra.Graph.Bipartite.AdjacencyMap.Algorithm" "algebraic-graphs-0.7-DxCmXygYU3a8wvsz565Q5f" '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 Source #
pairOfRight :: Matching a b -> Map b a Source #
matching :: (Ord a, Ord b) => [(a, b)] -> Matching a b Source #
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 Source #
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 Source #
maxMatching :: (Ord a, Ord b) => AdjacencyMap a b -> Matching a b Source #
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.
maxMatchingempty
==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)])) == 3matchingSize
(maxMatching (star
x (y:ys))) == 1matchingSize
(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) Source #
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 Source #
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 Source #
The number of vertices in a vertex cover. Complexity: O(1) time.
minVertexCover :: (Ord a, Ord b) => AdjacencyMap a b -> VertexCover a b Source #
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)).
minVertexCoverempty
== (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) Source #
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 Source #
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 Source #
The number of vertices in an independent set. Complexity: O(1) time.
maxIndependentSet :: (Ord a, Ord b) => AdjacencyMap a b -> IndependentSet a b Source #
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)).
maxIndependentSetempty
== (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) Source #
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 Source #
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