graphcontractionalgorithm.java

OpenJGraph是一个开源的Java库

package salvo.jesus.graph.algorithm;
import salvo.jesus.graph.*;
import java.util.*;

/**
 * GraphContraction is an algorithm class for managing a series of contractions
 * on a graph (directed or undirected).  It is abstract because it requires a
 * concrete subclass to supply certain rules about how the contraction should
 * be performed.  Note that GraphContraction modifies its input graph in place;
 * it does not construct a new graph.
 *
 * @author John V. Sichi
 */
public abstract class GraphContractionAlgorithm
{
    private Graph m_graph;

    /**
     * A map from the original vertex and edge sets to the resulting sets after
     * contraction.
     */
    private Map m_contractionMap;
    
    protected GraphContractionAlgorithm(Graph graph)
    {
        m_graph = graph;
        m_contractionMap = new HashMap();
    }

    /**
     * @return the graph on which this contraction operates
     */
    public Graph getGraph()
    {
        return m_graph;
    }

    /**
     * Contract two arbitrary vertices within a graph.  The vertices need not
     * be already connected.
     *
     * @param vRemain the vertex that will remain after contraction
     *
     * @param vRemove the vertex that will be removed by contraction
     *
     * @exception Exception if the graph cannot be modified
     */
    public void contractVertexPair(Vertex vRemain,Vertex vRemove)
        throws Exception
    {
        // in case these vertices have already been contracted, get their
        // current mappings
        vRemove = getContractionVertex(vRemove);
        vRemain = getContractionVertex(vRemain);
        
        if (vRemove == vRemain) {
            // that's easy enough...but maybe should filter any self-loops
            // through shouldBeSelfLoop() as well?
            return;
        }
        // transfer all of vRemove's edges to vRemain
        List edgeList = m_graph.getEdges(vRemove);
        if (edgeList == null) {
            edgeList = Collections.EMPTY_LIST;
        }
        Iterator edges = edgeList.iterator();
        while (edges.hasNext()) {
            Edge edge = (Edge) edges.next();
            Vertex opposite = edge.getOppositeVertex(vRemove);
            if (opposite == vRemain) {
                if (!shouldBeSelfLoop(edge)) {
                    continue;
                } else {
                    // below will create a self-loop
                }
            }
            
            if (opposite == vRemove) {
                // there was already a self-loop
                if (shouldBeSelfLoop(edge)) {
                    // transfer the accepted self-loop to vRemain
                    opposite = vRemain;
                } else {
                    // this rejected self-loop will go away when
                    // we delete vRemove at the end
                }
            }

            // preserve direction in case it's relevant (assumes vertexA is
            // always the source for a DirectedEdge)
            Edge newEdge;
            if (vRemove == edge.getVertexA()) {
                newEdge = copyEdge(edge,vRemain,opposite);
            } else {
                newEdge = copyEdge(edge,opposite,vRemain);
            }
            // record the edge contraction
            m_contractionMap.put(edge,newEdge);
        }

        // now lose vRemove
        m_graph.remove(vRemove);

        // record the vertex contraction
        m_contractionMap.put(vRemove,vRemain);
    }

    /**
     * Contract an arbitrary collection of vertices within a graph into a
     * single vertex. The vertices need not be already connected.
     *
     * @param vertices the vertices to be contracted; the first vertex returned
     * by this Collection's iterator will be the one to remain
     *
     * @exception Exception if the graph cannot be modified
     */
    public void contractVertices(Collection vertices)
        throws Exception
    {
        // Contraction is transitive, so we can do it willy-nilly by just
        // iterating over vertices and contracting each vertex
        // with the first one.
        Iterator iter = vertices.iterator();
        if (!iter.hasNext()) {
            return;
        }
        Vertex vRemain = (Vertex) iter.next();
        while (iter.hasNext()) {
            Vertex vRemove = (Vertex) iter.next();
            contractVertexPair(vRemain,vRemove);
        }
    }
    
    /**
     * Perform contractVertexPair for the two incident vertices of
     * each edge in a specified set.  For each edge, getVertexA() determines
     * vRemain and getVertexB() determines vRemove.
     *
     * @param edges the edges to contract
     *
     * @exception Exception if the graph cannot be modified
     */
    public void contractEdges(Collection edges)
        throws Exception
    {
        Iterator edgeIter = edges.iterator();
        while (edgeIter.hasNext()) {
            Edge edge = (Edge) edgeIter.next();
            contractVertexPair(edge.getVertexA(),edge.getVertexB());
        }
    }

    /**
     * Find the resulting contraction for a Vertex.
     *
     * @param v the Vertex to find the contraction for
     *
     * @return the contracted vertex (same as v if v has not been contracted)
     */
    public Vertex getContractionVertex(Vertex v)
    {
        return (Vertex) getContractionResult(v);
    }

    /**
     * Find the resulting contraction for an Edge.
     *
     * @param edge the Edge to find the contraction for
     *
     * @return the contracted edge (same as edge if edge has not been
     * contracted)
     */
    public Edge getContractionEdge(Edge edge)
    {
        return (Edge) getContractionResult(edge);
    }

    /**
     * Find the resulting contraction for a GraphComponent
     * (Vertex or Edge).
     *
     * @param c the GraphComponent
     *
     * @return the contracted component (same as c if c has not been
     * contracted)
     */
    public GraphComponent getContractionResult(GraphComponent c)
    {
        // a little bit of union-find fun
        GraphComponent c2 = (GraphComponent) m_contractionMap.get(c);
        if (c2 == null) {
            return c;
        }
        GraphComponent c3 = getContractionResult(c2);
        if (c3 != c2) {
            m_contractionMap.put(c,c3);
        }
        return c3;
    }
    
    /**
     * Subclass method called to decide whether a given edge
     * encountered during contraction should be turned into a self-loop
     * on the contracted vertex.
     */
    protected abstract boolean shouldBeSelfLoop(Edge e);

    /**
     * Subclass method called to add a new contracted edge equivalent to
     * oldEdge, but connecting vA to vB.  The rule may decide that oldEdge is
     * already equivalent to an existing edge between vA and vB, in which case
     * no new edge is added.  If a new edge is created, the implementation
     * should add it to getGraph().
     *
     * @param oldEdge the edge being contracted
     *
     * @param vA one vertex to which the new edge should be incident;
     * for a DirectedGraph, this is the source
     *
     * @param vB the other vertex to which the new edge should be incident;
     * for a DirectedGraph, this is the sink
     *
     * @return the new or existing edge
     *
     * @exception Exception if the graph cannot be modified
     */
    protected abstract Edge copyEdge(Edge oldEdge,Vertex vA,Vertex vB)
        throws Exception;
}

// End GraphContractionAlgorithm.java