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

Algorithms in C, Part 5 (Graph Algorithms) code

  void GRAPHspALL(Graph G);
double GRAPHspDIST(Graph G, int s, int t);
   int GRAPHspPATH(Graph G, int s, int t);
-----
void GRAPHdiameter(Graph G)
  { int v, w, vMAX = 0, wMAX = 0;
    double MAX = 0.0;
    GRAPHspALL(G);
    for (v = 0; v < G->V; v++)
      for (w = 0; w < G->V; w++)
        if (GRAPHspPATH(G, v, w) != G->V)
          if (MAX < GRAPHspDIST(G, v, w))
            { vMAX = v; wMAX = w; 
              MAX = GRAPHspDIST(G, v, w); }
    printf("Diameter is %f\n", MAX); 
    for (v = vMAX; v != wMAX; v = w)
      { printf("%d-", v);
        w = GRAPHspPATH(G, v, wMAX); }
    printf("%d\n", w);
  }
-----
static int st[maxV];
static double wt[maxV];
void GRAPHspALL(Graph G)
  { int v, w; Graph R = GRAPHreverse(G);
    G->dist = MATRIXdouble(G->V, G->V, maxWT);
    G->path = MATRIXint(G->V, G->V, G->V);
    for (v = 0; v < G->V; v++)
      {
        GRAPHpfs(R, v, st, wt);
        for (w = 0; w < G->V; w++)
          G->dist[w][v] = wt[w]; 
        for (w = 0; w < G->V; w++)
          if (st[w] != -1) G->path[w][v] = st[w]; 
      }
  }
double GRAPHspDIST(Graph G, int s, int t)
  { return G->dist[s][t]; }
int GRAPHspPATH(Graph G, int s, int t)
  { return G->path[s][t]; }
-----
void GRAPHspALL(Graph G)
  { int i, s, t;
    double **d = MATRIXdouble(G->V, G->V, maxWT);
    int **p = MATRIXint(G->V, G->V, G->V);
    for (s = 0; s < G->V; s++)
      for (t = 0; t < G->V; t++)
        if ((d[s][t] = G->adj[s][t]) < maxWT) 
          p[s][t] = t;
    for (i = 0; i < G->V; i++)
      for (s = 0; s < G->V; s++)
        if (d[s][i] < maxWT)
          for (t = 0; t < G->V; 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]; } 
    G->dist = d; G->path = p;
  }
-----
static int ts[maxV];
void GRAPHlpt(Graph G, int s, int st[], double wt[])
  { int i, v, w; link t;
    GRAPHts(G, ts);    
    for (v = ts[i = 0]; i < G->V; v = ts[i++])
      for (t = G->adj[v]; t != NULL; t = t->next)
        if (wt[w = t->v] < wt[v] + t->wt) 
          { st[w] = v; wt[w] = wt[v] + t->wt; }
  }
-----
void SPdfsR(Graph G, int s)
  { link u; int i, t; double wt;
    int **p = G->path; double **d = G->dist;
    for (u = G->adj[s]; u != NULL; u = u->next)
      {
        t = u->v; wt = u->wt;
        if (d[s][t] > wt)
          { d[s][t] = wt; p[s][t] = t; }
        if (d[t][t] == maxWT) SPdfsR(G, t); 
        for (i = 0; i < G->V; i++)
          if (d[t][i] < maxWT)
            if (d[s][i] > wt+d[t][i]) 
              { d[s][i] = wt+d[t][i]; p[s][i] = t; } 
      }
  }  
void GRAPHspALL(Graph G)
  { int v; 
    G->dist = MATRIXdouble(G->V, G->V, maxWT);
    G->path = MATRIXint(G->V, G->V, G->V);
    for (v = 0; v < G->V; v++)
      if (G->dist[v][v] == maxWT) SPdfsR(G, v);
  }
-----
#include <stdio.h>
#include "GRAPH.h"
#define Nmax 1000
main(int argc, char *argv[])
  { int i, s, t, N = atoi(argv[1]);
    double length[Nmax], start[Nmax];
    int st[Nmax];
    Graph G = GRAPHinit(N);
    for (i = 0; i < N; i++)
      scanf("%lf", &length[i]);
    while (scanf("%d %d", &s, &t) != EOF)
      GRAPHinsertE(G, EDGE(s, t, length[s]));
    GRAPHlpt(G, 0, st, start);
    for (i = 0; i < N; i++)
      printf("%3d %6.2f\n", i, start[i]);
  }
-----
void GRAPHbf(Graph G, int s, int st[], double wt[])
  { int v, w; link t; int N = 0;
    QUEUEinit(G->E);
    for (v = 0; v < G->V; v++)
      { st[v] = -1; wt[v] = maxWT; }
    wt[s] = 0.0; st[s] = 0; 
    QUEUEput(s); QUEUEput(G->V);
    while (!QUEUEempty())
      if ((v = QUEUEget()) == G->V)
        { if (N++ > G->V) return; QUEUEput(G->V); }
      else
        for (t = G->adj[v]; t != NULL; t = t->next)
          if (wt[w = t->v] > wt[v] + t->wt) 
            { wt[w] = wt[v] + t->wt; 
              QUEUEput(w); st[w] = v; }
  }


----------
CHAPTER 22. Network Flow
-----
#include <stdlib.h>
#include "GRAPH.h"
typedef struct node *link;
struct node 
  { int v; int cap; int flow; link dup; link next;};
struct graph 
  { int V; int E; link *adj; };
link NEW(int v, int cap, int flow, link next)
  { link x = malloc(sizeof *x);
    x->v = v; x->cap = cap; x->flow = flow; 
    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)
  { int v = e.v, w = e.w;
    G->adj[v] = NEW(w, e.cap, e.flow, G->adj[v]);
    G->adj[w] = NEW(v, -e.cap, -e.flow, G->adj[w]);
    G->adj[v]->dup = G->adj[w];
    G->adj[w]->dup = G->adj[v];
    G->E++;
  }
-----
static int flowV(Graph G, int v)
  { link t; int x = 0;
    for (t = G->adj[v]; t != NULL; t = t->next)
      x += t->flow;
    return x;
  }
int GRAPHflow(Graph G, int s, int t)
  { int v, val = flowV(G, s);
    for (v = 0; v < G->V; v++)
      if ((v != s) && (v != t))
        if (flowV(G, v) != 0) return 0;
    if (val + flowV(G, t) != 0) return 0;
    if (val <= 0) return 0;
    return val;
  }
-----
static int wt[maxV];
#define Q (u->cap < 0 ? -u->flow : u->cap - u->flow)
int GRAPHpfs(Graph G, int s, int t, link st[])
  { int v, w, d = M; link u;
    PQinit(); priority = wt;
    for (v = 0; v < G->V; v++)
      { st[v] = NULL; wt[v] = 0; PQinsert(v); }
    wt[s] = M; PQinc(s); 
    while (!PQempty())
      {
        v = PQdelmax();
        if ((wt[v] == 0) || (v == t)) break;
        for (u = G->adj[v]; u != NULL; u = u->next)
          if (Q > 0)
            if (P > wt[w = u->v]) 
              { wt[w] = P; PQinc(w); st[w] = u; }
        wt[v] = M;
      }
    if (wt[t] == 0) return 0; 
    for (w = t; w != s; w = st[w]->dup->v)
      { u = st[w]; d = ( Q > d ? d : Q ); }
    return d;
  }
void GRAPHmaxflow(Graph G, int s, int t)
  { int x, d;
    link st[maxV]; 
    while ((d = GRAPHpfs(G, s, t, st)) != 0) 
      for (x = t; x != s; x = st[x]->dup->v)
        { st[x]->flow += d; st[x]->dup->flow -= d; }
  }
-----
static int h[maxV], wt[maxV];
#define P ( Q > wt[v] ? wt[v] : Q )
#define Q (u->cap < 0 ? -u->flow : u->cap - u->flow)
int GRAPHmaxflow(Graph G, int s, int t)
  { int v, w, x;  link u;
    GRAPHdist(G, t, h);
    GQinit(); 
    for (v = 0; v < G->V; v++) wt[v] = 0; 
    GQput(s); wt[s] = maxWT; wt[t] = -maxWT;
    while (!GQempty())
      {
        v = GQget();
        for (u = G->adj[v]; u != NULL; u = u->next)
          if (P > 0 && v == s || h[v] == h[u->v]+1)
            { 
              w = u->v; x = P;
              u->flow += x; u->dup->flow -= x; 
              wt[v] -= x; wt[w] += x;
              if ((w != s) && (w != t)) GQput(w);
            }
        if ((v != s) && (v != t))
          if (wt[v] > 0) { h[v]++; GQput(v); }
      }        
  }
-----
void insertSTlinks(Graph G, int s, int t)
  { int i, sd;
    for (i = 0; i < G->V; i++)
      if ((sd = G->sd[i]) >= 0)
        GRAPHinsertE(G, EDGE(s, i, sd, 0, 0));
    for (i = 0; i < G->V; i++)
      if ((sd = G->sd[i]) < 0)
        GRAPHinsertE(G, EDGE(i, t, -sd, 0, 0));
  }
void removeSTlinks(Graph G)
  { int i;
    for (i = 0; i < G->V; i++)
      G->adj[i] = G->adj[i]->next;
  }
int GRAPHfeasible(Graph G)
  { int s = G->V, t = G->V+1, sd = 0; link u;
    insertSTlinks(G, s, t); G->V += 2;
    GRAPHmaxflow(G, s, t);
    for (u = G->adj[s]; u != NULL; u = u->next)
      sd += u->cap - u->flow;
    for (u = G->adj[t]; u != NULL; u = u->next)
      sd += u->cap - u->flow;
    G->V -= 2; removeSTlinks(G);
    return sd;
  }
-----
#include <stdio.h>
#include "GRAPH.h"
main(int argc, char *argv[])
  { Graph G; int i, v, w, E, V = atoi(argv[1]);
    G = GRAPHinit(2*V+2);
    for (i = 1; i <= V; i++)
      GRAPHinsertE(G, EDGE(0, i, 1, 0));
    while (scanf("%d %d", &v, &w) != EOF)
      GRAPHinsertE(G, EDGE(v, w, 1, 0));
    for (i = V+1; i <= V+V; i++)
      GRAPHinsertE(G, EDGE(i, V+V+1, 1, 0));
    if (GRAPHmaxflow(G, 0, V+V+1) == 0) return;
    E = GRAPHedges(a, G);
    for (i = 0; i < E; i++)
      if ((a[i].v != 0) && (a[i].w != V+V+1))
        if (a[i].flow == 1)
          printf("%d-%d\n", a[i].v, a[i].w);
  }
-----
int GRAPHcost(Graph G)
  { int i; link u; int cost = 0;
    for (i = 0; i < G->V; i++)
      for (u = G->adj[i]; u != NULL; u = u->next)
        if ((u->cap > 0) && (u->cost != C))
          cost += (u->flow)*(u->cost);
    return cost;
  }
-----
void addflow(link u, int d)
  { u->flow += d; u->dup->flow -=d; }
int GRAPHmincost(Graph G, int s, int t)
  { int d, x, w; link u, st[maxV]; 
    GRAPHmaxflow(G, s, t);
    while ((x = GRAPHnegcycle(G, st)) != -1)
      {
        u = st[x]; d = Q;
        for (w = u->dup->v; w != x; w = u->dup->v)
          { u = st[w]; d = ( Q > d ? d : Q ); }
        u = st[x]; addflow(u, d);
        for (w = u->dup->v; w != x; w = u->dup->v)
          { u = st[w]; addflow(u, d); }
      }
    return GRAPHcost(G);
  }
-----
#define ST(i) st[i]->dup->v
static int valid, phi[maxV];
int phiR(link st[], int v)
  {
    if (ST(v) == v) 
      { mark[v] = valid; return -C; }
    if (mark[v] != valid) 
      phi[v] =phiR(st, ST(v)) - st[v]->cost;
    mark[v] = valid;
    return phi[v]; 
  }
-----
int lca(link st[], int u, int v)
  { int i, j;
    mark[u] = ++valid; mark[v] = valid;
    while (u != v)
    { 
      u = ST(u); v = ST(v); 
      if (u != ST(u) && mark[u] == valid) return u;
      mark[u] = valid; 
      if (v != ST(v) && mark[v] == valid) return v;
      mark[v] = valid; 
    }
    return u;
  }      
link augment(link st[], link x)
{ link u, cyc[maxV]; int d, N;
  int t, i = x->v, j = x->dup->v;
  t = lca(st, i, j);
  cyc[0] = x; N = 1;
  while (i != t) 
    { cyc[N++] = st[i]->dup; i = ST(i); }
  while (j != t) 
    { cyc[N++] = st[j]; j = ST(j); }
  for (i = 0, d = C; i < N; i++)
    { u = cyc[i]; d = Q > d ? d : Q; }
  for (i = 0; i < N; i++) addflow(cyc[i], d);
  for (i = 0; i < N-1; i++)
    { u = cyc[N-1-i]; if (Q == 0) return u; }
  }
-----
int onpath(link st[], int a, int b, int c)
  { int i;
    for (i = a; i != c; i = ST(i))
      if (i == b) return 1;
    return 0;
  }
int reverse(link st[], int u, int x)
  { int i;
    while (i != st[x]->v)
      { i = st[u]->v; st[i] = st[u]->dup; u = i; }
  }
int update(link st[], link w, link y)
  { int t, u = y->v, v = y->dup->v, x = w->v;
    if (st[x] != w->dup) x = w->dup->v;
    t = lca(st, u, v);
    if (onpath(st, u, x, t)) 
      { st[u] = y; reverse(st, u, x); return; }
    if (onpath(st, v, x, t)) 
      { st[v] = y->dup; reverse(st, v, x); return; }
  }
-----
#define R(u)  u->cost - phi[u->dup->v] + phi[u->v]
void addflow(link u, int d)
  { u->flow += d; u->dup->flow -=d; }
int GRAPHmincost(Graph G, int s, int t)
  { int v; link u, x, st[maxV]; 
    GRAPHinsertE(G, EDGE(s, t, M, M, C));
    initialize(G, s, t, st); 
    for (valid = 1; valid++; )
    {
      for (v = 0; v < G->V; v++) 
        phi[v] = phiR(st, v);
      for (v = 0, x = G->adj[v]; v < G->V; v++)
        for (u = G->adj[v]; u != NULL; u = u->next)
          if (Q > 0)
            if (R(u) < R(x)) x = u;
      if (R(x) == 0) break;
      update(st, augment(st, x), x);
    }
    return GRAPHcost(G);
  }
-----
int R(link st[], link u)
  { return u->cost 
      - phiR(st, u->dup->v) + phiR(st, u->v); }
int GRAPHmincost(Graph G, int s, int t)
  { int v, old = 0; link u, x, st[maxV]; 
    GRAPHinsertE(G, EDGE(s, t, M, M, C));
    initialize(G, s, t, st); 
    for (valid = 1; valid != old; old = valid)
      for (v = 0; v < G->V; v++)
        for (u = G->adj[v]; u != NULL; u = u->next)
          if ((Q > 0) && (R(st, u) < 0))
          { update(st, augment(st, u), u); valid++; }
    return GRAPHcost(G);
  }
-----