graph.java

发布/订阅系统路由重配算法,可应用于ad hoc环境

/*
 * project: RebecaSim
 * package: graph
 * file:    Graph.java
 * 
 * version: 0.1
 * date:    04.04.2005
 * 
 * This software is part of the diploma thesis "Ein adaptives Brokernetz 
 * für Publish/Subscribe Systeme".
 */
package graph;

import java.util.*;
import util.*;

/**
 * TODO Insert class description here.
 *
 * @version 04.04.2005
 * @author  parzy
 */
public class Graph extends Element {

	private class AdjIterator implements AdjacencyIterator {
		private Vertex v;
		private Vertex vertex;
		private Edge edge;
		private ResetableIterator iterator;
		private int type;
		
		AdjIterator(Vertex v, SimpleHashtable adjacencyList, int type) {
			this.iterator = adjacencyList.valueIterator();
	 		this.v = v;
			this.vertex = null;
			this.edge = null;
			this.type = type;
		}
		
		public boolean hasNext() {
			return iterator.hasNext();
		}
		
		public Object next() {
			edge = (Edge)iterator.next();
			vertex = v.equals(edge.s) ? edge.t : edge.s;
			return type == VERTEX ? (Object)vertex : (Object)edge;
		}
		
		public Vertex vertex() {
			return vertex;
		}
		
		public Edge edge() {
			return edge;
		}
		
		public void remove() {
			iterator.remove();
		}
		
		public void reset() {
			iterator.reset();
		}
	}
	
	private static final int VERTEX = 0;
	private static final int EDGE = 1; 
	
	private SimpleHashtable vertices; 
	
	public Graph() {
		this.vertices = new SimpleHashtable();
	}
	
	
	public int getNumberOfVertices(){
		return vertices.size();
	}

	
	public boolean addVertices(Vertex[] vertices){
		boolean rst;
		rst = false;
		for(int i=0; i<vertices.length; i++){
			rst = rst || addVertex(vertices[i]);
		}
		return rst;
	}
	
	public boolean addVertex(Vertex v) {
		if (v == null) {
			throw new NullPointerException("Null is not a valid vertex.");
		}
		if (vertices.containsKey(v)) {
			return false;
		}
		vertices.put(v, new SimpleHashtable());
		return true;
	}
	
	
	public boolean containsVertex(Vertex v) {
		if (v == null) {
			throw new NullPointerException("Null is not a valid vertex.");
		}
		return vertices.containsKey(v);
	}
	
//	public boolean removeVertex(Vertex v) {
//
//		SimpleHashtable vList;
//		SimpleHashtable wList;
//		Edge e;
//		Vertex w;
//		
//		if (v == null) {
//			throw new NullPointerException("Null is not a valid vertex.");
//		}
//		
//		vList = (SimpleHashtable)vertices.remove(v);
//		if (vList != null) {
//			for (vList.keyIterator.reset(); vList.keyIterator.hasNext(); ) {
//				e = (Edge)vList.keyIterator.next();
//				w = v.equals(e.s) ? e.t : e.s;
//				wList = (SimpleHashtable)vertices.get(w);
//				wList.remove(e);
//			}
//			return true;
//		}
//		return false;
//	}
	
	// TODO: auch Hinzufügen von Kanten mit unbekannten Knoten zulassen
//	public boolean addEdge(Edge e) {
//
//		SimpleHashtable sList;
//		SimpleHashtable tList;
//		
//		if (e == null) {
//			throw new NullPointerException("Null is not a valid edge.");
//		}
//		
//		if ( (sList = (SimpleHashtable)vertices.get(e.s)) != null && 
//		     (tList = (SimpleHashtable)vertices.get(e.t)) != null) {
//			return sList.put(e,e) == null && tList.put(e,e) == null;
//		}				
//		throw new IllegalArgumentException("Edge contains unknown vertex.");
//	}

	public boolean addEdge(Edge e){
		
		SimpleHashtable edgeS;
		SimpleHashtable edgeT;

		edgeS = (SimpleHashtable)vertices.get(e.s);
		if(edgeS == null){
			edgeS = new SimpleHashtable();
			vertices.put(e.s,edgeS);
		}
		
		edgeT = (SimpleHashtable)vertices.get(e.t);
		if(edgeT == null){
			edgeT = new SimpleHashtable();
			vertices.put(e.t,edgeT);
		}
		
		
		
		if(edgeS.containsKey(e.t)){
			return false;
		}
		
		edgeS.put(e.t, e);
		edgeT.put(e.s, e);
		return true;
	}
	
//	public boolean containsEdge(Edge e) {
//
//		SimpleHashtable sList;
//		
//		if (e == null) {
//			throw new NullPointerException("Null is not a valid edge.");
//		}
//		
//		sList = (SimpleHashtable)vertices.get(e.s);
//		return sList != null && sList.get(e) != null;
//	}

	public boolean containsEdge(Edge e) {
		SimpleHashtable edges;
		
		edges = (SimpleHashtable)vertices.get(e.s);
		return edges != null && e.equals(edges.get(e.t));
	}
	
	public boolean containsEdge(Vertex v, Vertex w){
		return getEdge(v,w) != null;
	}
	
//	public Edge getEdge(Vertex v, Vertex w){
//		SimpleHashtable sList;
//		Edge e;
//		
//		if (v == null || w == null) {
//			throw new NullPointerException("Null is not a valid vertex.");
//		}
//		
//		sList = (SimpleHashtable)vertices.get(v);
//		if (sList != null){
//			for (sList.valueIterator.reset(); sList.valueIterator.hasNext();){
//				e = (Edge)sList.valueIterator.next();
//				if ((v.equals(e.s) && w.equals(e.t)) || 
//				    (v.equals(e.t) && w.equals(e.s))){
//					return e;
//				}
//			}
//		}
//		return null;
//	}

	public Edge getEdge(Vertex v, Vertex w) {
		SimpleHashtable edgeS;
		
		if (v == null || w == null) {
			throw new NullPointerException("Null is not a valid vertex.");
		}
		
		edgeS = (SimpleHashtable)vertices.get(v);
		return (Edge)edgeS.get(w);
	}
	
	
//	public boolean removeEdge(Edge e) {
//
//		SimpleHashtable sList;
//		SimpleHashtable tList;
//		
//		if (e == null) {
//			throw new NullPointerException("Null is not a valid edge.");
//		}
//		
//		sList = (SimpleHashtable)vertices.get(e.s);
//		if (sList != null && sList.remove(e) != null) {
//			tList = (SimpleHashtable)vertices.get(e.t);
//			tList.remove(e);
//			return true;
//		}
//		return false;
//	}
	
	public  boolean removeEdge(Edge e){

		SimpleHashtable edgeS;
		SimpleHashtable edgeT;

		edgeS = (SimpleHashtable)vertices.get(e.s);
		edgeT = (SimpleHashtable)vertices.get(e.t);

		if(edgeS == null || edgeT == null){
			return false;
		}
		
		return edgeS.remove(e.t) != null && edgeT.remove(e.s) != null;
	}
	
	
	// TODO: effizienter implementieren
//	public boolean removeEdge(Vertex v, Vertex w){
//		Edge e;
//		e = getEdge(v,w);
//		if(e != null){
//			return removeEdge(e);
//		}
//		return false;
//	}
	
	public boolean removeEdge(Vertex v, Vertex w){
		SimpleHashtable edgeS;
		SimpleHashtable edgeT;
		//Edge e;
		
		if (v == null || w == null) {
			throw new NullPointerException("Null is not a valid vertex.");
		}
		
		edgeS = (SimpleHashtable)vertices.get(v);
		edgeT = (SimpleHashtable)vertices.get(w);
		
		if(edgeS == null || edgeT == null) {
			return false;
		}
		return edgeS.remove(w) != null && edgeT.remove(v) != null;
	}
	
	
	public AdjacencyIterator adjacencyIterator(Vertex v) {
		return adjacencyIterator(v, EDGE);
	}
	
	private AdjacencyIterator adjacencyIterator(Vertex v, int type) {

		SimpleHashtable vList;
		
		if (v == null) {
			throw new NullPointerException("Null is not a valid vertex.");
		}
		
		vList = (SimpleHashtable)vertices.get(v);
		if (vList == null) {
			throw new NoSuchElementException();
		}
		return new AdjIterator(v, vList, type);
		
	}

	public AdjacencyIterator edgeAdjacencyIterator(Vertex v) {
		return adjacencyIterator(v, EDGE);
	}
	
	public AdjacencyIterator vertexAdjacencyIterator(Vertex v) {
		return adjacencyIterator(v, VERTEX);
	}
	
	public Iterator vertexIterator(){
		return vertices.keyIterator();
	}
	
	public Iterator edgeIterator() {
		return new EdgeIterator();
	}
	
	protected class EdgeIterator implements Iterator{
		Iterator vit;
		Iterator eit = null;
		Vertex v = null;
		Edge e = null;
		
		protected EdgeIterator() {
			this.vit = Graph.this.vertexIterator();
			if (vit.hasNext()) {
				v = (Vertex)vit.next();
				eit = ((SimpleHashtable)Graph.this.vertices.get(v)).valueIterator();
			}
		}
		
		public boolean hasNext() {
			toNext();
			return e != null;
		}
		
		public Object next() throws NoSuchElementException{
			Edge next;
			
			toNext();
			
			if (e == null) {
				throw new NoSuchElementException();
			}
			
			next = e;
			e = null;
			return next;
		}
		
		public void remove() {
			throw new UnsupportedOperationException();
		}
		
		private void toNext() {
			if(e != null) {
				return;
			}
			
			while (eit != null) {
               	while (eit.hasNext()) {
               		e = (Edge)eit.next();
               		if (v.equals(e.s)) {
               			return;
               		}               	
               	}
               	
               	if(vit.hasNext()) {
               		v = (Vertex)vit.next();
               		eit = ((SimpleHashtable)Graph.this.vertices.get(v)).valueIterator();
               	} else {
               		e = null;
               		v = null;
               		eit = null;
               	}
            }
		}
	}
}