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

Algorithms in Java, Part 5 (Graph Algorithms) code

  private void swim(int k)
    { while (k > 1 && less(k, (k+d-2)/d))
        { exch(k, (k+d-2)/d); k = (k+d-2)/d; } }
  private void sink(int k, int N)
    { int j;
      while ((j = d*(k-1)+2) <= N)
        { 
          for (int i = j+1; i < j+d && i <= N; i++)
            if (less(i, j)) j = i;
          if (!(less(j, k))) break;
          exch(k, j); k = j;
        }
    }
  doublePQi(int maxN, double[] a)
    { this.a = a; this.N = 0;
      pq = new int[maxN+1]; qp = new int[maxN+1];
      for (int i = 0; i <= maxN; i++) 
        { pq[i] = 0; qp[i] = 0; }
    }
  boolean empty() { return N == 0; }
  void insert(int v) 
    { pq[++N] = v; qp[v] = N; swim(N); }
  int getmin()
    { exch(1, N); sink(1, N-1); return pq[N--]; }
  void lower(int k)
    { swim(qp[k]); }
}

----------
CHAPTER 21. Shortest Paths
-----
class GraphSPT
{ private double[] wt;
  private Edge[] spt;
  GraphSPT(Graph G, int s)  
  { int V = G.V();
    wt = new double[V]; spt = new Edge[V]; 
    for (int v = 0; v < V; v++) wt[v] = maxWT; 
    doublePQi pQ = new doublePQi(V, wt);
    for (int v = 0; v < V; v++) pQ.insert(v);
    wt[s] = 0.0; pQ.lower(s);  
    while (!pQ.empty()) 
    { int v = pQ.getmin(); // wt[v] = 0.0;
      if (v != s && spt[v] == null) return; 
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
        { int w = e.other(v); 
          double P = wt[v] + e.wt();
          if (P < wt[w]) 
            { wt[w] = P; pQ.lower(w); spt[w] = e; }
        }
    }
  }
  Edge pathR(int v) { return spt[v]; }
  double dist(int v) { return wt[v]; }
}
-----
class GraphSPall // ADT interface
  { // implementations and private members hidden
    GraphSPall(GRAPH G)
    Edge path(int, int)
    Edge pathR(int, int)
    double dist(int, int)
  }
-----
static double diameter(Graph G)
{ int vmax = 0, wmax = 0;
  GraphSPall all = new GraphSPall(G);
  for (int v = 0; v < G.V(); v++)
    for (int w = 0; w < G.V(); w++)
      if (all.path(v, w) != null)
        if (all.dist(v, w) > all.dist(vmax, wmax))
          { vmax = v; wmax = w; }
  int v = vmax; Out.print(v + "");
  while (v != wmax) 
  { v = all.path(v, wmax).w(); Out.print("-" + v); }
  return all.dist(vmax, wmax);
}
-----
class GraphSPall
{ private GraphSPT[] A;
  GraphSPall(Graph G)  
    { 
      A = new GraphSPT[G.V()];
      for (int v = 0; v < G.V(); v++) 
        A[v] = new GraphSPT(G, v); 
    }
  Edge pathR(int s, int t) 
    { return A[s].pathR(t); }
  double dist(int s, int t) 
    { return A[s].dist(t); }
}
-----
class GraphSPall
{ private Edge[][] p;
  private double[][] d;
  GraphSPall(Graph G)  
    { int V = G.V();
      p = new Edge[V][V]; d = new double[V][V];
      for (int s = 0; s < V; s++) 
        for (int t = 0; t < V; t++) 
          d[s][t] = maxWT; 
      for (int s = 0; s < V; s++)
        for (int t = 0; t < V; t++) 
          if (G.edge(s, t) != null)
            { p[s][t] = G.edge(s, t); 
              d[s][t] = G.edge(s, t).wt(); } 
      for (int s = 0; s < V; s++) d[s][s] = 0.0;
      for (int i = 0; i < V; i++)
        for (int s = 0; s < V; s++)
          if (p[s][i] != null)
            for (int t = 0; t < V; t++)
              if (s != t) 
                if (d[s][t] > d[s][i] + d[i][t])
                  { p[s][t] = p[s][i];
                    d[s][t] = d[s][i] + d[i][t]; }
    }
  Edge path(int s, int t) 
    { return p[s][t]; }
  double dist(int s, int t) 
    { return d[s][t]; }
}
-----
class DagLPT
{ private double[] wt;
  private Edge[] lpt;
  DagLPT(Graph G)  
  { 
    wt = new double[G.V()]; lpt = new Edge[G.V()]; 
    DagTS ts = new DagTS(G);
    for (int j = 0; j < G.V(); j++) 
     { int v = ts.order(j);
       AdjList A = G.getAdjList(v);
       for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
         { int w = e.w();
           if (wt[w] < wt[v] + e.wt())
             { wt[w] = wt[v] + e.wt(); lpt[w] = e; }       
         }
     }
  }
  Edge pathR(int v) { return lpt[v]; }
  double dist(int v) { return wt[v]; }
}
-----
class DagSPall
{ 
  private Edge[][] p;
  private double[][] d;
  void dfsR(Graph G, int s)  
    { AdjList A = G.getAdjList(s);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
      { int t = e.w(); double w = e.wt();
        if (d[s][t] > w)
          { d[s][t] = w; p[s][t] = e; }
        if (p[t][t] == null) dfsR(G, t);
        for (int i = 0; i < G.V(); i++)
          if (p[t][i] != null)
            if (d[s][i] > w + d[t][i])
            { d[s][i] = w + d[t][i]; p[s][i] = e; }
      }
    }
  DagSPall(Graph G)  
    { int V = G.V();
      p = new Edge[V][V]; d = new double[V][V];
      for (int s = 0; s < V; s++) 
        for (int t = 0; t < V; t++) 
          d[s][t] = maxWT; 
      for (int s = 0; s < V; s++)
        if (p[s][s] == null) dfsR(G, s);
    }
  Edge path(int s, int t) 
    { return p[s][t]; }
  double dist(int s, int t) 
    { return d[s][t]; }
}
-----
class Schedule
  {
    public static void main(String[] args)
      { int N = Integer.parseInt(args[0]);
        double[] duration = new double[N];
        Graph G = new Graph(N, true);
        In.init();
        for (int i = 0; i < N; i++) 
          duration[i] = In.getDouble();
        while (!In.empty())
          { int s = In.getInt(), t = In.getInt();
            G.insert(new Edge(s, t, duration[s])); }
        if (!GraphUtilities.acyclic(G)) 
          { Out.println("not feasible"); return; }
        DagLPT lpt = new DagLPT(G);
        for (int i = 0; i < N; i++)
          Out.println(i + "  " + lpt.dist(i));
      }
  }  
-----
  GraphSPT(Graph G, int s)  
  { int V = G.V(), N = 0;
    wt = new double[V]; spt = new Edge[V]; 
    for (int v = 0; v < V; v++) wt[v] = maxWT; 
    intQueue Q = new intQueue(G.E());
    wt[s] = 0.0; Q.put(s);  Q.put(V);
    while (!Q.empty()) 
    { int v;
      while ((v = Q.get()) == V) 
        { if (N++ > V) return; Q.put(V); }
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
        { int w = e.other(v); 
          double P = wt[v] + e.wt();
          if (P < wt[w]) 
            { wt[w] = P; Q.put(w); spt[w] = e; }
        }
    }
  }

----------
CHAPTER 22. Network Flow
-----
static int flow(Network G, int v) 
  { int x = 0;
    AdjList A = G.getAdjList(v);
    for (Edge e = A.beg(); !A.end(); e = A.nxt())
      x += e.from(v) ? e.flow() : -e.flow();
    return x; 
  }
static boolean flowcheck(Network G, int s, int t) 
  { 
    for (int v = 0; v < G.V(); v++)
      if ((v != s) && (v != t))
        if (flow(G, v) != 0) return false;
    int sflow = flow(G, s);
    if (sflow < 0) return false;
    if (sflow + flow(G, t) != 0) return false;
    return true; 
  }    
-----
class Edge
  { private int pv, pw, pcap, pflow;
    Edge(int v, int w, int cap)
      { pv = v; pw = w; pcap = cap; pflow = 0; }
    int v() { return pv; }  
    int w() { return pw; }
    int cap() { return pcap; }
    int flow() { return pflow; }
    boolean from (int v)
      { return pv == v; } 
    int other(int v)
      { return from(v) ? pw : pv; } 
    int capRto(int v)
      { return from(v) ? pflow : pcap - pflow; }
    void addflowRto(int v, int d) 
      { pflow += from(v) ? -d : d; }
  }
-----
class NetworkMaxFlow
{ private Network G; private int s, t;
  private int[] wt;
  private Edge[] st;
  private int ST(int v) { return st[v].other(v); }
  private void augment(int s, int t)
    { int d = st[t].capRto(t);
      for (int v = ST(t); v != s; v = ST(v))
        if (st[v].capRto(v) < d) 
          d = st[v].capRto(v);
      st[t].addflowRto(t, d); 
      for (int v = ST(t); v != s; v = ST(v))
        st[v].addflowRto(v, d); 
    }
  private boolean pfs()
    // Program 22.4
  NetworkMaxFlow(Network G, int s, int t)  
    { this.G = G; this.s = s; this.t = t;
      wt = new int[G.V()]; st = new Edge[G.V()];
      while (pfs()) augment(s, t);
    }
}
-----
private boolean pfs()
{ intPQi pQ = new intPQi(G.V(), wt);
  for (int v = 0; v < G.V(); v++) 
    { wt[v] = 0; st[v] = null; pQ.insert(v); }
  wt[s] = -Edge.M; pQ.lower(s);  
  while (!pQ.empty()) 
    { int v = pQ.getmin(); wt[v] = -Edge.M; 
      if (v == t) break;  
      if (v != s && st[v] == null) break;  
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
        { int w = e.other(v);
          int cap = e.capRto(w);
          int P = cap < -wt[v] ? cap : -wt[v];
          if (cap > 0 && -P < wt[w]) 
            { wt[w] = -P; pQ.lower(w); st[w] = e; }
        }
    }
  return st[t] != null;
}
-----
class NetworkMaxFlow
{ private Network G; private int s, t;
  private int[] h, wt;
  private void initheights()
    // See Exercise 22.52
  NetworkMaxFlow(Network G, int s, int t)  
  { this.G = G; this.s = s; this.t = t;
    wt = new int[G.V()]; h = new int[G.V()];
    initheights();
    intGQ gQ = new intGQ(G.V());
    gQ.put(s); wt[t] = -(wt[s] = Edge.M*G.V());
    while (!gQ.empty()) 
    { int v = gQ.get();
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
        { int w = e.other(v), cap = e.capRto(w);
          int P = cap < wt[v] ? cap : wt[v];
          if (P > 0 && v == s || h[v] == h[w]+1) 
            { e.addflowRto(w, P); 
              wt[v] -= P; wt[w] += P;
              if ((w != s) && (w != t)) gQ.put(w); 
            }
        }
      if (v != s && v != t && wt[v] > 0)
        { h[v]++; gQ.put(v); }
    }
  }
}
-----
class NetworkFeasibleFlow
{ 
  NetworkFeasibleFlow(Network G, int[] sd)  
  { 
    Network F = new Network(G.V()+2);
    for (int v = 0; v < G.V(); v++) 
     { AdjList A = G.getAdjList(v);
       for (Edge e = A.beg(); !A.end(); e = A.nxt())  
         F.insert(e);
     }    
    int s = G.V(), t = G.V()+1;
    for (int i = 0; i < G.V(); i++)
      if (sd[i] >= 0) 
           F.insert(new Edge(s, i, sd[i]));
      else F.insert(new Edge(i, t, -sd[i]));
    NetworkMaxFlow M = new NetworkMaxFlow(F, s, t);
  }
}
-----
class BipartiteMatch
{
  public static void main(String[] args)
  { int N = Integer.parseInt(args[0]);
    int s = 2*N, t = 2*N+1;
    Network G = new Network(2*N + 2);
    for (int i = 0; i < N; i++)
      G.insert(new Edge(s, i, 1));
    for (int i = N; i < 2*N; i++)
      G.insert(new Edge(i, t, 1));
    for (In.init(); !In.empty(); )
      G.insert(new Edge(In.getInt(),In.getInt(),1));
    NetworkMaxFlow M = new NetworkMaxFlow(G, s, t);
    for (int i = 0; i < N; i++) 
    {
      AdjList A = G.getAdjList(i);
      for (Edge e = A.beg(); !A.end(); e = A.nxt())
        if (e.flow() == 1 &&  e.from(i))
          Out.println(e.v() + "-" + e.w());
    }
  }
}  
-----
static int cost(Network G)
{ int x = 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) && e.costRto(e.w()) < Edge.C)
          x += e.flow()*e.costRto(e.w()); 
    }
  return x; 
}
-----
class NetworkMinCost
{ private Network G; private int s, t;
  private Edge[] st;
  private int ST(int v) { return st[v].other(v); }
  private void augment(int s, int t)
    // See Program 22.3 
  private int negcyc()
    // See Exercise 22.108
  NetworkMinCost(Network G, int s, int t)  
   { this.G = G; this.s = s; this.t = t;
     st = new Edge[G.V()];
     NetworkMaxFlow M = new NetworkMaxFlow(G, s, t);
     for (int x = negcyc(); x != -1; x = negcyc())
       { augment(x, x); }
   }
}
-----
private int phiR(int v) 
  { 
    if (mark[v] == valid) return phi[v];
    phi[v] = phiR(ST(v)) - st[v].costRto(v);
    mark[v] = valid;
    return phi[v]; 
  }
-----
private int lca(int v, int w) 
  { mark[v] = ++valid; mark[w] = valid;
    while (v != w)
      { 
        if (v != t) v = ST(v);
        if (v != t && mark[v] == valid) return v;
        mark[v] = valid;
        if (w != t) w = ST(w); 
        if (w != t && mark[w] == valid) return w;
        mark[w] = valid; 
      }
    return v; 
  }
private Edge augment(Edge x)
  { int v = x.v(), w = x.w(); int r = lca(v, w);
    int d = x.capRto(w);
    for (int u = w; u != r; u = ST(u))
      if (st[u].capRto(ST(u)) < d) 
        d = st[u].capRto(ST(u));
    for (int u = v; u != r; u = ST(u))
      if (st[u].capRto(u) < d) 
        d = st[u].capRto(u);
    x.addflowRto(w, d); Edge e = x;
    for (int u = w; u != r; u = ST(u))
      { st[u].addflowRto(ST(u), d); 
        if (st[u].capRto(ST(u)) == 0) e = st[u]; }
    for (int u = v; u != r; u = ST(u))
      { st[u].addflowRto(u, d); 
        if (st[u].capRto(u) == 0) e = st[u]; }
    return e;
  }
-----
private boolean onpath(int a, int b, int c)
  { 
    for (int i = a; i != c; i = ST(i))
      if (i == b) return true;
    return false; 
  }
private void reverse(int u, int x)
  { Edge e = st[u];
    for (int i = ST(u); i != x; i = ST(i))
      { Edge y = st[i]; st[i] = e; e = y; } 
  }
private void subs(Edge w, Edge y) 
  { int u = y.w(), v = y.v(), x = w.w();
    if (st[x] != w) x = w.v(); 
    int r = lca(u, v);
    if (onpath(u, x, r))
      { reverse(u, x); st[u] = y; return; }
    if (onpath(v, x, r))
      { reverse(v, x); st[v] = y; return; } 
  }
-----
private int costR(Edge e, int v)
  { int R = e.cost() + phi[e.w()] - phi[e.v()];
    return  e.from(v) ? R : -R; }
private Edge besteligible()
  { Edge x = null; int V = G.V();
    for (int v = 0, min = Edge.C*V; v < V; v++) 
    {
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt())
        if (e.capRto(e.other(v)) > 0) 
          if (e.capRto(v) == 0)
            if (costR(e, v) < min) 
              { x = e; min = costR(e, v); } 
    }
    return x;
  }
-----
class NetworkMinCost
{ private Network G; private int s, t, valid;
  private Edge[] st;
  private int[] mark, phi;
  private int ST(int v) { return st[v].other(v); }
  private void dfsR(Edge x, int v) 
    // See Exercise 22.117   
  private int phiR(int v)           // Program 22.10   
  private Edge augment(Edge x)      // Program 22.11 
  private void subs(Edge w, Edge y) // Program 22.12
  private int costR(Edge e, int v)  // Program 22.13
  private Edge besteligible()       // Program 22.13
  NetworkMinCost(Network G, int s, int t)  
    { int V = G.V(); 
      this.G = G; this.s = s; this.t = t; 
      st = new Edge[V];
      mark = new int[V]; phi = new int[V];
      for (int i = 0; i < V; i++) mark[i] = -1;
      Edge z = new Edge(s, t, Edge.M*V, Edge.C*V);
      G.insert(z); z.addflowRto(t, z.cap()); 
      dfsR(z, t);
      for (valid = 1; ; valid++ ) 
        { 
          phi[t] = z.costRto(s); mark[t] = valid; 
          for (int v = 0; v < V; v++) 
            if (v != t) phi[v] = phiR(v);
          Edge x = besteligible();
          if (costR(x, x.v()) == 0) break;
          subs(augment(x), x);
        }
      G.remove(z);
    }
}
-----
int old = 0;
for (valid = 1; valid != old; ) 
  {
    old = valid;
    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.capRto(e.other(v)) > 0)
          if (e.capRto(v) == 0)
            { subs(augment(e), e); valid++; }
    }
  }