graph.java

p2p仿真

/**
 * @(#)Graph.java	ver 1.2  6/20/2005
 *
 * Modified by Weishuai Yang ([e-mail]). 
 * 
 * GT-ITM file parser
 *
 * this file is based on KOM / LetsQoS Topology Conversion Tools
 */

package gps.network.graph;

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * graph is an object representing network topology.
 * 
 * this file is based on KOM / LetsQoS Topology Conversion Tools.
 *
 * Two ways to add a node:
 * Instanciate a Node object and call graph.addNode() to get back the key of the node.
 * Or call graph.newNode() to get back a new node that is already added to the graph.
 *
 * Same for adding new links.
 * @author Oliver Heckmann
 */
public class Graph {
    /**
     * all nodes
     */
	private List nodes = new LinkedList();
	/**
	 * all links
	 */
	private List links = new LinkedList();

	// Meta information about the graph
	/**
	 * graph comment
	 */
	String comment;
	/**
	 * graph creator
	 */
	String creator;
	/**
	 * graph file path
	 */
	String graphfile;
	
	/**
	 * graph validity
	 */
	private boolean valid=true;

	/** Creates new Graph */
	public Graph() {
	}

	/**
	 * gets file path
	 * @return file path
	 */
	public String getGraphFile(){
		return graphfile;
	}
	/**
	 * sets file path
	 * @param f file path
	 */
	public void setGraphFile(String f){
		graphfile=f;
	}

	/**
	 * check validity
	 * @return true if valid
	 */
	public boolean isValid(){
	    return valid;
	}
	/**
	 * gets comment
	 * @return comment
	 */
	public String getComment() {
		return comment;
	}
	/**
	 * sets comment
	 * @param comment new comment
	 */
	public void setComment(String comment) {
		this.comment = comment;
	}
	/**
	 * gets creator
	 * @return creator
	 */
	public String getCreator() {
		return creator;
	}
	/**
	 * sets creator
	 * @param creator new creator
	 */
	public void setCreator(String creator) {
		this.creator = creator;
	}

	// *************************** Node handling

	/**
	 * add a node to the graph
	 * @param n new node
	 * @return node id
	 */
	public int addNode(Node n) {
		int key = nodes.size();
		nodes.add(key, n);
		n.setKey(key);
		return key;
	}

	/** creates a new Node that is already element of the graph 
	 * (no need to call addNode())
	 * @return the new node
	 */
	public Node newNode() {
		Node ret = new Node();
		addNode(ret);
		return ret;
	}

	/**
	 * Retrieve a node
	 * @param key node id
	 * @return node
	 */
	public Node getNode(int key) {
		return (Node) nodes.get(key);
	}

	/**
	 * gets number of nodes
	 * @return number of nodes
	 */
	public int getNumberOfNodes() {
		return nodes.size();
	}

	// ******************************* Link handling
	/**
	 * adds undirected link
	 * @param fromNode source node
	 * @param toNode destination node
	 * @return link
	 */
	public Link newUndirectedLink(int fromNode, int toNode) {
		Link ret = new Link(false, fromNode, toNode);
		addLink(ret);
		return ret;
	}
	/**
	 * adds directed link
	 * @param fromNode source node
	 * @param toNode destination node
	 * @return link
	 */
	public Link newDirectedLink(int fromNode, int toNode) {
		Link ret = new Link(true, fromNode, toNode);
		addLink(ret);
		return ret;
	}

	/**
	 * add link
	 * @param l link
	 * @return the key of the link
	 */
	public int addLink(Link l) {
		int key = links.size();
		links.add(key, l);
		return key;
	}

	/**
	 * gets link
	 * @param key key of the link
	 * @return link
	 */
	public Link getLink(int key) {
		return (Link) links.get(key);
	}

	/**
	 * gets number of links
	 * @return number of links
	 */
	public int getNumberOfLinks() {
		return links.size();
	}

	// ********************************** Sets of nodes and links
	/**
	 * gets all links
	 * @return array of link
	 */
	public Link[] getAllLinks() {
		Object[] na = links.toArray();
		Link[] ret = new Link[na.length];
		for (int i = 0; i < ret.length; i++) {
			ret[i] = (Link) na[i];
		}
		return ret;
	}

	/**
	 * 
	 * gets all undirected links
	 * @return array of undirected links
	 */
	private Link[] getAllUndirectedLinks() {
		List ret = new LinkedList();
		Iterator it = links.iterator();
		while (it.hasNext()) {
			Link l = (Link) it.next();
			if (!l.isDirected())
				ret.add(l);
		}
		Link[] reta = new Link[ret.size()];
		for (int i = 0; i < reta.length; i++) {
			reta[i] = (Link) ret.get(i);
		}
		return reta;
	}

	/**
	 * gets all directed links
	 * @return array of directed links
	 */
	private Link[] getAllDirectedLinks() {
		List ret = new LinkedList();
		Iterator it = links.iterator();
		while (it.hasNext()) {
			Link l = (Link) it.next();
			if (l.isDirected())
				ret.add(l);
		}
		Link[] reta = new Link[ret.size()];
		for (int i = 0; i < reta.length; i++) {
			reta[i] = (Link) ret.get(i);
		}
		return reta;
	}

	/**
	 * gets all nodes
	 * @return array of nodes
	 */
	public Node[] getAllNodes() {
		Object[] na = nodes.toArray();
		Node[] ret = new Node[na.length];
		for (int i = 0; i < ret.length; i++) {
			ret[i] = (Node) na[i];
		}
		return ret;
	}


	/**
	 * converting the graph into a human readable string
	 * @return string description of the graph
	 */
	public String toString() {
		String ret =
			"number of nodes: " + this.getNumberOfNodes() + "\nnumber of links: " + this.getNumberOfLinks() + "\n";
		Node[] nodes = this.getAllNodes();
		for (int i = 0; i < nodes.length; i++) {
			ret += nodes[i].toString() + "\n";
		}
		Link[] links = this.getAllLinks();
		for (int i = 0; i < links.length; i++) {
			ret += links[i].toString() + "\n";
		}
		return ret;
	}

	/**
	 * Read from a file in the GML topology file format
	 * @param filename file name
	 * @return graph object
	 */
	public static Graph fromGMLFile(String filename) throws IOException, GraphException {
		return fromGMLFile(new BufferedInputStream(new FileInputStream(filename)));
	}
	
	
	/**
	 * Read from a file in the GML topology file format
	 * @param file File object
	 * @return graph object
	 */
	public static Graph fromGMLFile(File file) throws IOException, GraphException {
		return fromGMLFile(new BufferedInputStream(new FileInputStream(file)));
	}
	
	/**
	 * Read from a file in the GML topology file format
	 * @param r buffered input stream
	 * @return graph object
	 * @throws IOException
	 * @throws GraphException
	 */
	public static Graph fromGMLFile(BufferedInputStream r) throws IOException, GraphException {
		return GMLReader.readGraph(r);
	}

	/**
	 * write to a file in the GML topology file format
	 * @param filename file name
	 */
	public void writeToGML(String filename) throws IOException, GraphException {
		writeToGML(new File(filename));
	}

	/**
	 * write to a file in the GML topology file format
	 * @param f File object
	 */
	public void writeToGML(File f) throws IOException, GraphException {
		BufferedWriter bwriter = new BufferedWriter(new FileWriter(f));
		bwriter.write("graph [");
		bwriter.newLine();

		if ((comment != null) && (!comment.equals(""))) {
			bwriter.write("\tcomment \"" + comment + "\"");
			bwriter.newLine();
		}
		if ((creator != null) && (!creator.equals(""))) {
			bwriter.write("\tcreator \"" + creator + "\"");
			bwriter.newLine();
		}
		Node[] nodes = this.getAllNodes();
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i] != null) {
				bwriter.write("\tnode [");
				bwriter.newLine();
				bwriter.write("\t\tid " + nodes[i].getKey());
				bwriter.newLine();
				if ((nodes[i].getProperties().getLabel() != null)
					&& (!nodes[i].getProperties().getLabel().equals(""))) {
					bwriter.write("\t\tproperties \"" + nodes[i].getProperties().getLabel() + "\"");
					bwriter.newLine();
				}
				if ((nodes[i].getProperties().getTraffic() != null)
					&& (!nodes[i].getProperties().getTraffic().equals(""))) {
					bwriter.write("\t\ttraffic \"" + nodes[i].getProperties().getTraffic() + "\"");
					bwriter.newLine();
				}
				bwriter.write("\t\ttype " + nodes[i].getProperties().getType());
				bwriter.newLine();
				bwriter.write("\t\tgraphics [");
				bwriter.newLine();
				bwriter.write("\t\t\tcenter [");
				bwriter.newLine();
				bwriter.write("\t\t\t\tx " + nodes[i].getProperties().getX());
				bwriter.newLine();
				bwriter.write("\t\t\t\ty " + nodes[i].getProperties().getY());
				bwriter.newLine();

				bwriter.write("\t\t\t]");
				bwriter.newLine();
				bwriter.write("\t\t]");
				bwriter.newLine();
				bwriter.write("\t]");
				bwriter.newLine();
			}
		}
		Link[] links = this.getAllDirectedLinks();
		for (int i = 0; i < links.length; i++) {
			writeGMLLink(bwriter, links[i]);
		}
		links = this.getAllUndirectedLinks();
		for (int i = 0; i < links.length; i++) {
			writeGMLLink(bwriter, links[i]);
		}
		bwriter.write("]");
		bwriter.close();
	}

	private void writeGMLLink(BufferedWriter bwriter, Link link) throws IOException {
		if (link != null) {
			bwriter.write("\tedge [");
			bwriter.newLine();
			if (link.getProperties().getDirection()) {
				bwriter.write("\t\tsimplex 1");
				bwriter.newLine();
			} else {
				bwriter.write("\t\tsimplex 0");
				bwriter.newLine();
			}
			if ((link.getProperties().getLabel() != null) && (!link.getProperties().getLabel().equals(""))) {
				bwriter.write("\t\tproperties \"" + link.getProperties().getLabel() + "\"");
				bwriter.newLine();
			}
			if (link.getProperties().getBandwidth() > 0) {
				bwriter.write("\t\tbandwidth " + link.getProperties().getBandwidth());
				bwriter.newLine();
			}
			if (link.getProperties().getDelay() > 0) {
				bwriter.write("\t\tdelay " + link.getProperties().getDelay());
				bwriter.newLine();
			}
			if (link.getProperties().getDistance() > 0) {
				bwriter.write("\t\tdistance " + link.getProperties().getDistance());
				bwriter.newLine();
			}
			if (link.getProperties().getCosts() > 0) {
				bwriter.write("\t\tcosts " + link.getProperties().getCosts());
				bwriter.newLine();
			}
			bwriter.write("\t\tsource " + link.fromNode());
			bwriter.newLine();
			bwriter.write("\t\ttarget " + link.toNode());
			bwriter.newLine();