Thread: [jgrapht-developers] Feedback on BipartiteGraph implementation

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

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 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.

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