*  This file is part of the X10 project (http://x10-lang.org).
 *  This file is licensed to You under the Eclipse Public License (EPL);
 *  You may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *      http://www.opensource.org/licenses/eclipse-1.0.php
 *  (C) Copyright IBM Corporation 2006-2010.
import x10.io.File;
import x10.util.Ordered;
import x10.util.Random;
import x10.util.StringBuilder;
import x10.util.concurrent.atomic.*;
import utils.CmdLnArgs;
import utils.QSort;

 * Simple implementation of a directed graph and breadth-first search. An
 * undirected graph is simply a directed graph for which, whenever there is
 * an edge from v2 to v1, there is also one from v1 to v2.  For such graphs,
 * we wind up keeping twice as much data around as we really need, but there
 * does not seem to be a simple way to avoid it in view of how we need to
 * access the data.
 * Another thing to keep in mind is that we are really thinking in terms of
 * sparse graphs, by which we mean graphs whose mean number of edges per
 * vertex is small compared to the number of vertices.  Were the graph not
 * sparse--that is, were it dense--we would use an entirely different
 * representation, namely the graph's full adjacency matrix.
 * The goal is computing maximal spanning trees for UNDIRECTED graphs.
 * The problem is not a lot harder for directed graphs, but involves enough
 * more code that it will distract from the points we want to make here:
 * the use of interfaces to achieve generic methods, and the use of "finish"
 * at a point long distant from the code that spawns the various threads.
public class Graph1(vertices: Int, edges: Int) {
	private static type Vertex = Int;
	// For our initial aggregation of the edge set, we need both ends of each
	// edge.  We could sort worrying only about one end, because all we care
	// about is getting all vertices adjacent to a given vertex: the order we
	// get them in is irrelevant.
	private static struct Edge implements Ordered[Edge] {
		public v: Vertex;  // this is the vertex we'll sort on
	   public w: Vertex;
	   public def this(a: Vertex, b: Vertex) {
	   	v = a;
	   	w = b;
	   // the ordered interface
	   public operator this <  (that: Edge): Boolean = v<that.v || (v==that.v && w<that.w);
	   public operator this >  (that: Edge): Boolean = v>that.v || (v==that.v && w>that.w);
	   public operator this <= (that: Edge): Boolean = v<=that.v || (v==that.v && w<=that.w);
	   public operator this >= (that: Edge): Boolean = v>=that.v || (v==that.v && w>=that.w);
	   public operator - this: Edge = Edge(w, v);
	   public def toString() = ""+v+"-->"+w;
	 * as the name implies: one entry for each edge in the graph.
	 * PROGRAMMING NOTE: We keep both ends of the edge here, but we really
	 * only need to keep one vertex, because once the edges are sorted, we
	 * have an index into the edge set that tells us where the edges out of
	 * each vertex are.  For really large edge sets, the storage savings
	 * are worth the extra trouble.  If you're interested, look at Graph3.x10
	 * for one such implementation.
	public val  edgeSet:  Array[Edge](1); 
	 * an index into edgeSet: first(n) is the index of the first entry in edgeSet
	 * that is the other vertex for an edge of vertex n.
	 * PROGRAMMING NOTE: We add an entry first(vertices) as a sentinel so that
	 * for all n, (including the last one, vertices-1) the vertex n has 
	 * first(n+1)-first(n) edges.
	public val  first:    Array[Int](1); 
	// For the spanning tree calculation:
	private var treeEdge: Array[Edge](1);  // we accumulate the tree's edges here
	private var visited:  Array[AtomicBoolean](1); // tracks vertices we've processed
	private var nextInTree: AtomicInteger; // where to save the next tree edge
   private static val NOT_AN_EDGE = Edge(-1,-1); // default initial value

    * Sorts the entire edge set array and indexes it for use in the traversal.
    * @param vertices the vertices are labelled 0 through vertices-1
    * @param edgeSet as the name suggests: one entry for each edge
	public def this(vertices: Int, edgeSet: Array[Edge](1)) {
		this(vertices, edgeSet.size, edgeSet);

    * Sorts the first "edges" entries in the edge set and indexes them
	 * for use in the traversal.
    * @param vertices the vertices are labelled 0 through vertices-1
    * @param edges the number of edges: may be less than edgeSet.size
    * @param edgeSet as the name suggests: one entry for each edge
    * PROGRAMMING NOTE: Initializing the index is a two-pass algorithm.  The first
    * pass counts the edges out of each vertex v and sets the index, first(v),
    * equal to the the first entry in edgeSet for its edges.  The second pass is
    * BACKWARD over "first" itself.  It sets first(v) for any v with no edges
    * leading out of it to first(v+1).  On exit, we that for every vertex v,
    * the number of edges leading out of it is f(v+1)-f(v), and the first such
    * edge is at index first(v).
	public def this(vertices: Int, edges: Int, edgeSet: Array[Edge](1)) {
	   val firstEdge = edgeSet.region.min(0);
	   val lastEdge  = firstEdge + edges - 1;
      val qsort = new QSort[Edge]();
      qsort.quicksort(edgeSet, firstEdge, lastEdge);
 		property(vertices,  edges);
		this.edgeSet = edgeSet;
		first  = new Array[Int](vertices+1, (k: Int)=>-1);
		if (edges > 0) {
			var e: Edge = edgeSet(firstEdge);
			var v: Int = e.v;  // edges are sorted, so v is the min
			first(v) = 0;      // and it is also v's first edge
			for(var k: Int = firstEdge+1; k <=lastEdge; k++) {
				e = edgeSet(k);
				if (e.v > v) { // if so, we're starting a new vertex
					v = e.v;
					first(v) = k;
		// now fill in the entries in first for vertices with NO edges:
		var lastFirst: Int = first(vertices) = edges;
		for(var v:Int = vertices-1; v>=0; --v) {
			if (first(v) == -1) first(v) = lastFirst;
			else lastFirst = first(v);
	 * Starting from the given vertex, create a spanning tree by visting vertices
	 * breadth first.  After collecting the edges, we construct a Graph1 from them
	 * so that the edges are sorted and can be pretty-printed cleanly.
	 * @return the Graph1 representing the tree.
   public def visitAllFrom(vertex: Vertex) {
   	treeEdge = new Array[Edge](2*vertices, (k: Int) => NOT_AN_EDGE);
   	visited = new Array[AtomicBoolean](vertices, (k: Int) => new AtomicBoolean(false));
   	nextInTree = new AtomicInteger(0);
      finish visit(vertex);
      visited = null;
      val treeSize = nextInTree.get();
      val span = new Graph1(vertices, treeSize, treeEdge);
      treeEdge = null;
      return span;
    * Recursive breadth-first search marks v's children as visited and saves the
    * edges from v to any child that has not already been visited.
    * @param v the vertex from which to start
    * We are lavish here in firing off a thread for just about every vertex.  Each
    * thread saves the first new vertex it finds to handle by itself, and given the
    * short path-length per vertex spent in visit(), the thread might do well to
    * save a few more in order to amortize the start-up and tear-down cost of the
    * threads.
    * From an X10 learning point of view, the critical point here is that the 
    * "finish" that synchronizes an async may be nowhere in view, and it may
    * be coordinating asyncs spawned by asyncs to an arbitrary depth within the
    * statement it guards. 
   private def visit(var v: Vertex) {
   	while(v >= 0) {
      	val lastV: Int = first(v+1)-1;
	   	var pending: Vertex = -1;              // this thread's next vertex to try
	   	for (var nextV: Int = first(v); nextV <= lastV; nextV++) {
	   		val w = edgeSet(nextV).w;
	         val wHasBeenVisited = visited(w).getAndSet(true);
	         if (!wHasBeenVisited)  {
	         	val n = nextInTree.getAndAdd(1);
	        	   treeEdge(n) = Edge(v, w);
	         	if (pending == -1) pending = w;  // save the first w for this async
	            else async visit(w);             // others get their own async        	
	   	v = pending;
	// everything below is just here so we can exercise the code above
	 * writes out the graph as a directed graph in the following format:
	 *    The first line is "n m" where n is the number of vertices and m
	 *        is the number of edges
	 *    The remaining lines are either whitespace (the last line) or
	 *       "v [ w1 w2 ... wk ]" in which v is a vertex number and each
	 *       w is the other end of one of v's edges.
	 * @return a pretty-printed string representation of the directed graph
	public def toString(): String {
		return this.toString(true);
	 * writes out the graph either as a directed or undirected graph.
	 * The format is described in the comments to toString().  
	 * @param directed: if false, only include those edges v-->w that
	 *    satisfy v <= w.
	 * @return a pretty-printed string representation of the graph
	public def toString(directed: Boolean): String {
		val buffer = new StringBuilder();
		val actualEdges = directed ? edges : edges/2;
		buffer.add(""+vertices+" "+actualEdges+"\r\n");
		for(var v: Vertex = 0; v<vertices; v++) {
			val firstV = first(v);
			val lastV  = first(v+1) - 1;
			buffer.add(v); buffer.add(" [");
			if (firstV <= lastV) {
				if (directed) {
					for(var nextV: Int = firstV; nextV <= lastV; nextV++) {
	               buffer.add(" "+edgeSet(nextV).w); 
				else {
					for(var nextV: Int = firstV; nextV <= lastV; nextV++) {
						val w = edgeSet(nextV).w;
	               if(v <= w) buffer.add(" "+w); 
			buffer.add(" ]\r\n");
		return buffer.result();
	 * Uses a random number generator to create a directed graph that represents
	 * an undirected graph--that is, for every edge v-->w there is also an edge
	 * w-->v.
	 * @param vertices the number of vertices--we'll label them from 0 up...
	 * @param edges the number of (undirected) edges.  
	 * @param seed for the random number generator
	 * @param allowCycles if true, do NOT allow any edges from a vertex to itself
	 * @return the Graph1 constructed
	public static def makeFromRandom(vertices: Int, edges: Int, seed: Long, allowCycles: Boolean) {
		val r = new Random(seed);
		val edgeSet = new Array[Edge](2*edges, NOT_AN_EDGE);
		val size = 2*edges;
		val rnBound = 100*vertices;
		for(var k: Int = 0; k<size; k+=2) {
			val start = r.nextInt(rnBound) % vertices;
			var end: Int = r.nextInt(rnBound) % vertices;
			if(!allowCycles) while(end == start) {
				end = r.nextInt(rnBound)%vertices;
			edgeSet(k) = Edge(start, end);
			edgeSet(k+1) = Edge(end, start);
      return new Graph1(vertices, edgeSet);
	 * Reads a file whose contents are identical with the output of our
	 * toString method.
	 * @param path the location of the file read in.
	 * @return the Graph1 constructed
	public static def makeFromFile(path: String) {
      val inputFile  = path;
      val I  = new File(inputFile);
      val lines = I.lines();
      val firstLine = lines.next().trim().split(" ");
      val vertices = Int.parseInt(firstLine(0));
      val edges = Int.parseInt(firstLine(1));
		val edgeSet = new Array[Edge](edges);
		var k: Int = 0;
      while(lines.hasNext()) {
         val whole = lines.next().trim().split("[");
         if (whole.length < 2) continue;
         val v = Int.parseInt(whole(0).trim());
         val ender = whole(1).indexOf(']');
         val wSet = whole(1).substring(0, ender).trim().split(" ");
         for(var n: Int=0; n<wSet.length; n++) {
         	val w = Int.parseInt(wSet(n));
   			edgeSet(k++) = Edge(v, w);
      return new Graph1(vertices, edgeSet);
	 * Constructs a graph and finds the maximal tree starting from some
	 * one vertex. The command line parameters are:
	 * For reading from a file:
	 *     -f path   use the file named by path as input for the graph
	 * For a graph with random edges:
	 *     -v nnn    how many vertices: default is 10
	 *     -e nnn    how many edges: default is 30
	 *     -s nnn    the seed for the random number generator: default is 127
	 * General:
	 *     -v0 nnn   use nnn as the starting vertex: default is 0
	 *     -in bbb   if bbb is true, write the input graph to the console
	 *     -out bbb  if bbb is true, write the output graph to the console
	 *     -both bbb if bbb is true, write both the graphs to the console
	 * nnn is an integer, and bbb is a boolean: any of the strings "yes", "no",
	 * "1", "0", "true", or "false".  The default is to show only the output,
   public static def main(args: Array[String](1)): Void {
      try {
      	val g: Graph1;
         val argsHash = new CmdLnArgs(args);
         if (argsHash.isKey("f")) {
         	val path = argsHash.getFirstValue("f");
         	g = makeFromFile(path);
         else {
         	val vertices = argsHash.getInt("v", 10);
         	val edges = argsHash.getInt("e", 15); // will double with back edges
         	val seed =  argsHash.getInt("s", 127);
         	val allowCycles = argsHash.getBoolean("c", false);
         	g = makeFromRandom(vertices, edges, seed, allowCycles);
         val start    = argsHash.getInt("v0", 0);
         val tree     = g.visitAllFrom(start);
         val showBoth = argsHash.getBoolean("both", false);
         val showIn   = argsHash.getBoolean("in", false) || showBoth;
         val showOut  = argsHash.getBoolean("out", true) || showBoth;
         if (showIn)   Console.OUT.println(g);
         if (showBoth) Console.OUT.println("\r\n===============\r\n");
         if (showOut)  Console.OUT.println(tree);
      catch(e: Exception) {