graph.java

能在 ns-2 下模拟出一个使用 swarm 算法通讯的网络

/*******************************************************************************
 ** BonnMotion - a mobility scenario generation and analysis tool             **
 ** Copyright (C) 2002, 2003 University of Bonn                               **
 **                                                                           **
 ** This program is free software; you can redistribute it and/or modify      **
 ** it under the terms of the GNU General Public License as published by      **
 ** the Free Software Foundation; either version 2 of the License, or         **
 ** (at your option) any later version.                                       **
 **                                                                           **
 ** This program is distributed in the hope that it will be useful,           **
 ** but WITHOUT ANY WARRANTY; without even the implied warranty of            **
 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             **
 ** GNU General Public License for more details.                              **
 **                                                                           **
 ** You should have received a copy of the GNU General Public License         **
 ** along with this program; if not, write to the Free Software               **
 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA **
 *******************************************************************************/

package edu.bonn.cs.iv.graph;

import edu.bonn.cs.iv.util.*;

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

/** This class implements a directed graph. However, many methods operate und undirected graphs, and expected that the edges are symmetric; if they are not, their output is undefined. */

public class Graph {
	/** Save the nodes of type Node. */
	protected SortedList nodeList = new SortedList();

	/** Create empty graph. */
	public Graph() {}

	/** Reads a graph object from a BufferedReader. */
	public Graph(BufferedReader in) throws IOException {
		String r = readFromFile(in);
		if (r != null)
			throw new IOException("Graph.<init>: cannot load graph: " + r);
	}

	/** Retrieve node with a certain ID. If it does not exist, it will be added to the graph.
 * 	@param id Node ID.
 * 	@return Sought or newly created node. */
	public Node checkNode(int id) {
		Node n = (Node)nodeList.get(id);
		if (n != null)
			return n;
		else {
			n = new Node(id, this);
			nodeList.add(n);
			return n;
		}
	}

	/** Added a node to the graph. Cooperates with Node.addToGraph. */
	public void addNode(Node n) {
		if (((n.homeGraph() != null) && (n.homeGraph() != this)) || (nodeList.add(n) == -1)) {
			System.out.println("Graph.addNode: so nicht!");
			System.exit(0);
		}
		if (n.homeGraph() == null)
			n.addToGraph(this);
	}

	/** Retrieve node with a certain ID.
 * 	@param id Node ID.
 * 	@return Sought node or null, if non-existent. */
	public Node getNode(int id) {
		return (Node)nodeList.get(id);
	}

	/** Retrieve node from a certain position of the internal node list.
 * 	@param pos Position of the node in the internal list.
 * 	@return Sought node. */
	public Node nodeAt(int pos) {
		return (Node)nodeList.elementAt(pos);
	}

	/** Get position of a node in the internal list. */
	public int indexOf(int id) {
		return nodeList.indexOf(id);
	}

	/** Remove a node from the graph. Cooperates with Node.removeFromGraph.
 * 	@param v Node to be deleted.
 * 	@return true, if the node was in this graph, else false. */
	public boolean delNode(Node v) {
		if (v.homeGraph() == this) {
			boolean r = nodeList.delete(v.getKey()) != null;
			v.removeFromGraph();
			return r;
		}
		else {
			if (v.homeGraph() == null)
				System.out.println("DEBUG: v.homeGraph() == null");
			else
				System.out.println("DEBUG: v.homeGraph() != null");
			(new RuntimeException("Graph.delNode: falscher Graph Du Pfeife!")).printStackTrace();
			return false;
		}
	}

	/** Get number of nodes in this graph.
 * 	@return Node count. */
	public int nodeCount() {
		return nodeList.size();
	}

	/** Change the weight of an edge. If this edge does not yet exist, its weight is assumed to be 0.
 * 	@param src ID of the source node.
 * 	@param dst ID of the destination ndoe.
 * 	@param delta Value to be added to the weight. */
	public void adjustWeight(int src, int dst, int delta) {
		Node s = checkNode(src);
		Node d = checkNode(dst);
		s.adjustWeight(d, delta);
	}


	/** Retrieve the distances (in edges, regardless of their weight!) of all nodes to a certain node.
 * 	@param start Node, to which the distances shall be calculated.
 *  @return Array with the distances. An array position corresponds to the position of the node in the internal node list. The node at a certain position can be retrieved with nodeAt. The distance -1 means that the node is node reachable. */
	public int[] labelDist(int startID) {
		int level = 0;
		int dist[] = new int[nodeList.size()];
		for (int i = 0; i < dist.length; i++)
			dist[i] = -1;
		dist[nodeList.indexOf(startID)] = 0;
		boolean n = true;
		while (n) {
			n = false;
			for (int i = 0; i < dist.length; i++)
				if (dist[i] == level) {
					Node v = nodeAt(i);
					for (int j = 0; j < v.outDeg(); j++) {
						Node w = v.succAt(j).dstNode();
						int pos = nodeList.indexOf(w.getKey());
						if (dist[pos] == -1) {
							dist[pos] = level + 1;
							n = true;
						}
					}
				}
			level++;
		}
		return dist;
	}

	public double[] unidirRemove(int[] result) {
		result[0] = 0; // removed edges (weight)
		result[1] = 0; // # source nodes whose edges are removed
		result[2] = 0; // # dest nodes whose edges are removed
		result[3] = 0; // bidirectional edges (weight)
		int[] uSrc = new int[nodeList.size()];
		int[] uDst = new int[nodeList.size()];
		for (int i = 0; i < nodeList.size(); i++) {
			uSrc[i] = 0;
			uDst[i] = 0;
		}
		for (int i = 0; i < nodeList.size(); i++) {
			Node v = (Node)nodeList.elementAt(i);
			int vID = v.getKey();
			for (int j = 0; j < v.outDeg(); j++) {
				Edge e = v.succAt(j);
				Node w = e.dest;
				if (w.getSucc(vID) == null) {
					uSrc[vID]++;
					uDst[w.getKey()]++;
					result[0] += e.weight;
					v.delSuccAt(j--);
				} else {
					result[3] += e.weight;
				}
			}
		}
		int asrc = 0, adst = 0;
		for (int i = 0; i < nodeList.size(); i++) {
			if (uSrc[i] > 0) {
				result[1]++;
				asrc += uSrc[i];
			}
			if (uDst[i] > 0) {
				result[2]++;
				adst += uDst[i];
			}
		}
		double[] r = new double[2];
		r[0] = (double)asrc / (double)result[1];
		r[1] = (double)adst / (double)result[2];
		return r;
	}

	public int[] biconnectivity(int s) {
		String u = "Graph.biconnectivity():visited";
	
		int nodes = nodeList.size();
		Node ns = nodeAt(s);
	
		boolean[] aPoint = new boolean[nodes];
		for (int i = 0; i < nodes; i++)
			aPoint[i] = false;
		int biconnectivity = 0;
	
		Vector bcc = new Vector();
	
		int[] num = new int[nodes];
		for (int i = 0; i < nodes; i++)
			num[i] = -1;
		
		int[] pred = new int[nodes];
		for (int i = 0; i < nodes; i++)
			pred[i] = -1;
		
		int[] lo = new int[nodes];
		
		bcc.addElement(new Integer(s));
		int i = 0;
		int v = s;
		Node nv = ns;
		num[v] = i;
		lo[v] = i;
		
		boolean cont = true;

		while (cont) {
			int w;
			do {
				for (w = 0; (w < nv.outDeg()) && (nv.succAt(w).getLabel(u) != null); w++);
				if (w < nv.outDeg()) {
					Node nw = nv.succAt(w).dstNode();
					nv.succAt(w).setLabel(u, "");
					nw.getSucc(nv.getKey()).setLabel(u, "");
					w = indexOf(nw.getKey());
					if (num[w] < 0) {
						pred[w] = v;
						lo[w] = num[w] = ++i;
						bcc.addElement(new Integer(w));
						v = w;
						nv = nw;
					} else
						if (lo[v] > num[w])
							lo[v] = num[w];
				} else
					w = nodes;
			} while (w < nodes);
			if (pred[v] != s) {
				if (lo[v] < num[pred[v]]) {
					if (lo[pred[v]] > lo[v])
						lo[pred[v]] = lo[v];
				} else {
					int c = 1;
					boolean found = false;
					while (! found) {
						int x = ((Integer)bcc.elementAt(bcc.size() - 1)).intValue();
						c++;
						found = (x == v);
						bcc.removeElementAt(bcc.size() - 1);
					}
					aPoint[pred[v]] = true;
					if (c > 2) {
						biconnectivity += c * (c - 1);
					}
				}
			} else {
				for (cont = false, w = 0; (! cont) && (w < ns.outDeg()); w++)
					cont = (ns.succAt(w).getLabel(u) == null);
				if (cont) {
					int c = 1;
					boolean found = false;
					while (! found) {
						int x = ((Integer)bcc.elementAt(bcc.size() - 1)).intValue();
						c++;
						found = (x == v);
						bcc.removeElementAt(bcc.size() - 1);
					}
					aPoint[s] = true;
					if (c > 2) {
						biconnectivity += c * (c - 1);
					}
				}
			}
			v = pred[v];
			nv = nodeAt(v);
			for (cont = (pred[v] >= 0), w = 0; (! cont) && (w < nv.outDeg()); w++)
				cont = (nv.succAt(w).getLabel(u) == null);
		}
		
		biconnectivity += bcc.size() * (bcc.size() - 1);
		int[] rVal = new int[2];
		rVal[0] = 0;
		for (i = 0; i < nodes; i++)
			if (aPoint[i])
				rVal[0]++;
		rVal[1] = biconnectivity / 2;
		
		for (i = 0; i < nodes; i++) {
			nv = nodeAt(i);
			for (int j = 0; j < nv.outDeg(); j++)
				nv.succAt(j).removeLabel(u);
		}
		
		return rVal;
	}

	/** Copy this graph with all its nodes and edges.
 * 	@return Copy of graph. */
	public Object clone() {
		Graph g = new Graph();
		for (int i = 0; i < nodeList.size(); i++) {
			Node v = (Node)nodeList.elementAt(i);
			int vID = v.getKey();
			g.checkNode(vID);
			for (int j = 0; j < v.outDeg(); j++) {
				Edge e = v.succAt(j);
				g.adjustWeight(vID, e.dstNode().getKey(), e.weight);
			}
		}
		return g;
	}

	/** Check for cycles.
 * 	@return true, if this graph is free of cycles, else false. */
	public boolean isTree() {
		int n = nodeCount();
		byte[] marker = new byte[n];
		int dCount = 0;
		int m1 = 0, m2 = 0;