peoplegraph.java

这是一个matlab的java实现。里面有许多内容。请大家慢慢捉摸。

		Iterator viter = vertices.iterator();
		while (viter.hasNext()) {
			Vertex v = (Vertex) viter.next();
			Iterator eiter = getEdges (v).iterator();
			while (eiter.hasNext()) {
				Edge e = (Edge) eiter.next();
				// overwrite previous edge because we just care about value
				sortedEdges.put (betweenness.get (e.toString()), e);
			}
		}
		return ((Integer) sortedEdges.lastKey()).intValue();
	}
	
	public void printTopNBetweennessNodes (int n, HashMap betweenness) {
		if (n > getVerticesCount())
			n = getVerticesCount();
		TreeMap rankedPeople = sortPeopleByBetweenness (betweenness);
		Iterator miter = rankedPeople.keySet().iterator();
		int nprinted = 0;
		while (miter.hasNext() && nprinted < n) {
			Integer key = (Integer) miter.next();
			Vector peeps = (Vector) rankedPeople.get (key);
			System.err.println ("Betweeness=" + key);
			for (int pi=0; pi < peeps.size(); pi++) {
				if (nprinted > n)
					break;
				Person p = (Person) peeps.get (pi);
				p.printPersonalInfo();
			}
		}
	}
	
	public void printConnectedComponents () {
		forgetConnectedSets();
		Iterator iter = getConnectedSet ().iterator();
		int i=0;
		while (iter.hasNext()) {
			Set set = (Set) iter.next();
			if (set.size() > 1) {
				System.err.println ("Set " + i + ": [");
				Iterator viter = set.iterator();
				
				while (viter.hasNext()) {
					VertexImpl v = (VertexImpl) viter.next();
					Person p = (Person)v.getObject();
					System.err.print (p.getFirstName() + ",");
				}
				System.err.println ("]");
			}
			i++;
		}
	}

	public void printConnectedComponentsStatistics () {
		forgetConnectedSets();
		ArrayList components = new ArrayList (getConnectedSet());
		double sum = 0.0;
		int count = 0;
		for (int i=0; i < components.size(); i++) {
			int size = ((Set)components.get(i)).size();
			if (size > 1) {
				System.err.println ("COMPONENT " + i + " has " + (size) + " vertices");
				count++;
				sum += size;
			}
		}
		System.err.println ("Number Clusters: " + count);
		System.err.println ("Average cluster size: " + (sum / count));
	}

	/** For each vertex, calculate its "betweenness" as the some of the
	 * betweenness for all of its adjacent edges. */
	public TreeMap sortPeopleByBetweenness (HashMap edgeHash) {
		TreeMap personMap = new TreeMap ();
		Iterator viter = getVerticesIterator ();
		while (viter.hasNext()) {
			VertexImpl v = (VertexImpl)viter.next();
			int totalBetweenness=0;
			List edges = getEdges (v);
			for (int i=0; i < edges.size(); i++) {				
				Integer bt = (Integer)edgeHash.get (((EdgeImpl)edges.get(i)).toString());
				totalBetweenness += (bt == null) ? 0 : bt.intValue();
			}
			Integer key = new Integer (totalBetweenness);
			Vector peeps = (Vector) personMap.get (key);
			if (peeps == null)
				peeps = new Vector();
			peeps.add ((Person)v.getObject());
			personMap.put (key, peeps);
		}
		return personMap;
	}

	/** Sort edges by betweenness. */
	public TreeMap sortEdgesByBetweenness (HashMap edgeHash) {
		TreeMap edgeMap = new TreeMap ();
		Iterator eiter = getEdgeSet().iterator ();
		while (eiter.hasNext()) {
			Edge e = (Edge)eiter.next();
			Integer key = (Integer)edgeHash.get (e.toString());
			if (key == null)
				throw new IllegalArgumentException ("edge " + e + " not in edgeHash");
			Vector storedEdges = (Vector) edgeMap.get (key);
			if (storedEdges == null)
				storedEdges = new Vector();
			storedEdges.add (e);
			edgeMap.put (key, storedEdges);
		}
		return edgeMap;
	}

	/** Return a HashMap mapping each edge to its betweenness value,
	 * where betweenness = # shortest paths that traverse edge i */
	public HashMap getBetweennessOfEdges () {
		HashMap hash = new HashMap (getEdgesCount());
		Iterator viter = getVerticesIterator();
		ShortestPathDijkstraAlgorithm dijkstra = new ShortestPathDijkstraAlgorithm (this, new HeapNodeComparator (0));
		int vi=0;
		while (viter.hasNext()) {
			Vertex v = (Vertex)viter.next();
			WeightedGraph paths = dijkstra.shortestPath (v);
			if (paths != null && paths.getVerticesCount() != 0) // null if isolated node
				depthFirstCountBetweenness (new Stack(), v, null, hash, paths);
		}
		// we've counted the betweenness of each edge twice. now divide by
		// 2 to get actual betweenness.
		divideBy (hash, 2);
		return hash;
	}

	
	/** Divide each element of the hash by 2 */
	private void divideBy (HashMap hash, int q) {
		Iterator iter = hash.keySet().iterator();
		while (iter.hasNext()) {
			String e = (String) iter.next();
			int count = ((Integer)hash.get (e)).intValue();
			hash.put (e.toString(), new Integer (count/2));
		}
		
	}
	
	/** Traverse the shortest path graph in depth first order, keeping a
	 * stack of edges in the current path. After each step, increment
	 * the betweenness values for each edge in edgeList.*/
	private void depthFirstCountBetweenness (Stack edges, Vertex v, Vertex source, HashMap edgeCounts, WeightedGraph graph) {
		List nextEdges = graph.getEdges (v);
		if (nextEdges == null) // no new neighbors
			return;
		for (int i=0; i < nextEdges.size(); i++) {
			EdgeImpl e = (EdgeImpl) nextEdges.get (i);
			Vertex nextVertex = e.getOppositeVertex (v);
			// if a new vertex
			if (source == null || !nextVertex.equals (source)) { 
				edges.push (e);
				incrementBetweenness (edges, edgeCounts);
				depthFirstCountBetweenness (edges, nextVertex, v, edgeCounts, graph);
				edges.pop();
			}
		}
	}

	/** Increment the betweenness count for each edge in
	 * <code>edges</code>*/
	private void incrementBetweenness (Stack edges, HashMap edgeCounts) {
		Iterator iter = edges.iterator();
		while (iter.hasNext()) {
			EdgeImpl e = (EdgeImpl) iter.next();
			Integer count = (Integer)edgeCounts.get (e.toString());
			if (count == null)
				count = new Integer (0);
			edgeCounts.put (e.toString(), new Integer (count.intValue()+1));
		}
	}
	
	public TreeMap sortPeopleByDegree () {
		TreeMap map = new TreeMap();
		Iterator viter = getVerticesIterator();
		while (viter.hasNext()) {
			VertexImpl v = (VertexImpl)viter.next();
			Integer key = new Integer (getEdges (v).size());
			Vector peeps = (Vector) map.get (key);
			if (peeps == null) {
				peeps = new Vector();
			}
			peeps.add ((Person)v.getObject());
			map.put (key, peeps);			
		}
		return map;
	}
	

	public void printDegreeDistribution () {
		TreeMap map = sortPeopleByDegree ();
		Iterator miter = map.keySet().iterator();
		while (miter.hasNext()) {
			Integer key = (Integer) miter.next();
			System.err.println ("DEGREE " + key + ": " + ((Vector)map.get (key)).size());
		}		
	}

	/** rank people by degree */
	public void printPeopleByDegree () {
		TreeMap map = sortPeopleByDegree ();
		Iterator miter = map.keySet().iterator();
		while (miter.hasNext()) {
			Integer key = (Integer) miter.next();
			System.err.println ("DEGREE " + key);
			Vector peeps = (Vector) map.get (key);
			for (int pi=0; pi < peeps.size(); pi++) {
				Person p = (Person) peeps.get (pi);
				p.printPersonalInfo();
			}
		}
	}

	private static final long serialVersionUID = 1;
	private static final int CURRENT_SERIAL_VERSION = 0;
	
	private void writeObject (ObjectOutputStream out) throws IOException {
		out.writeInt (CURRENT_SERIAL_VERSION);
	}
	private void readObject (ObjectInputStream in) throws IOException, ClassNotFoundException {
		int version = in.readInt ();
	}

}