New type of pattern: bipartite subgraphs

[fedarko]

Thought I'd made an issue for this elsewhere, but apparently not.

A common thing I've noticed in metagenomes (and that has come up in the past as an example of something neat that MetagenomeScope is good for detecting) is nodes that form a "bipartite" graph. Bipartite graphs are mostly defined for undirected graphs (although apparently there's some prior work on directed bipartite graphs), but we can generalize them to directed assembly graphs with the following definition that I made up just now:

An arbitrary subgraph G' = (V', E') of a directed graph G = (V, E) is locally bipartite if V' can be partitioned into two sets of nodes, S1 and S2, such that:

• All nodes in S1 have at least one outgoing edge to a node in S2
• All nodes in S1 do not have outgoing edges to any nodes outside of S2
• All nodes in S2 have at least one incoming edge from a node in S1
• All nodes in S2 do not have incoming edges from any nodes outside of S1

This definition might have some holes in it, but it gets the point across.

If we can handle #202 (allowing patterns with multiple start / end nodes), then we can support these sorts of patterns. Highlighting these could actually be really useful!

I'm not sure what the complexity of detecting these patterns will be, but it probably won't be too bad (I imagine we can come up with some heuristics to pretty quickly disqualify most nodes not in these patterns).

[fedarko]

An additional use case for identifying these sorts of patterns: for all the edges located within a bipartite pattern (i.e. between two nodes that are located in the same bipartite pattern), ignore Graphviz' coordinates and just represent them as a basic line (IIRC, a basicbezier, as described in the code right now?). This way, we knock out probably the biggest contributors to the occlusion issue described in #127.