Screenshot instructions:
Windows
Mac
Red Hat Linux
Ubuntu
Click URL instructions:
Rightclick on ad, choose "Copy Link", then paste here →
(This may not be possible with some types of ads)
From: Lucas Scharenbroich <lscharen@jp...>  20071007 03:13:22
Attachments:
Message as HTML

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. Here are some items I think could be up for debate: 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? 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. 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 selfexplanatory  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. 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. Thank you, Lucas /** * A bipartite delegator enforces the partitioning of the graph vertices into * two disjoint sets. An additional addVertex() method is added which allows * the assignment of vertices to a one partition or the other. The addEdge() * methods are checked and the addition will fail if the bipartite constraints * are violated * * @author Lucas J. Scharenbroich * @since Oct. 5, 2007 */ import java.util.*; import org.jgrapht.*; import org.jgrapht.graph.*; import org.jgrapht.traverse.*; import org.jgrapht.event.*; public class BipartiteGraph<V, E> extends GraphDelegator<V, E> { public enum Partition {V1, V2}; protected final Map<Partition, Set<V>> vertexSetMapping = new EnumMap<Partition, Set<V>>(Partition.class); /** * Constructor for BipartiteGraph. * * @param g the backing graph over which the bipartite topology * is to be constrained */ public BipartiteGraph(final Graph<V, E> g) { super(g); vertexSetMapping.put(Partition.V1, new HashSet<V>()); vertexSetMapping.put(Partition.V2, new HashSet<V>()); // Run through the current set of vertices and edges and // place them arbitrarily is the two classes. This is // really the best we can do with a general graph. If // a bipartite violation is detected, throw an exception // // We can't just iterate over the edgeSet because this can // fail for cases like the following // // e1 e2 e3 // v1 > v2 > v3 < v4 // // If the edges are visited in the order e1, e3, e2, then // we might partition the vertices as ((v1, v4), (v2, v3). // When e2 is encountered, v2 and v3 are in the same set // and the test fails, even though there is a bipartite // paritioning of the vertices, e.g. ((v1, v3), (v2, v4)) GraphIterator<V, E> iterator = new DepthFirstIterator<V, E>(g); iterator.addTraversalListener(new BipartiteListener(g)); while (iterator.hasNext()) { iterator.next(); } } /** * A small, private class to walk a graph and partition it into two classes. */ private final class BipartiteListener extends TraversalListenerAdapter<V, E> { private final Graph<V, E> g; public BipartiteListener(Graph<V, E> g) { this.g = g; } public void edgeTraversed(EdgeTraversalEvent<V, E> e) { V source = g.getEdgeSource(e.getEdge()); V target = g.getEdgeTarget(e.getEdge()); Set<V> V1 = vertexSetMapping.get(Partition.V1); Set<V> V2 = vertexSetMapping.get(Partition.V2); boolean V1source = V1.contains(source); boolean V1target = V1.contains(target); boolean V2source = V2.contains(source); boolean V2target = V2.contains(target); // If both vertices are in either set, throw an exception if ((V1source && V1target)  (V2source && V2target)) { String msg = new StringBuffer() .append( source ) .append(" and ") .append(target) .append( "are in the same parition").toString(); throw new IllegalArgumentException(msg) ; } // Make sure that at least one of the vertices has been seen if (!( V1source  V2source  V1target  V2target)) { String msg = "Free edge encountered in traversal"; throw new IllegalArgumentException(msg); } // If only the source has been seen, assign the target to the other set if (V1source && !(V1target  V2target)) { vertexSetMapping.get(Partition.V2).add(target); } if (V2source && !(V1target  V2target)) { vertexSetMapping.get(Partition.V1).add(target); } // If only the target has been seen, assign the source to the other set if (V1target && !(V1source  V2source)) vertexSetMapping.get(Partition.V2).add(source); if (V2target && !( V1source  V2source)) vertexSetMapping.get(Partition.V1).add(source); } public void vertexTraversed(VertexTraversalEvent<V> e) { V v = e.getVertex(); // If this vertex has not been encountered before, assign it // to the first partition if (!vertexSetMapping.get(Partition.V1).contains(v) && !vertexSetMapping.get(Partition.V2).contains(v)) { vertexSetMapping.get(Partition.V1).add(v); } } } /** * Finds the partition set that the vertex belongs to. Return null if * the vertex does not exist. * * @param v Vertex * @return */ private Partition vertexPartition(V v) { for (Map.Entry<Partition, Set<V>> entry : vertexSetMapping.entrySet()) if (entry.getValue().contains( v )) return entry.getKey(); return null; } /** * Check that the source and target vertices are not in the same partition * before joining them. */ @Override public E addEdge(V sourceVertex, V targetVertex) { if (vertexPartition(sourceVertex).equals(vertexPartition (targetVertex))) { return null; } else { return super.addEdge(sourceVertex, targetVertex); } } @Override public boolean addEdge(V sourceVertex, V targetVertex, E e) { if (vertexPartition(sourceVertex).equals(vertexPartition (targetVertex))) { String msg = "A Bipartite graph cannot join vertices in the same set"; throw new IllegalArgumentException(msg); } return super.addEdge( sourceVertex, targetVertex, e ); } @Override public boolean addVertex(V v) { return addVertex(v, Partition.V1); } public boolean addVertex(V v, Partition partition) { boolean rval = super.addVertex(v); if (rval) { vertexSetMapping.get(partition).add(v); } return rval; } /** * Find a vertex in a given partition * * @param v * @param partition * @return true if the vertex is in the partition */ public boolean containsVertex(V v, Partition partition) { return vertexSetMapping.get(partition).contains(v); } @Override public boolean removeVertex(V v) { boolean rval = super.removeVertex(v); if (rval) { vertexSetMapping.get(vertexPartition(v)).remove(v); } return rval; } /** * Get the set of all vertices in one of the partitions * @param partition * @return a set of vertices */ public Set<V> vertexSet(Partition partition) { return Collections.unmodifiableSet(vertexSetMapping.get (partition)); } } 
From: John V. Sichi <jsichi@gm...>  20071010 05:58:32

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. Thanks Lucas. I'll take a look at this for the next release. Review comments from other developers would be appreciated. JVS 
From: John V. Sichi <jsichi@gm...>  20071105 04:03:46

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 spaceefficient 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 kpartite 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 selfexplanatory  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 
Sign up for the SourceForge newsletter:
No, thanks