Version 2 (modified by gemacke, 9 years ago) (diff)


We have several exercises that utilize Luby's algorithm for finding a maximal independent set in parallel.

Let G be the graph.

Luby's algorithm works in stages where each stage creates I, an independent set of the vertices of G (that is probably not maximal), and removes the vertices in I and all of their neighbors from G to create G'. If G' is not empty, then another stage is run on G'. The maximal independent set is the union of all the independent sets created at each stage.

In a stage the algorithm loops over all the edges in G and plays a game between the vertices of each edge that determines a loser. All losers are discarded. The remaining vertices make up an independent set.

For our exercises, we will be creating code to implement one stage of Luby's algorithm. This will give an independent set, but not necessarily a maximal independent set. The game we will play is to set the vertex with the highest degree as the loser. Ties will be broken by vertex ids where the vertex with the higher id is the loser. This is a reasonable choice for a game because choosing a vertex with high degree would take out a lot of vertices from the set making the set smaller.

Exercise 1

The file tutorial/exercise1.cpp contains the skeleton code for the exercise. Everything is written except the function find_independent_set().

template <typename Graph>
find_independent_set(Graph& g, bool* active_verts)

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.

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.

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.

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.

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: tutorial/graphs/triangle.graph and 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.

If you get stuck, an answer for exercise1.cpp is located in tutorial/exercise2.cpp.

Exercise 2

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.

Exercise 3

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.