graph_algorithms_code.txt

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

class PFS : public SEARCH<Graph> 
{ vector<int> st;
  void searchC(Edge e)
  { GQ<Edge> Q(G.V());
    Q.put(e); ord[e.w] = cnt++; 
    while (!Q.empty()) 
      {
        e = Q.get(); st[e.w] = e.v;        
        typename Graph::adjIterator A(G, e.w);
        for (int t = A.beg(); !A.end(); t = A.nxt()) 
          if (ord[t] == -1)
            { Q.put(Edge(e.w, t)); ord[t] = cnt++; }
          else 
            if (st[t] == -1) Q.update(Edge(e.w, t));
      }
  }
public:
  PFS(Graph &G) : SEARCH<Graph>(G), st(G.V(), -1)
    { search(); }
  int ST(int v) const { return st[v]; }
};

-----
template <class Item>
class GQ
  {
    private:
      vector<Item> s; int N;
    public:
      GQ(int maxN) : s(maxN+1), N(0) { }
      int empty() const
        { return N == 0; }
      void put(Item item)
        { s[N++] = item; }
      void update(Item x) { }
      Item get()
        { int i = int(N*rand()/(1.0+RAND_MAX));
          Item t = s[i];
          s[i] = s[N-1];
          s[N-1] = t;
          return s[--N]; }
  };

----------
CHAPTER 19. Digraphs and DAGs
-----
template <class inGraph, class outGraph> 
void reverse(const inGraph &G, outGraph &R)
  { 
    for (int v = 0; v < G.V(); v++) 
      { typename inGraph::adjIterator A(G, v);
        for (int w = A.beg(); !A.end(); w = A.nxt()) 
          R.insert(Edge(w, v));
      }
  }
-----
template <class Graph> class DFS
{ const Graph &G;
  int depth, cnt, cntP;
  vector<int> pre, post;
  void show(char *s, Edge e)
    { for (int i = 0; i < depth; i++) cout << "  ";
      cout << e.v << "-" << e.w << s << endl; }
  void dfsR(Edge e)
    { int w = e.w; show(" tree", e);
      pre[w] = cnt++; depth++;
      typename Graph::adjIterator A(G, w);
      for (int t = A.beg(); !A.end(); t = A.nxt())
      { Edge x(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--;
    }
public:
  DFS(const Graph &G) : G(G), cnt(0), cntP(0), 
    pre(G.V(), -1), post(G.V(), -1)
    { for (int v = 0; v < G.V(); v++) 
        if (pre[v] == -1) dfsR(Edge(v, v)); }
};
-----
template <class tcGraph, class Graph> class TC 
{ tcGraph T;
public:
  TC(const Graph &G) : T(G) 
    { 
      for (int s = 0; s < T.V(); s++) 
        T.insert(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(Edge(s, t));
    }
  bool reachable(int s, int t) const
    { return T.edge(s, t); }
};
-----
template <class Graph> class tc 
{ Graph T; const Graph &G;
  void tcR(int v, int w)
  { 
    T.insert(Edge(v, w));
    typename Graph::adjIterator A(G, w);
    for (int t = A.beg(); !A.end(); t = A.nxt())
      if (!T.edge(v, t)) tcR(v, t);
  }
public:
  tc(const Graph &G) : G(G), T(G.V(), true)
    { for (int v = 0; v < G.V(); v++) tcR(v, v); }
  bool reachable(int v, int w)
    { return T.edge(v, w); }
};
-----
int compressR(link h)
  { STx st;
    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;
  }
-----
template <class Dag> class dagTS 
{ const Dag &D;
  int cnt, tcnt;
  vector<int> pre, post, postI;
  void tsR(int v)
    { 
      pre[v] = cnt++;
      typename Dag::adjIterator A(D, v);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        if (pre[t] == -1) tsR(t);
      post[v] = tcnt; postI[tcnt++] = v;
    }
public:
  dagTS(const Dag &D) : D(D), tcnt(0), cnt(0),
   pre(D.V(), -1), post(D.V(), -1), postI(D.V(), -1)
    { for (int v = 0; v < D.V(); v++)
        if (pre[v] == -1) tsR(v); }
  int operator[](int v) const { return postI[v]; }
  int relabel(int v) const { 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;
    }
-----
#include "QUEUE.cc"
template <class Dag> class dagTS
{ const Dag &D;
  vector<int> in, ts, tsI;
public:
  dagTS(const Dag &D) : D(D), 
    in(D.V(), 0), ts(D.V(), -1), tsI(D.V(), -1) 
  { QUEUE<int> Q;
    for (int v = 0; v < D.V(); v++) 
      {
        typename Dag::adjIterator A(D, 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++) 
      {
        ts[j] = Q.get(); tsI[ts[j]] = j;
        typename Dag::adjIterator A(D, ts[j]);
        for (int t = A.beg(); !A.end(); t = A.nxt()) 
          if (--in[t] == 0) Q.put(t);
      }
  }
  int operator[](int v) const { return ts[v]; }
  int relabel(int v) const { return tsI[v]; }
};
-----
template <class tcDag, class Dag> class dagTC
{ tcDag T; const Dag &D;
  int cnt;
  vector<int> pre;
  void tcR(int w)
  { 
    pre[w] = cnt++;
    typename Dag::adjIterator A(D, w);
    for (int t = A.beg(); !A.end(); t = A.nxt())
      { 
        T.insert(Edge(w, t));
        if (pre[t] > pre[w]) continue;
        if (pre[t] == -1) tcR(t);
        for (int i = 0; i < T.V(); i++)
          if (T.edge(t, i)) T.insert(Edge(w, i));
      }
  }
public:
  dagTC(const Dag &D) : D(D), cnt(0), 
    pre(D.V(), -1), T(D.V(), true)
    { for (int v = 0; v < D.V(); v++) 
       if (pre[v] == -1) tcR(v); }
  bool reachable(int v, int w) const 
    { return T.edge(v, w); }
};
-----
template <class Graph> class SC 
{ const Graph &G;
  int cnt, scnt;
  vector<int> postI, postR, id;
  void dfsR(const Graph &G, int w)
  { 
    id[w] = scnt;
    typename Graph::adjIterator A(G, w);
    for (int t = A.beg(); !A.end(); t = A.nxt())
      if (id[t] == -1) dfsR(G, t);
    postI[cnt++] = w;
  }
public:
  SC(const Graph &G) : G(G), cnt(0), scnt(0), 
    postI(G.V()), postR(G.V()), id(G.V(), -1)
    { Graph R(G.V(), true);
      reverse(G, R);
      for (int v = 0; v < R.V(); v++)
        if (id[v] == -1) dfsR(R, v);
      postR = postI; cnt = scnt = 0;
      id.assign(G.V(), -1);
      for (int v = G.V()-1; v >= 0; v--)
        if (id[postR[v]] == -1)
          { dfsR(G, postR[v]); scnt++; }
    }
  int count() const { return scnt; }
  bool stronglyreachable(int v, int w) const 
    { return id[v] == id[w]; }
};
-----
#include "STACK.cc"
template <class Graph> class SC 
{ const Graph &G;
  STACK<int> S;
  int cnt, scnt;
  vector<int> pre, low, id;
  void scR(int w)
  { int t; 
    int min = low[w] = pre[w] = cnt++;
    S.push(w);
    typename Graph::adjIterator A(G, 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++;
  }
public:
  SC(const Graph &G) : G(G), cnt(0), scnt(0), 
    pre(G.V(), -1), low(G.V()), id(G.V())
    { for (int v = 0; v < G.V(); v++) 
        if (pre[v] == -1) scR(v); }
  int count() const { return scnt; }
  bool stronglyreachable(int v, int w) const 
    { return id[v] == id[w]; }
};
-----
  void scR(int w)
  { int v;
    pre[w] = cnt++;
    S.push(w); path.push(w);
    typename Graph::adjIterator A(G, w);
    for (int t = A.beg(); !A.end(); t = A.nxt())
      if (pre[t] == -1) scR(t);
      else if (id[t] == -1) 
        while (pre[path.top()] > pre[t]) path.pop();
    if (path.top() == w) path.pop(); else return;
    do { id[v = S.pop()] = scnt; } while (v != w);
    scnt++;
  }
-----
template <class Graph> class TC 
{ const Graph &G; DenseGRAPH *K;
  dagTC<DenseGRAPH, Graph> *Ktc;
  SC<Graph> *Gsc;
public:
  TC(const Graph &G) : G(G)
    { 
      Gsc = new SC<Graph>(G); 
      K = new DenseGRAPH(Gsc->count(), true);
      for (int v = 0; v < G.V(); v++) 
      { typename Graph::adjIterator A(G, v);
        for (int t = A.beg(); !A.end(); t = A.nxt())
          K->insert(Edge(Gsc->ID(v), Gsc->ID(t))); }
      Ktc = new dagTC<DenseGRAPH, Graph>(*K);
    }
  ~TC() { delete K; delete Ktc; delete Gsc; }
  bool reachable(int v, int w)
  { return Ktc->reachable(Gsc->ID(v), Gsc->ID(w));}
};

----------
CHAPTER 20. Minimum Spanning Trees
-----
class EDGE
  { 
    public:
      EDGE(int, int, double);
      int v() const;
      int w() const;
      double wt() const;
      bool from(int) const;
      int other(int) const;
  };
template <class Edge> class GRAPH
  {
    public:
      GRAPH(int, bool);
      ~GRAPH();
      int V() const;
      int E() const;
      bool directed() const;
      int insert(Edge *);
      int remove(Edge *);
      Edge *edge(int, int);
      class adjIterator
        {
          public:
            adjIterator(const GRAPH &, int);
            Edge *beg();
            Edge *nxt();
            bool end();
        };
  };
-----
template <class Graph, class Edge> 
vector <Edge *> edges(const Graph &G)
{ int E = 0;
  vector <Edge *> a(G.E()); 
  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)) a[E++] = e;
    }
  return a;
}
-----
template <class Edge> class DenseGRAPH
{ int Vcnt, Ecnt; bool digraph;
  vector <vector <Edge *> > adj;
public:
  DenseGRAPH(int V, bool digraph = false) :
    adj(V), Vcnt(V), Ecnt(0), digraph(digraph)
    { 
      for (int i = 0; i < V; i++) 
        adj[i].assign(V, 0);
    }
  int V() const { return Vcnt; }
  int E() const { return Ecnt; }
  bool directed() const { return digraph; }
  void insert(Edge *e)
    { int v = e->v(), w = e->w();
      if (adj[v][w] == 0) 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] != 0) Ecnt--;
      adj[v][w] = 0;
      if (!digraph) adj[w][v] = 0; 
    } 
  Edge* edge(int v, int w) const 
    { return adj[v][w]; }
  class adjIterator;
  friend class adjIterator;
};
-----
template <class Edge>
class DenseGRAPH<Edge>::adjIterator
{ const DenseGRAPH<Edge> &G;
  int i, v;
public:
  adjIterator(const DenseGRAPH<Edge> &G, int v) : 
    G(G), v(v), i(0) { }
  Edge *beg()
    { i = -1; return nxt(); }
  Edge *nxt()
    {
      for (i++; i < G.V(); i++)
        if (G.edge(v, i)) return G.adj[v][i];
      return 0;
    }
  bool end() const
    { return i >= G.V(); }
};
-----
template <class Edge> class SparseMultiGRAPH
{ int Vcnt, Ecnt; bool digraph;
  struct node
    { Edge* e; node* next;
      node(Edge* e, node* next): e(e), next(next) {}
    };
  typedef node* link;
  vector <link> adj;
public:
  SparseMultiGRAPH(int V, bool digraph = false) :
    adj(V), Vcnt(V), Ecnt(0), digraph(digraph) { }
  int V() const { return Vcnt; }
  int E() const { return Ecnt; }
  bool directed() const { return digraph; }
  void insert(Edge *e)
    { 
      adj[e->v()] = new node(e, adj[e->v()]);
      if (!digraph) 
        adj[e->w()] = new node(e, adj[e->w()]); 
      Ecnt++;
    } 
  class adjIterator;
  friend class adjIterator;
};
-----
template <class Graph, class Edge> class MST
{ const Graph &G;
  vector<double> wt;
  vector<Edge *> fr, mst;
public:
  MST(const Graph &G) : G(G), 
    mst(G.V()), wt(G.V(), G.V()), fr(G.V())
    { int min = -1; 
      for (int v = 0; min != 0; v = min) 
      { 
        min = 0;
        for (int w = 1; w < G.V(); w++) 
          if (mst[w] == 0)
            { double P; Edge* e = G.edge(v, w);
              if (e)
                if ((P = e->wt()) < wt[w])
                  { wt[w] = P; fr[w] = e; }
              if (wt[w] < wt[min]) min = w;
            }
        if (min) mst[min] = fr[min];
      }
    }
  void show() 
  { for (int v = 1; v < G.V(); v++) 
      if (mst[v]) mst[v]->show();} 
};
-----
template <class Graph, class Edge> class MST
{ const Graph &G;
  vector<double> wt;
  vector<Edge *> fr, mst;
  void pfs(int s) 
  { PQi<double> pQ(G.V(), wt);
    pQ.insert(s);
    while (!pQ.empty()) 
    { int v = pQ.getmin(); 
      mst[v] = fr[v];
      typename Graph::adjIterator A(G, v);
      for (Edge* e = A.beg(); !A.end(); e = A.nxt()) 
        { double P = e->wt(); int w = e->other(v); 
          if (fr[w] == 0)
            { wt[w] = P; pQ.insert(w); fr[w] = e; }
          else if (mst[w] == 0 && P < wt[w])
            { wt[w] = P; pQ.lower(w); fr[w] = e; }
        }
    }
  }
public:
  MST(Graph &G) : G(G), 
    fr(G.V()), mst(G.V()), wt(G.V(), -1)
    { for (int v = 0; v < G.V(); v++)
        if (mst[v] == 0) pfs(v); }
};
-----
template <class Graph, class Edge, class EdgePtr> 
class MST
{ const Graph &G;
  vector<EdgePtr> a, mst;
  UF uf;
public:
  MST(Graph &G) : G(G), uf(G.V()), mst(G.V())
  { int V = G.V(), E = G.E();
    a = edges<Graph, Edge, EdgePtr>(G);
    sort<EdgePtr>(a, 0, E-1);
    for (int i = 0, k = 1; i < E && k < V; i++)
      if (!uf.find(a[i]->v, a[i]->w)) 
        { uf.unite(a[i]->v, a[i]->w);
          mst[k++] = a[i]; }
  }
};
-----
template <class Graph, class Edge> class MST
{ const Graph &G;
  vector<Edge *> a, b, mst;
  UF uf;
public:
  MST(const Graph &G): G(G), uf(G.V()), mst(G.V()+1)
  { a = edges<Graph, Edge>(G);
    int N, k = 1;
    for (int E = a.size(); E != 0; E = N) 
    { int h, i, j;
      b.assign(G.V(), 0);
      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 (!b[i] || e->wt() < b[i]->wt()) b[i] = e;
        if (!b[j] || e->wt() < b[j]->wt()) b[j] = e;
        a[N++] = e;
      }
      for (h = 0; h < G.V(); h++) 
       if (b[h])
        if (!uf.find(i = b[h]->v(), j = b[h]->w()))
          { uf.unite(i, j); mst[k++] = b[h]; }
      }
  }
};
-----
template <class keyType> class PQi 
{ int d, N;
  vector<int> pq, qp; 
  const vector<keyType> &a; 
  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; }