Re: [jgrapht-developers] Feedback on BipartiteGraph implementation

[John V. S. <js...@gm...>]

Lucas Scharenbroich wrote:
> All,
> 
> Please find an implementation of a BipartiteGraph attached.  I've seen 
> this requested a few times in the archives and, since I need it myself 
> to build upon, I thought I'd post the implementation for feedback and 
> comments.

Hi Lucas,

Sorry for the very slow response (been busy at work)...below are some 
review comments from me.

> 1) I implemented BipartiteGraph as a GraphDelegator.  This seemed to be 
> the path of least resistance.  Is there a better place in the class 
> hierarchy to put this?

The alternative would be to implement it as a constraining mask on an 
underlying listenable graph.  The constraining part involves adding a 
listener to prevent the bipartite condition from being violated on edge 
addition.

The listener approach has the advantage of decoupling the bipartite 
aspect from other structural aspects of the graph.  It also helps make 
sure the mask stays in sync with the underlying graph.

The problem is that currently the listener framework does not support 
constraints; i.e. a listener cannot cleanly veto a change.  (It can veto 
it uncleanly by throwing a RuntimeException, leaving the graph in 
violation of the constraint; there are other issues such as atomicity 
for methods like removeAllEdges.)

So, if we wanted to do it this way, we would need to implement 
constraints generically first, and then this would be the first usage.

If not, the GraphDelegator approach seems fine; we could always retrofit 
later for constraints.

> 2) I track the membership of vertices to partitions by keeping a private 
> Map.  This is potentially inefficient since Vertex object references are 
> duplicated.  I can't come up with a more space-efficient approach at the 
> moment and this was "good enough" for a first implementation.

Fine with me.  The partition vertex sets are also useful for 
constructing subgraph views.

The map approach can also be generalized to k-partite graphs later; this 
also requires generalizing the notion of partition identifier beyond a 
fixed enum.

> 3) The traversal in the constructor to build a bipartite graph from the 
> input graph is a bit messy.  Is a TraversalListener the best way to do this?
> Most of the method are self-explanatory -- I just added checks to ensure 
> that the bipartite property holds after each method.  I also added 
> additional methods for adding vertices to specific partitions and 
> getting the set of partition vertices.  I have junit tests for this code 
> that I have not posted yet.

I don't know of anything simpler than the traversal listener.  But there 
is one small tweak needed for directed graphs.  For the example in your 
Javadoc, if you start with v3, you might put v4 in the same partition, 
since it will be seen before traversing e3; then you'll get an error 
when e3 is traversed.  The tweak is to wrap g using 
Graphs.undirectedGraph and give that to the DFS so that it will ignore 
edge direction.

One question:  why is the behavior for addEdge(V,V) and addEdge(V,V,E) 
different?  Seems like both should complain about constraint violations.

> Obviously, there is quite a bit more documentation to write before it's 
> in sufficient shape for submission, but I thought it would be good to 
> get some feedback.

Send me the final version along with unit tests, and I'll commit to 
Subversion.

JVS