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

Algorithms in C, Part 5 (Graph Algorithms) code

        This file contains the code from "Algorithms in C, Third Edition,
        Part 5," by Robert Sedgewick, and is covered under the copyright
        and warranty notices in that book. Permission is granted for this
        code to be used for educational purposes in association with the text,
        and for other uses not covered by copyright laws, provided that
        the following notice is included with the code:

                "This code is from "Algorithms in C, Third Edition,"
                by Robert Sedgewick, Addison-Wesley, 2002."

        Commercial uses of this code require the explicit written
        permission of the publisher. Send your request for permission,
        stating clearly what code you would like to use, and in what
        specific way, to: [e-mail]


----------
CHAPTER 17. Graph Properties and Types
-----
typedef struct { int v; int w; } Edge;
Edge EDGE(int, int);

typedef struct graph *Graph;
Graph GRAPHinit(int);
 void GRAPHinsertE(Graph, Edge);
 void GRAPHremoveE(Graph, Edge);
  int GRAPHedges(Edge [], Graph G);
Graph GRAPHcopy(Graph);
 void GRAPHdestroy(Graph);
-----
#include <stdio.h>
#include "GRAPH.h"
main(int argc, char *argv[])
  { int V = atoi(argv[1]), E = atoi(argv[2]);
    Graph G = GRAPHrand(V, E);
    if (V < 20) 
         GRAPHshow(G);
    else printf("%d vertices, %d edges, ", V, E);
    printf("%d component(s)\n", GRAPHcc(G));
  }
-----
#include <stdlib.h>
#include "GRAPH.h"
struct graph { int V; int E; int **adj; };
Graph GRAPHinit(int V)
  { Graph G = malloc(sizeof *G);
    G->V = V; G->E = 0;
    G->adj = MATRIXint(V, V, 0);
    return G;
  }
void GRAPHinsertE(Graph G, Edge e)
  { int v = e.v, w = e.w;
    if (G->adj[v][w] == 0) G->E++;
    G->adj[v][w] = 1; 
    G->adj[w][v] = 1;
  }
void GRAPHremoveE(Graph G, Edge e)
  { int v = e.v, w = e.w;
    if (G->adj[v][w] == 1) G->E--;
    G->adj[v][w] = 0; 
    G->adj[w][v] = 0;
  }
int GRAPHedges(Edge a[], Graph G)
  { int v, w, E = 0;
    for (v = 0; v < G->V; v++)
      for (w = v+1; w < G->V; w++)
        if (G->adj[v][w] == 1) 
          a[E++] = EDGE(v, w); 
    return E;
  }
-----
int **MATRIXint(int r, int c, int val)
  { int i, j;
    int **t = malloc(r * sizeof(int *));
    for (i = 0; i < r; i++)
      t[i] = malloc(c * sizeof(int));
    for (i = 0; i < r; i++)
      for (j = 0; j < c; j++)
        t[i][j] = val;
    return t;
  }
-----
void GRAPHshow(Graph G)
  { int i, j; 
    printf("%d vertices, %d edges\n", G->V, G->E);
    for (i = 0; i < G->V; i++)
      {
        printf("%2d:", i);
        for (j = 0; j < G->V; j++)
          if (G->adj[i][j] == 1) printf(" %2d", j);
        printf("\n");
      }
  }
-----
#include <stdlib.h>
#include "GRAPH.h"
typedef struct node *link;
struct node { int v; link next; };
struct graph { int V; int E; link *adj; };
link NEW(int v, link next)
  { link x = malloc(sizeof *x);
    x->v = v; x->next = next;     
    return x;                         
  }
Graph GRAPHinit(int V)
  { int v;
    Graph G = malloc(sizeof *G);
    G->V = V; G->E = 0;
    G->adj = malloc(V*sizeof(link));
    for (v = 0; v < V; v++) G->adj[v] = NULL;
    return G;
  }
void GRAPHinsertE(Graph G, Edge e)
  { int v = e.v, w = e.w;
    G->adj[v] = NEW(w, G->adj[v]);
    G->adj[w] = NEW(v, G->adj[w]); 
    G->E++;
  }
int GRAPHedges(Edge a[], Graph G)
  { int v, E = 0; link t;  
    for (v = 0; v < G->V; v++)
      for (t = G->adj[v]; t != NULL; t = t->next)
        if (v < t->v) a[E++] = EDGE(v, t->v); 
    return E;
  }
-----
int randV(Graph G)
  { return G->V * (rand() / (RAND_MAX + 1.0)); }
Graph GRAPHrand(int V, int E)
  { Graph G = GRAPHinit(V);
    while (G->E < E)
      GRAPHinsertE(G, EDGE(randV(G), randV(G)));
    return G;
  }
-----
Graph GRAPHrand(int V, int E)
  { int i, j;
    double p = 2.0*E/V/(V-1);
    Graph G = GRAPHinit(V);
    for (i = 0; i < V; i++)
      for (j = 0; j < i; j++)
        if (rand() < p*RAND_MAX)
          GRAPHinsertE(G, EDGE(i, j));
    return G;
  }
-----
#include <stdio.h>
#include "GRAPH.h"
#include "ST.h"
Graph GRAPHscan(int Vmax, int Emax)
  { char v[100], w[100];
    Graph G = GRAPHinit(Vmax);
    STinit();
    while (scanf("%99s %99s", v, w) == 2)
      GRAPHinsertE(G, EDGE(STindex(v), STindex(w)));
    return G;
  }
-----
#include <stdlib.h>
typedef struct STnode* link;
struct STnode { int index, d; link l, m, r; };
static link head;
static int val, N; 
void STinit() 
  { head = NULL; N = 0; }
link stNEW(int d)
  { link x = malloc(sizeof *x);   
    x->index = -1; x->d = d; 
    x->l = NULL; x->m = NULL; x->r = NULL;
    return x;
  }
link indexR(link h, char* v, int w)
  { int i = v[w];
    if (h == NULL) h = stNEW(i); 
    if (i == 0) 
      { 
        if (h->index == -1) h->index = N++;
        val = h->index;
        return h;
      }
    if (i < h->d) h->l = indexR(h->l, v, w);
    if (i == h->d) h->m = indexR(h->m, v, w+1);
    if (i > h->d) h->r = indexR(h->r, v, w);
    return h;
  }
int STindex(char* key)
  { head = indexR(head, key, 0); return val; }
-----
static int visited[maxV];
int pathR(Graph G, int v, int w)
  { int t; 
    if (v == w) return 1;
    visited[v] = 1;
    for (t = 0; t < G->V; t++)
      if (G->adj[v][t] == 1)
        if (visited[t] == 0)
          if (pathR(G, t, w)) return 1;
    return 0;
  }
int GRAPHpath(Graph G, int v, int w)
  { int t; 
    for (t = 0; t < G->V; t++) visited[t] = 0;
    return pathR(G, v, w);
  }
-----
static int visited[maxV];
int pathR(Graph G, int v, int w, int d)
  { int t; 
    if (v == w) 
      { if (d == 0) return 1; else return 0; }
    visited[v] = 1; 
    for (t = 0; t < G->V; t++)
      if (G->adj[v][t] == 1)
        if (visited[t] == 0)
          if (pathR(G, t, w, d-1)) return 1;
    visited[v] = 0;
    return 0;
  }
int GRAPHpathH(Graph G, int v, int w)
  { int t; 
    for (t = 0; t < G->V; t++) visited[t] = 0;
    return pathR(G, v, w, G->V-1);
  }
-----
int GRAPHpathE(Graph G, int v, int w)
  { int t;
    t = GRAPHdeg(G, v) + GRAPHdeg(G, w);
    if ((t % 2) != 0) return 0;
    for (t = 0; t < G->V; t++)
      if ((t != v) && (t != w))
        if ((GRAPHdeg(G, t) % 2) != 0) return 0;
    return 1;
  }
-----
#include "STACK.h"
int path(Graph G, int v)
  { int w; 
    for (; G->adj[v] != NULL; v = w)
      { 
        STACKpush(v); 
        w = G->adj[v]->v; 
        GRAPHremoveE(G, EDGE(v, w)); 
      }
    return v;
  }
void pathEshow(Graph G, int v, int w)
  { 
    STACKinit(G->E);
    printf("%d", w);
    while ((path(G, v) == v) && !STACKempty())
      { v = STACKpop(); printf("-%d", v); }
    printf("\n");
  }
-----
#define GRAPHiso(G, v) (GRAPHdeg(G, v) == 0)
void pathEshow(Graph G, int v, int w)
  { int t; 
    if ((v == w) && (G->E == 0)) return;
    for (t = 0; t < G->V; t++)
      if (G->adj[v][t] != 0) 
        {
          GRAPHremoveE(G, EDGE(v, t));
          if (GRAPHiso(G, v) || GRAPHpath(G, t, v))
            {
              printf("%d-%d\n", v, t); 
              pathEshow(G, t, w);
              GRAPHinsertE(G, EDGE(v, t));
              return; 
            }
          GRAPHinsertE(G, EDGE(v, t));
        }
  }

----------
CHAPTER 18. Graph Search
-----
#define dfsR search
void dfsR(Graph G, Edge e)
  { int t, w = e.w;
    pre[w] = cnt++; 
    for (t = 0; t < G->V; t++)
      if (G->adj[w][t] != 0) 
        if (pre[t] == -1)
          dfsR(G, EDGE(w, t)); 
  }
-----
void dfsR(Graph G, Edge e)
  { link t; int w = e.w;
    pre[w] = cnt++; 
    for (t = G->adj[w]; t != NULL; t = t->next)
      if (pre[t->v] == -1) 
        dfsR(G, EDGE(w, t->v)); 
  }
-----
static int cnt, pre[maxV];
void GRAPHsearch(Graph G)
  { int v;
    cnt = 0;
    for (v = 0; v < G->V; v++) pre[v] = -1;
    for (v = 0; v < G->V; v++)
      if (pre[v] == -1) 
        search(G, EDGE(v, v));
  }
-----
void dfsRcc(Graph G, int v, int id)
  { link t; 
    G->cc[v] = id;
    for (t = G->adj[v]; t != NULL; t = t->next)
      if (G->cc[t->v] == -1) dfsRcc(G, t->v, id); 
  }
int GRAPHcc(Graph G)
  { int v, id = 0;
    G->cc = malloc(G->V * sizeof(int));
    for (v = 0; v < G->V; v++) 
      G->cc[v] = -1;
    for (v = 0; v < G->V; v++)
      if (G->cc[v] == -1) dfsRcc(G, v, id++);
    return id;
  }
int GRAPHconnect(Graph G, int s, int t)
  { return G->cc[s] == G->cc[t]; }
-----
void dfsReuler(Graph G, Edge e)
  { link t;
    printf("-%d", e.w);
    pre[e.w] = cnt++;
    for (t = G->adj[e.w]; t != NULL; t = t->next)
      if (pre[t->v] == -1) 
        dfsReuler(G, EDGE(e.w, t->v)); 
      else if (pre[t->v] < pre[e.v])
        printf("-%d-%d", t->v, e.w);
    if (e.v != e.w) 
         printf("-%d", e.v);
    else printf("\n");
  }
-----
int dfsRcolor(Graph G, int v, int c)
  { link t; 
    G->color[v] = 1-c;
    for (t = G->adj[v]; t != NULL; t = t->next)
      if (G->color[t->v] == -1) 
        { if (!dfsRcolor(G, t->v, 1-c)) return 0; }
      else if (G->color[t->v] != c) return 0;
    return 1;
  }
int GRAPHtwocolor(Graph G)
  { int v, id = 0;
    G->color = malloc(G->V * sizeof(int));
    for (v = 0; v < G->V; v++) 
      G->color[v] = -1;
    for (v = 0; v < G->V; v++)
      if (G->color[v] == -1) 
        if (!dfsRcolor(G, v, 0)) return 0;
    return 1;
  }
-----
void bridgeR(Graph G, Edge e)
  { link t; int v, w = e.w;
    pre[w] = cnt++; low[w] = pre[w];
    for (t = G->adj[w]; t != NULL; t = t->next)
      if (pre[v = t->v] == -1) 
        {
          bridgeR(G, EDGE(w, v)); 
          if (low[w] > low[v]) low[w] = low[v];
          if (low[v] == pre[v]) 
            bcnt++; printf("%d-%d\n", w, v);
        }
      else if (v != e.v)
        if (low[w] > pre[v]) low[w] = pre[v];
  }
-----
#define bfs search
void bfs(Graph G, Edge e)
  { int v, w;
    QUEUEput(e);
    while (!QUEUEempty())
      if (pre[(e = QUEUEget()).w] == -1)
        {
          pre[e.w] = cnt++; st[e.w] = e.v;
          for (v = 0; v < G->V; v++)
            if (G->adj[e.w][v] == 1)
              if (pre[v] == -1)
                QUEUEput(EDGE(e.w, v)); 
        }
  }
-----
void bfs(Graph G, Edge e)
  { int v, w;
    QUEUEput(e); pre[e.w] = cnt++; 
    while (!QUEUEempty())
      {
        e = QUEUEget(); 
        w = e.w; st[w] = e.v; 
        for (v = 0; v < G->V; v++)
          if ((G->adj[w][v] == 1) && (pre[v] == -1))
           { QUEUEput(EDGE(w, v)); pre[v] = cnt++; }
      }
  }
-----
#define pfs search
void pfs(Graph G, Edge e)