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

Algorithms in C, Part 5 (Graph Algorithms) code

  { link t; int v, w;
    GQput(e); pre[e.w] = cnt++;
    while (!GQempty())
      {
        e = GQget(); w = e.w; st[w] = e.v; 
        for (t = G->adj[w]; t != NULL; t = t->next)
          if (pre[v = t->v] == -1)
            { GQput(EDGE(w, v)); pre[v] = cnt++; }
          else if (st[v] == -1)
            GQupdate(EDGE(w, v));
      }
  }
-----
#include <stdlib.h>
#include "GQ.h"
static Item *s;
static int N;
void RQinit(int maxN)
  { s = malloc(maxN*sizeof(Item)); N = 0; }
int RQempty()
  { return N == 0; }
void RQput(Item x)
  { s[N++] = x; }
void RQupdate(Item x)
  { }
Item RQget()
  { Item t;
    int i = N*(rand()/(RAND_MAX + 1.0));
    t = s[i]; s[i] = s[N-1]; s[N-1] = t;    
    return s[--N]; 
  }

----------
CHAPTER 19. Digraphs and DAGs
-----
Graph GRAPHreverse(Graph G)
  { int v; link t;
    Graph R = GRAPHinit(G->V);
    for (v = 0; v < G->V; v++) 
      for (t = G->adj[v]; t != NULL; t = t->next)
        GRAPHinsertE(R, EDGE(t->v, v));        
    return R;
  }
-----
void dfsR(Graph G, Edge e)
  { link t; int i, v, w = e.w; Edge x;
    show("tree", e);
    pre[w] = cnt++; 
    for (t = G->adj[w]; t != NULL; t = t->next)
      if (pre[t->v] == -1) 
        dfsR(G, EDGE(w, t->v)); 
      else 
        { v = t->v; x = EDGE(w, v);
          if (post[v] == -1) show("back", x);
          else if (pre[v] > pre[w]) show("down", x);
          else show("cross", x);
        }
    post[w] = cntP++; 
  }
-----
void GRAPHtc(Graph G)
  { int i, s, t;
    G->tc = MATRIXint(G->V, G->V, 0);
    for (s = 0; s < G->V; s++)
      for (t = 0; t < G->V; t++)
        G->tc[s][t] = G->adj[s][t];
    for (s = 0; s < G->V; s++) G->tc[s][s] = 1;
    for (i = 0; i < G->V; i++)
      for (s = 0; s < G->V; s++)
        if (G->tc[s][i] == 1)
          for (t = 0; t < G->V; t++)
            if (G->tc[i][t] == 1) G->tc[s][t] = 1; 
  }
int GRAPHreach(Graph G, int s, int t)
  { return G->tc[s][t]; }
-----
void TCdfsR(Graph G, Edge e)
  { link t; 
    G->tc[e.v][e.w] = 1; 
    for (t = G->adj[e.w]; t != NULL; t = t->next)
      if (G->tc[e.v][t->v] == 0) 
        TCdfsR(G, EDGE(e.v, t->v)); 
  }
void GRAPHtc(Graph G, Edge e)
  { int v, w;
    G->tc = MATRIXint(G->V, G->V, 0);
    for (v = 0; v < G->V; v++) 
      TCdfsR(G, EDGE(v, v));
  }
int GRAPHreach(Graph G, int s, int t)
  { return G->tc[s][t]; }
-----
int compressR(link h)
  { int l, r, t; 
    if (h == NULL) return 0;
    l = compressR(h->l); 
    r = compressR(h->r);
    t = STindex(l*Vmax + r);
    adj[t].l = l; adj[t].r = r;
    return t;
  }
-----
static int cnt0;
static int pre[maxV];
void DAGts(Dag D, int ts[])
  { int v; 
    cnt0 = 0;
    for (v = 0; v < D->V; v++) 
      { ts[v] = -1; pre[v] = -1; }
    for (v = 0; v < D->V; v++)
      if (pre[v] == -1) TSdfsR(D, v, ts);
}
void TSdfsR(Dag D, int v, int ts[])
  { link t; 
    pre[v] = 0; 
    for (t = D->adj[v]; t != NULL; t = t->next)
      if (pre[t->v] == -1) TSdfsR(D, t->v, ts); 
    ts[cnt0++] = v;
  }
-----
void TSdfsR(Dag D, int v, int ts[])
  { int w;
    pre[v] = 0; 
    for (w = 0; w < D->V; w++)
      if (D->adj[w][v] != 0) 
        if (pre[w] == -1) TSdfsR(D, w, ts); 
    ts[cnt0++] = v;
  }
-----
#include "QUEUE.h"
static int in[maxV];
void DAGts(Dag D, int ts[])
  { int i, v; link t;
    for (v = 0; v < D->V; v++) 
      { in[v] = 0; ts[v] = -1; }
    for (v = 0; v < D->V; v++) 
      for (t = D->adj[v]; t != NULL; t = t->next)
        in[t->v]++;
    QUEUEinit(D->V);
    for (v = 0; v < D->V; v++)
      if (in[v] == 0) QUEUEput(v);
    for (i = 0; !QUEUEempty(); i++)
      {
        ts[i] = (v = QUEUEget());
        for (t = D->adj[v]; t != NULL; t = t->next)
          if (--in[t->v] == 0) QUEUEput(t->v);
      }
  }
-----
void DAGtc(Dag D)
  { int v;
    D->tc = MATRIXint(D->V, D->V, 0);
    for (v = 0; v < D->V; v++) pre[v] = -1; 
    for (v = 0; v < D->V; v++) 
      if (pre[v] == -1) TCdfsR(D, EDGE(v, v)); 
  }
void TCdfsR(Dag D, Edge e)
  { int u, i, v = e.w;
    pre[v] = cnt++;
    for (u = 0; u < D->V; u++)
      if (D->adj[v][u] != 0)
        { 
          D->tc[v][u] = 1; 
          if (pre[u] > pre[v]) continue;
          if (pre[u] == -1) TCdfsR(D, EDGE(v, u)); 
          for (i = 0; i < D->V; i++)
            if (D->tc[u][i] == 1) D->tc[v][i] = 1;
        }            
  }
int DAGreach(Dag D, int s, int t)
  { return D->tc[s][t]; }
-----
static int post[maxV], postR[maxV];
static int cnt0, cnt1;
void SCdfsR(Graph G, int w)
  { link t;
    G->sc[w] = cnt1; 
    for (t = G->adj[w]; t != NULL; t = t->next)
      if (G->sc[t->v] == -1) SCdfsR(G, t->v); 
    post[cnt0++] = w;
  }
int GRAPHsc(Graph G)
  { int v; Graph R;
    R = GRAPHreverse(G);
    cnt0 = 0; cnt1 = 0;
    for (v = 0; v < G->V; v++) R->sc[v] = -1;
    for (v = 0; v < G->V; v++)
      if (R->sc[v] == -1) SCdfsR(R, v);
    cnt0 = 0; cnt1 = 0;
    for (v = 0; v < G->V; v++) G->sc[v] = -1;
    for (v = 0; v < G->V; v++) postR[v] = post[v];
    for (v = G->V-1; v >=0; v--)
      if (G->sc[postR[v]] == -1) 
        { SCdfsR(G, postR[v]); cnt1++; }
    GRAPHdestroy(R);
    return cnt1;
  }
int GRAPHstrongreach(Graph G, int s, int t)
  { return G->sc[s] == G->sc[t]; }
-----
void SCdfsR(Graph G, int w)
  { link t; int v, min;
    pre[w] = cnt0++; low[w] = pre[w]; min = low[w];
    s[N++] = w; 
    for (t = G->adj[w]; t != NULL; t = t->next)
      {
        if (pre[t->v] == -1) SCdfsR(G, t->v);
        if (low[t->v] < min) min = low[t->v];
      }
    if (min < low[w]) { low[w] = min; return; }
    do
      { G->sc[(v = s[--N])] = cnt1; low[v] = G->V; }
    while (s[N] != w); 
    cnt1++;
  }
-----
void SCdfsR(Graph G, int w)
  { link t; int v;
    pre[w] = cnt0++; 
    s[N++] = w; path[p++] = w; 
    for (t = G->adj[w]; t != NULL; t = t->next)
      if (pre[t->v] == -1) SCdfsR(G, t->v);
      else if (G->sc[t->v] == -1) 
             while (pre[path[p-1]] > pre[t->v]) p--;
    if (path[p-1] != w) return; else p--;
    do G->sc[s[--N]] = cnt1; while (s[N] != w);
    cnt1++;
  }
-----
Dag K;
void GRAPHtc(Graph G)
  { int v, w; link t; int *sc = G->sc;
    K = DAGinit(GRAPHsc(G));
    for (v = 0; v < G->V; v++) 
      for (t = G->adj[v]; t != NULL; t = t->next)
        DAGinsertE(K, dagEDGE(sc[v], sc[t->v]));
    DAGtc(K);
  }
int GRAPHreach(Graph G, int s, int t)
  { return DAGreach(K, G->sc[s], G->sc[t]); }

----------
CHAPTER 20. Minimum Spanning Trees
-----
#include <stdlib.h>
#include "GRAPH.h"
struct graph { int V; int E; double **adj; };
Graph GRAPHinit(int V)
  { int v;
    Graph G = malloc(sizeof *G);
    G->adj = MATRIXdouble(V, V, maxWT);
    G->V = V; G->E = 0;
    return G;
  }
void GRAPHinsertE(Graph G, Edge e)
  { 
    if (G->adj[e.v][e.w] == maxWT) G->E++;
    G->adj[e.v][e.w] = e.wt; 
    G->adj[e.w][e.v] = e.wt; 
  }
-----
#include "GRAPH.h"
typedef struct node *link;
struct node { int v; double wt; link next; };
struct graph { int V; int E; link *adj; };
link NEW(int v, double wt, link next)
  { link x = malloc(sizeof *x);
    x->v = v; x->wt = wt; x->next = next;     
    return x;                         
  }
Graph GRAPHinit(int V)
  { int i;
    Graph G = malloc(sizeof *G);
    G->adj = malloc(V*sizeof(link));
    G->V = V; G->E = 0;
    for (i = 0; i < V; i++) G->adj[i] = NULL;
    return G;
  }
void GRAPHinsertE(Graph G, Edge e)
  { link t; 
    int v = e.v, w = e.w;
    if (v == w) return;
    G->adj[v] = NEW(w, e.wt, G->adj[v]);
    G->adj[w] = NEW(v, e.wt, G->adj[w]);
    G->E++;
  }
-----
static int fr[maxV];
#define P G->adj[v][w]
void GRAPHmstV(Graph G, int st[], double wt[])
  { int v, w, min; 
    for (v = 0; v < G->V; v++)
      { st[v] = -1; fr[v] = v; wt[v] = maxWT; }
    st[0] = 0; wt[G->V] = maxWT;
    for (min = 0; min != G->V; )
      {
        v = min; st[min] = fr[min];
        for (w = 0, min = G->V; w < G->V; w++)
          if (st[w] == -1)
            { 
              if (P < wt[w]) 
                { wt[w] = P; fr[w] = v; }
              if (wt[w] < wt[min]) min = w; 
            }
      }
  }
-----
#define GRAPHpfs GRAPHmst
static int fr[maxV];
static double *priority;
int less(int i, int j)
  { return priority[i] < priority[j]; }
#define P t->wt
void GRAPHpfs(Graph G, int st[], double wt[])
  { link t; int v, w; 
    PQinit(); priority = wt; 
    for (v = 0; v < G->V; v++)
      { st[v] = -1; fr[v] = -1; }
    fr[0] = 0; PQinsert(0);
    while (!PQempty())
      {
        v = PQdelmin(); st[v] = fr[v]; 
        for (t = G->adj[v]; t != NULL; t = t->next)
          if (fr[w = t->v] == -1) 
            { wt[w] = P; PQinsert(w); fr[w] = v; }
          else if ((st[w] == -1) && (P < wt[w])) 
            { wt[w] = P; PQdec(w); fr[w] = v; }
      }
  }
-----
void GRAPHmstE(Graph G, Edge mst[])
  { int i, k; Edge a[maxE]; 
    int E = GRAPHedges(a, G);
    sort(a, 0, E-1);
    UFinit(G->V);
    for (i= 0, k = 0; i < E && k < G->V-1; i++)
      if (!UFfind(a[i].v, a[i].w))
        {
          UFunion(a[i].v, a[i].w);
          mst[k++] = a[i];
        }
  }
-----
Edge nn[maxV], a[maxE];
void GRAPHmstE(Graph G, Edge mst[])
  { int h, i, j, k, v, w, N; Edge e;
    int E = GRAPHedges(a, G);
    for (UFinit(G->V); E != 0; E = N)
      {
        for (k = 0; k < G->V; k++) 
          nn[k] = EDGE(G->V, G->V, maxWT);
        for (h = 0, N = 0; h < E; h++)
          {
            i = find(a[h].v); j = find(a[h].w); 
            if (i == j) continue;
            if (a[h].wt < nn[i].wt) nn[i] = a[h];
            if (a[h].wt < nn[j].wt) nn[j] = a[h];
            a[N++] = a[h]; 
          }
        for (k = 0; k < G->V; k++) 
          {
            e = nn[k]; v = e.v; w = e.w;
            if ((v != G->V) && !UFfind(v, w)) 
              { UFunion(v, w); mst[k] = e; }
          }
      }
  }
-----
fixUp(Item a[], int k)
  {
    while (k > 1 && less(a[(k+d-2)/d], a[k]))
      { exch(a[k], a[(k+d-2)/d]); k = (k+d-2)/d; }
  }
fixDown(Item a[], int k, int N)
  { int i, j;
    while ((d*(k-1)+2) <= N)
      { j = d*(k-1)+2;
        for (i = j+1; (i < j+d) && (i <= N); i++)
          if (less(a[j], a[i])) j = i;
        if (!less(a[k], a[j])) break;
        exch(a[k], a[j]); k = j;
      }
  }

----------
CHAPTER 21. Shortest Paths
-----
#define GRAPHpfs GRAPHspt
#define P (wt[v] + t->wt)
void GRAPHpfs(Graph G, int s, int st[], double wt[])
  { int v, w;  link t;
    PQinit(); priority = wt;
    for (v = 0; v < G->V; v++)
      { st[v] = -1; wt[v] = maxWT; PQinsert(v); }
    wt[s] = 0.0; PQdec(s);
    while (!PQempty())
      if (wt[v = PQdelmin()] != maxWT)
        for (t = G->adj[v]; t != NULL; t = t->next)
          if (P < wt[w = t->v]) 
            { wt[w] = P; PQdec(w); st[w] = v; }
  }
-----