graph_algorithms_code.txt

book: Algorithms in C++, Part 5 (Graph Algorithms) code

  void fixUp(int k)
    { while (k > 1 && a[pq[(k+d-2)/d]] > a[pq[k]])
        { exch(k, (k+d-2)/d); k = (k+d-2)/d; } }
  void fixDown(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 (a[pq[j]] > a[pq[i]]) j = i;
          if (!(a[pq[k]] > a[pq[j]])) break;
          exch(k, j); k = j;
        }
    }
public:
  PQi(int N, const vector<keyType> &a, int d = 3) : 
    a(a), pq(N+1, 0), qp(N+1, 0), N(0), d(d) { }
  int empty() const { return N == 0; }
  void insert(int v) 
    { pq[++N] = v; qp[v] = N; fixUp(N); }
  int getmin()
    { exch(1, N); fixDown(1, N-1); return pq[N--]; }
  void lower(int k)
    { fixUp(qp[k]); }
};

----------
CHAPTER 21. Shortest Paths
-----
 template <class Graph, class Edge> class SPT
{ const Graph &G;
  vector<double> wt;
  vector<Edge *> spt;
public:
  SPT(const Graph &G, int s) : G(G), 
    spt(G.V()), wt(G.V(), G.V())
  { PQi<double> pQ(G.V(), wt);
    for (int v = 0; v < G.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] == 0) return;  
      typename Graph::adjIterator A(G, v); 
      for (Edge* e = A.beg(); !A.end(); e = A.nxt()) 
        { int w = e->w(); 
          double P = wt[v] + e->wt();
          if (P < wt[w]) 
            { wt[w] = P; pQ.lower(w); spt[w] = e; }
        }
    }
  }
  Edge *pathR(int v) const { return spt[v]; }
  double dist(int v) const { return wt[v]; }
};
-----
template <class Graph, class Edge> class SPall
{
  public:
    SPall(const Graph &);
    Edge *path(int, int) const;
    Edge *pathR(int, int) const;
    double dist(int, int) const;
};
-----
template <class Graph, class Edge>
double diameter(Graph &G)
{ int vmax = 0, wmax = 0;
  allSP<Graph, Edge> all(G);
  for (int v = 0; v < G.V(); v++)
    for (int w = 0; w < G.V(); w++)
      if (all.path(v, w))
        if (all.dist(v, w) > all.dist(vmax, wmax))
          { vmax = v; wmax = w; }
  int v = vmax; cout << v;
  while (v != wmax) 
   { v = all.path(v, wmax)->w(); cout << "-" << v; }
  return all.dist(vmax, wmax);
}
-----
#include "SPT.cc"
template <class Graph, class Edge> class allSP
{ const Graph &G;
  vector< SPT<Graph, Edge> *> A;
public:
  allSP(const Graph &G) : G(G), A(G.V())
    { for (int s = 0; s < G.V(); s++) 
        A[s] = new SPT<Graph, Edge>(G, s); }
  Edge *pathR(int s, int t) const
    { return A[s]->pathR(t); }
  double dist(int s, int t) const
    { return A[s]->dist(t); }
};
-----
template <class Graph, class Edge> class allSP 
{ const Graph &G;
  vector <vector <Edge *> > p;
  vector <vector <double> > d;
public:
  allSP(const Graph &G) : G(G), p(G.V()), d(G.V())
    { int V = G.V(); 
      for (int i = 0; i < V; i++) 
        { p[i].assign(V, 0); d[i].assign(V, V); }
      for (int s = 0; s < V; s++)
        for (int t = 0; t < V; t++) 
          if (G.edge(s, t))
            { 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;
      for (int i = 0; i < V; i++)
        for (int s = 0; s < V; s++)
          if (p[s][i])
            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) const
    { return p[s][t]; }
  double dist(int s, int t) const
    { return d[s][t]; }
};
-----
#include "dagTS.cc"
template <class Graph, class Edge> class LPTdag
{ const Graph &G;
  vector<double> wt;
  vector<Edge *> lpt;
public:
  LPTdag(const Graph &G) : G(G), 
    lpt(G.V()), wt(G.V(), 0)
  { int j, w;
    dagTS<Graph> ts(G);
    for (int v = ts[j = 0]; j < G.V(); v = ts[++j]) 
    { typename Graph::adjIterator A(G, v);
      for (Edge* e = A.beg(); !A.end(); e = A.nxt()) 
        if (wt[w = e->w()] < wt[v] + e->wt())
          { wt[w] = wt[v] + e->wt(); lpt[w] = e; }
    }
  }
  Edge *pathR(int v) const { return lpt[v]; }
  double dist(int v) const { return wt[v]; }
};
-----
template <class Graph, class Edge> class allSPdag 
{ const Graph &G;
  vector <vector <Edge *> > p;
  vector <vector <double> > d;
  void dfsR(int s) 
  { typename Graph::adjIterator A(G, 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] == 0) dfsR(t);
      for (int i = 0; i < G.V(); i++)
        if (p[t][i])
          if (d[s][i] > w + d[t][i])
            { d[s][i] = w + d[t][i]; p[s][i] = e; }
    }
  }
public:
  allSPdag(const Graph &G) : G(G), 
    p(G.V()), d(G.V())
  { int V = G.V(); 
    for (int i = 0; i < V; i++) 
      { p[i].assign(V, 0); d[i].assign(V, V); }
    for (int s = 0; s < V; s++)
      if (p[s][s] == 0) dfsR(s);
  }
  Edge *path(int s, int t) const 
    { return p[s][t]; }
  double dist(int s, int t) const 
    { return d[s][t]; }
};
-----
#include "GRAPHbasic.cc"
#include "GRAPHio.cc"
#include "LPTdag.cc"
typedef WeightedEdge EDGE;
typedef DenseGRAPH<EDGE> GRAPH;
int main(int argc, char *argv[])
  { int i, s, t, N = atoi(argv[1]);
    double duration[N];
    GRAPH G(N, true);
    for (int i = 0; i < N; i++) 
      cin >> duration[i];
    while (cin >> s >> t) 
      G.insert(new EDGE(s, t, duration[s]));
    LPTdag<GRAPH, EDGE> lpt(G);
    for (i = 0; i < N; i++)
      cout << i << " " << lpt.dist(i) << endl;
  }
-----
  SPT(Graph &G, int s) : G(G), 
    spt(G.V()), wt(G.V(), G.V())
  { QUEUE<int> Q; int N = 0;
    wt[s] = 0.0; 
    Q.put(s); Q.put(G.V());
    while (!Q.empty())
    { int v;
      while ((v = Q.get()) == G.V()) 
        { if (N++ > G.V()) return; Q.put(G.V()); }
      typename Graph::adjIterator A(G, v); 
      for (Edge* e = A.beg(); !A.end(); e = A.nxt()) 
        { int w = e->w(); 
          double P = wt[v] + e->wt();
          if (P < wt[w])
            { wt[w] = P; Q.put(w); spt[w] = e; }
        }
    }
  }

----------
CHAPTER 22. Network Flow
-----
template <class Graph, class Edge> class check
{
 public:
  static int flow(Graph &G, int v) 
    { int x = 0;
      typename Graph::adjIterator A(G, v);
      for (Edge* e = A.beg(); !A.end(); e = A.nxt()) 
        x += e->from(v) ? e->flow() : -e->flow();
      return x; 
    }
  static bool flow(Graph &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
{ int pv, pw, pcap, pflow;
public:
  EDGE(int v, int w, int cap) :
      pv(v), pw(w), pcap(cap), pflow(0) { }
  int v() const { return pv; }
  int w() const { return pw; }
  int cap() const { return pcap; }
  int flow() const { return pflow; }
  bool from (int v) const 
    { return pv == v; } 
  int other(int v) const 
    { return from(v) ? pw : pv; } 
  int capRto(int v) const
    { return from(v) ? pflow : pcap - pflow; }
  void addflowRto(int v, int d) 
    { pflow += from(v) ? -d : d; }
};
-----
template <class Graph, class Edge> class MAXFLOW
{ const Graph &G;
  int s, t;
  vector<int> wt;
  vector<Edge *> st;
  int ST(int v) const { return st[v]->other(v); }
  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); 
    }
  bool pfs();
public:
  MAXFLOW(const Graph &G, int s, int t) : G(G),
    s(s), t(t), st(G.V()), wt(G.V())
  { while (pfs()) augment(s, t); }
};
-----
template <class Graph, class Edge>
bool MAXFLOW<Graph, Edge>::pfs()
  { PQi<int> pQ(G.V(), wt);
    for (int v = 0; v < G.V(); v++) 
      { wt[v] = 0; st[v] = 0; pQ.insert(v); }
    wt[s] = -M; pQ.lower(s);  
    while (!pQ.empty()) 
    { int v = pQ.getmin(); wt[v] = -M; 
      if (v == t || (v != s && st[v] == 0)) break;  
      typename Graph::adjIterator A(G, 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] != 0;
  }
-----
template <class Graph, class Edge> class MAXFLOW
{ const Graph &G;
  int s, t;
  vector<int> h, wt;
  void initheights();
public:
  MAXFLOW(const Graph &G, int s, int t) : G(G),
    s(s), t(t), h(G.V()), wt(G.V(), 0)
  { initheights();
    GQ gQ(G.V());
    gQ.put(s); wt[t] = -(wt[s] = M*G.V());
    while (!gQ.empty()) 
    { int v = gQ.get();
      typename Graph::adjIterator A(G, 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 (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); }
    }
  }
};
-----
#include "MAXFLOW.cc"
template <class Graph, class Edge> class FEASIBLE
{ const Graph &G;
  void freeedges(const Graph &F, int v)
   { typename Graph::adjIterator A(F, v);
     for (EDGE* e = A.beg(); !A.end(); e = A.nxt())
       delete e;
   }
public:
  FEASIBLE(const Graph &G, vector<int> sd) : G(G)
  { 
    Graph F(G.V()+2);
    for (int v = 0; v < G.V(); v++) 
    {
      typename Graph::adjIterator A(G, 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]));
    MAXFLOW<Graph, Edge>(F, s, t);
    freeedges(F, s); freeedges(F, t);
  }
};
-----
#include "GRAPHbasic.cc"
#include "MAXFLOW.cc"
int main(int argc, char *argv[])
{ int s, t, N = atoi(argv[1]);
  GRAPH<EDGE> G(2*N+2);
  for (int i = 0; i < N; i++)
    G.insert(new EDGE(2*N, i, 1));
  while (cin >> s >> t) 
    G.insert(new EDGE(s, t, 1));
  for (int i = N; i < 2*N; i++)
    G.insert(new EDGE(i, 2*N+1, 1));
  MAXFLOW<GRAPH<EDGE>, EDGE>(G, 2*N, 2*N+1);
  for (int i = 0; i < N; i++)
    {
      GRAPH<EDGE>::adjIterator A(G, i);
      for (EDGE* e = A.beg(); !A.end(); e = A.nxt()) 
        if (e->flow() == 1 &&  e->from(i))
        cout << e->v() << "-" << e->w() << endl;
    }
        
}
-----
static int cost(Graph &G)
{ int x = 0;
  for (int v = 0; v < G.V(); v++) 
    { 
      typename Graph::adjIterator A(G, v);
      for (Edge* e = A.beg(); !A.end(); e = A.nxt()) 
        if (e->from(v) && e->costRto(e->w()) < C)
          x += e->flow()*e->costRto(e->w()); 
    }
  return x; 
}
-----
template <class Graph, class Edge> class MINCOST
{ const Graph &G;
  int s, t;
  vector<int> wt;
  vector <Edge *> st;
  int ST(int v) const;
  void augment(int, int);
  int negcyc(int);
  int negcyc();
public:
  MINCOST(const Graph &G, int s, int t) : G(G),
    s(s), t(t), st(G.V()), wt(G.V())
  { MAXFLOW<Graph, Edge>(G, s, t);
    for (int x = negcyc(); x != -1; x = negcyc())
      { augment(x, x); }
  }
};
-----
  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]; 
    }
-----
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; 
  }
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;
  }
-----
  bool onpath(int a, int b, int c)
    { 
      for (int i = a; i != c; i = ST(i))
        if (i == b) return true;
      return false; 
    }
  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; } 
    }
  void update(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; } 
    }
-----
int costR(Edge *e, int v)
  { int R = e->cost() + phi[e->w()] - phi[e->v()];
    return  e->from(v) ? R : -R; }
Edge *besteligible()
{ Edge *x = 0;
  for (int v = 0, min = C*G.V(); v < G.V(); v++) 
    {
      typename Graph::adjIterator A(G, 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;
}
-----
template <class Graph, class Edge> class MINCOST
{ const Graph &G; int s, t; int valid; 
  vector<Edge *> st; vector<int> mark, phi;
  void dfsR(Edge);
  int ST(int); 
  int phiR(int); 
  int lca(int, int);  Edge *augment(Edge *);
  bool onpath(int, int, int); 
  void reverse(int, int);
  void update(Edge *, Edge *); 
  int costR(Edge *, int); Edge *besteligible();
public:
  MINCOST(Graph &G, int s, int t) : G(G), s(s), t(t) 
    st(G.V()), mark(G.V(), -1), phi(G.V())
  { 
    Edge *z = new EDGE(s, t, M*G.V(), C*G.V());
    G.insert(z);
    z->addflowto(t, z->cap()); 
    dfsR(z);
    for (valid = 1; ; valid++ ) 
      { 
        phi[t] = z->costRto(s); mark[t] = valid; 
        for (int v = 0; v < G.V(); v++) 
          if (v != t) phi[v] = phiR(v);
        Edge *x = besteligible();
        if (costR(x, x->v()) == 0) break;
        update(augment(x), x);
      }
    G.remove(z); delete z;
  }
-----
int old = 0;
for (valid = 1; valid != old; ) 
  {
    old = valid;
    for (int v = 0; v < G.V(); v++) 
    {
      typename Graph::adjIterator A(G, v); 
      for (Edge* e = A.beg(); !A.end(); e = A.nxt()) 
        if (e->capRto(e->other(v)) > 0)
          if (e->capRto(v) == 0)
            { update(augment(e), e); valid++; }
    }
  }