graph.java

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

		for (int i = 0; i < marker.length; i++)
			marker[i] = 0;
		while (m2 < n) {
			byte s = (m1 > 0) ? (byte)1: (byte)0;
			int i = 0;
			while (marker[i++] != s);
			Node v = nodeAt(--i);
			marker[i] = 2;
			if (m1 > 0)
				m1--;
			m2++;
			for (int j = 0; j < v.outDeg(); j++) {
				int k = indexOf(v.succAt(j).dstNode().getKey());
				if (marker[k] == 1)
					return false;
				else
					if (marker[k] == 0) {
						marker[k] = 1;
						m1++;
					}
			}
		}
		return true;
	}

    /** Delete nodes that have whether incoming nor outgoing edges.
 * 	@return Number of nodes removed. */
    public int deleteSingletons() {
		int singletons = 0;
        for (int i = 0; i < nodeCount(); i++) {
            Node n = nodeAt(i);
            if ((n.inDeg() == 0) && (n.outDeg() == 0)) {
				singletons++;
                delNode(n);
                i--;
            }
        }
		return singletons;
    }

	/** Find edge with maximum weight. */
	public Edge findMaxEdge() {
		Edge r = null;
		for (int i = 0; i < nodeList.size(); i++) {
			Node n = (Node)nodeList.elementAt(i);
			for (int j = 0; j < n.outDeg(); j++) {
				Edge e = n.succAt(j);
				if (r == null)
					r = e;
				else
					if (r.weight < e.weight)
						r = e;
			}
		}
		return r;
	}

	/** Find edge with minimum weight. */
	public Edge findMinEdge() {
		Edge r = null;
		for (int i = 0; i < nodeList.size(); i++) {
			Node n = (Node)nodeList.elementAt(i);
			for (int j = 0; j < n.outDeg(); j++) {
				Edge e = n.succAt(j);
				if (r == null)
					r = e;
				else
					if (r.weight > e.weight)
						r = e;
			}
		}
		return r;
	}

	/** Create a maximum spanning tree of this graph (expects the graph to be undirected). */
	public Graph maximumSpanningTree() {
		Heap h = new Heap(false);
		Graph tree = new Graph();
		int[] part = new int[nodeList.size()];
		for (int i = 0; i < nodeList.size(); i++) {
			Node v = (Node)nodeList.elementAt(i);
			int vID = v.getKey();
			tree.checkNode(vID);
			part[i] = i;
			for (int j = 0; j < v.outDeg(); j++) {
				Edge e = v.succAt(j);
				if (vID < e.dstNode().getKey()) // damit wir die Kanten nicht in beiden Richtungen betrachten
					h.add(e, (double)e.weight);
			}
		}
		int np = part.length; // number of partitions
		while ((h.size() > 0) && (np > 1)) {
			Edge e = (Edge)h.deleteMin();
			int vID = e.srcNode().getKey();
			int wID = e.dstNode().getKey();
			int vPos = nodeList.indexOf(vID);
			int wPos = nodeList.indexOf(wID);
			Node tv = tree.checkNode(vID);
			Node tw = tree.checkNode(wID);
			if (part[vPos] != part[wPos]) {
				tv.addSucc(tw, e.weight);
				tw.addSucc(tv, e.weight);
				int o = part[wPos];
				for (int i = 0; i < part.length; i++)
					if (part[i] == o)
						part[i] = part[vPos];
				np--;
			}
		}
		return tree;
	}

	/** Hilfsfunktion f黵 sort, vertauscht in einem Array zwei Elemente. */
	/** Number of connected components (expects undirected graph).
	@param threshold Only account for edges with a weight of at least this value. */
	public int partitions(int threshold) {
		int components = 0;
		SortedList[] s = new SortedList[2];
		s[0] = new SortedList();
		s[1] = (SortedList)nodeList.clone();
        while (s[1].size() > 0) {
    		Vector toDo = new Vector();
            Node src = (Node)s[1].deleteElementAt(0);
    		s[0].add(src);
    		toDo.addElement(src);
    		while (toDo.size() > 0) {
    			Node v = (Node)toDo.firstElement();
    			toDo.removeElementAt(0);
    			int vID = v.getKey();
    			for (int i = 0; i < v.outDeg(); i++) {
    				Edge e = v.succAt(i);
                    if (e.weight >= threshold) {
     				Node w = e.dstNode();
    	    			int wID = w.getKey();
    		    		if (s[0].indexOf(wID) == -1) {
    			    		s[0].add(w);
    				    	s[1].delete(wID);
    					    toDo.addElement(w);
        				}
                    }
    			}
            }
			components++;
            s[0] = new SortedList();
		}
		return components;
	}

	/** "Degree of separation" within this graph (expects the graph do be undirected).
	@param threshold Only account for edges with a weight of at least this value.
	@return "Degree of separation": How likely is that two randomly chosen nodes lie within the same connected component? */
	public double partdeg(int threshold) {
		double rVal = 0.0;
		SortedList[] s = new SortedList[2];
		s[0] = new SortedList();
		s[1] = (SortedList)nodeList.clone();
        while (s[1].size() > 0) {
    		Vector toDo = new Vector();
            Node src = (Node)s[1].deleteElementAt(0);
    		s[0].add(src);
    		toDo.addElement(src);
    		while (toDo.size() > 0) {
    			Node v = (Node)toDo.firstElement();
    			toDo.removeElementAt(0);
    			int vID = v.getKey();
    			for (int i = 0; i < v.outDeg(); i++) {
    				Edge e = v.succAt(i);
                    if (e.weight >= threshold) {
     				Node w = e.dstNode();
    	    			int wID = w.getKey();
    		    		if (s[0].indexOf(wID) == -1) {
    			    		s[0].add(w);
    				    	s[1].delete(wID);
    					    toDo.addElement(w);
        				}
                    }
    			}
            }
			rVal += (double)(s[0].size() * (nodeList.size() - s[0].size()));
            s[0] = new SortedList();
		}
		return rVal / (double)(nodeList.size() * (nodeList.size() - 1));
	}

	/** Retrieve connected components (expects undirected graph).
	@param threshold Only account for edges with a weight of at least this value. */
	public SortedList[] getCCs(int threshold) {
        Vector components = new Vector();
		SortedList[] s = new SortedList[2];
		s[0] = new SortedList();
		s[1] = (SortedList)nodeList.clone();
        while (s[1].size() > 0) {
    		Vector toDo = new Vector();
            Node src = (Node)s[1].deleteElementAt(0);
    		s[0].add(src);
    		toDo.addElement(src);
    		while (toDo.size() > 0) {
    			Node v = (Node)toDo.firstElement();
    			toDo.removeElementAt(0);
    			int vID = v.getKey();
    			for (int i = 0; i < v.outDeg(); i++) {
    				Edge e = v.succAt(i);
                    if (e.weight >= threshold) {
     				Node w = e.dstNode();
    	    			int wID = w.getKey();
    		    		if (s[0].indexOf(wID) == -1) {
    			    		s[0].add(w);
    				    	s[1].delete(wID);
    					    toDo.addElement(w);
        				}
                    }
    			}
            }
			components.addElement(s[0]);
            s[0] = new SortedList();
		}
		SortedList[] r = new SortedList[components.size()];
		for (int i = 0; i < r.length; i++)
			r[i] = (SortedList)components.elementAt(i);
		return r;
	}

	/** Calculate maximum flow between two nodes with the highest-label preflow-push algorithm.
 * 	@return Residual graph. */
	public static Graph maxFlow(Graph g, Node src, Node dst) {
		int srcID = src.getKey();
		int dstID = dst.getKey();
		int[] dist = g.labelDist(dst.getKey());
		int[] excess = new int[dist.length];
		Graph flowGraph = new Graph();
		for (int i = 0; i < g.nodeCount(); i++)
			flowGraph.checkNode(g.nodeAt(i).getKey());
		Graph resGraph = (Graph)g.clone();
		Heap active = new Heap(false);
		for (int i = 0; i < src.outDeg(); i++) {
			Edge e = src.succAt(i);
			int wID = e.dstNode().getKey();
			int wPos = g.indexOf(wID);
			flowGraph.adjustWeight(srcID, wID, e.weight);
			resGraph.adjustWeight(srcID, wID, -e.weight);
			resGraph.adjustWeight(wID, srcID, e.weight);
			excess[wPos] = e.weight;
			active.add(resGraph.checkNode(wID), (double)dist[wPos]);
		}
		dist[g.indexOf(srcID)] = g.nodeCount();
		while (active.size() > 0) {
			Node rv = (Node)active.deleteMin();
			int vID = rv.getKey();
			if ((vID != srcID) && (vID != dstID)) {
				int vPos = g.indexOf(vID);
				Node fv = flowGraph.checkNode(vID);
				int minDist = Integer.MAX_VALUE;
				int minDistPos = -1;
				boolean done = false;
				for (int i = 0; i < rv.outDeg(); i++) {
					Edge e = rv.succAt(i);
					Node rw = e.dstNode();
					int wID = rw.getKey();
					int wPos = g.indexOf(wID);
					int min = (e.weight < excess[vPos]) ? e.weight : excess[vPos];
					if (min > 0) {
						if (dist[vPos] == dist[wPos] + 1) {
							Node fw = flowGraph.checkNode(wID);
							int prevForeFlow = fv.getSuccWeight(wID);
							int prevBackFlow = fw.getSuccWeight(vID);
							if (prevBackFlow == 0)
								fv.adjustWeight(fw, min);
							else
								if (min <= prevBackFlow)
									fw.adjustWeight(fv, -min);
								else {
									fw.adjustWeight(fv, -prevBackFlow);
									fv.adjustWeight(fw, min - prevBackFlow);
								}
							rv.adjustWeight(rw, -min);
							rw.adjustWeight(rv, min);
							excess[vPos] -= min;
							excess[wPos] += min;
							if (excess[wPos] == min)
								active.add(rw, (double)dist[wPos]);
							if (excess[vPos] > 0)
								active.add(rv, (double)dist[vPos]);
							done = true;
							break;
						}
						else
							if (dist[wPos] < minDist) {
								minDistPos = wPos;
								minDist = dist[wPos];
							}
					}
				}
				if (! done) {
					if (minDistPos >= 0) {
						dist[vPos] = dist[minDistPos] + 1;
						active.add(rv, (double)dist[vPos]);
					}
					else {
						System.out.println("Graph.maxFlow: this is impossible: nowhere to put the flow!!");
						System.out.println("Node: " + vID);
						System.out.println("Edges in original graph: ");
						Node v = g.getNode(vID);
						for (int i = 0; i < v.inDeg(); i++)
							System.out.println(v.predAt(i));
						for (int i = 0; i < v.outDeg(); i++)
							System.out.println(v.succAt(i));
						System.out.println("Edges in flow graph: ");
						for (int i = 0; i < fv.inDeg(); i++)
							System.out.println(fv.predAt(i));
						for (int i = 0; i < fv.outDeg(); i++)
							System.out.println(fv.succAt(i));
						System.out.println("Edges in residual graph: ");
						for (int i = 0; i < rv.inDeg(); i++)
							System.out.println(rv.predAt(i));
						for (int i = 0; i < rv.outDeg(); i++)
							System.out.println(rv.succAt(i));
						System.exit(0);
					}
				}
			}
		}
		return resGraph;
	}

	/** Create the "seperator tree" of a graph (expects undirected graph). */
	public static Graph buildSeperatorTree(Graph g) {
		int nodeCount = g.nodeCount();
		// In folgendem Array wird zu jedem Knoten derjenige Knoten gespeichert, an den er im Seperator Tree angekn黳ft werden mu