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

Exercises
v2 v3 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 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. 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. Note that the answer from the exercise may not be the maximal independent set because the exercise is to perform only one stage of Luby's algorithm. 33 33 34 34 [[Image(max_indset.jpg, align=center)]]