From: Lucas Scharenbroich <lscharen@jp...>  20071007 03:13:22

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)); } } 