Should generate a String that graph does not have a label, not 'null'.

AbstractGraph.java

/*
 * AbstractGraph.java
 *
 * Created: 10th of November 2003
 *
 * File Version: 0.4
 *
 * History:
 * --------
 * - The methods are implemented, They were not implemented before, Tomas Saxeggen and Lars Johansson, 20031118
 * - changed JavaDoc, MH, 20031205
 * - modified tailDfs to handle edgeTypes more correct, now and empty Set is interpreted as all types allowed, RL, 040120
 */
package grail.interfaces;

import grail.iterators.EdgeIterator;
import grail.iterators.NodeIterator;
import grail.iterators.NullNodeIterator;
import grail.properties.GraphProperties;

import java.util.Enumeration;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Set;
import java.util.Vector;

/**
 * All graphs should inherit from this class, although it is not requiered it is
 * strongly recommended. It implements many methods that you would have to
 * implement yourself if you don't inherit this class. These methods is not
 * always the most efficient since they can't assume anything about the
 * underlying implementation. If the underlying implementations provides a way
 * of optimizing any method, just override it.
 * 
 * @author Tomas Saxeggen and Lars Johansson
 * @version 0.4
 */
public abstract class AbstractGraph extends AbstractElement implements
		GraphInterface {
	// ~ Static fields/initializers
	// ---------------------------------------------

	// ~ Instance fields
	// --------------------------------------------------------

	protected boolean isacyclic = false;

	protected boolean isconnected = false;

	protected boolean iscyclic = false;

	protected boolean isnotconnected = false;

	private Hashtable properties = new Hashtable();

	protected Vector visited = new Vector();

	// ~ Methods
	// ----------------------------------------------------------------

	/*
	 * @pre There exists a graph either directed or undirected @post The state
	 * of the graph object remains unchanged
	 */
	public final boolean isCyclic() {
		return iscyclic;
	}

	/*
	 * @pre There exists a graph either directed or undirected @post The state
	 * of the graph object remains unchanged
	 */
	public boolean isAcyclic() {
		return isacyclic;
	}

	/*
	 * @pre There exists a graph either directed or undirected @post The state
	 * of the graph object remains unchanged
	 */
	public boolean isConnected() {
		return isconnected;
	}

	/*
	 * @pre There exists a graph either directed or undirected @post The state
	 * of the graph object remains unchanged
	 */
	public boolean isNotConnected() {
		return isnotconnected;
	}

	// /**
	// * @pre There exists a graph either directed or undirected @post The graph
	// * objects property is changed
	// */
	// public void setProperty(GraphProperties key, Object value) {
	// if ((key == null) || (value == null))
	// return;
	// if (!key.isValidValue(value))
	// throw new ClassCastException();
	// propertyKeys.add(key);
	// properties.put(key, value);
	// }

	// /*
	// * @pre There exists a graph either directed or undirected @post The state
	// * of the graph object remains unchanged
	// */
	// public Object getProperty(GraphProperties passKey) {
	// return properties.get(passKey);
	// }

	/*
	 * @pre There exists a graph either directed or undirected and fromNode and
	 * toNode must belong to the graph object @post The state of the graph
	 * object remains unchanged
	 */
	public boolean isReachable(NodeInterface fromNode, NodeInterface toNode) {
		visited.removeAllElements();
		if (isDirected()) {
			return isReachableDirectedRecursive(fromNode, toNode);
		}

		return isReachableUndirectedRecursive(fromNode, toNode);

	}

	private boolean isReachableUndirectedRecursive(NodeInterface from,
			NodeInterface to) {
		if (from == to)
			return true;
		visited.add(from);
		NodeIterator ni = ((UndirectedGraphInterface) this)
				.neighbors((UndirectedNodeInterface) from);
		while (ni.hasNext()) {
			ni.next();
			NodeInterface n = ni.getNode();
			if (to == n)
				return true;
			else if (!visited.contains(n)) {
				if (isReachableUndirectedRecursive(n, to))
					return true;
			}
		}
		return false;
	}

	private boolean isReachableDirectedRecursive(NodeInterface from,
			NodeInterface to) {
		if (from == to)
			return true;
		visited.add(from);
		NodeIterator ni = ((DirectedGraphInterface) this)
				.getSuccessors((DirectedNodeInterface) from);
		while (ni.hasNext()) {
			ni.next();
			NodeInterface n = ni.getNode();
			if (to == n)
				return true;
			else if (!visited.contains(n)) {
				if (isReachableDirectedRecursive(n, to))
					return true;
			}
		}
		return false;
	}

	/*
	 * @pre There exists a graph either directed or undirected @post The state
	 * of the graph object remains unchanged
	 */
	public NodeIterator bfs(NodeInterface startNode, Set edgeTypes) {
		final Set rt = edgeTypes;

		if (!this.containsNode(startNode))
			return new NodeIterator() {
				public boolean hasNext() {
					return false;
				}

				public void next() {
				}

				public NodeInterface getNode() {
					return null;
				}
			};

		final Vector worklist = new Vector();
		final Vector visited2 = new Vector();

		worklist.add(startNode);
		visited2.add(startNode);

		final GraphInterface g = this;

		return new NodeIterator() {
			private NodeInterface node = null;

			private boolean isRelevant(EdgeInterface e) {
				boolean res = ((rt == null) || rt.contains(e
						.getProperty(GraphProperties.TYPE)));

				return res;
			}

			public boolean hasNext() {
				return !worklist.isEmpty();
			}

			public void next() {
				node = (NodeInterface) worklist.firstElement();
				visited2.add(node);
				worklist.remove(node);

				if (isDirected()) {
					EdgeIterator ei = ((DirectedGraphInterface) g)
							.outEdges((DirectedNodeInterface) node);

					while (ei.hasNext()) {
						ei.next();

						DirectedEdgeInterface ve = (DirectedEdgeInterface) ei
								.getEdge();

						if (isRelevant(ve) && !visited2.contains(ve.getTo())
								&& !worklist.contains(ve.getTo()))
							worklist.add(ve.getTo());
					}
				} else { // is undirected

					EdgeIterator ei = ((UndirectedGraphInterface) g)
							.edges((UndirectedNodeInterface) node);

					while (ei.hasNext()) {
						ei.next();

						UndirectedEdgeInterface ve = (UndirectedEdgeInterface) ei
								.getEdge();

						if (isRelevant(ve)
								&& !visited2.contains(ve.getSecondNode())
								&& !worklist.contains(ve.getSecondNode()))
							worklist.add(ve.getSecondNode());

						if (isRelevant(ve)
								&& !visited2.contains(ve.getFirstNode())
								&& !worklist.contains(ve.getFirstNode()))
							worklist.add(ve.getFirstNode());
					}
				}
			}

			public NodeInterface getNode() {
				return node;
			}
		};
	}

	/*
	 * @pre There exists a graph either directed or undirected @post The state
	 * of the graph object remains unchanged
	 */
	public NodeIterator dfs(NodeInterface node, Set edgeTypes) {
		if (node == null || !this.containsNode(node))
			return new NullNodeIterator();

		Vector visited2 = new Vector();
		Vector worklist = new Vector();
		Vector temp = new Vector();

		// NodeIterator nodes = this.nodes();

		worklist.add(node);

		temp = tailDfs(node, edgeTypes, visited2, worklist, temp);

		final Vector result = temp;

		return new NodeIterator() {
			private NodeInterface sbgn = null;

			public boolean hasNext() {
				return !result.isEmpty();
			}

			public void next() {
				sbgn = (NodeInterface) result.firstElement();
				result.remove(sbgn);
			}

			public NodeInterface getNode() {
				return sbgn;
			}
		};
	}

	/*
	 * @pre There exists a graph either directed or undirected @post The value
	 * of the attributes isconnected and isnotconnected in the graph object is
	 * changed
	 */
	public void testIsConnected() {
		int number = this.nodeCount();
		NodeIterator ni = this.nodes();
		NodeInterface node;
		Vector check = new Vector();

		if (isDirected()) {
			while (ni.hasNext()) {
				ni.next();
				node = ni.getNode();

				NodeIterator dni = myDfs(node);
				check = toVector(dni);

				if (check.size() == number) {
					isconnected = true;
					isnotconnected = false;
				}
			}
		} else {
			ni.next();
			node = ni.getNode();

			NodeIterator uni = myDfs(node);
			check = toVector(uni);

			if (check.size() == number) {
				isconnected = true;
				isnotconnected = false;
			}
		}
	}

	/*
	 * Public test command for cyclic. Determines the state of the isCyclic and
	 * isAcyclic attributes. @pre There exists a graph either directed or
	 * undirected @post The value of the attributes iscyclic and isacyclic in
	 * the graph object is changed
	 */
	public void testIsCyclic() {
		boolean temp = true;

		if (isDirected()) {
			DirectedGraphInterface d = (DirectedGraphInterface) this;
			Hashtable nodes = new Hashtable();
			DirectedNodeInterface root;
			DirectedNodeInterface nod;
			NodeIterator ni = d.nodes();
			int indegree;

			while (ni.hasNext()) {
				ni.next();
				nod = (DirectedNodeInterface) ni.getNode();
				indegree = d.inDegree(nod);
				nodes.put(nod, Integer.valueOf(indegree));
			}

			while (!nodes.isEmpty()) {
				root = findRoot(nodes);

				if (root != null) {
					nodes.remove(root);
					EdgeIterator ei = d.outEdges(root);

					while (ei.hasNext()) {
						ei.next();
						nod = (DirectedNodeInterface) ((DirectedEdgeInterface) ei
								.getEdge()).getTo();
						indegree = ((Integer) nodes.get(nod)).intValue();
						indegree -= 1;
						nodes.put(nod, Integer.valueOf(indegree));
					}
				} else {
					iscyclic = true;
					isacyclic = false;
					temp = false;

					break;
				}
			}

			if (temp) {
				iscyclic = false;
				isacyclic = true;
			}
		} else {
			UndirectedGraphInterface ud = (UndirectedGraphInterface) this;
			Vector nodes = new Vector();
			Vector edges = new Vector();
			UndirectedNodeInterface node;
			NodeIterator ni;
			ni = ud.nodes();

			while (ni.hasNext()) {
				ni.next();
				node = (UndirectedNodeInterface) ni.getNode();

				if (hasUndirectedCycle(node, nodes, edges)) {
					iscyclic = true;
					isacyclic = false;
					temp = false;

					break;
				}
			}

			if (temp) {
				iscyclic = false;
				isacyclic = true;
			}
		}
	}

	/*
	 * @pre There exists a graph either directed or undirected @post The state
	 * of the graph object remains unchanged
	 */

	/**
	 * Returns the label of the graph.
	 * 
	 * @return String containing some basic information about the graph, like
	 *         its label, count of nodes and edges and status.
	 */
	@Override
	public String toString() {
		return (String) getProperty(GraphProperties.LABEL);
	}

	private DirectedNodeInterface findRoot(Hashtable ht) {
		Integer zero = Integer.valueOf(0);
		Integer temp = Integer.valueOf(0);
		DirectedNodeInterface root;

		if (ht.containsValue(zero)) {
			Enumeration e = ht.keys();

			while (e.hasMoreElements()) {
				root = (DirectedNodeInterface) e.nextElement();
				temp = (Integer) ht.get(root);

				if (temp.intValue() == 0) {
					return root;
				}
			}
		}

		return null;
	}

	private boolean hasUndirectedCycle(UndirectedNodeInterface n1,
			Vector visitedNodes, Vector visitedEdges) {
		visitedNodes.add(n1);

		UndirectedGraphInterface ud = (UndirectedGraphInterface) this;
		EdgeIterator ei = ud.edges(n1);
		UndirectedEdgeInterface edge;
		UndirectedNodeInterface n2;

		while (ei.hasNext()) {
			ei.next();
			edge = (UndirectedEdgeInterface) ei.getEdge();

			if (!visitedEdges.contains(edge)) {
				visitedEdges.add(edge);
				n2 = edge.getSecondNode();

				if (n1 == n2) {
					n2 = edge.getFirstNode();
				}

				if (visitedNodes.contains(n2)) {
					return true;
				}
				if (hasUndirectedCycle(n2, visitedNodes, visitedEdges)) {
					return true;

				}
			}
		}

		return false;
	}

	private NodeIterator myDfs(NodeInterface nod) {
		visited.removeAllElements();

		NodeIterator ni = myrecDfs(nod);

		return ni;
	}

	private NodeIterator myrecDfs(NodeInterface nod) {
		if (!this.containsNode(nod))
			return new NodeIterator() {
				public boolean hasNext() {
					return false;
				}

				public void next() {
				}

				public NodeInterface getNode() {
					return null;
				}
			};

		visited.add(nod);

		NodeIterator ni = null;

		if (isDirected()) {
			DirectedGraphInterface d = (DirectedGraphInterface) this;
			ni = d.getSuccessors((DirectedNodeInterface) nod);
		} else {
			UndirectedGraphInterface ud = (UndirectedGraphInterface) this;
			ni = ud.neighbors((UndirectedNodeInterface) nod);
		}

		while (ni.hasNext()) {
			ni.next();

			NodeInterface node = ni.getNode();

			if (!visited.contains(node)) {
				myrecDfs(node);
			}
		}

		return new NodeIterator() {
			Enumeration e = visited.elements();

			NodeInterface node;

			public boolean hasNext() {
				return e.hasMoreElements();
			}

			public void next() {
				node = (NodeInterface) e.nextElement();
			}

			public NodeInterface getNode() {
				return node;
			}
		};
	}

	private Vector tailDfs(NodeInterface node, Set edgeTypes, Vector visitedP,
			Vector worklist, Vector result) {
		EdgeIterator edges;

		if (isDirected()) {
			DirectedGraphInterface d = (DirectedGraphInterface) this;
			edges = d.outEdges((DirectedNodeInterface) node);
		} else {
			UndirectedGraphInterface ud = (UndirectedGraphInterface) this;
			edges = ud.edges((UndirectedNodeInterface) node);
		}
		// TODO: replace inefficient Vector with a Set, this improves contains
		// operation
		if (worklist.contains(node) && !visitedP.contains(node)) {
			visitedP.add(node);
			worklist.remove(node);
			result.add(node);

			while (edges.hasNext()) {
				edges.next();

				EdgeInterface edge = edges.getEdge();

				if (isDirected()) {
					// interpret null or an empty edgTypes set as all types
					// allowed.
					if ((edgeTypes == null)
							|| (edgeTypes.isEmpty())
							|| edgeTypes.contains(edge
									.getProperty(GraphProperties.TYPE))) {
						DirectedNodeInterface successor = ((DirectedEdgeInterface) edge)
								.getTo();
						worklist.add(successor);
						result = tailDfs(successor, edgeTypes, visitedP,
								worklist, result);
					}
				} else {
					UndirectedNodeInterface otherNode = null;

					if (((UndirectedEdgeInterface) edge).getFirstNode().equals(
							node)) {
						otherNode = ((UndirectedEdgeInterface) edge)
								.getSecondNode();
					} else {
						otherNode = ((UndirectedEdgeInterface) edge)
								.getFirstNode();
					}

					worklist.add(otherNode);
					result = tailDfs(otherNode, edgeTypes, visitedP, worklist,
							result);
				}
			}
		}

		return result;
	}

	private Vector toVector(NodeIterator ni) {
		Vector graphpart = new Vector();
		NodeIterator temp = ni;

		while (temp.hasNext()) {
			temp.next();

			NodeInterface nod = temp.getNode();
			graphpart.add(nod);
		}

		return graphpart;
	}

	protected HashSet propertyKeys = new HashSet();

	// public Collection getProperties() {
	// return propertyKeys;
	// }

	// @Override
	// public abstract Object clone();

}