Changes between Version 1 and Version 2 of Exercises
 Timestamp:
 04/22/10 17:28:44 (9 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Exercises
v1 v2 24 24 The function takes a graph and a boolean array that will return the resulting independent set. The boolean array active_verts is an uninitialized array of size of the number of vertices in g and indexed by vertex id. True indicates the vertex is in the set. You will need to initialize active_verts to all true indicating that all vertices are initially in the independent set. As you examine edges, you will set losers' entries in active_verts to false. 25 25 26 Note that no locking needs to be performed. Since we start with all vertices as winners and set them to losers, we can get a smaller independent set than if we used locking. But, this is okay because we just want an independent set . A slightly smaller one is okay.26 Note that no locking needs to be performed. Since we start with all vertices as winners and set them to losers, we can get a smaller independent set than if we used locking. But, this is okay because we just want an independent set, not a maximal one. A slightly smaller one is okay. 27 27 28 28 You can potentially get a larger independent set and do less work if you only play the game for edges that have both vertices still in the independent set. Since you are skipping some edges, you might as well skip self loops as well. They don't have any clear cut meaning with regard to independent sets, so we will just ignore them. … … 30 30 To loop over all the edges, we will use the two level loop construct described in FirstMtglExample. The outer loop iterates over all the vertices in g and the inner loop iterates over all of the adjacencies of each vertex. Since we don't actually need the edges, this is probably more efficient as long as the compiler will collapse the two loops. Our game is simple enough that this is possible. 31 31 32 The main function reads in a graph from standard input just like the examples in FirstMtglExample. It initializes the graph, prints the graph, calls find_independent_set(), and prints out the independent set. There are two input graphs: [source:trunk/tutorial/graphs/triangle.graph tutorial/graphs/triangle.graph] and [source:trunk/tutorial/graphs/indset.graph tutorial/graphs/indset.graph]. The file triangle.graph is the simple triangle graph from FirstMtglExample. The graph in indset.graph is a slightly bigger graph shown in the following diagram. 33 34 [[Image(indset.jpg, align=center)]] 35 36 For comparison purposes, the maximal independent set for this graph is: 32 The main function reads in a graph from standard input just like the examples in FirstMtglExample. It initializes the graph, prints the graph, calls find_independent_set(), and prints out the independent set. There are two input graphs: [source:trunk/tutorial/graphs/triangle.graph tutorial/graphs/triangle.graph] and [source:trunk/tutorial/graphs/indset.graph tutorial/graphs/indset.graph]. The graph in triangle.graph is the simple triangle graph from FirstMtglExample. The graph in indset.graph is a slightly bigger graph and is shown in the following diagram. The vertices with red borders represent the maximal independent set of the graph. 37 33 38 34 [[Image(max_indset.jpg, align=center)]] … … 41 37 42 38 = Exercise 2 = 39 40 This exercise builds upon Exercise 1 and changes the I/O to read a srcs / dests file format using read_binary() in mtgl_io.hpp. There are srcs / dests files provided in tutorial/graph/ for the triangle and independent set graphs. They are of endianness for the XMT. 41 42 = Exercise 3 = 43 44 This exercise builds upon Exercise 2. The student should use a property map instead of an array for the active verts. The student should also iterate over all the edges using an edge iterator instead of iterating over all the vertices and their adjacencies.