The Datafile PD-CD 4/DATAFILE_PDCD4.iso/unix/unixtools/util/dev/c/graph

Text File | 1992-07-21 | 6.9 KB | 347 lines

/*      > C.Graph - Graph data type */

#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"

#ifdef test
#include <stdio.h>
#endif

/* Return values from functions */

#define OK      1
#define ERR     0

/* Create an empty graph */

graph graph_new (int val_len, int weight_len)
{
        graph g;

        g = malloc( sizeof(struct graph) );

        if ( g == NULL )
                return NULL;

        g->nodes = NULL;

        return g;
}

/* Create a new node, with value VALUE, and install it in graph G */

node graph_newnode (graph g, void *value)
{
        node n;
        struct nodelist *p;

        n = malloc( sizeof(struct node) - 1 + g->val_len );

        if ( n == NULL )
                return NULL;

        p = malloc( sizeof(struct nodelist) );

        if ( p == NULL )
        {
                free(n);
                return NULL;
        }

        n->val_len  = g->val_len;
        n->num_succ = 0;
        n->num_pred = 0;
        n->preds    = NULL;
        n->succs    = NULL;
        memcpy(n->value,value,g->val_len);

        p->node = n;
        p->next = g->nodes;

        g->nodes = p;

        return n;
}

/* Create a new arc, between nodes FROM and TO, with weight WEIGHT, and
   install it in graph G */

arc graph_newarc (graph g, node from, node to, void *weight)
{
        arc a;
        struct arclist *p1;
        struct arclist *p2;

        a = malloc( sizeof(struct arc) - 1 + g->weight_len );

        if ( a == NULL )
                return NULL;

        p1 = malloc( sizeof(struct arclist) );

        if ( p1 == NULL )
        {
                free(a);
                return NULL;
        }

        p2 = malloc( sizeof(struct arclist) );

        if ( p2 == NULL )
        {
                free(a);
                free(p1);
                return NULL;
        }

        a->start = from;
        a->end   = to;
        memcpy(a->weight,weight,g->weight_len);

        p1->arc = a;
        p2->arc = a;

        ++from->num_succ;
        p1->next = from->succs;
        from->succs = p1;

        ++to->num_pred;
        p2->next = to->preds;
        to->preds = p2;

        return a;
}

/* Remove arc A from graph G */

void graph_freearc (graph g, arc a)
{
        node n;
        struct arclist *p;
        struct arclist *del;

        n = a->start;

        --n->num_succ;

        p = n->succs;

        if ( p->arc == a )
        {
                del = p;
                n->succs = p->next;
        }

        else
        {
                for ( ; p->next != NULL; p = p->next )
                {
                        if ( p->next->arc == a )
                        {
                                del = p->next;
                                p->next = del->next;
                                break;
                        }
                }
        }

        free(del);

        n = a->end;

        --n->num_pred;

        p = n->preds;

        if ( p->arc == a )
        {
                del = p;
                n->preds = p->next;
        }

        else
        {
                for ( ; p->next != NULL; p = p->next )
                {
                        if ( p->next->arc == a )
                        {
                                del = p->next;
                                p->next = del->next;
                                break;
                        }
                }
        }

        free(del);

        free(a);
}

/* Free a node N from graph G */

int graph_freenode (graph g, node n)
{
        struct nodelist *p = g->nodes;
        struct nodelist *del = NULL;
        struct arclist *a;
        struct arclist *temp;

        if ( p->node == n )
        {
                del = p;
                g->nodes = p->next;
        }
        else
        {
                for ( ; p->next != NULL; p = p->next )
                {
                        if ( p->next->node == n )
                        {
                                del = p->next;
                                p->next = del->next;
                                break;
                        }
                }
        }

        if ( del == NULL )
                return ERR;

        free(del);

        a = n->preds;

        while ( a != NULL )
        {
                temp = a->next;
                graph_freearc(g,a->arc);
                free(a);
                a = temp;
        }

        a = n->succs;

        while ( a != NULL )
        {
                temp = a->next;
                graph_freearc(g,a->arc);
                free(a);
                a = temp;
        }

        free(n);

        return OK;
}

void graph_free (graph g)
{
        graph_clear(g);
        free(g);
}

void graph_clear (graph g)
{
        struct nodelist *p = g->nodes;

        while ( p != NULL )
        {
                temp = p->next;
                graph_freenode(g,p->node);
                free(p);
                p = temp;
        }

        g->nodes = NULL;
}

int graph_copy (graph g1, graph g2)
{
}

int graph_equal (graph g1, graph g2)
{
}

int graph_empty (graph g)
{
}

int graph_size (graph g)
{
}

int graph_iterate (graph g, int (*process)(void *))
{
}

/* graph-specific routines */

/*---------------------------------------------------------------------------*/

#ifdef test
int print (void *ptr)
{
        printf("%d ",*(int *)ptr);
        return STATUS_CONTINUE;
}

void graph_dump (graph g)
{
        printf("Graph: ");
        graph_iterate(g,print);
        putchar('\n');
}
#endif

/*---------------------------------------------------------------------------*/

#ifdef test

#define BUFLEN 255

int main (void)
{
        char buf[BUFLEN];
        int i, j, num;
        graph g[10];

        for ( i = 0; i < 10; ++i )
                g[i] = graph_new(sizeof(int));

        for ( ; ; )
        {
                printf(">");
                fgets(buf,BUFLEN,stdin);

                if ( buf[0] == '\n' || buf[0] == '\0' )
                        continue;
                else if ( sscanf(buf,"clear %1d",&i) == 1 )
                        graph_clear(g[i]);
                else if ( sscanf(buf,"copy %1d %1d",&i,&j) == 2 )
                        graph_copy(g[i],g[j]);
                else if ( sscanf(buf,"equal %1d %1d",&i,&j) == 2 )
                        printf("%s\n",(graph_equal(g[i],g[j]) ? "yes" : "no"));
                else if ( sscanf(buf,"empty %1d",&i) == 1 )
                        printf("%s\n",(graph_empty(g[i]) ? "yes" : "no"));
                else if ( sscanf(buf,"size %1d",&i) == 1 )
                        printf("%d\n",graph_size(g[i]));
                else if ( sscanf(buf,"dump %1d",&i) == 1 )
                        graph_dump(g[i]);
                else if ( strncmp(buf,"quit",4) == 0 )
                        break;
                else
                        printf("Mistake\n");
        }

        printf("Deleting g[0-9]\n");
        for ( i = 0; i < 10; ++i )
                graph_free(g[i]);

        return 0;
}

#endif