Bipartite graphs

This page is for discussing and tracking the ongoing development of support for undirected bipartite graphs.

Requirements

For now, we are only implementing adjacency maps for bipartite graphs. We are going to define it in the module Algebra.Graph.Bipartite.AdjacencyMap (henceforth Bipartite.AdjacencyMap).

Here is a suggested definition for the AdjacencyMap

module Algebra.Graph.Bipartite.AdjacencyMap where

data AdjacencyMap a b = BAM { leftToRight :: Map a (Set b), rightToLeft :: Map b (Set a) }

The consistency check would have the following signature:

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

This function should check that there is an edge x → y in leftToRight if and only if there is an edge y → x in rightToLeft.

There should also be a construction function provided

import qualified Algebra.Graph.Graph as G
import qualified Algebra.Graph.AdjacencyMap as AM

fromGraph :: (Ord a, Ord b) => G.Graph (Either a b) -> AdjacencyMap a b

As we want to apply the existing algorithms, we might want to implement the inverse function

toAdjacencyMap :: (Ord a, Ord b) => AdjacencyMap a b -> AM.AdjacencyMap (Either a b)

Discussion

Another option is to define the Bipartite.AdjacencyMap as below:

newtype AdjacencyMap a b = BAM { bam :: AM.AdjacencyMap (Either a b) }

So that we can just do the following:

toAdjacencyMap :: (Ord a, Ord b) => AdjacencyMap a b -> AM.AdjacencyMap (Either a b)
toAdjacencyMap = bam

Though this approach simplifies (and maybe optimizes) reusing existing algorithms, I find it rather unnatural. Another point is that it is not type-safe, though it is an internal data type and we can control the safety with proper testing.

Vasily: Personally, I don't find the optimization very useful. One needs to have a Graph to construct a Bipartite.AdjacencyMap and we have only a linear space overhead (and, maybe, n log n time overhead, I am not sure about time guarantees of maps in Haskell) for more reliability.

Andrey: I agree with the above. Another point in favour of the implementation with two maps is performance: I'm pretty sure some algorithms on bipartite graphs will need fast access to the list of edges adjacent to a right vertex.

Tasks

Conversions (in review)

We might need the following conversion functions:

import qualified Algebra.Graph.Graph as G
import qualified Algebra.Graph.AdjacencyMap as AM

-- Ignores the edges between left and right vertices
fromGraph :: (Ord a, Ord b) => G.Graph (Either a b) -> AdjacencyMap a b

-- Ignores the edges between left and right vertices
fromAdjacencyMap :: (Ord a, Ord b) => AM.AdjacencyMap (Either a b) -> AdjacencyMap a b

toAdjacencyMap :: (Ord a, Ord b) => AdjacencyMap a b -> AM.AdjacencyMap (Either a b)

Checking graph for being bipartite (in progress)

Andrey: There is an interesting algorithm lurking somewhere here, which would detect whether a graph is actually bipartite and will split it in parts. Something like this:

detectParts :: AM.AdjacencyMap a -> Maybe (Bipartite.AdjacencyMap a a)

Vasily: This is the part in which I was not very accurate. Indeed, I meant exactly this. I also thought that one may need some proof for the graph being not bipartite to return Either ProofType (Bipartite.AdjacencyMap a a). The only one I can think of right now is returning an odd cycle, but it looks like it's too complicated and no one will ever need it.

Alga-style construction primitives (in review)

Why don't we make it a Graph.Class.Graph instance?

import qualified Algebra.Graph.Class as GC

instance (Ord a, Ord b) => GC.Graph (AdjacencyMap a b) where
    type Vertex (AdjacencyMap a b) = Either a b
    -- empty :: AdjacencyMap a b
    empty = undefined
    -- vertex :: Either a b -> AdjacencyMap a b
    vertex = undefined
    -- overlay :: AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b
    overlay = undefined
    -- connect :: AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b
    connect = undefined

Of course, connect connects only proper pairs of vertices.

ToGraph instance for Bipartite.AdjacencyMap

Though minimal ToGraph instance only needs toGraph or foldg functions to be implemented, many other functions in this instance might be optimized for Bipartite.AdjacencyMap. This task is to detect these functions and implement them.

Note: This is a large task and it should probably be split into subtasks before implementation.