Changes between Version 2 and Version 3 of Exercises


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

--

Legend:

Unmodified
Added
Removed
Modified
  • Exercises

    v2 v3  
    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 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. 
     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.  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. 
    3333 
    3434[[Image(max_indset.jpg, align=center)]]