Ptidej-v5.2-master/DRAM Libraries/src/dram/utils/salvo/MyDirectedGraphWeakImpl.java
package dram.utils.salvo;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import salvo.jesus.graph.DirectedEdge;
import salvo.jesus.graph.DirectedGraph;
import salvo.jesus.graph.Edge;
import salvo.jesus.graph.GraphAddEdgeEvent;
import salvo.jesus.graph.GraphAddVertexEvent;
import salvo.jesus.graph.GraphListener;
import salvo.jesus.graph.GraphRemoveEdgeEvent;
import salvo.jesus.graph.GraphRemoveVertexEvent;
import salvo.jesus.graph.StopAtVisitor;
import salvo.jesus.graph.Vertex;
import salvo.jesus.graph.adaptor.GraphDelegator;

/**
 * A weak implementation of the DirectedGraph interface.
 *
 * @author		Jesus M. Salvo Jr.
 */
class MyDirectedGraphWeakImpl extends GraphDelegator implements DirectedGraph,
		GraphListener {

	private static final long serialVersionUID = -2718883367961089045L;

	/**
	 * DirectedVertexData is the data structure kept for each vertex which is
	 * part of this directed graph.  It mirrors GraphImpl.VertexData
	 */
	private class DirectedVertexData implements Serializable {
		private static final long serialVersionUID = 1871365392604156628L;

		private ArrayList incomingEdges;
		private ArrayList outgoingEdges;
		private List unmodifiableIncomingEdges;
		private List unmodifiableOutgoingEdges;

		DirectedVertexData() {
			this.incomingEdges = new ArrayList();
			this.outgoingEdges = new ArrayList();
		}

		final List getIncomingEdges() {
			return this.incomingEdges;
		}

		final List getOutgoingEdges() {
			return this.outgoingEdges;
		}

		public final List getUnmodifiableIncomingEdges() {
			if (this.unmodifiableIncomingEdges == null) {
				this.unmodifiableIncomingEdges =
					Collections.unmodifiableList(this.incomingEdges);
			}
			return this.unmodifiableIncomingEdges;
		}

		public final List getUnmodifiableOutgoingEdges() {
			if (this.unmodifiableOutgoingEdges == null) {
				this.unmodifiableOutgoingEdges =
					Collections.unmodifiableList(this.outgoingEdges);
			}
			return this.unmodifiableOutgoingEdges;
		}
	}

	// private TreeMap vertexDataMap;
	private Map vertexDataMap;

	/**
	 * Creates a new instance of DirectedGraphWeakImpl.
	 */
	public MyDirectedGraphWeakImpl(MyGraphImpl graph) {
		super(graph);
		//vertexDataMap = new TreeMap();
		this.vertexDataMap = new HashMap();
		graph.addListener(this);
	}

	protected DirectedVertexData getVertexData(Vertex v) {
		return (DirectedVertexData) this.vertexDataMap.get(v);
	}

	/**
	 * Returns the outgoing edges of a particular Vertex in the Graph.
	 *
	 * @param v Vertex you want to determine its outgoing edges.
	 * @return List of outgoing edges of the specified Vertex.
	 */
	public List getOutgoingEdges(Vertex v) {
		return getVertexData(v).getUnmodifiableOutgoingEdges();
	}

	/**
	 * Returns the incoming edges of a particular Vertex in the Graph.
	 *
	 * @param v Vertex you want to determine its incoming edges.
	 * @return List of incoming edges of the specified Vertex.
	 */
	public List getIncomingEdges(Vertex v) {
		return getVertexData(v).getUnmodifiableIncomingEdges();
	}

	/**
	 * Returns the vertices that are adjacent to a specified Vertex,
	 * respecting the direction of the Edge from the specified Vertex.
	 *
	 * @param v Vertex you want to determine its outgoing adjacent vertices.
	 * @param outGoing If true, method will return outgoing adjacent vertices.
	 * If false, method will return incoming adjacent vertices.
	 * @return List of outgoing / incoming vertices adjacent to the specified
	 * Vertex.
	 */
	private List getAdjacentVertices(Vertex v, boolean outGoing) {
		List adjacentVertices = new ArrayList(10);
		List incidentEdges;
		Iterator iterator;
		Edge edge;
		Vertex oppositeVertex;

		if (outGoing)
			incidentEdges = this.getOutgoingEdges(v);
		else
			incidentEdges = this.getIncomingEdges(v);

		iterator = incidentEdges.iterator();
		while (iterator.hasNext()) {
			edge = (Edge) iterator.next();
			oppositeVertex = edge.getOppositeVertex(v);
			adjacentVertices.add(oppositeVertex);
		}

		return Collections.unmodifiableList(adjacentVertices);
	}

	/**
	 * Returns the vertices that are adjacent to a specified Vertex where the
	 * Edge is outgoing from the specified Vertex to the adjacent vertex.
	 *
	 * @param v Vertex you want to determine its outgoing adjacent vertices.
	 * @return List of outgoing vertices adjacent to the specified Vertex.
	 */
	public List getOutgoingAdjacentVertices(Vertex v) {
		return this.getAdjacentVertices(v, true);
	}

	/**
	 * Returns the vertices that are adjacent to a specified Vertex where the
	 * Edge is incoming from the specified Vertex to the adjacent vertex.
	 *
	 * @param v Vertex you want to determine its incoming adjacent vertices.
	 * @return List of incoming vertices adjacent to the specified Vertex.
	 */
	public List getIncomingAdjacentVertices(Vertex v) {
		return this.getAdjacentVertices(v, false);
	}

	/**
	 * Returns an Edge in the Graph whose origin is fromVertex and destination
	 * is toVertex.  If there is more than one Edge that has the same origin
	 * and destination in the Graph, the first matching Edge is returned.
	 *
	 * @param fromVertex Vertex that is the origin of the directed Edge
	 * @param toVertex Vertex that is the destination of the directed Edge
	 * @return Edge whose origin is fromVertex and destination is toVertex
	 * @see salvo.jesus.graph.Edge
	 */
	public DirectedEdge getEdge(Vertex fromvertex, Vertex tovertex) {
		List outIncidentEdges;
		Iterator iterator;
		DirectedEdge edge;

		// Get the adjacent edge set of the from vertex
		outIncidentEdges = this.getOutgoingEdges(fromvertex);

		// Find the edge where the direction is to the tovertex
		iterator = outIncidentEdges.iterator();
		while (iterator.hasNext()) {
			edge = (DirectedEdge) iterator.next();
			if (edge.getSink() == tovertex) {
				// Edge is found.
				iterator = null;
				return edge;
			}
		}
		return null;
	}

	/**
	 * Determines if there is a path from Vertex fromVertex to Vertex toVertex.
	 * This will not return true if the only path has at least one Edge
	 * pointing in the opposite direction of the path.
	 *
	 * @param fromVertex starting Vertex for the path
	 * @param toVertex ending Vertex for the path
	 * @return true if there is a path from Vertex to toVertex. false
	 * otherwise.
	 */
	public boolean isPath(Vertex fromVertex, Vertex toVertex) {
		StopAtVisitor visitor = new StopAtVisitor(toVertex);
		getGraph().getTraversal().traverse(fromVertex, visitor);
		return visitor.wasFound();
	}

	/**
	 * Determines if there is a cycle from Vertex fromVertex. A cycle occurs
	 * when there is a path from the specified Vertex back to itself, taking
	 * into consideration that direction of the Edges along the path.
	 *
	 * @param fromVertex Vertex to be tested for a cycle path.
	 * @return true if there is a cycle path from fromVertex to itself.
	 */
	public boolean isCycle(Vertex fromVertex) {
		List outedges = this.getOutgoingEdges(fromVertex);
		Iterator iterator = outedges.iterator();
		DirectedEdge dedge;
		Vertex adjacentVertex;

		// REVIEW jvs 2-Feb-2002 -- seems like we should be able to
		// tweak the DFS implementation to allow us to skip fromVertex
		// initially so we wouldn't have to iterate over the edges here

		// For each outgoing edge of the vertex ...
		while (iterator.hasNext()) {
			dedge = (DirectedEdge) iterator.next();
			// ... get the opposite vertex
			adjacentVertex = dedge.getOppositeVertex(fromVertex);
			// .. and check if there is a path from the opposite vertex back to
			// the vertex
			if (this.isPath(adjacentVertex, fromVertex))
				// There is a cycle
				return true;
		}

		// No cycle
		return false;
	}

	// -- GraphListener implementation --

	// we don't care about most before vertex events
	public void beforeVertexAdded(GraphAddVertexEvent event) {
	}

	public void beforeVertexRemoved(GraphRemoveVertexEvent event) {
	}

	// but we do care about this before event; use this as a chance to make
	// sure that the Edge being added is a DirectedEdge 
	public void beforeEdgeAdded(GraphAddEdgeEvent event)
			throws ClassCastException {
		event.getEdge();
	}

	public void beforeEdgeRemoved(GraphRemoveEdgeEvent event) {
	}

	// and we do care about after events; this is where we keep the
	// directed graph data structures in sync with the undirected

	public void afterVertexAdded(GraphAddVertexEvent event) {
		this.vertexDataMap.put(event.getVertex(), new DirectedVertexData());
	}

	public void afterVertexRemoved(GraphRemoveVertexEvent event) {
		this.vertexDataMap.remove(event.getVertex());
	}

	public void afterEdgeAdded(GraphAddEdgeEvent event) {
		DirectedEdge dedge = (DirectedEdge) event.getEdge();

		DirectedVertexData vd1 = getVertexData(dedge.getSource());
		DirectedVertexData vd2 = getVertexData(dedge.getSink());
		vd1.getOutgoingEdges().add(dedge);
		vd2.getIncomingEdges().add(dedge);
	}

	public void afterEdgeRemoved(GraphRemoveEdgeEvent event) {
		Vertex fromvertex;
		Vertex tovertex;

		DirectedEdge dedge = (DirectedEdge) event.getEdge();

		// Get source and sink vertices of edge
		fromvertex = dedge.getSource();
		tovertex = dedge.getSink();

		// Get the vector of outgoing edge of the source and the
		// vector of incoming edges of the sink.
		DirectedVertexData vdFrom = getVertexData(fromvertex);
		DirectedVertexData vdTo = getVertexData(tovertex);

		// Remove the edge from the source's outgoing edges
		vdFrom.getOutgoingEdges().remove(dedge);
		// Remove the edge from the sink's incoming edges
		vdTo.getIncomingEdges().remove(dedge);
	}

}
