---

SuperSetReduction.java

package gov.nasa.arc.ase.util.graph;

import java.io.*;
import java.util.BitSet;

public class SuperSetReduction {
  private static boolean included(boolean[] a, boolean[] b) {
    final int al = a.length;
    final int bl = b.length;

    for(int i = 0; i < al; i++)
      if(a[i] && !b[i])
    return false;

    return true;
  }  
  public static void main(String[] args) {
    if(args.length > 1) {
      System.out.println("usage:");
      System.out.println("\tjava gov.nasa.arc.ase.util.graph.SuperSetReduction [<filename>]");
      return;
    }

    Graph g = null;

    try {
      if(args.length == 0)
    g = Graph.load();
      else
    g = Graph.load(args[0]);
    } catch(IOException e) {
      System.out.println("Can't load the graph.");
      return;
    }

    g = reduce(g);

    g.save();
  }  
  public static Graph reduce(Graph g) {
    final int nsets = g.getIntAttribute("nsets");
    String type = g.getStringAttribute("type");
    String ac = g.getStringAttribute("ac");

    if(!type.equals("gba"))
      throw new RuntimeException("invalid graph type: " + type);

    if(ac.equals("nodes")) {
      final int nnodes = g.getNodeCount();

      final boolean[][] asets = new boolean[nsets][nnodes];

      g.forAllNodes(new EmptyVisitor() {
    public void visitNode(Node n) {
      for(int i = 0; i < nsets; i++) {
        String acc = "acc"+i;
        if(n.getBooleanAttribute(acc)) {
          asets[i][n.getId()] = true;
          n.setBooleanAttribute(acc, false);
        }
      }
    }
      });

      boolean[] remove = new boolean[nsets];

      for(int i = 0; i < nsets; i++) {
    for(int j = 0; j < nsets && !remove[i] ; j++) {
      if(i != j && !remove[j])
        if(included(asets[j], asets[i]))
          remove[i] = true;
    }
      }

      int n_nsets = 0;
      for(int i = 0; i < nsets; i++)
    if(!remove[i]) n_nsets++;

      boolean[][] n_asets = new boolean[n_nsets][nnodes];

      n_nsets = 0;
      for(int i = 0; i < nsets; i++)
    if(!remove[i])
      n_asets[n_nsets++] = asets[i];

      g.setIntAttribute("nsets", n_nsets);

      for(int i = 0; i < nnodes; i++) {
    Node n = g.getNode(i);
    for(int j = 0; j < n_nsets; j++)
      if(n_asets[j][i])
        n.setBooleanAttribute("acc"+j, true);
      }

      return g;
    } else if(ac.equals("edges")) {
      final int nedges = g.getEdgeCount();

      final boolean[][] asets = new boolean[nsets][nedges];
      final Edge[] edges = new Edge[nedges];

      g.forAllEdges(new EmptyVisitor(new Integer(0)) {
    public void visitEdge(Edge e) {
      int id = ((Integer)arg).intValue();
      arg = new Integer(id+1);

      edges[id] = e;

      for(int i = 0; i < nsets; i++) {
        String acc = "acc"+i;
        if(e.getBooleanAttribute(acc)) {
          asets[i][id] = true;
          e.setBooleanAttribute(acc, false);
        }
      }
    }
      });

      boolean[] remove = new boolean[nsets];

      for(int i = 0; i < nsets; i++) {
    for(int j = 0; j < nsets && !remove[i] ; j++) {
      if(i != j && !remove[j])
        if(included(asets[j], asets[i]))
          remove[i] = true;
    }
      }

      int n_nsets = 0;
      for(int i = 0; i < nsets; i++)
    if(!remove[i]) n_nsets++;

      boolean[][] n_asets = new boolean[n_nsets][nedges];

      n_nsets = 0;
      for(int i = 0; i < nsets; i++)
    if(!remove[i])
      n_asets[n_nsets++] = asets[i];

      g.setIntAttribute("nsets", n_nsets);

      for(int i = 0; i < nedges; i++) {
    Edge e = edges[i];
    for(int j = 0; j < n_nsets; j++)
      if(n_asets[j][i])
        e.setBooleanAttribute("acc"+j, true);
      }

      return g;
    } else
      throw new RuntimeException("invalid accepting type: " + ac);
  }  
}

---