graph.java

p2p仿真

		// read first character of every line as char
		char firstLetter = a.charAt(0);
		if (firstLetter == '#' /*|| firstLetter == '\r\n' */
			) {
			return true;
		} else {
			return false;
		}
	}

	private static boolean isVertexLine(String a) {
		StringTokenizer t = new StringTokenizer(a); //cut string
		int numOfTokens = 0;
		while (t.hasMoreTokens()) {
			numOfTokens = numOfTokens + 1;
			t.nextToken();
		}
		// Decide whether a line contains nodes or edges information by the number of tokens
		if ((numOfTokens == 4) & (isCommentLine(a) == false)) {
			return true;
		} else {
			return false;
		}
	}

	private static boolean isEdgeLine(String a) {
		StringTokenizer t = new StringTokenizer(a); //cut string
		int numOfTokens;
		numOfTokens = 0;
		while (t.hasMoreTokens()) {
			numOfTokens = numOfTokens + 1;
			t.nextToken();
		}
		// seven tokens are in lines with edges information
		if ((numOfTokens == 7) & (isCommentLine(a) == false)) {
			return true;
		} else {
			return false;
		}
	}

} //end TIERSReader

/**
 * Class to read INET files of the INET Generator
 */ 
class INETReader {
	final static int MAXNODES = 100000;
	public static Graph readGraph(BufferedReader line) throws IOException, GraphException {
		Graph g = new Graph();
		String aktLine;
		int[] keyList = new int[MAXNODES];
		int nodeCount = 0; //number of nodes
		int edgeCount = 0; // number of edges
		int checkNodeCount = 0;
		int checkEdgeCount = 0;
		int count = -1; //counter
		int times = 0;

		while ((aktLine = line.readLine()) != null) { //till there is no line left

			//empty line
			if (aktLine.length() == 0) {
				continue;
			} // then do nothing - next line
			//Comment line
			if (aktLine.charAt(0) == '#') {
				continue;
			} // do nothing - next line

			if (count == -1) {
				StringTokenizer t = new StringTokenizer(aktLine); //cut String into token
				checkNodeCount = Integer.parseInt(t.nextToken()); //first token is the number of nodes
				checkEdgeCount = Integer.parseInt(t.nextToken()); //second token is the number of edges
				times = checkNodeCount + checkEdgeCount;
				count++;
				continue;
			};

			//Nodes
			if (count < checkNodeCount) {
				StringTokenizer t = new StringTokenizer(aktLine); // cut String
				int nodeID = Integer.parseInt(t.nextToken()); //analyse first token
				if (nodeID != count) {
					int fileLine = count + 2;
					System.out.println("Warning: File contains suspicious node ID at line: " + fileLine);
				}
				double x = Double.parseDouble(t.nextToken()); //second token
				double y = Double.parseDouble(t.nextToken()); //third token
				Node n = new Node();
				int key = g.addNode(n);
				keyList[nodeCount++] = key;
				n.getProperties().setX(x);
				n.getProperties().setY(y);
				n.getProperties().setType(NodeProperties.CORE_NODE);
				count++;
				continue;
			}
			//Edges
			if ((checkNodeCount <= count) && (count < times)) {
				StringTokenizer t = new StringTokenizer(aktLine); //cut String
				int sourceID = Integer.parseInt(t.nextToken()); //first token
				if ((checkNodeCount == count) && (sourceID != 0)) {
					throw new GraphException("Error: Invalid number of nodes declared or node 0 is not connected");
				}
				int destinationID = Integer.parseInt(t.nextToken()); //second token
				double weight = Double.parseDouble(t.nextToken()); //third token weight not cosidered
				if (sourceID > nodeCount) {
					throw new GraphException("Invalid nodeId" + sourceID);
				}
				if (destinationID > nodeCount) {
					throw new GraphException("Invalid nodeId" + destinationID);
				}
				Link l = new Link(false, keyList[sourceID], keyList[destinationID]);
				edgeCount++;
				g.addLink(l);
				count++;
				continue;
			};
			if (times <= count) {
				throw new GraphException("Error: Wrong File Format Type INET: More lines than nodes and edges declared.");
			};
		} // end while

		//Check if checkNodeCount is equal to nodeCount
		if (checkNodeCount != nodeCount) {
			throw new GraphException("File Format Type: wrong number of vertices declared! ");
		}

		//Check if checkEdgecount is equal to edgeCount
		if (checkEdgeCount != edgeCount) {
			throw new GraphException("File Format Type: wrong number of edges declared!");
		};
		return g;
	} //end public static
} //end INETReader

// Class to read GTTS files
//is identic with the ALTReader

/**
 * Class to read NLANR files of the NLANR
 */ 
class NLANRReader {
	final static int MAXNODES = 100000;
	public static Graph readGraph(BufferedReader line) throws IOException, GraphException {
		Graph g = new Graph();
		String aktLine;
		int[] keyList = new int[MAXNODES];
		int nodeCount = 0; // number of nodes
		int edgeCount = 0; // number of edges
		String[] link = new String[MAXNODES];
		int[] idList = new int[MAXNODES];
		int count = 1;
		//nodes
		while ((aktLine = line.readLine()) != null) { // until the last line
			if (aktLine.length() == 0) {
				continue;
			} //empty line
			if (aktLine.charAt(0) == '#') {
				continue;
			} //comment line
			switch (aktLine.charAt(0)) {
				case '0' :
				case '1' :
				case '2' :
				case '3' :
				case '4' :
				case '5' :
				case '6' :
				case '7' :
				case '8' :
				case '9' :
					StringTokenizer t = new StringTokenizer(aktLine); //cut string t
					int nodeID = Integer.parseInt(t.nextToken()); //first token - node ID
					String trash = t.nextToken(); //second token is "->"
					int degree = Integer.parseInt(t.nextToken()); //third token is the outdegree of the node
					link[count] = t.nextToken(); //fourth token contains all linked nodes
					idList[count] = nodeID;
					count++;
					Node n = new Node();
					int key = g.addNode(n);
					n.getProperties().setType(NodeProperties.CORE_NODE); //all nodes represent an AS
					keyList[nodeCount++] = key;
					break;
				default :
					throw new GraphException("Wrong File Format Type NLANR at Line 1100 ");
			}
		} //while nodes

		//edges
		for (int i = 1; i < count; i++) {
			StringTokenizer c = new StringTokenizer(link[i], ":"); //cut string links at ':'
			for (int d = 0;(d < c.countTokens()); d++) {
				int target = Integer.parseInt(c.nextToken());
				int nodeID = idList[i];
				if (nodeID > idList[count - 1]) {
					throw new GraphException("Invalid nodeId (source) " + nodeID);
				}
				if (target > idList[count - 1]) {
					throw new GraphException("Invalid nodeId (target) " + target);
				}
				Link l = new Link(false, keyList[nodeID], keyList[target]);
				g.addLink(l);
				edgeCount++;
			}
		};
		return g;
	} // end Graph
} // end class NLANRReader


/**
 * Class to read CSV files
 */
class CSVReader {
	final static int MAXNODES = 100000;
	public static Graph readGraph(BufferedReader line) throws IOException, GraphException {
		Graph g = new Graph();
		String aktLine;
		int[] keyList = new int[MAXNODES];
		int nodeCount = 0; //number of nodes
		int edgeCount = 0; // number of edges
		int checkNodeCount = 0;
		int checkEdgeCount = 0;
		int count = -3; //counter
		int times = 0;
		String[] link = new String[MAXNODES];
		String[] band = new String[MAXNODES];
		int[] idList = new int[MAXNODES];

		while ((aktLine = line.readLine()) != null) { //till there is no line left
			//empty line
			if (aktLine.length() == 0) {
				continue;
			} // then do nothing - next line
			//Comment line
			if (aktLine.charAt(0) == '#') {
				continue;
			} // do nothing - next line
			//Info
			if (count == -3) { //contains plainsize
				count++;
				continue;
			};
			if (count == -2) { //contains number of nodes
				StringTokenizer t = new StringTokenizer(aktLine, ","); // cut String
				checkNodeCount = Integer.parseInt(t.nextToken()); //analyse first token
				count++;
				continue;
			};
			if (count == -1) { //contains number of edges
				StringTokenizer t = new StringTokenizer(aktLine, ","); // cut String
				checkEdgeCount = Integer.parseInt(t.nextToken()); //analyse first token
				times = checkEdgeCount + checkNodeCount;
				count++;
				continue;
			};

			//Nodes
			if (count < checkNodeCount) {
				StringTokenizer t = new StringTokenizer(aktLine, ","); // cut String
				int nodeID = Integer.parseInt(t.nextToken()); //analyse first token
				if (nodeID != count) {
					int fileLine = count + 2;
					System.out.println("Warning: File contains suspicious node ID at line: " + fileLine);
				}
				idList[count + 1] = nodeID;
				String trash = t.nextToken(); //second token contains the name
				double x = Double.parseDouble(t.nextToken()); //third token contains x
				double y = Double.parseDouble(t.nextToken()); //fourth token contains y
				int type = Integer.parseInt(t.nextToken()); //fifth token contains type
				link[count + 1] = t.nextToken(); //sixth token contains the links
				band[count + 1] = t.nextToken(); //eighth token contains the bandwidths
				Node n = new Node();
				int key = g.addNode(n);
				keyList[nodeCount++] = key;
				n.getProperties().setX(x);
				n.getProperties().setY(y);
				n.getProperties().setType(type);
				count++;
				continue;
			}
			if (count >= checkNodeCount) {
				StringTokenizer t = new StringTokenizer(aktLine, ","); // cut String
				if (t.countTokens() != 0) {
					System.out.println("Warning: Found more nodes than declared");
					System.out.println(" That may cause File Format Type Errors.");
				}
			}

		} // end while

		//Check if checkNodeCount is equal to nodeCount
		if (checkNodeCount != nodeCount) {
			if (checkNodeCount > nodeCount) {
				System.out.println("Warning: Found less nodes than declared");
			}

			//throw new GraphException("File Format Type: wrong number of vertices declared! ");
		}

		for (int i = 1; i <= count; i++) { //read out the link information
			//Edges
			StringTokenizer edges = new StringTokenizer(link[i], "-"); //cut String
			StringTokenizer bw = new StringTokenizer(band[i], "-");
			int degree = edges.countTokens();
			for (int d = 0; d < degree; d++) {
				try {
					int destinationID = Integer.parseInt(edges.nextToken());
					int sourceID = idList[i];
					if (sourceID > nodeCount) {
						throw new GraphException("Invalid nodeId" + sourceID);
					}
					if (destinationID > nodeCount) {
						throw new GraphException("Invalid nodeId" + destinationID);
					}
					Link l = new Link(true, keyList[sourceID], keyList[destinationID]);
					l.getProperties().setBandwidth(Double.parseDouble(bw.nextToken()));
					edgeCount++;
					g.addLink(l);
				} catch (Exception el) {
					System.out.println("check the number of links and bandwidth in line:" + idList[i]);
					el.printStackTrace();
				}
			} //end for d
		} // end for i

		//Check if checkEdgecount is equal to edgeCount
		if (checkEdgeCount != edgeCount) {
			System.out.println("Warning: wrong number of edges declared");
			//throw new GraphException("File Format Type: wrong number of edges declared!");
		};
		return g;
	} //end public static
} //end CSVReader

/**
 * gml lexer
 */
class GMLlexer {
	public static int GMLstring = 256;
	public static int GMLinteger = 257;
	public static int GMLreal = 258;
	public static int GMLeof = 259;
	public static int GMLkey = 260;

	private InputStream stream_;
	private int linenumber_ = 0;
	private int nextChar_ = '\n';

	private String stringval_;
	private double doubleval_;

	private int tokenType_;

	public GMLlexer(InputStream streamin) {
		stream_ = streamin;
	}

	public int nextToken() throws IOException {
		skipWhitespace_();

		if ((nextChar_ >= 'a' && nextChar_ <= 'z') || (nextChar_ >= 'A' && nextChar_ <= 'Z'))
			// Key
			{
			stringval_ = "";
			int index = 0;
			while ((nextChar_ >= 'a' && nextChar_ <= 'z')
				|| (nextChar_ >= 'A' && nextChar_ <= 'Z')
				|| (nextChar_ >= '0' && nextChar_ <= '9')) {
				stringval_ += String.valueOf((char) nextChar_);
				nextChar_ = stream_.read();
			}
			return (tokenType_ = GMLkey);
		} else if (nextChar_ == '-' || (nextChar_ >= '0' && nextChar_ <= '9')) {
			// Number
			double fracval = 0, expval = 0, intval = 0;
			boolean havefrac = false, haveexp = false, isneg = false, expisneg = false;

			if (nextChar_ == '-') {
				isneg = true;
				nextChar_ = stream_.read();
				if (nextChar_ < '0' || nextChar_ > '9'); // throw a parse warning
			}

			while (nextChar_ >= '0' && nextChar_ <= '9') {
				intval = intval * 10 + nextChar_ - '0';
				// Add check here later for overflow.
				nextChar_ = stream_.read();
			}

			if (nextChar_ == '.') {
				havefrac = true;
				nextChar_ = stream_.read();
				// Accepts no digits after decimal.
				while (nextChar_ >= '0' && nextChar_ <= '9') {
					fracval = (fracval + (double) (nextChar_ - '0')) / 10.0;
					nextChar_ = stream_.read();
				}
			}

			if (nextChar_ == 'e' || nextChar_ == 'E') {
				stream_.mark(3);
				nextChar_ = stream_.read();
				if (nextChar_ < '0' && nextChar_ > '9' && nextChar_ != '-' && nextChar_ != '+')
					stream_.reset();
				else {
					if (nextChar_ == '+' || nextChar_ == '-') {
						if (nextChar_ == '-')
							expisneg = true;
						nextChar_ = stream_.read();
					}

					if (nextChar_ < '0' && nextChar_ > '9')
						stream_.reset();
					else {
						haveexp = true;

						while (nextChar_ >= '0' && nextChar_ <= '9') {
							expval = expval * 10.0 + (double) (nextChar_ - '0');
							nextChar_ = stream_.read();
						}
					}
				}
			}
			doubleval_ = intval;
			if (havefrac)
				doubleval_ += fracval;
			if (isneg)
				doubleval_ = -doubleval_;
			if (expisneg)
				expval = -expval;
			if (haveexp)
				doubleval_ *= Math.pow(10.0, expval);

			if (!havefrac && !haveexp)
				return (tokenType_ = GMLinteger);
			return GMLreal;