Add support for bipartite graphs

[snowleopard]

https://en.wikipedia.org/wiki/Bipartite_graph

Note that Graph (Either a b) with vertices of types a and b allows connecting vertices of the same type, that is, the resulting graph is not bipartite.

One possible approach to this has been discussed in this twitter thread.

[boggle]

I like the idea of modelling bipartite graphs. Not sure how to model partition membership though.

One option is to demand that membership in a partition A or B should be deducible from the vertex label. Perhaps this could be modeled using type A g, type B g, partition :: Vertex g => Either (A g) (B g), via a boolean predicate, or just kept hidden in the type class implementation.

Alternatively, we could also introduce new primitives for controlling partition membership, like left :: g -> Vertex g -> g (and right resp) that would remove conflicting edges.

[snowleopard]

Not sure how to model partition membership though.

@boggle Oops. Somehow I didn't realise we need to do this.

Indeed, if we'd like to abstract over bipartite graphs and, for example, have a generic algorithm for bipartite matching, then we need to expose the partitions. Seems to be a pretty large design space, again.

[boggle]

I came up with this:

https://github.com/snowleopard/alga/compare/master...boggle:bipartite?expand=1

Observations:

• Tying partition membership to the vertex label type ensures all graphs use the same idea about which vertex belongs where
• It's necessary to get the list of vertices per partition, only way to do that without adding additional datastructures is via toGraph and foldg while elegant that felt somewhat painful
• This could also be done without additional (left/right) graphs at the expense of extracting partition vertices via foldg

[snowleopard]

@boggle Thanks for the experiment!

It looks like some of the complications in the code are due to the fact that you make sure that no edges are created inside partitions. However, we don't necessarily need to do that, because the law says it's OK to have edges inside a partition -- they don't matter and can later be removed.

For example, consider expressions 1 * 2 * a * b and (1 + 2) * (a + b), with A = {1,2} and B = {a,b}. According to the law u + v = u * v for all u,v \in A or u,v \in B, these two expressions are equivalent and describe the same bipartite graph. Your current implementation seems to make effort to only allow the latter representation, but I think it's unnecessary. Let's allow both representations to co-exist, but create a custom Eq instance so that 1 * 2 * a * b == (1 + 2) * (a + b). The same is done with undirected graphs, where 1 * 2 and 2 * 1 have different representations but are treated as equal graphs. (And, in fact, with directed graphs too, where 1 + 1 == 1.)

We can of course allow the user to obtain a canonical representation of a bipartite graph, by providing a function like edgeList :: BipartiteGraph a b -> [(a, b)] or similar.

One aspect which is unclear to me is how to properly define the Bipartite type class.

{-|
The class of /bipartite graphs/ that splits vertices into two partitions A and B
and satisfies the following axiom

  * u + v = u * v for all u,v \in A or u,v \in B
-}
class Graph g => Bipartite g

It feels awkward that the law refers to non-existing notions A and B, yet adding type A g and type B g into the signature is awkward too, because there is some redundancy in the presence of Vertex g.

We could add a predicate, e.g. partition :: Vertex g -> Bool or even a more sophisticated version using a custom data type data Partition = A | B and partition :: Vertex g -> Partition, but this doesn't allow writing type-safe functions like edgeList :: BipartiteGraph a b -> [(a, b)] where the compiler checks that we cannot accidentally mix the partitions. So, I think it would be best to have a type-level distinction between the vertices in the partition, such as with g ~ Either a b, but I'm not yet sure how to express this in the type class definition.

[boggle]

Agreed, we shouldn't rule out any valid algebraic description of a bipartite graph.

However what is the end goal for alga? Right now it seems to be focused primarily on being able to construct graphs using the algebra in a way that allows using different representations. I would expect that mid to long term actual operations on graphs that extract data (triangle counts, connected components, ...) would be considered very useful. One would probably not want to implement those again for different classes of graphs (bipartite, undirected) if possible and rather implement them by e.g. transforming a bipartite graph to a regular graph without intra-partition edges. One way of achieving this is by going via an edge list, although this feels unnecessarily sequential. In the experiment, I was trying to instead construct such a graph inside Bigraph for any underlying Graph g representation for easy extraction and use by a later algorithm - though that perhaps fixes the representation too early and a better route would be to just record operations (like the standard graph implementation does) and then use a specialized form of toGraph to construct a regular graph from that. Not sure what the right design approach is here but I would expect us to find more cases where a specialized class of graphs (like Bipartite) is to be translated to a regular graph using an arbitrary representation.

On the topic of representing partitions, I see only two viable options:

• A typeclass like Choose a which allows to distinguish between vertices
• Adding another primitive covertex a and leaving the details to graph representations

I think using predicates a -> Bool isn't great because they would not be tied to the type a and therefore two Bipartite a could be constructed using different predicates!

Also, only providing instances like Bipartite (Either a b) is limiting, it would rule out alot of other interesting ways of partitioning vertices implicitly (e.g. Ints by their sign, or some boolean field in a record etc).

[snowleopard]

However what is the end goal for alga? Right now it seems to be focused primarily on being able to construct graphs using the algebra in a way that allows using different representations.

@boggle Indeed, at the moment Alga is not very useful. It can construct various graphs, but the rest of the functionality is poor and can be split into two categories:

• Simple algorithms operating on the core graph language, such as induce, removeEdge, hasEdge.
• A couple of standard graph algorithms operating on edge lists, such as dfs, scc, topSort, export.

I would expect that mid to long term actual operations on graphs that extract data (triangle counts, connected components, ...) would be considered very useful.

Yes, of course! However, most interesting algorithms (even as simple as triangle counts) are non-trivial to implement directly in the algebraic graph representation. I'm working on several algorithms at the moment, starting with very basic ones such as dfs and there is a lot of exciting work ahead, but if the goal is to start providing useful functionality today, then I don't see a better approach than to use standard algorithms via a translation layer (using the representation that is the best match for a particular algorithm -- it could be an edge list for connected components or a matrix for triangle counts). This is what I did with bfs, scc and topSort and it seems to be pretty convenient to use. It could be best to provide these functions from the top-level module Algebra.Graph doing the necessary conversion to AdjacencyMap so that the user doesn't have to think about which representation to choose.

Note that most algorithms are also very sensitive to the actual graph and to get the best performance you actually need to write different algorithms for general graphs and for bipartite graphs. As a representative example, consider the matching problem -- it's relatively easy for unweighted bipartite graphs, but becomes much harder for general graphs and/or for weighted graphs. Alas, we can't hope to reuse any code here.

One way of achieving this is by going via an edge list, although this feels unnecessarily sequential. In the experiment, I was trying to instead construct such a graph inside Bigraph for any underlying Graph g representation for easy extraction and use by a later algorithm

Can you give a specific example of an algorithm you'd like to run on bipartite graphs? Let's see if we can find a way to reuse some code for general and for bipartite graphs for a specific example -- perhaps this could help us figure out the best design.

[nobrakal]

After reading the discussion, one thing is not clear: Do we need/want to express vertices types in the type of a Bipartite graph ?

• For the yes answer, it allows to write type-safe functions like edgeList :: Bipartite a b -> [(a, b)], which seems great for matching problem, where the two partitions are very different (like a set of men and a set of women)
• On the other hand, many graphs are bipartite, like path n, or as @boggle said, someone can want to split values without distinguish their types.

I personally prefer the first option, because I think type-safe functions are very important, and it will allows a very clean syntax (like leftPart :: Bipartite a b = [a]). The problem of distinguishing positive integer from negative ones seems more like a problem of dependents types and I don't think workarounds like Choose a or using predicates will simplify things.

Can you give a specific example of an algorithm you'd like to run on bipartite graphs?

About the matching problem on unweighted graphs, there is the Hopcroft–Karp algorithm which provide the maximum matching in a bipartite graph.

There are much simpler/common ones like the Hungarian Algorithm but there are for edge labeled graphs, so maybe not for now in alga.

[snowleopard]

@nobrakal I also prefer the typed variant.

If we summarise the discussions so far, we can have something like:

{-|
The class of /bipartite graphs/ whose vertices are partitioned into two parts L (left)
and R (right), such that there are no edges within parts. Bipartite graphs satisfy the
following axiom:

  * u + v = u * v for all u,v \in L or u,v \in R
-}
class Graph g => Bipartite g
    type LeftPart g 
    type RightPart g
    partition :: Vertex g -> Either (LeftPart g) (RightPart g)

but there are for edge labelled graphs, so maybe not for now in alga.

We will have labelled graphs soon! :-)

[snowleopard]

I think we can close this issue. We don't have an algebraic implementation yet but Algebra.Graph.Bipartite.AdjacencyMap and Algebra.Graph.Bipartite.AdjacencyMap.Algorithm are a good start.