code: /*
   * Copyright (c) 2017, Hisao Tamaki
   */
  
  package tw.exact;
  
  import java.util.ArrayList;
  
  import java.util.Arrays;
  
  public class Bag implements Comparable<Bag>{
    Bag parent;
    XBitSet vertexSet;
    int size;
    Graph graph;
    int conv[];
    int inv[];
    ArrayList<Bag> nestedBags;
    ArrayList<Separator> separators;
    ArrayList<Separator> incidentSeparators;
    int width;
    int separatorWidth;
    int lowerBound;
    int inheritedLowerBound;
    boolean optimal; 
    
    SafeSeparator ss;
    
    public Bag(Graph graph) {
      this(null, graph.all);
      this.graph = graph;
   }
    
    public Bag(Bag parent, XBitSet vertexSet) {
      this.parent = parent;
      this.vertexSet = vertexSet;
      size = vertexSet.cardinality();
      incidentSeparators = new ArrayList<>();
    }
    
    public void initializeForDecomposition() {
      if (graph == null) {
        if (parent == null) {
          throw new RuntimeException("graph not available for decomposition");
        }
        else {
          makeLocalGraph();
        }
      }
      nestedBags = new ArrayList<>();
      separators = new ArrayList<>();
      width = 0;
      separatorWidth = 0;
    }
    
    public void attachSeparator(Separator separator) {
      incidentSeparators.add(separator);
    }
  
    public void makeRefinable() {
      makeLocalGraph();
      nestedBags = new ArrayList<>();
      separators = new ArrayList<>();
    }
    
    public int maxNestedBagSize() {
      if (nestedBags != null) {
        int max = 0;
        for (Bag bag:nestedBags) {
          if (bag.size > max) {
            max = bag.size;
          }
        }
        return max;
      }
      return -1;
    }
    
    public Bag addNestedBag(XBitSet vertexSet) {
      Bag bag = new Bag(this, vertexSet);
      nestedBags.add(bag);
      return bag;
    }
  
    public Separator addSeparator(XBitSet vertexSet) {
      Separator separator = new Separator(this, vertexSet);
      separators.add(separator);
      return separator;
    }
    
    public void addIncidentSeparator(Separator separator) {
      incidentSeparators.add(separator);
    }
  
    private void makeLocalGraph() {
      graph = new Graph(size);
      conv = new int[parent.size];
      inv = new int[size];
      
      XBitSet vertexSet = this.vertexSet;
  
      int k = 0;
      for (int v = 0; v < parent.size; v++) {
        if (vertexSet.get(v)) {
          conv[v] = k;
          inv[k++] = v;
        }
        else {
          conv[v] = -1;
        }
      }
  
      graph.inheritEdges(parent.graph, conv, inv);
  
  //    System.out.println("filling all, " + incidentSeparators.size() + " incident separators");
      for (Separator separator: incidentSeparators) {
  //      System.out.println("filling " + separator);
          graph.fill(convert(separator.vertexSet, conv));
      }
    }
    
    public int getWidth() {
      if (nestedBags == null) {
        return size - 1;
      }
      int max = 0;
      for (Bag bag: nestedBags) {
        int w = bag.getWidth();
        if (w > max) {
          max = w;
        }
      }
      for (Separator separator: separators) {
        int w = separator.vertexSet.cardinality();
        if (w > max) {
          max = w;
        }
      }
      return max;
  
    }
    
    public void setWidth() {
      // assumes that the bag is flat
      
  //    System.out.println("setWidth for " + this.vertexSet);
  //    System.out.println("nestedBags = " + nestedBags);
  
      if (nestedBags == null) {
        width = size - 1;
        separatorWidth = 0;
        return;
      }
      
      width = 0;
      separatorWidth = 0;
      
      for (Bag bag: nestedBags) {
        if (bag.size - 1 > width) {
          width = bag.size - 1;
        }
      }
  
      for (Separator separator: separators) {
        if (separator.size > separatorWidth) {
          separatorWidth = separator.size;
        }
      }
      
      if (separatorWidth > width) {
        width = separatorWidth;
      }
    }
    
    public void flatten() {
      if (nestedBags == null) {
        return;
      }
      
      validate();
      for (Bag bag: nestedBags) {
        if (bag.nestedBags != null) {
          bag.flatten();
        }
      }
      validate();
      ArrayList<Separator> newSeparatorList = new ArrayList<>();
      for (Separator separator: separators) {
  //      System.out.println(separator.incidentBags.size() + " incident bags of " + 
  //          separator);
        ArrayList<Bag> newIncidentBags = new ArrayList<>();
        for (Bag bag: separator.incidentBags) {
          if (bag.parent == this && bag.nestedBags != null &&
              !bag.nestedBags.isEmpty()) {
            Bag nested = bag.findNestedBagContaining(
                convert(separator.vertexSet, bag.conv));
            if (nested == null) {
              bag.dump();
              System.out.println(" does not have a bag containing " + 
                  convert(separator.vertexSet, bag.conv) + " which is originally " + 
                  separator.vertexSet);
              this.dump();
            }
                
            newIncidentBags.add(nested);
            nested.addIncidentSeparator(separator);
          }
          else {
            newIncidentBags.add(bag);
          }
        }
        if (!newIncidentBags.isEmpty()) {
          separator.incidentBags = newIncidentBags;
          newSeparatorList.add(separator);
        }
  //      System.out.println("processed separator :" + separator);
      }
      separators = newSeparatorList;
      
      ArrayList<Bag> temp = nestedBags;
      nestedBags = new ArrayList<>();
      for (Bag bag: temp) {
        if (bag.nestedBags != null && !bag.nestedBags.isEmpty()) {
          for (Bag nested: bag.nestedBags) {
  //          System.out.println("inverting " + nested);
            nested.invert();
            nestedBags.add(nested);
  //          System.out.println("inverted " + nested);
          }
          for (Separator separator: bag.separators) {
  //          System.out.println("inverting sep " + separator);
            separator.invert();
            this.separators.add(separator);
  //          System.out.println("inverted sep " + separator);
          }
        }
        else {
  //        System.out.println("adding original bag " + bag.vertexSet);
          nestedBags.add(bag);
        }
      }
      setWidth();
  //    System.out.println("bag of size " + size + " flattened into " + nestedBags.size() + " bags and width " +
  //        width);
  //    for (Bag bag: nestedBags) {
  //      System.out.println("incident separators of " + bag.vertexSet);
  //      for (Separator s: bag.incidentSeparators) {
  //        System.out.println("  " + s.vertexSet);
  //        for (Bag b: s.incidentBags) {
  //          System.out.println("        " + b.vertexSet);
  //        }
  //      }
  //    }
    }
    
    public Bag findNestedBagContaining(XBitSet vertexSet) {
      for (Bag bag: nestedBags) {
        if (vertexSet.isSubset(bag.vertexSet)) {
          return bag;
        }
      }
      return null;
    }
  
    public void invert() {
      vertexSet = convert(vertexSet, parent.inv);
      parent = parent.parent;
    }
    
    public void convert() {
      vertexSet = convert(vertexSet, parent.conv);
    }
    
    public XBitSet convert(XBitSet s) {
      return convert(s, conv);
    }
    
    private XBitSet convert(XBitSet s, int[] conv) {
      if (conv.length < s.length()) {
        return null;
      }
      XBitSet result = new XBitSet();
      for (int v = s.nextSetBit(0); v >= 0;
          v = s.nextSetBit(v + 1)) {
        result.set(conv[v]);
      }
      return result;
    }
    
    public TreeDecomposition toTreeDecomposition() {
      setWidth();
      TreeDecomposition td = new TreeDecomposition(0, width, graph);
      for (Bag bag: nestedBags) {
        td.addBag(bag.vertexSet.toArray());
      }
      
      for (Separator separator: separators) {
         XBitSet vs = separator.vertexSet;
        Bag full = null;
        for (Bag bag: separator.incidentBags) {
          if (vs.isSubset(bag.vertexSet)) {
            full = bag;
            break;
          }
        }
   
        if (full != null) {
          int j = nestedBags.indexOf(full) + 1;
          for (Bag bag: separator.incidentBags) {
  
            if (bag != full) {
              td.addEdge(j, nestedBags.indexOf(bag) + 1);
            }
          }
        }
        else {
          int j = td.addBag(separator.vertexSet.toArray());
          for (Bag bag: separator.incidentBags) {
            td.addEdge(j, nestedBags.indexOf(bag) + 1);
          }
        }
      }
      
      return td;
    }
    
    public void detectSafeSeparators() {
      ss = new SafeSeparator(graph);
      for (Separator separator: separators) {
  //      separator.figureOutSafetyBySPT();
        separator.figureOutSafety(ss);
      }
    }
    
    public void pack() {
      ArrayList<Bag> newBagList = new ArrayList<>();
      for (Bag bag: nestedBags) {
        if (bag.parent == this) {
          ArrayList<Bag> bagsToPack = new ArrayList<>();
          bag.collectBagsToPack(bagsToPack, null);
  //        System.out.println("bags to pack: " + bagsToPack);
          if (bagsToPack.size() >= 2) {
            XBitSet vertexSet = new XBitSet(graph.n);
            for (Bag toPack: bagsToPack) {
              vertexSet.or(toPack.vertexSet);
            }
            Bag packed = new Bag(this, vertexSet);
            packed.initializeForDecomposition();
            packed.nestedBags = bagsToPack;
            for (Bag toPack: bagsToPack) {
              toPack.parent = packed;
              toPack.convert();
            }
            newBagList.add(packed);
          }
          else {
            newBagList.add(bag);
          }
        }
      }
      nestedBags = newBagList;
      
      ArrayList<Separator> newSeparatorList = new ArrayList<>();
      
      for (Separator separator: separators) {
        boolean internal = true;
        Bag parent = null;
        for (Bag b: separator.incidentBags) {
          if (b.parent == this) {
            internal = false;
            break;
          }
          else if (parent == null) {
            parent = b.parent;
          }
          else if (b.parent != parent) {
            internal = false;
            break;
          }
        }
        if (internal) {
          separator.parent = parent;
          separator.convert();
          parent.separators.add(separator);
        }
        else {
          ArrayList<Bag> newIncidentBags = new ArrayList<>();
          for (Bag b: separator.incidentBags) {
            if (b.parent == this) {
              newIncidentBags.add(b);
            }
            else {
              newIncidentBags.add(b.parent);
              b.parent.incidentSeparators.add(separator);
              b.incidentSeparators.remove(separator);
            }
          }
          separator.incidentBags = newIncidentBags;
          newSeparatorList.add(separator);    
        }
      }
      
      separators = newSeparatorList;
      
      for (Bag bag: nestedBags) {
        bag.setWidth();
      }
      setWidth();
    }
    
    public void collectBagsToPack(ArrayList<Bag> list, Separator from) {
      list.add(this);
      for (Separator separator: incidentSeparators) {
  //      System.out.println(" safe = " + separator.safe);
        if (separator == from || separator.safe || separator.wall) {
          continue;
        }
        separator.collectBagsToPack(list,  this);
      }
    }
    
    public int countSafeSeparators() {
      int count = 0;
      for (Separator separator: separators) {
        if (separator.safe) {
          count++;
        }
      }
      return count;
    }
    
    public void dump() {
      dump("");
    }
    
    public void validate() {
      if (nestedBags != null) {
  //      assert !nestedBags.isEmpty() : "no nested bags " + this; 
        for (Bag b: nestedBags) {
          b.validate();
          assert !b.vertexSet.isEmpty(): "empty bag " + b;
          assert b.parent == this: "parent of " + b + 
              "\n which is " + b.parent +
              "\n is supposed to be " + this;
        }
        for (Separator s: separators) {
          assert !s.vertexSet.isEmpty(): "empty seprator " + s;
          assert s.parent == this: "parent of " + s + 
              "\n which is " + s.parent +
              "\n is supposed to be " + this;
        }
        for (Bag b: nestedBags) {
          for (Separator s: b.incidentSeparators) {
            assert !s.vertexSet.isEmpty(): "empty seprator " + s + 
            "\n incident to " + b;
            assert s.parent == this: "parent of " + s + 
                "\n which is " + s.parent +
                "\n is supposed to be " + this + 
                "\n where the separator is incident to bag " + b;
            assert s.vertexSet.isSubset(b.vertexSet): "separator vertex set " + s.vertexSet + 
            "\n is not a subset of the bag vertex set " + b.vertexSet;
          }
        }
        for (Separator separator: separators) {
          for (Bag b: separator.incidentBags) {
            assert b != null;
            assert b.parent == this: "parent of " + b + 
                "\n which is " + b.parent +
                "\n is supposed to be " + this + 
                "\n where the bag is incident to separator " + separator;
            assert separator.vertexSet.isSubset(b.vertexSet): "separator vertex set " + 
                separator.vertexSet + 
            "\n is not a subset of the bag vertex set " + b.vertexSet;
          }
        }
      }
    }
    
    private void dump(String indent) {
      System.out.println(indent + "bag:" + vertexSet);
      System.out.print(indent + "width = " + width + ", conv = ");
      System.out.println(Arrays.toString(conv));
      if (nestedBags != null) {
        System.out.println(indent + nestedBags.size() + " subbags:"); 
        for (Bag bag: nestedBags) {
          bag.dump(indent + "  ");
        }
        for (Separator separator: separators) {
          separator.dump(indent + "  ");
        }
      }
    }
    
    public void canonicalize() {
      boolean moving = true;
      while (moving = true) {
        moving = false;
        for (Bag bag: nestedBags) {
          if (bag.trySplit()) {
            moving = true;
          }
        }
        if (moving) {
          flatten();
        }
      }
    }
  
    private boolean trySplit() {
      return false;
    }
  
    public String toString() {
      StringBuilder sb = new StringBuilder();
      if (parent != null) {
        sb.append("bag" + parent.nestedBags.indexOf(this) + ":");
      }
      else {
        sb.append("root bag :");
      }
      sb.append(vertexSet);
      return sb.toString();
    }
  
    @Override
    public int compareTo(Bag b) {
      if (size != b.size) {
        return b.size - size;
      }
      return XBitSet.ascendingComparator.compare(b.vertexSet, vertexSet);
    }
  }
  