Changes between Version 1 and Version 2 of Exercises


Ignore:
Timestamp:
04/22/10 17:28:44 (9 years ago)
Author:
gemacke
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Exercises

    v1 v2  
    2424The 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. 
    2525 
    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. 
     26Note 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. 
    2727 
    2828You 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. 
     
    3030To 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. 
    3131 
    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: 
     32The 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. 
    3733 
    3834[[Image(max_indset.jpg, align=center)]] 
     
    4137 
    4238= Exercise 2 = 
     39 
     40This 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 
     44This 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.