---

SCCReduction.java

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

import java.io.*;
import java.util.BitSet;
//#ifdef JDK11


//#else JDK11
import java.util.List;
import java.util.Iterator;
//#endif JDK11

public class SCCReduction {
  private static boolean anyAcceptingState(List scc, Graph g) {
    String type = g.getStringAttribute("type");
    String ac = g.getStringAttribute("ac");

    if(type.equals("ba")) {
      if(ac.equals("nodes")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      if(n.getBooleanAttribute("accepting"))
        return true;
    }
      } else if(ac.equals("edges")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      for(Iterator j = n.getOutgoingEdges().iterator(); j.hasNext(); ) {
        Edge e = (Edge)j.next();

        if(e.getBooleanAttribute("accepting"))
          return true;
      }
    }
      } else
    throw new RuntimeException("invalid accepting type: " + ac);
    } else if(type.equals("gba")) {
      int nsets = g.getIntAttribute("nsets");

      if(ac.equals("nodes")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      for(int j = 0; j < nsets; j++)
        if(n.getBooleanAttribute("acc"+j))
          return true;
    }
      } else if(ac.equals("edges")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      for(Iterator j = n.getOutgoingEdges().iterator(); j.hasNext(); ) {
        Edge e = (Edge)j.next();

        for(int k = 0; k < nsets; k++)
          if(e.getBooleanAttribute("acc"+j))
        return true;
      }
    }
      } else
    throw new RuntimeException("invalid accepting type: " + ac);
    } else
      throw new RuntimeException("invalid graph type: " + type);

    return false;
  }  
  private static void clearAccepting(List scc, Graph g) {
    String type = g.getStringAttribute("type");
    String ac = g.getStringAttribute("ac");

    if(type.equals("ba")) {
      if(ac.equals("nodes")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      n.setBooleanAttribute("accepting", false);
    }
      } else if(ac.equals("edges")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      for(Iterator j = n.getOutgoingEdges().iterator(); j.hasNext(); ) {
        Edge e = (Edge)j.next();

        e.setBooleanAttribute("accepting", false);
      }
    }
      } else
    throw new RuntimeException("invalid accepting type: " + ac);
    } else if(type.equals("gba")) {
      int nsets = g.getIntAttribute("nsets");

      if(ac.equals("nodes")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      for(int j = 0; j < nsets; j++)
        n.setBooleanAttribute("acc"+j, false);
    }
      } else if(ac.equals("edges")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      for(Iterator j = n.getOutgoingEdges().iterator(); j.hasNext(); ) {
        Edge e = (Edge)j.next();

        for(int k = 0; k < nsets; k++)
          e.setBooleanAttribute("acc"+k, false);
      }
    }
      } else
    throw new RuntimeException("invalid accepting type: " + ac);
    } else
      throw new RuntimeException("invalid graph type: " + type);
  }  
  private static void clearExternalEdges(List scc, Graph g) {
    String type = g.getStringAttribute("type");
    String ac = g.getStringAttribute("ac");

    if(type.equals("ba")) {
      if(ac.equals("nodes")) {
      } else if(ac.equals("edges")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      for(Iterator j = n.getOutgoingEdges().iterator(); j.hasNext(); ) {
        Edge e = (Edge)j.next();

        if(!scc.contains(e.getNext()))
          e.setBooleanAttribute("accepting", false);
      }
    }
      } else
    throw new RuntimeException("invalid accepting type: " + ac);
    } else if(type.equals("gba")) {
      int nsets = g.getIntAttribute("nsets");

      if(ac.equals("nodes")) {
      } else if(ac.equals("edges")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      for(Iterator j = n.getOutgoingEdges().iterator(); j.hasNext(); ) {
        Edge e = (Edge)j.next();

        if(!scc.contains(e.getNext()))
          for(int k = 0; k < nsets; k++)
        e.setBooleanAttribute("acc"+k, false);
      }
    }
      } else
    throw new RuntimeException("invalid accepting type: " + ac);
    } else
      throw new RuntimeException("invalid graph type: " + type);
  }  
  private static boolean isAccepting(List scc, Graph g) {
    String type = g.getStringAttribute("type");
    String ac = g.getStringAttribute("ac");

    if(type.equals("ba")) {
      if(ac.equals("nodes")) {
    for(Iterator i = scc.iterator(); i.hasNext(); )
      if(((Node)i.next()).getBooleanAttribute("accepting"))
        return true;

    return false;
      } else if(ac.equals("edges")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      for(Iterator j = n.getOutgoingEdges().iterator(); j.hasNext(); ) {
        Edge e = (Edge)j.next();

        if(e.getBooleanAttribute("accepting"))
          return true;
      }
    }

    return false;
      } else
    throw new RuntimeException("invalid accepting type: " + ac);
    } else if(type.equals("gba")) {
      int nsets = g.getIntAttribute("nsets");
      BitSet found = new BitSet(nsets);
      int nsccs = 0;

      if(ac.equals("nodes")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      for(int j = 0; j < nsets; j++) {
        if(n.getBooleanAttribute("acc"+j))
          if(!found.get(j)) {
        found.set(j);
        nsccs++;
          }
      }
    }
      } else if(ac.equals("edges")) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      for(Iterator j = n.getOutgoingEdges().iterator(); j.hasNext(); ) {
        Edge e = (Edge)j.next();

        for(int k = 0; k < nsets; k++) {
          if(e.getBooleanAttribute("acc"+k))
        if(!found.get(k)) {
          found.set(k);
          nsccs++;
        }
        }
      }
    }
      } else
    throw new RuntimeException("invalid accepting type: " + ac);

      return nsccs == nsets;
    } else
      throw new RuntimeException("invalid graph type: " + type);
  }  
  private static boolean isTerminal(List scc) {
    for(Iterator i = scc.iterator(); i.hasNext(); ) {
      Node n = (Node)i.next();

      for(Iterator j = n.getOutgoingEdges().iterator(); j.hasNext(); )
    if(!scc.contains(((Edge)j.next()).getNext()))
      return false;
    }

    return true;
  }  
  private static boolean isTransient(List scc) {
    if(scc.size() != 1) return false;

    Node n = (Node)scc.get(0);
    for(Iterator i = n.getOutgoingEdges().iterator();
    i.hasNext(); )
      if(((Edge)i.next()).getNext() == n) 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.SCCReduction [<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) {
    boolean changed;
    String type = g.getStringAttribute("type");
    String ac = g.getStringAttribute("ac");
    boolean acNodes = ac.equals("nodes");

    for(Iterator i = SCC.scc(g).iterator(); i.hasNext(); )
      clearExternalEdges((List)i.next(), g);

    do {
      changed = false;

      List sccs = SCC.scc(g);

      for(Iterator i = sccs.iterator(); i.hasNext(); ) {
    List scc = (List)i.next();
    boolean accepting = isAccepting(scc, g);


    if(!accepting && isTerminal(scc)) {
      changed = true;

      for(Iterator j = scc.iterator(); j.hasNext(); )
        ((Node)j.next()).remove();
    } else if(isTransient(scc) || !accepting) {
      changed |= anyAcceptingState(scc, g);
      clearAccepting(scc, g);
    }
      }
    } while(changed);

    return g;
  }  
}

---