graph.c

压缩包里面的都是精致的基本C语言小程序

#include <stdio.h>
#include "mystdlib.h"
#include "queue.h"
#include "nat.h"
#include "commonInter.h"
#include "plist.h"
#include "property.h"
#include "linkedList.h"
#include "error.h"
#include "counter.h"
#include "control.h"
#include "dot.h"
#include "graph.h"

struct graph
{
  str graphName;
  linkedList vs;
};

typedef struct vertex *vertex;
typedef struct edge *edge;

struct vertex
{
  tyVft vft;
  poly info;
  linkedList edges;
  plist plist;
};

struct edge
{
  tyVft vft;
  vertex from;
  vertex to;
  plist plist;
};

struct tyVft vertexVft;
struct tyVft edgeVft;

static int vertexFlag = 1;
static int edgeFlag = 1;

static int vertexEquals (poly v1, poly v2);
static plist vertexGetPlist (poly data);
static int vertexHashCode (poly data);
static str vertexToString (poly data);

static int edgeEquals (poly v1, poly v2);
static plist edgeGetPlist (poly data);
static int edgeHashCode (poly data);
static str edgeToString (poly data);

static vertex searchVertex (graph g, poly data);


graph newGraph (str graphName)
{
  graph g = checkedMalloc (sizeof (*g));
  g->graphName = graphName;
  g->vs = newLinkedList ();
  
  return g;
}

static vertex newVertex (poly data)
{
  vertex v = checkedMalloc (sizeof (*v));
  if (vertexFlag)
  {
    vertexFlag--;
    vertexVft.equals = vertexEquals;
    vertexVft.getPlist = vertexGetPlist;
    vertexVft.hashCode = vertexHashCode;
    vertexVft.toString = vertexToString;
  }
  v->vft = &vertexVft;
  v->info = data;
  v->edges = newLinkedList ();
  v->plist = newPlist ();
  
  return v;
}

static vertex searchVertex (graph g, poly data)
{
  linkedList p = linkedListGetFirst (g->vs);
  
  tyEquals eq = getVft (data)->equals;
  while (p)
  {
    if (eq (data, (((vertex)(p->data))->info)))
    {
      return p->data;
    }
    else
    {
      p = p->next;
    }
  }
  error ("vertex not found: graph.c\n");
  return NULL;
}

static int vertexEquals (poly v1, poly v2)
{
  return plistEquals (((vertex)v1)->plist, ((vertex)v2)->plist);
}

static plist vertexGetPlist (poly data)
{
  return ((vertex)(data))->plist;
}

static int vertexHashCode (poly data)
{
  // a trivial but correct one
  return 0;
}

static str vertexToString (poly data)
{
  exception ("not implemented yet: graph.c\n");
  return NULL;
}

/*
static edge newEdge (graph g, poly from, poly to)
{
  edge e = checkedMalloc (sizeof (*e));
  if (edgeFlag)
  {
    edgeFlag--;
    edgeVft.equals = edgeEquals;
    edgeVft.getPlist = edgeGetPlist;
    edgeVft.hashCode = edgeHashCode;
    edgeVft.toString = edgeToString;
  }
  e->vft = &edgeVft;
  vertex fromVertex = searchVertex (g, from);
  vertex toVertex = searchVertex (g, to);
  
  e->from = fromVertex;
  e->to = toVertex;
  e->plist = newPlist ();
  
  return e;
}
*/

static edge newEdge2 (vertex fromVertex, vertex toVertex)
{
  edge e = checkedMalloc (sizeof (*e));
  if (edgeFlag)
  {
    edgeFlag--;
    edgeVft.equals = edgeEquals;
    edgeVft.getPlist = edgeGetPlist;
    edgeVft.hashCode = edgeHashCode;
    edgeVft.toString = edgeToString;
  }
  e->vft = &edgeVft;
  e->from = fromVertex;
  e->to = toVertex;
  e->plist = newPlist ();
  
  return e;
}

static int edgeEquals (poly v1, poly v2)
{
  return plistEquals (((edge)v1)->plist, ((edge)v2)->plist);  
}

static plist edgeGetPlist (poly data)
{
  return ((edge)data)->plist;
}

static int edgeHashCode (poly data)
{
  // a trivial but correct one
  return 0;
}

static str edgeToString (poly data)
{
  exception ("not implemented yet: graph.c\n");
  return NULL;
}

void graphInsertVertex (graph g, poly x)
{
  vertex v = newVertex (x);
  linkedListInsertTail (g->vs, v);
  return;
}

void graphInsertEdge (graph g, poly from, poly to)
{  
  vertex fromVertex = searchVertex (g, from);
  vertex toVertex = searchVertex (g, to);
  edge e = newEdge2 (fromVertex, toVertex);
  linkedListInsertTail (fromVertex->edges, e);
  
  return;
}

void graphListAllVertex (graph g, tyVisit visit)
{
  linkedList l = linkedListGetFirst (g->vs);
  
  while (l)
  {
    visit (((vertex)(l->data))->info);
    l = l->next;
  }
  return;
}

void graphToJpg (graph g, str fname)
{
  dot d = newDot ();
  str name = strConcat (g->graphName, fname);
  
  str emptyStr = newStr ("");
  
  linkedList l = linkedListGetFirst (g->vs);
  
  while (l)
  {
    vertex v = (vertex)(l->data);
    str sFrom = getVft (v->info)->toString (v->info);
    linkedList es = linkedListGetFirst (v->edges);
    while (es)
    {
      edge e = (edge)(es->data);
      str sTo = getVft (e->to->info) ->toString (e->to->info);
      dotInsert (sFrom, sTo, emptyStr, d);
      es = es->next;
    }
    l = l->next;
  }
  
  dotToJpg (d, strToCharStar (name));
}

static void graphDfsDoit (vertex v, property visited, tyVisit visit)
{
  if (visit)
  {
    printf ("\nnow dfs visiting vertex: ");
    visit (v->info);
  }
  propertyAdd (visited, v, newNat (1));
  linkedList edges = linkedListGetFirst (v->edges);
  
  while (edges)
  {
    edge e = edges->data;
    vertex to = e->to;
    poly value = propertyPeek (visited, to);
    if (!value)
      graphDfsDoit (to, visited, visit);
    edges = edges->next;
  }
  return;
}

void graphDfs (graph g, poly start, tyVisit visit)
{
  linkedList vs = linkedListGetFirst (g->vs);
  vertex stv = searchVertex (g, start);
  property visited = newProperty ();
  
  if (stv)
    graphDfsDoit (stv, visited, visit);
  
  while (vs)
  {
    vertex current = vs->data;
    poly value = propertyPeek (visited, current);
    if (!value)
      graphDfsDoit (current, visited, visit);
    vs = vs->next;
  }
  
  propertyDestroy (visited);
  return;
}

static void graphDfsTreeDoit (vertex v, property visited, tree tree)
{
  propertyAdd (visited, v, newNat (1));
  linkedList edges = linkedListGetFirst (v->edges);
  
  while (edges)
  {
    edge e = edges->data;
    vertex to = e->to;
    poly value = propertyPeek (visited, to);
    if (!value)
    {
      poly info1 = v->info;
      poly info2 = to->info;
      treeInsertEdge (tree, info1, info2);
      nat n = counterNext ();
      if (controlDfs)
        treeToJpg (tree, strConcat (newStr ("-"), natToString (n)));
      graphDfsTreeDoit (to, visited, tree);
    }
    edges = edges->next;
  }
  return;
}

tree graphDfsTree (graph g, poly start)
{
  counterReset ();
  linkedList vs, temp;
  vs = linkedListGetFirst (g->vs);
  temp = vs;
  vertex stv = searchVertex (g, start);
  
  str gname = strConcat (g->graphName, newStr ("-dfsTree"));
  tree tree = newTree (gname);
  while (temp)
  {
    vertex v = temp->data;
    poly info = v->info;
    treeInsertVertex (tree, info);
    temp = temp->next;
  }  
  
  property visited = newProperty ();
  
  if (stv)
    graphDfsTreeDoit (stv, visited, tree);
  
  while (vs)
  {
    vertex current = vs->data;
    poly value = propertyPeek (visited, current);
    if (!value)
      graphDfsTreeDoit (current, visited, tree);
    vs = vs->next;
  }
  
  propertyDestroy (visited);
  return tree;
}

static void graphBfsDoit (vertex start, property visited, tyVisit visit)
{
  queue q = newQueue ();
  enQueue (q, start);  
  
  while (! queueIsEmpty (q))
  {
    vertex current = deQueue (q);
    if (visit)
    {
      printf ("\nnow bfs visiting vertex: ");
      visit (current->info);
    }    
    
    linkedList edges = linkedListGetFirst (current->edges);
    while (edges)
    {
      edge e = edges->data;
      vertex to = e->to;
      poly value = propertyPeek (visited, to);
      if (!value)
      {
        propertyAdd (visited, to, newNat (1));
        enQueue (q, to);
      }
      edges = edges->next;
    }
  }
}

void graphBfs (graph g, poly start, tyVisit visit)
{
  linkedList vs = linkedListGetFirst (g->vs);
  property visited = newProperty ();
  
  vertex vst = searchVertex (g, start);
  
  propertyAdd (visited, vst, newNat (1));
  graphBfsDoit (vst, visited, visit);
  
  while (vs)
  {
    vertex current = vs->data;
    poly value = propertyPeek (visited, current);
    if (!value)
    {
      propertyAdd (visited, current, newNat (1));
      graphBfsDoit (current, visited, visit);
    }
    vs = vs->next;
  }
  
  propertyDestroy (visited);
  return;
}

static void graphBfsTreeDoit (vertex start, property visited, tree tree)
{
  queue q = newQueue ();
  enQueue (q, start);  
  
  while (! queueIsEmpty (q))
  {
    vertex current = deQueue (q);
    
    linkedList edges = linkedListGetFirst (current->edges);
    while (edges)
    {
      edge e = edges->data;
      vertex to = e->to;
      poly value = propertyPeek (visited, to);
      if (!value)
      {
        treeInsertEdge (tree, current->info, to->info);
        if (controlBfs)
          treeToJpg (tree, strConcat (newStr ("-"), natToString (counterNext())));
        propertyAdd (visited, to, newNat (1));
        enQueue (q, to);
      }
      edges = edges->next;
    }
  }
}

tree graphBfsTree (graph g, poly start)
{
  counterReset ();
  linkedList vs = linkedListGetFirst (g->vs);
  property visited = newProperty ();
  str treeName = strConcat (g->graphName, newStr ("-bfsTree"));
  tree tree = newTree (treeName);
  
  linkedList temp = vs;
  while (temp)
  {
    vertex v = temp->data;
    treeInsertVertex (tree, v->info);
    temp = temp->next;
  }
  
  vertex vst = searchVertex (g, start);
  
  propertyAdd (visited, vst, newNat (1));
  graphBfsTreeDoit (vst, visited, tree);
  
  while (vs)
  {
    vertex current = vs->data;
    poly value = propertyPeek (visited, current);
    if (!value)
    {
      propertyAdd (visited, current, newNat (1));
      graphBfsTreeDoit (current, visited, tree);
    }
    vs = vs->next;
  }
  
  propertyDestroy (visited);
  return tree;
}