/*
 * Copyright (c) 2017, Hiromu Ohtsuka
*/

package tw.heuristic;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Set;
import java.util.HashSet;
import java.util.Random;
import java.util.Collections;

public class MainDecomposer{
  public static enum Mode{
    greedy, pathDecomposition, treeDecomposition
  }
  public static final long MAX_TIME = 1800000;
  public static final long INITIAL_TIME_MS = 4000;
  public static final int MAX_MULTIPLICITY = 1;
  public static final long CUT_D_TIME_MS = 300000;
  public static final long DETECT_TIME_MS = 10000;

  private static Random random;
  private static Graph wholeGraph;
  private static TreeDecomposition best;
  private static int[][] invs;
  private static Bag[] bags;
  private static long detectSum;
  private static long startTime;
  private static int print_tw_below;

  private static final boolean DEBUG = false;

  private static int countGD, countPD, countTD;

  private static final Comparator< Bag > WIDTH_DESCENDING_ORDER =
    new Comparator< Bag >(){
      @Override
        public int compare(Bag b1, Bag b2){
          return -(Integer.compare(b1.getWidth(), b2.getWidth()));
        }
    };

  public static TreeDecomposition getBestTreeDecompositionSoFar(){
    return best;
  }

  private static void commit(){
    if(bags == null){
      return;
    }

    if(DEBUG){
      comment("commit");
    }

    Bag[] copiedBags = new Bag[bags.length];
    for(int i = 0; i < copiedBags.length; i++){
      copiedBags[i] = (Bag)bags[i].clone();
    }

    if(bags.length == 1){
      // trivial tree decomposition
      if(copiedBags[0].nestedBags == null || copiedBags[0].nestedBags.isEmpty()){
        TreeDecomposition trivial =
          new TreeDecomposition(0, copiedBags[0].graph.n - 1, copiedBags[0].graph);
        trivial.addBag(copiedBags[0].graph.all.toArray());
        if(best == null || trivial.width < best.width){
          best = trivial;
          comment("width = " + best.width);
          printTime();
		  if(best.width <= print_tw_below-1) {
			TreeDecomposition result = getBestTreeDecompositionSoFar();
			result.writeTo(System.out);
			System.out.print("=\n");
		  }
        }
        return;
      }

      copiedBags[0].flatten();
      TreeDecomposition td = copiedBags[0].toTreeDecomposition();
      setWidth(td);

      if(best == null || td.width < best.width){
        best = td;
        comment("width = " + best.width);
        printTime();
        if(best.width <= print_tw_below-1) {
          TreeDecomposition result = getBestTreeDecompositionSoFar();
          result.writeTo(System.out);
          System.out.print("=\n");
        }
      }

      return;
    }

    TreeDecomposition td = new TreeDecomposition(0, 0, wholeGraph);
    for(int i = 0; i < copiedBags.length; i++){
      // trivial tree decomposition
      if(copiedBags[i].nestedBags == null || copiedBags[i].nestedBags.isEmpty()){
        TreeDecomposition trivial =
          new TreeDecomposition(0, copiedBags[i].graph.n - 1, copiedBags[i].graph);
        trivial.addBag(copiedBags[i].graph.all.toArray());
        td.combineWith(trivial, invs[i], null);
      }
      else{
        copiedBags[i].flatten();
        td.combineWith(copiedBags[i].toTreeDecomposition(), invs[i], null);
      }
    }
    setWidth(td);

    if(best == null || td.width < best.width){
      best = td;
      comment("width = " + best.width);
      printTime();
	  if(best.width <= print_tw_below-1) {
		TreeDecomposition result = getBestTreeDecompositionSoFar();
		result.writeTo(System.out);
		System.out.print("=\n");
	  }
    }
  }

  private static void setWidth(TreeDecomposition td){
    if(td == null){
      return;
    }
    int width = -1;
    for(int i = 1; i <= td.nb; i++){
      width = Math.max(width, td.bags[i].length - 1);
    }
    td.width = width;
  }

  private static void comment(String comment){
    System.out.println("c " + comment);
  }

  private static void printTime(){
    comment("time = " + (System.currentTimeMillis() - startTime) + " ms");
  }

  private static void initializeForDecomposition(Graph graph, long seed){
    wholeGraph = graph;
    best = null;
    bags = null;
    invs = null;
    detectSum = 0;
    random = new Random(seed);
    startTime = System.currentTimeMillis();

    // trivial tree decomposition
    best = new TreeDecomposition(0, wholeGraph.n - 1, wholeGraph);
    best.addBag(wholeGraph.all.toArray());

    if(DEBUG){
      comment("seed = " + seed);
    }
  }

  public static TreeDecomposition decompose(Graph graph, long seed){
    initializeForDecomposition(graph, seed);

    if(graph.n == 0){
      best = new TreeDecomposition(0, -1, graph);
      return best;
    }

    ArrayList< VertexSet > components = graph.getComponents(new VertexSet());

    int nc = components.size();

    if(nc == 1){
      if(graph.n <= 2){
        best = new TreeDecomposition(0, graph.n - 1, graph);
        best.addBag(graph.all.toArray());
        return best;
      }

      bags = new Bag[1];
      bags[0] = new Bag(graph);

      if(decomposeWithSmallCuts(bags[0])){
        commit();
      }

      if(bags[0].countSafeSeparators() == 0){
        decomposeGreedy(bags[0]);
      }
      else{
        for(Bag nb : bags[0].nestedBags){
          nb.makeRefinable();
          decomposeGreedy(nb);
        }
        bags[0].flatten();
      }

      commit();

      while(!bags[0].optimal){
        improveWithSeparators(bags[0], bags[0].getWidth());
        commit();
        bags[0].flatten();
      }

      return getBestTreeDecompositionSoFar();
    }

    Graph[] graphs = new Graph[nc];
    invs = new int[nc][];
    for(int i = 0; i < nc; i++){
      VertexSet component = components.get(i);
      graphs[i] = new Graph(component.cardinality());
      invs[i] = new int[graphs[i].n];
      int[] conv = new int[graph.n];
      int k = 0;
      for(int v = 0; v < graph.n; v++){
        if(component.get(v)){
          conv[v] = k;
          invs[i][k] = v;
          ++k;
        }
        else{
          conv[v] = -1;
        }
      }
      graphs[i].inheritEdges(graph, conv, invs[i]);
    }

    bags = new Bag[nc];
    for(int i = 0; i < nc; i++){
      bags[i] = new Bag(graphs[i]);
    }

    commit();

    for(int i = 0; i < nc; i++){
      decomposeWithSmallCuts(bags[i]);
    }

    commit();

    for(int i = 0; i < nc; i++){
      if(bags[i].countSafeSeparators() == 0){
        decomposeGreedy(bags[i]);
      }
      else{
        for(Bag nb : bags[i].nestedBags){
          nb.makeRefinable();
          decomposeGreedy(nb);
        }
        bags[i].flatten();
      }
    }

    commit();

    PriorityQueue< Bag > queue =
      new PriorityQueue< >(nc, WIDTH_DESCENDING_ORDER);

    for(int i = 0; i < nc; i++){
      queue.offer(bags[i]);
    }

    while(!queue.isEmpty()){
      Bag b = queue.poll();
      improveWithSeparators(b, b.getWidth());
      commit();
      b.flatten();
      if(!b.optimal){
        queue.offer(b);
      }
    }

    return getBestTreeDecompositionSoFar();
  }

  private static void improveWithSeparators(Bag bag, int k){
    if(bag.parent != null){
      bag.makeLocalGraph();
    }

    if(bag.getWidth() <= k - 1){
      return;
    }

    if(bag.separators == null){
      improve(bag, k);
      return;
    }

    if(bag.countSafeSeparators() > 0){
      bag.pack();
      for(Bag b : bag.nestedBags){
        improveWithSeparators(b, k);
      }
      return;
    }

    if(detectSum < DETECT_TIME_MS){
      detectSum += bag.detectSafeSeparators(DETECT_TIME_MS - detectSum);
    }

    if(bag.countSafeSeparators() == 0){
      improve(bag, k);
    }
    else{
      bag.pack();
      for(Bag b : bag.nestedBags){
        improveWithSeparators(b, k);
      }
    }
  }

  private static boolean improve(Bag bag, int k){
    if(bag.parent != null){
      bag.makeLocalGraph();
    }

    if(bag.getWidth() <= k - 1){
      return true;
    }

    if(bag.nestedBags == null){
      tryDecomposeExactly(bag, bag.graph.minDegree(), k - 1, k - 1);
      return bag.getWidth() <= k - 1;
    }

    while(bag.getWidth() >= k){
      Bag maxBag = null;
      for(Bag nb : bag.nestedBags){
        if(maxBag == null || nb.size > maxBag.size){
          maxBag = nb;
        }
      }
      long timeMS = INITIAL_TIME_MS;
      int gdVS = maxBag.size, pdVS = maxBag.size, tdVS = maxBag.size;
      int count = 0;
      while(true){
        if(DEBUG){
          comment("timeMS = " + timeMS);
          comment("gdVS = " + gdVS);
          comment("pdVS = " + pdVS);
          comment("tdVS = " + tdVS);
          comment("countGD = " + countGD);
          comment("countPD = " + countPD);
          comment("countTD = " + countTD);
        }
        gdVS = tryImproveWith(Mode.greedy, 
            bag, maxBag, timeMS, gdVS, 10, 3);
        if(gdVS < 0){
          ++countGD;
          break;
        }
        pdVS = tryImproveWith(Mode.pathDecomposition, 
            bag, maxBag, timeMS, pdVS, 30, 2);
        if(pdVS < 0){
          ++countPD;
          break;
        }
        tdVS = tryImproveWith(Mode.treeDecomposition, 
            bag, maxBag, timeMS, tdVS, 3, 3);
        if(tdVS < 0){
          ++countTD;
          break;
        }
        refresh(bag, maxBag, Math.max(gdVS, Math.max(pdVS, tdVS)) + 30);
        break;
      }
    }

    return true;
  }

  private static void searchBagsToImproveLikeTree(Bag bag, Separator from, int max,
      int targetWidth, ArrayList< Separator > separatorsToCheck){
    Set< Bag > visitedBags = new HashSet< >();
    VertexSet vs = new VertexSet();

    visitedBags.add(bag);
    vs.or(bag.vertexSet);

    collectSubsetBags(visitedBags, vs);

    while(vs.cardinality() < max){
      if(!choiceBagAtRandom(visitedBags, vs)){
        break;
      }
    }

    collectBagsConnectingLargeSeparator(visitedBags, vs, targetWidth, 0);
    collectSeparatorsTocheck(visitedBags, separatorsToCheck);
  }

  private static void searchBagsToImproveLikePath(Bag bag, Separator from, int max,
      int targetWidth, ArrayList< Separator > separatorsToCheck){
    Set< Bag > visitedBags = new HashSet< >();
    VertexSet vs = new VertexSet();

    visitedBags.add(bag);
    vs.or(bag.vertexSet);

    collectBagsLikePath(bag, visitedBags, vs, 4 * max / 5);

    while(vs.cardinality() < max){
      if(!choiceBagAtRandom(visitedBags, vs)){
        break;
      }
    }

    collectBagsConnectingLargeSeparator(visitedBags, vs, targetWidth, 0);
    collectSeparatorsTocheck(visitedBags, separatorsToCheck);
  }

  private static void collectBagsLikePath(
      Bag bag, Set< Bag > visitedBags, VertexSet vs, int max){
    Bag s = bag, t = bag;
    while(vs.cardinality() < max){
      ArrayList< Bag > tBags = new ArrayList< >();
      for(Separator is : t.incidentSeparators){
        for(Bag ib : is.incidentBags){
          if(ib != t && ib != s && !visitedBags.contains(ib)){
            tBags.add(ib);
          }
        }
      }
      if(!tBags.isEmpty()){
        t = tBags.get(random.nextInt(tBags.size()));
        visitedBags.add(t);
        vs.or(t.vertexSet);
      }

      if(vs.cardinality() >= max){
        break;
      }

      ArrayList< Bag > sBags = new ArrayList< >();
      for(Separator is : s.incidentSeparators){
        for(Bag ib : is.incidentBags){
          if(ib != s && ib != t && !visitedBags.contains(ib)){
            sBags.add(ib);
          }
        }
      }
      if(!sBags.isEmpty()){
        s = sBags.get(random.nextInt(sBags.size()));
        visitedBags.add(s);
        vs.or(s.vertexSet);
      }

      if(tBags.isEmpty() && sBags.isEmpty()){
        break;
      }
    }

    collectSubsetBags(visitedBags, vs);
  }

  private static boolean choiceBagAtRandom(Set< Bag > visitedBags, VertexSet vs){
    ArrayList< Bag > outers = new ArrayList< >();
    for(Bag b : visitedBags){
      for(Separator is : b.incidentSeparators){
        for(Bag nb : is.incidentBags){
          if(nb != b && !visitedBags.contains(nb)){
            outers.add(nb);
          }
        }
      }
    }
    if(!outers.isEmpty()){
      Bag bag = outers.get(random.nextInt(outers.size()));
      visitedBags.add(bag);
      vs.or(bag.vertexSet);
      collectSubsetBags(visitedBags, vs);
      return true;
    }
    return false;
  }

  private static void collectSubsetBags(Set< Bag > visitedBags, VertexSet vs){
    ArrayList< Bag > toVisited = new ArrayList< >();
    while(true){
      for(Bag b : visitedBags){
        for(Separator is : b.incidentSeparators){
          for(Bag ib : is.incidentBags){
            if(ib != b && !visitedBags.contains(ib)
                && ib.vertexSet.isSubset(b.vertexSet)){
              toVisited.add(ib);
            }
          }
        }
      }
      if(toVisited.isEmpty()){
        return;
      }
      for(Bag b : toVisited){
        visitedBags.add(b);
        vs.or(b.vertexSet);
      }
      toVisited.clear();
    }
  }

  private static void collectBagsConnectingLargeSeparator(
      Set< Bag > visitedBags, VertexSet vs, int targetWidth, int d){
    ArrayList< Bag > toVisited = new ArrayList< >();
    while(true){
      for(Bag b : visitedBags){
        for(Separator is : b.incidentSeparators){
          if(Math.abs(targetWidth - is.size) <= d){
            for(Bag ib : is.incidentBags){
              if(!visitedBags.contains(ib)){
                toVisited.add(ib);
              }
            }
          }
        }
      }
      if(toVisited.isEmpty()){
        return;
      }
      for(Bag b : toVisited){
        visitedBags.add(b);
        vs.or(b.vertexSet);
        collectSubsetBags(visitedBags, vs);
      }
      toVisited.clear();
    }
  }

  private static void collectBagsFormingStar(
      Set< Bag > visitedBags, VertexSet vs){
    ArrayList< Bag > toVisited = new ArrayList< >();
    while(true){
      for(Bag b : visitedBags){
        for(Separator is : b.incidentSeparators){
          // star
          if(is.incidentBags.size() >= 3){
            for(Bag ib : is.incidentBags){
              if(!visitedBags.contains(ib)){
                toVisited.add(ib);
              }
            }
          }
        }
      }
      if(toVisited.isEmpty()){
        return;
      }
      for(Bag b : toVisited){
        visitedBags.add(b);
        vs.or(b.vertexSet);
        collectSubsetBags(visitedBags, vs);
      }
      toVisited.clear();
    }
  }

  private static void collectSeparatorsTocheck(
      Set< Bag > visitedBags, ArrayList< Separator > separatorsToCheck){
    for(Bag b : visitedBags){
      for(Separator is : b.incidentSeparators){
        for(Bag ib : is.incidentBags){
          if(ib != b && !visitedBags.contains(ib)){
            separatorsToCheck.add(is);
            break;
          }
        }
      }
    }
  }

  private static Bag findBagContaining(Bag bag, Bag whole){
    if(bag == whole){
      return whole;
    }

    for(Bag nb : whole.nestedBags){
      if(nb == bag){
        return nb;
      }
      if(nb.nestedBags == null){
        continue;
      }
      for(Bag b : nb.nestedBags){
        if(b == bag){
          return nb;
        }
      }
    }

    return null;
  }

  private static void decomposeGreedy(Bag bag){
    bag.initializeForDecomposition();
    GreedyDecomposer mfd = new GreedyDecomposer(bag);
    mfd.decompose();
  }

  private static boolean decomposeWithSmallCuts(Bag bag){
    bag.initializeForDecomposition();
    CutDecomposer cd = new CutDecomposer(bag);
    cd.decompose(CUT_D_TIME_MS);
    if(DEBUG){
      comment("finish cut decompose");
    }
    return bag.nestedBags != null && !bag.nestedBags.isEmpty();
  }

/*
  private static void decomposeGreedyWithSmallCuts(Bag bag){
    bag.initializeForDecomposition();
    CutDecomposer cd = new CutDecomposer(bag);
    cd.decompose();

    // [TODO]
    // commit();

    if(DEBUG){
      comment("finish cut decompose");
    }

    if(bag.countSafeSeparators() == 0){
      GreedyDecomposer gd = new GreedyDecomposer(bag);
      gd.decompose();
    }
    else{
      for(Bag nb : bag.nestedBags){
        nb.makeRefinable();
        GreedyDecomposer gd = new GreedyDecomposer(nb);
        gd.decompose();
      }
    }

    bag.flatten();
  }
  */

  private static void tryDecomposeExactly(Bag bag, int lowerBound, int upperBound, int targetWidth){
    if(lowerBound > upperBound){
      return;
    }

    Bag triedBag = (Bag)bag.clone();

    if(triedBag.parent != null){
      triedBag.makeLocalGraph();
    }

    decomposeGreedy(triedBag);
    if(triedBag.getWidth() <= targetWidth){
      replace(triedBag, bag);
      return;
    }

    triedBag.initializeForDecomposition();
    MTDecomposerHeuristic mtd = new MTDecomposerHeuristic(
        triedBag, lowerBound, upperBound, null, null, MAX_TIME);
    mtd.setMaxMultiplicity(MAX_MULTIPLICITY);
    if(!mtd.decompose()){
      return;
    }

    if(triedBag.getWidth() <= targetWidth){
      replace(triedBag, bag);
    }
  }

  private static int tryImproveWith(Mode mode,
      Bag whole, Bag maxBag, long time, int vsSize, int cycle, int d){
    if(DEBUG){
      comment("mode = " + mode);
      comment("cycle = " + cycle);
      comment("d = " + d);
      comment("timeLimit = " + time);
    }

    int k = whole.getWidth();
    int targetSize = vsSize;
    int count = 0;
    long sum = 0;
    while(true){
      if(DEBUG){
        comment("k = " + k);
        comment("vs = " + targetSize);
        comment("count = " + count);
        comment("sum = " + sum);
      }

      ArrayList< Separator > separatorsToCheck = new ArrayList< >();
      switch(mode){
        case greedy : case treeDecomposition :
          searchBagsToImproveLikeTree(
              maxBag, null, targetSize, k - 1, separatorsToCheck);
          break;
        case pathDecomposition :
          searchBagsToImproveLikePath(
              maxBag, null, targetSize, k - 1, separatorsToCheck);
          break;
      }
      for(Separator s : separatorsToCheck){
        s.wall = true;
      }
      if(!separatorsToCheck.isEmpty()){
        whole.pack();
      }

      Bag target;
      if(!separatorsToCheck.isEmpty()){
        target = findBagContaining(maxBag, whole);
      }
      else{
        target = whole;
      }

      if(DEBUG){
        comment("targetSize = " + target.size);
      }

      if(target.parent != null){
        target.makeLocalGraph();
      }

      Bag triedBag = (Bag)target.clone();
      triedBag.initializeForDecomposition();
      boolean success = false;
      switch(mode){
        case greedy :
          GreedyDecomposer gd = new GreedyDecomposer(triedBag);
          if(gd.decompose(time - sum)){
            success = true;
          }
          sum += gd.getTimeMS();
          break;

        case pathDecomposition :
          PathDecomposer pd = new PathDecomposer(triedBag, 
              triedBag.graph.minDegree(), k - 1);
          if(pd.decompose(time - sum)){
            success = true;
          }
          sum += pd.getTimeMS();
          break;

        case treeDecomposition :
          MTDecomposerHeuristic mtd = new MTDecomposerHeuristic(
              triedBag, triedBag.graph.minDegree(), k - 1, null, null, time - sum);
          mtd.setMaxMultiplicity(MAX_MULTIPLICITY);
          if(mtd.decompose()){
            success = true;
          }
          sum += mtd.getTimeMS();
          break;
      }

      for(Separator s : separatorsToCheck){
        s.wall = false;
      }

      if(success && triedBag.getWidth() <= k - 1){
        replace(triedBag, target);
        whole.flatten();
        return -1;
      }

      if(!separatorsToCheck.isEmpty()){
        whole.flatten();
      }

      if(sum >= time){
        break;
      }

      if(count % cycle == 0){
        targetSize += d;
      }

      ++count;
    }

    return targetSize;
  }

  private static void refresh(Bag whole, Bag maxBag, int vsSize){
    int k = whole.getWidth();
    ArrayList< Separator > separatorsToCheck = new ArrayList< >();
    searchBagsToImproveLikeTree(
        maxBag, null, vsSize, k - 1, separatorsToCheck);

    for(Separator s : separatorsToCheck){
      s.wall = true;
    }

    if(!separatorsToCheck.isEmpty()){
      whole.pack();
    }

    Bag target;
    if(!separatorsToCheck.isEmpty()){
      target = findBagContaining(maxBag, whole);
    }
    else{
      target = whole;
    }

    if(target.parent != null){
      target.makeLocalGraph();
    }
    target.initializeForDecomposition();
    GreedyDecomposer gd = new GreedyDecomposer(target);
    gd.decompose();

    for(Separator s : separatorsToCheck){
      s.wall = false;
    }

    whole.flatten();
  }

  private static void replace(Bag from, Bag to){
    to.graph = from.graph;
    to.nestedBags = from.nestedBags;
    to.separators = from.separators;
    to.incidentSeparators = from.incidentSeparators;

    for(Bag b : to.nestedBags){
      b.parent = to;
    }
    for(Separator s : to.separators){
      s.parent = to;
    }
  }

  private MainDecomposer(){}

  public static void main(String[] args){
    Runtime.getRuntime().addShutdownHook(new Thread(){
        @Override
        public void run(){
        TreeDecomposition result = getBestTreeDecompositionSoFar();
        if(result == null){
        comment("no solution");
        return;
        }
        //if(result.isValid(System.err)){
        comment("width = " + result.width);
        printTime();
        result.writeTo(System.out);
        //}
        //if(result.isValid(System.err)){
        //  comment("validation ok");
        //}
        }
        });

    long seed = 42;
	print_tw_below = -1;
    if(args.length >= 2){
      if("-s".equals(args[0])){
        seed = Long.parseLong(args[1]);
      } else if("-p".equals(args[0])){
        print_tw_below = Integer.parseInt(args[1]);
      }
    }
    if(args.length >= 4){
      if("-s".equals(args[2])){
        seed = Long.parseLong(args[3]);
      } else if("-p".equals(args[2])){
        print_tw_below = Integer.parseInt(args[3]);
      }
    }

    Graph graph = Graph.readGraph(System.in);

    comment("read Graph");

    decompose(graph, seed);

    printTime();
  }
}
