DEMONSTRATION PROGRAM

THE INDEPENDENT SET ALGORITHM

ASHAY DHARWADKER

COPYRIGHT © 2006

http://www.dharwadker.org/independent_set

HOW TO USE THIS PROGRAM


  • Start the program:
    • Open Independent Set Algorithm.exe...
  • Input the graph:
    • From the main menu select Input File > Open graph.txt...
    • In the file graph.txt, write the number of vertices of the graph followed by the adjacency matrix of the graph. All entries must be separated by white space. Recall that the adjacency matrix of a labelled simple graph with n vertices 1, 2,..., n is an nxn matrix with entry in row i and column j equal to 1 if there is an edge connecting vertex i with vertex j and 0 otherwise. For example, if you wish to input the Petersen graph shown below
      then the number of vertices is 10 and the adjacency matrix is
       
       1 2 3 4 5 6 7 8 9 10 
      1 
      2 
      3 
      4 
      5 
      6 
      7 
      8
      9
      10      		  0 1 0 0 1 0 1 0 0 0 
       1 0 1 0 0 0 0 1 0 0 
       0 1 0 1 0 0 0 0 1 0 
       0 0 1 0 1 0 0 0 0 1 
       1 0 0 1 0 1 0 0 0 0 
       0 0 0 0 1 0 0 1 1 0 
       1 0 0 0 0 0 0 0 1 1 
       0 1 0 0 0 1 0 0 0 1 
       0 0 1 0 0 1 1 0 0 0 
       0 0 0 1 0 0 1 1 0 0 

      thus the file graph.txt should be written as
       

      graph.txt
      10
       0 1 0 0 1 0 1 0 0 0 
       1 0 1 0 0 0 0 1 0 0 
       0 1 0 1 0 0 0 0 1 0 
       0 0 1 0 1 0 0 0 0 1 
       1 0 0 1 0 1 0 0 0 0 
       0 0 0 0 1 0 0 1 1 0 
       1 0 0 0 0 0 0 0 1 1 
       0 1 0 0 0 1 0 0 0 1 
       0 0 1 0 0 1 1 0 0 0 
       0 0 0 1 0 0 1 1 0 0 

      Save the modified file graph.txt. For more examples, select Examples from the main menu.

  • Find Independent Sets of size at least k:
    • On the main dialog, input the value of k. This should be an integer less than the number of vertices of the graph. 
    • On the main dialog, press the button Find independent sets of size at least k.
    • After the computation ends, from the main menu select Output File > Open sets.txt...
  • Visualizer:
    • From the main menu select Visualizer > Start Visualizer... This opens a new dialog showing the largest independent set found by the algorithm. Note that for the vertices labeled 1, 2, ..., n, the vertex labeled  i is positioned on the unit circle at coordinates (cos(2pi / n), sin(2pi / n)). Press ESC to close the visualizer dialog.

For more details visit the website
http://www.dharwadker.org/independent set