import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Scanner;

/**
 * Class to find the maximal independent set from the give graph matrix Solves
 * CS255 homework assignment #3
 *
 * @author SJSU Students
 * @version 1.00 2015/04/03
 *
 */
public class ParallelMIS
{
   /**
    * Read the values from the text file and store it in 2D matrix form
    *
    * @param fileName filename along with path of text file
    */
   public static void readGraph(String fileName)
   {
      File f = new File(fileName);
      Scanner sc = null;
      ArrayList<String[]> al = new ArrayList<String[]>();
      int matSize = 0;
      try
      {
         sc = new Scanner(f);
      }
      catch (FileNotFoundException e1)
      {
         System.out.println("File Not found at specified path");
         e1.printStackTrace();
      }
      while (sc.hasNextLine())
      {
         matSize++;
         al.add(sc.nextLine().split(" "));
      }
      graphMatrix = new int[matSize][matSize];
      for (int i = 0; i < matSize; i++)
      {
         String[] s = al.get(i);
         int degreeCount = 0;
         for (int j = 0; j < matSize; j++)
         {
            graphMatrix[i][j] = Integer.parseInt(s[j]);
            if (graphMatrix[i][j] == 1)
            {
               degreeCount++;
            }
         }
         hMapNodeDegree.put(i, degreeCount);
      }
      sc.close();
   }

   public static void main(String args[])
   {
      readGraph(args[0]);

      while (hMapNodeDegree.size() != 0)
      {
         independentSetForRound = new HashSet<Integer>();
         boolean isAddVertex = false;
         boolean isVertexMarker = true;
         int startIndex = 0;
         int endIndex = graphMatrix[0].length - 1;

         EdgeMarkThread markeVertex = new EdgeMarkThread(isAddVertex,
               isVertexMarker, startIndex, endIndex);
         markeVertex.start();
         try
         {
            markeVertex.join();
         }
         catch (InterruptedException e)
         {
            e.printStackTrace();
         }

         isVertexMarker = false;
         EdgeMarkThread tm = new EdgeMarkThread(isAddVertex, isVertexMarker,
               startIndex, endIndex);
         tm.start();
         try
         {
            tm.join();
         }
         catch (InterruptedException e)
         {
            e.printStackTrace();
         }

         isAddVertex = true;
         isVertexMarker = false;
         EdgeMarkThread addVertex = new EdgeMarkThread(isAddVertex,
               isVertexMarker, startIndex, endIndex);
         addVertex.start();
         try
         {
            addVertex.join();
         }
         catch (InterruptedException e)
         {
            e.printStackTrace();
         }

         identifiedSet.addAll(independentSetForRound);
         if(maximalIndependentSet.size()<independentSetForRound.size())
         {
        	 maximalIndependentSet = new HashSet<Integer>(independentSetForRound);
         }

         Iterator<Integer> iterator = independentSetForRound.iterator();
         while (iterator.hasNext())
         {
            Integer nodeID = iterator.next();
            hMapNodeDegree.remove(nodeID);
            float unmarkValue = 0f;
            hMapNodeMarkVal.put(nodeID, unmarkValue);
            for (int i = 0; i < graphMatrix[0].length; i++)
            {
               graphMatrix[nodeID][i] = 0;
            }
         }
      }

      for(Integer vertexId:maximalIndependentSet)
      {
    	  System.out.println(vertexId);
      }
   }

   public static int[][] graphMatrix;
   public static HashMap<Integer, Integer> hMapNodeDegree
      = new HashMap<Integer, Integer>();
   public static HashMap<Integer, Float> hMapNodeMarkVal
      = new HashMap<Integer, Float>();
   public static HashSet<Integer> identifiedSet = new HashSet<Integer>();
   public static HashSet<Integer> independentSetForRound = new HashSet<Integer>();
   public static HashSet<Integer> maximalIndependentSet = new HashSet<Integer>();
}

/**
 * Class to compute the task in parallel by divide conquer approach Solves
 * CS255 homework assignment #3
 *
 * @author Nirav Patel
 * @version 1.00 2015/04/03
 */
class EdgeMarkThread extends Thread
{
   private int lowIndex;
   private int highIndex;
   private boolean isVertexMarker = false;
   private boolean isAddVertex = false;

   public EdgeMarkThread(boolean isAddVertex, boolean isVertexMarker,
         int lowIndex, int highIndex)
   {
      this.lowIndex = lowIndex;
      this.highIndex = highIndex;
      this.isVertexMarker = isVertexMarker;
      this.isAddVertex = isAddVertex;
   }

   public void run()
   {
      if (lowIndex == highIndex)
      {
         float unmarkValue = 0f;
         if (isVertexMarker)
         {
            if (!ParallelMIS.identifiedSet.contains(lowIndex))
            {
               if (0 == ParallelMIS.hMapNodeDegree.get(lowIndex))
               {
                  ParallelMIS.independentSetForRound.add(lowIndex);
               }
               else
               {
                  float minX = 0.0f;
                  float maxX = 1.0f;

                  Random rand = new Random();

                  float randomFloat = rand.nextFloat() * (maxX - minX)
                        + minX;
                  float probFloat = (float) 1
                        / (float) (2 * ParallelMIS.hMapNodeDegree
                              .get(lowIndex));

                  if (randomFloat > probFloat)
                  {
                     ParallelMIS.hMapNodeMarkVal
                           .put(lowIndex,
                                 (float) 1
                                       /(float)(2*ParallelMIS.hMapNodeDegree
                                             .get(lowIndex)));
                  }
                  else
                  {
                     ParallelMIS.hMapNodeMarkVal.put(lowIndex, unmarkValue);
                  }
               }
            }
         }
         else if (isAddVertex)
         {
            if (ParallelMIS.hMapNodeMarkVal.containsKey(lowIndex)
                  && unmarkValue != ParallelMIS.hMapNodeMarkVal
                        .get(lowIndex))
            {
               ParallelMIS.independentSetForRound.add(lowIndex);
            }
         }
         else
         {
            int startIndex = 0;
            int endIndex = ParallelMIS.graphMatrix[0].length - 1;
            EdgeMarkInner tmi = new EdgeMarkInner(lowIndex, startIndex,
                  endIndex);
            tmi.start();
            try
            {
               tmi.join();
            }
            catch (InterruptedException e)
            {
               e.printStackTrace();
            }
         }
      }
      else
      {
         int mid = (lowIndex + highIndex) / 2;
         EdgeMarkThread tm1 = new EdgeMarkThread(isAddVertex,
               isVertexMarker, lowIndex, mid);
         EdgeMarkThread tm2 = new EdgeMarkThread(isAddVertex,
               isVertexMarker, mid + 1, highIndex);
         tm1.start();
         tm2.start();
         try
         {
            tm1.join();
            tm2.join();
         }
         catch (InterruptedException e)
         {
            e.printStackTrace();
         }
      }
   }
}

/**
 * Class to compute the task in parallel by divide conquer approach Solves
 * CS255 homework assignment #3
 *
 * @author Nirav Patel
 * @version 1.00 2015/04/03
 */
class EdgeMarkInner extends Thread
{
   private int rowId;
   private int lowIndex;
   private int highIndex;

   public EdgeMarkInner(int rowId, int lowIndex, int highIndex)
   {
      this.rowId = rowId;
      this.lowIndex = lowIndex;
      this.highIndex = highIndex;
   }

   public void run()
   {
      if (lowIndex == highIndex)
      {
         if (ParallelMIS.graphMatrix[rowId][lowIndex] == 1)
         {
            float unmarkValue = 0f;

            if (ParallelMIS.hMapNodeDegree.get(rowId) != null
                  && ParallelMIS.hMapNodeDegree.get(lowIndex) != null)
            {
               if (ParallelMIS.hMapNodeMarkVal.get(rowId) != null
                     && ParallelMIS.hMapNodeMarkVal.get(lowIndex) != null
                     && ParallelMIS.hMapNodeMarkVal.get(rowId) > 0
                     && ParallelMIS.hMapNodeMarkVal.get(lowIndex) > 0)
               {
                  if (ParallelMIS.hMapNodeDegree.get(rowId)
                		  < ParallelMIS.hMapNodeDegree.get(lowIndex))
                  {
                     ParallelMIS.hMapNodeMarkVal.put(rowId, unmarkValue);
                  }
                  else
                  {
                     ParallelMIS.hMapNodeMarkVal.put(lowIndex,
                           unmarkValue);
                  }
               }
            }
         }
      }
      else
      {
         int mid = (lowIndex + highIndex) / 2;
         EdgeMarkInner tm1 = new EdgeMarkInner(rowId, lowIndex, mid);
         EdgeMarkInner tm2 = new EdgeMarkInner(rowId, mid + 1, highIndex);
         tm1.start();
         tm2.start();
         try
         {
            tm1.join();
            tm2.join();
         }
         catch (InterruptedException e)
         {
            e.printStackTrace();
         }
      }
   }
}