algorithms in java, part 5 (graph algorithms) code.txt

Algorithms in Java, Part 5 (Graph Algorithms) code

        if (ord[t] == -1) 
          { Q.put(new Edge(w, t)); ord[t] = cnt++; }
        else 
          if (st[t] == -1) Q.update(new Edge(w, t));
    }
}
-----
class EdgeGQ
  {
    private Edge[] s; private int N;
    EdgeGQ(int maxN)
      { s = new Edge[maxN + 1]; N = 0; }
    boolean empty()
      { return (N == 0); }
    void put(Edge item)
      { s[N++] = item; }
    void update(Edge x) { }
    Edge get()
      { int i = (int) (N*Math.random());
        Edge t = s[i]; s[i] = s[N-1]; s[N-1] = t;
        return s[--N]; 
      }
  }

----------
CHAPTER 19. Digraphs and DAGs
-----
static Graph reverse(Graph G)
  { Graph R = new Graph(G.V(), true);
    for (int v = 0; v < G.V(); v++) 
      {
        AdjList A = G.getAdjList(v);
        for (int w = A.beg(); !A.end(); w = A.nxt()) 
          R.insert(new Edge(w, v));
      }
    return R;
  }
-----
class GraphDFS
{ private Graph G;
  private int depth, cnt, cntP;
  private int[] pre, post; 
  private void show(String s, Edge e)
    { 
      for (int k = 0; k < depth; k++) 
        Out.print("  ");
      Out.println(e.v + "-" + e.w + " " + s); 
    }
  private void dfsR(Edge e)
    { int w = e.w; show("tree", e); 
      pre[w] = cnt++; depth++;
      AdjList A = G.getAdjList(w);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        { Edge x = new Edge(w, t);
          if (pre[t] == -1) dfsR(x);
          else if (post[t] == -1) show("back", x);
          else if (pre[t] > pre[w]) show("down", x);
          else show("cross", x);
        }
      post[w] = cntP++; depth--;
    }
  GraphDFS(Graph G, int v)  
    { this.G = G; depth = 0; cnt = 0; cntP = 0;
      pre = new int[G.V()]; post = new int[G.V()];
      for (int t = 0; t < G.V(); t++)
        { pre[t] = -1; post[t] = -1; }
      for (int t = 0; t < G.V(); t++)
        if (pre[t] == -1) dfsR(new Edge(t, t)); 
    }
}
-----
class GraphTC
{ private DenseGraph T;
  GraphTC(Graph G)  
    { 
      T = GraphUtilities.densecopy(G);
      for (int s = 0; s < T.V(); s++) 
        T.insert(new Edge(s, s));
      for (int i = 0; i < T.V(); i++)
        for (int s = 0; s < T.V(); s++)
          if (T.edge(s, i))
            for (int t = 0; t < T.V(); t++)
              if (T.edge(i, t))
                T.insert(new Edge(s, t));
    }
  boolean reachable(int s, int t)
    { return T.edge(s, t); }
}
-----
class GraphTC
{ private Graph G;
  private DenseGraph T;
  void tcR(int v, int w)  
    { 
      T.insert(new Edge(v, w));
      AdjList A = G.getAdjList(w);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        if (!T.edge(v, t)) tcR(v, t);
    }
  GraphTC(Graph G)  
    { this.G = G; T = new DenseGraph(G.V(), true);
      for (int v = 0; v < T.V(); v++) tcR(v, v); }
  boolean reachable(int v, int w)
    { return T.edge(v, w); }
}
-----
int compressR(Node h)
  { 
    if (h == null) return 0;
    l = compressR(h.l); 
    r = compressR(h.r);
    t = st.index(l + "", r + "");
    adj[t].l = l; adj[t].r = r;
    return t;
  }
-----
class DagTS
{ private Graph G;
  private int cnt, tcnt;
  private int[] pre, post, postI;
  private void tsR(int v)  
    { 
      pre[v] = cnt++;
      AdjList A = G.getAdjList(v);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        if (pre[t] == -1) tsR(t);
      post[v] = tcnt; postI[tcnt++] = v;
    }
  DagTS(Graph G)  
    { this.G = G; cnt = 0; tcnt = 0; 
      pre = new int[G.V()]; 
      post = new int[G.V()]; postI = new int[G.V()];
      for (int t = 0; t < G.V(); t++)
        { pre[t] = -1; post[t] = -1; postI[t] = -1;}
      for (int t = 0; t < G.V(); t++)
        if (pre[t] == -1) tsR(t); 
    }
  int order(int v) { return postI[v]; }
  int relabel(int v) { return post[v]; }
}
-----
  void tsR(int v)  
    { 
      pre[v] = cnt++;
      for (int w = 0; w < D.V(); w++)
        if (D.edge(w, v))
          if (pre[w] == -1) tsR(w);
      post[v] = tcnt; postI[tcnt++] = v;
    }
-----
class DagTS
{ private Graph D;
  private int[] in, ts, tsI;
  DagTS(Graph D)  
  { this.D = D; 
    intQueue Q = new intQueue(D.V());
    in = new int[D.V()]; 
    ts = new int[D.V()]; tsI = new int[D.V()];
    for (int t = 0; t < D.V(); t++)
      { in[t] = 0; ts[t] = -1; tsI[t] = -1; }
    for (int v = 0; v < D.V(); v++) 
      {
        AdjList A = D.getAdjList(v);
        for (int t = A.beg(); !A.end(); t = A.nxt()) 
          in[t]++;
      }
    for (int v = 0; v < D.V(); v++)
      if (in[v] == 0) Q.put(v);
    for (int j = 0; !Q.empty(); j++) 
      {
        int k = Q.get(); ts[j] = k; tsI[ts[j]] = j;
        AdjList A = D.getAdjList(k);
        for (int t = A.beg(); !A.end(); t = A.nxt()) 
          if (--in[t] == 0) Q.put(t);
      }
  }
  int order(int v) { return ts[v]; }
  int relabel(int v) { return tsI[v]; }
}
-----
class GraphTC
{ private Graph G; private DenseGraph D;
  private int cnt;
  private int[] pre;
  void tcR(int w)  
    { 
      pre[w] = cnt++;
      AdjList A = D.getAdjList(w);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
      { 
        D.insert(new Edge(w, t));
        if (pre[t] > pre[w]) continue;
        if (pre[t] == -1) tcR(t);
        for (int i = 0; i < D.V(); i++)
         if (D.edge(t, i)) D.insert(new Edge(w, i));
      }
    }
  GraphTC(Graph G)  
    { this.G = G; cnt = 0;
      D = GraphUtilities.densecopy(G);
      pre = new int[G.V()];
      for (int v = 0; v < D.V(); v++) pre[v] = -1;
      for (int v = 0; v < D.V(); v++) 
        if (pre[v] == -1) tcR(v); 
    }
  boolean reachable(int v, int w)
    { return D.edge(v, w); }
}
-----
class GraphSC
{ private int cnt, scnt;
  private int[] id, postI, postR;
  private void dfsR(Graph G, int w)  
    { 
      id[w] = scnt;
      AdjList A = G.getAdjList(w);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        if (id[t] == -1) dfsR(G, t);
      postI[cnt++] = w;
    }
  GraphSC(Graph G)  
    { Graph R = GraphUtilities.reverse(G); 
      id = new int[G.V()]; postI = new int[G.V()];
      cnt = 0; scnt = 0; 
      for (int t = 0; t < R.V(); t++) id[t] = -1;
      for (int t = 0; t < R.V(); t++)
        if (id[t] == -1) dfsR(R, t); 
      postR = new int[G.V()];
      for (int t = 0; t < R.V(); t++)
        { postR[t] = postI[t]; }
      cnt = 0; scnt = 0; 
      for (int t = 0; t < R.V(); t++) id[t] = -1;
      for (int v = G.V()-1; v >= 0; v--)
        if (id[postR[v]] == -1)
          { dfsR(G, postR[v]); scnt++; }
    }
  int count() { return scnt; }
  boolean stronglyreachable(int v, int w)
    { return id[v] == id[w]; }
}
-----
class GraphSC
{ private Graph G;
  private int cnt, scnt;
  private int[] id, pre, low;
  private intStack S;
  private void scR(int w)  
    { int t, min = low[w] = pre[w] = cnt++;
      S.push(w);
      AdjList A = G.getAdjList(w);
      for (t = A.beg(); !A.end(); t = A.nxt()) 
        { if (pre[t] == -1) scR(t);
          if (low[t] < min) min = low[t]; }
      if (min < low[w]) { low[w] = min; return; }
      do 
        { id[t = S.pop()] = scnt; low[t] = G.V(); }
      while (t != w);
      scnt++;
    }
  GraphSC(Graph G)  
    { this.G = G; 
      S = new intStack(G.V());
      id = new int[G.V()]; 
      pre = new int[G.V()]; low = new int[G.V()];
      for (int t = 0; t < G.V(); t++)
        { id[t] = -1; pre[t] = -1; low[t] = -1; }
      for (int v = G.V()-1; v >= 0; v--)
        if (pre[v] == -1) scR(v); 
    }
  int count() { return scnt; }
  boolean stronglyreachable(int v, int w)
    { return id[v] == id[w]; }
}
-----
  private void scR(int w)  
    { int v; 
      pre[w] = cnt++;
      S.push(w); P.push(w);
      AdjList A = G.getAdjList(w);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        if (pre[t] == -1) scR(t);
        else if (id[t] == -1) 
          while (pre[P.top()] > pre[t]) P.pop();
      if (P.top() == w) P.pop(); else return;
      do { id[v = S.pop()] = scnt; } while (v != w);
      scnt++;
    }
-----
class GraphTC
{ private GraphSC Gsc;
  private DagTC Ktc;
  GraphTC(Graph G)  
    { DenseGraph K;
      Gsc = new GraphSC(G);
      K = new DenseGraph(Gsc.count(), true);
      for (int v = 0; v < G.V(); v++) 
       { 
        AdjList A = G.getAdjList(v);
        for (int t = A.beg(); !A.end(); t = A.nxt()) 
          K.insert(new Edge(Gsc.ID(v), Gsc.ID(t))); 
       }
      Ktc = new DagTC(K);
    }
  boolean reachable(int v, int w)
    { return Ktc.reachable(Gsc.ID(v), Gsc.ID(w));}
}

----------
CHAPTER 20. Minimum Spanning Trees
-----
class Edge implements Item // ADT interface
  { // implementations and private members hidden
    Edge(int, int, double)
    int v()
    int w()
    double wt()
    boolean from(int)
    int other(int)
    public boolean less(Item)
    public String toString() 
  }
class Graph // ADT interface
  { // implementations and private members hidden
    Graph(int, boolean)
    int V()
    int E()
    boolean directed()
    int insert(Edge)
    void remove(Edge)
    Edge edge(int, int)
    AdjList getAdjList(int)
  }
-----
class Graph
  { private int Vcnt, Ecnt;
    private boolean digraph;
    private Edge adj[][];
    Graph(int V, boolean flag)
      {
        Vcnt = V; Ecnt = 0; digraph = flag;
        adj = new Edge[V][V];
      }
    int V() { return Vcnt; }
    int E() { return Ecnt; }
    boolean directed() { return digraph; }
    void insert(Edge e)
      { int v = e.v(), w = e.w();
        if (adj[v][w] == null) Ecnt++;
        adj[v][w] = e;
        if (!digraph) adj[w][v] = e; 
      } 
    void remove(Edge e)
      { int v = e.v(), w = e.w();
        if (adj[v][w] == null) Ecnt--;
        adj[v][w] = null;
        if (!digraph) adj[w][v] = null; 
      } 
    Edge edge(int v, int w) 
      { return adj[v][w]; }
    AdjList getAdjList(int v)
      // Program 20.4
  }
-----
AdjList getAdjList(int v)
  { return new AdjArray(v); }
private class AdjArray implements AdjList
  { 
    private int i, v;
    adjArray(int v)
      { this.v = v; i = -1; }
    public Edge beg()
      { i = -1; return nxt(); }
    public Edge nxt()
      {
        for (i++; i < V(); i++)
          if (edge(v, i) != null) 
            return edge(v, i);
        return null;
      }
    public boolean end()
      { return i >= V(); }
  }
-----
class Graph // sparse multigraph implementation
  { private int Vcnt, Ecnt;
    private boolean digraph;
    private class Node
      { Edge e; Node next;
        Node(Edge x, Node t) { e = x; next = t; } }
    private Node adj[];
    Graph(int V, boolean flag)
      {
        Vcnt = V; Ecnt = 0; digraph = flag;
        adj = new Node[V];
      }
    int V() { return Vcnt; }
    int E() { return Ecnt; }
    boolean directed() { return digraph; }
    void insert(Edge e)
      { int v = e.v(), w = e.w();
        adj[v] = new Node(e, adj[v]);
        if (!digraph) adj[w] = new Node(e, adj[w]); 
        Ecnt++;
      } 
    AdjList getAdjList(int v)
      // See Program 17.10 and Exercise 20.13
  }
-----
static Edge[] edges(Graph G)
{ Edge[] a = new Edge[G.E()];
  int E = 0; 
  for (int v = 0; v < G.V(); v++) 
    {
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
        if (e.from(v)) a[E++] = e;
    }
  return a;
}
-----
class GraphMST
{ 
  private double[] wt;
  private Edge[] fr, mst;
  GraphMST(Graph G)
    { 
      wt = new double[G.V()];
      mst = new Edge[G.V()]; fr = new Edge[G.V()];
      for (int v = 0; v < G.V(); v++) wt[v] = maxWT; 
      int min = -1; 
      for (int v = 0; min != 0; v = min) 
        { Edge e;
          min = 0;
          for (int w = 1; w < G.V(); w++) 
            if (mst[w] == null)
              { double P = 0.0; e = G.edge(v, w);
                if (e != null)
                  if ((P = e.wt()) < wt[w])
                    { wt[w] = P; fr[w] = e; }
                if (wt[w] < wt[min]) min = w;
              }
          if (min != 0) mst[min] = fr[min];
        }
    }
}
-----
class GraphMST
{ private double[] wt; private Edge[] fr, mst;
  private void pfs(Graph G, int s)
  { doublePQi pQ = new doublePQi(G.V(), wt);
    pQ.insert(s);
    while (!pQ.empty())
    { int v = pQ.getmin();
      mst[v] = fr[v];        
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
        { double P = e.wt(); int w = e.other(v); 
          if (fr[w] == null)
            { wt[w] = P; pQ.insert(w); fr[w] = e; }
          else if (mst[w] == null && P < wt[w])
            { wt[w] = P; pQ.lower(w); fr[w] = e; }
        }
    }
  }
  GraphMST(Graph G)  
    { wt = new double[G.V()];
      mst = new Edge[G.V()]; fr = new Edge[G.V()];
      for (int v = 0; v < G.V(); v++) wt[v] = -1.0; 
      for (int v = 0; v < G.V(); v++)
        if (mst[v] == null) pfs(G, v);
    }
}
-----
class GraphMST
{ private int V;
  private UF uf;
  private Edge[] a, mst;
  GraphMST(Graph G)
    { int v, w, E;
      E = G.E(); V = G.V();
      mst = new Edge[V]; 
      uf = new UF(V);
      a = GraphUtilities.edges(G);
      Sort.sort(a, 0, E-1);
      for (int i = 0, k = 1; i < E && k < V; i++)
        if (!uf.find(v = a[i].v(), w = a[i].w()))
          { uf.unite(v, w); mst[k++] = a[i]; }
    }
}
-----
class GraphMST
{ private UF uf;
  private Edge[] a, b, mst;
  GraphMST(Graph G)
  { Edge z = new Edge(0, 0, maxWT);
    uf = new UF(G.V());
    a = GraphUtilities.edges(G); 
    b = new Edge[G.V()]; mst = new Edge[G.V()+1]; 
    int N, k = 1;
    for (int E = G.E(); E != 0; E = N) 
      { int h, i, j;
        for (int t = 0; t < G.V(); t++) b[t] = z;
        for (h = 0, N = 0; h < E; h++) 
          { Edge e = a[h];
            i = uf.find(e.v()); j = uf.find(e.w());
            if (i == j) continue;
            if (e.wt() < b[i].wt()) b[i] = e;
            if (e.wt() < b[j].wt()) b[j] = e;
            a[N++] = e;
          }
        for (h = 0; h < G.V(); h++) 
         if (b[h] != z)
          if (!uf.find(i = b[h].v(), j = b[h].w()))
            { uf.unite(i, j); mst[k++] = b[h]; }
      }
  }
}
-----
class doublePQi 
{ private int N, d = 3; 
  private double[] a; private int[] pq, qp; 
  private boolean less(int i, int j)
    { return a[pq[i]] < a[pq[j]]; }
  private void exch(int i, int j)
    { int t = pq[i]; pq[i] = pq[j]; pq[j] = t;
      qp[pq[i]] = i; qp[pq[j]] = j; }