/* * 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); visited(vertex).set(true); 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 * * PROGRAMMING NOTES: * 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) { e.printStackTrace(Console.ERR); } } }