/*---------------------------------------------------------------------- File : graph.c Contents: adding vertices and edges for different representations conversions of different graph representations topological sorting of different graph representations Author : Christian Borgelt History : 11.06.1998 file created 30.06.1998 some conversion functions added 01.07.1998 all functions debugged 02.07.1998 topological sorting functions added 08.07.1998 topological sorting functions finished ----------------------------------------------------------------------*/ #include #include #include /*---------------------------------------------------------------------- Preprocessor Definitions ----------------------------------------------------------------------*/ #define BS_LIST 64 /* block size for list */ #define BS_MATRIX 8 /* block size for matrix */ /* --- error codes --- */ #define OK 0 /* no error */ #define E_NONE 0 /* no error */ #define E_NOMEM (-1) /* not enough memory */ #define E_PARSE (-2) /* parse error on list */ #define E_ILLID (-3) /* illegal identifier */ #define E_CYCLIC (-4) /* graph is not acyclic */ #define E_UNKNOWN (-5) /* unknown error */ /*---------------------------------------------------------------------- Type Definitions ----------------------------------------------------------------------*/ typedef struct { /* --- list --- */ int size; /* current size of element vector */ int cnt; /* current number of elements */ int *vec; /* list element vector */ } LIST; /* (list) */ typedef struct { /* --- adjacency matrix --- */ int size; /* current size of the matrix */ int vtcnt; /* current number of vertices */ int edcnt; /* current number of edges */ int **mat; /* matrix of elements */ } ADJMAT; /* (adjacency matrix) */ typedef struct _aledge { /* --- adjacency list edge --- */ int id; /* identifier of destination vertex */ struct _aledge *succ; /* successor in list */ } ALEDGE; /* (adjacency list edge) */ typedef struct _alvert { /* --- adjacency list vertex --- */ int id; /* identifier of vertex */ struct _alvert *succ; /* successor in vertex list */ struct _aledge *edges; /* list of edges from the vertex */ } ALVERT; /* (adjacency list vertex) */ typedef struct { /* --- adjacency list --- */ int vtcnt; /* current number of vertices */ int edcnt; /* current number of edges */ ALVERT *verts; /* list of vertices */ } ADJLIST; /* (adjacency list) */ /*---------------------------------------------------------------------- Constants ----------------------------------------------------------------------*/ const char *errmsgs[] = { /* error messages */ /* E_NONE 0 */ "no error\n", /* E_NOMEM -1 */ "not enough memory\n", /* E_PARSE -2 */ "parse error on list\n", /* E_ILLID -3 */ "illegal identifier\n", /* E_CYCLIC -4 */ "graph is not acyclic\n", /* E_UNKNOWN -5 */ "unknown error\n" }; /*---------------------------------------------------------------------- Global Variables ----------------------------------------------------------------------*/ static char *prgname; /* program name for error messages */ /*---------------------------------------------------------------------- General List Operations ----------------------------------------------------------------------*/ LIST* lst_create (int size) { /* --- create a list */ LIST *list; /* created list */ if (size < 2) size = 2; /* check for minimal list size */ list = (LIST*)malloc(sizeof(LIST)); if (!list) return NULL; /* allocate memory for the list body */ list->vec = (int*)malloc(size *sizeof(int)); if (!list->vec) { free(list); return NULL; } list->size = size; /* allocate memory for element vector */ list->cnt = 2; /* and initialize fields */ list->vec[0] = list->vec[1] = 0; return list; /* return the created list */ } /* lst_create() */ /*--------------------------------------------------------------------*/ void lst_delete (LIST *list) { /* --- delete a list */ free(list->vec); /* delete the element vector */ free(list); /* and the list body */ } /* lst_delete() */ /*--------------------------------------------------------------------*/ int lst_adapt (LIST *list, int size) { /* --- check and adapt a list */ int *new; /* new (enlarged) list */ int tmp; /* temporary buffer */ if (list->size >= size) /* if the list is large enough, */ return 0; /* abort the function */ tmp = list->size /* compute new vector size */ + ((list->size > BS_LIST) ? (list->size >> 1) : BS_LIST); if (tmp > size) size = tmp; /* check against given size */ new = (int*)realloc(list->vec, size *sizeof(int)); if (!new) return -1; /* allocate a new (enlarged) list */ list->vec = new; list->size = size; return 0; /* return `ok' */ } /* lst_adapt() */ /*--------------------------------------------------------------------*/ void lst_show (LIST *list) { /* --- show a list */ int i; /* loop variable */ printf("(%d", list->vec[0]); /* print the first element */ for (i = 1; i < list->cnt; i++) /* traverse and print */ printf(",%d", list->vec[i]); /* the remaining elements */ printf(")\n"); /* terminate the output line */ } /* lst_show() */ /*---------------------------------------------------------------------- Standard List Functions ----------------------------------------------------------------------*/ int sl_edcmp (const void *p1, const void *p2) { /* --- compare two edges */ if (*(const int*)p1 > *(const int*)p2) return 1; if (*(const int*)p1 < *(const int*)p2) return -1; return 0; /* return sign of vertex id. diff. */ } /* sl_edcmp() */ /*--------------------------------------------------------------------*/ int sl_addvert (LIST *sl, int cnt) { /* --- add vertices to a std. list */ sl->vec[0] += cnt; /* increment vertex counter */ return 0; /* return `ok' */ } /* sl_addvert() */ /*--------------------------------------------------------------------*/ int sl_addedge (LIST *sl, int src, int dst) { /* --- add an edge to a standard list */ if ((src <= 0) || (src > sl->vec[0]) || (dst <= 0) || (dst > sl->vec[0])) return E_ILLID; /* check vertex indices */ if (lst_adapt(sl, sl->cnt +2) != 0) /* adapt the list */ return E_NOMEM; /* (enlarge it, if necessary) */ sl->vec[1]++; /* increment the number of edges */ sl->vec[sl->cnt++] = src; /* set source and destination */ sl->vec[sl->cnt++] = dst; /* vertex identifier of new edge */ return 0; /* return `ok' */ } /* sl_addedge() */ /*--------------------------------------------------------------------*/ #if 1 /* normal (in-degree) version */ int sl_topsort (LIST *sl) { /* --- sort graph topologically */ int i, j, k; /* loop variables */ int *indegs; /* in-degrees of vertices */ int *map; /* mapping for vertex numbers */ int *p; /* to traverse the list */ map = (int*)calloc(2 *sl->vec[0], sizeof(int)); if (!map) return E_NOMEM; /* allocate memory for work buffers */ indegs = map +sl->vec[0]; /* and organize it (2 vectors in 1) */ for (p = sl->vec +3, i = sl->vec[1]; --i >= 0; p += 2) indegs[*p -1]++; /* determine in-degrees of vertices */ for (i = 1; i <= sl->vec[0]; i++) { /* traverse vertex identifiers */ for (j = sl->vec[0]; --j >= 0; ) /* traverse in-degree vector */ if (indegs[j] == 0) break;/* look for a vertex with no predec. */ if (j < 0) { /* if there is no such vertex, */ free(map); return E_CYCLIC; } /* abort the function */ indegs[j] = -1; /* otherwise mark vertex as processed */ map[j] = i; /* note step number as new identifier */ for (p = sl->vec +2, k = sl->vec[1]; --k >= 0; p += 2) { if (*p == j+1) indegs[p[1] -1]--; } /* remove edges from the processed */ } /* vertex from the in-degree vector */ for (p = sl->vec +2, i = 2 *sl->vec[1]; --i >= 0; p++) *p = map[*p -1]; /* set new vertex identifiers */ free(map); /* delete work buffers */ return 0; /* return `ok' */ } /* sl_topsort() */ /*--------------------------------------------------------------------*/ #else /* alternative (out-degree) version */ int sl_topsort (LIST *sl) { /* --- sort graph topologically */ int i, j, k; /* loop variables */ int *outdegs; /* out-degrees of vertices */ int *map; /* mapping for vertex numbers */ int *p; /* to traverse the list */ map = (int*)calloc(2 *sl->vec[0], sizeof(int)); if (!map) return E_NOMEM; /* allocate memory for work buffers */ outdegs = map +sl->vec[0]; /* and organize it (2 vectors in 1) */ for (p = sl->vec +2, i = sl->vec[1]; --i >= 0; p += 2) outdegs[*p -1]++; /* determine out-degrees of vertices */ for (i = sl->vec[0]; i > 0; i--) { /* traverse vertex identifiers */ for (j = sl->vec[0]; --j >= 0; ) /* traverse out-degree vector */ if (outdegs[j] ==0) break;/* look for a vertex with no succ. */ if (j < 0) { /* if there is no such vertex, */ free(map); return E_CYCLIC; } /* abort the function */ outdegs[j] = -1; /* otherwise mark vertex as processed */ map[j] = i; /* note step number as new identifier */ for (p = sl->vec +2, k = sl->vec[1]; --k >= 0; p += 2) { if (p[1] == j+1) outdegs[*p -1]--; } /* remove edges from the processed */ } /* vertex from the out-degree vector */ for (p = sl->vec +2, i = 2 *sl->vec[1]; --i >= 0; p++) *p = map[*p -1]; /* set new vertex identifiers */ free(map); /* delete work buffers */ return 0; /* return `ok' */ } /* sl_topsort() */ #endif /*---------------------------------------------------------------------- Vertex-Oriented List Functions ----------------------------------------------------------------------*/ int vl_addvert (LIST *vl, int cnt) { /* --- add vertices to a v.o. list */ if (lst_adapt(vl, vl->cnt +cnt) != 0) /* adapt the list */ return E_NOMEM; /* (enlarge it, if necessary) */ vl->vec[0] += cnt; /* increment vertex counter */ vl->cnt += cnt; /* and length of list */ while (--cnt >= 0) /* set out-degree */ vl->vec[vl->cnt -cnt-1] = 0;/* of new vertices */ return 0; /* return `ok' */ } /* vl_addvert() */ /*--------------------------------------------------------------------*/ int vl_addedge (LIST *vl, int src, int dst) { /* --- add an edge to a v.o. list */ int i, j; /* vector indices, number of elements */ if ((src <= 0) || (src > vl->vec[0]) || (dst <= 0) || (dst > vl->vec[0])) return E_ILLID; /* check vertex indices */ if (lst_adapt(vl, vl->cnt +1) != 0) /* adapt the list */ return E_NOMEM; /* (enlarge it, if necessary) */ for (j = 2, i = src; --i > 0; ) j += vl->vec[j] +1; /* find the index of the out-degree */ j += ++vl->vec[j]; /* of the source and increment it */ for (i = vl->cnt; --i >= j; ) /* shift right all elements to the */ vl->vec[i+1] = vl->vec[i]; /* right of the dest. vertex list */ vl->vec[1]++; vl->cnt++; /* increment the number of edges and */ vl->vec[j] = dst; /* set the destination identifier */ return 0; /* return `ok' */ } /* vl_addedge() */ /*--------------------------------------------------------------------*/ int vl_topsort (LIST *vl) { /* --- sort graph topologically */ int i, j, k; /* loop variables */ int *indegs; /* in-degrees of vertices */ int *map; /* mapping for vertex numbers */ int *buf; /* buffer for reordered list */ int *p, *q; /* to traverse the list */ map = (int*)calloc(3 *vl->vec[0] +vl->vec[1], sizeof(int)); if (!map) return E_NOMEM; /* allocate memory for work buffers */ indegs = map +vl->vec[0]; /* and organize it (3 vectors in 1, */ buf = q = indegs +vl->vec[0]; /* third vector is for reordering) */ for (p = vl->vec +2, i = vl->vec[0]; --i >= 0; ) { for (j = *p++; --j >= 0; p++) indegs[*p -1]++; /* traverse edge descriptions and */ } /* determine in-degrees of vertices */ for (i = 1; i <= vl->vec[0]; i++) { /* traverse vertex identifiers */ for (j = vl->vec[0]; --j >= 0; ) /* traverse in-degree vector */ if (indegs[j] == 0) break;/* look for a vertex with no predec. */ if (j < 0) { /* if there is no such vertex, */ free(map); return E_CYCLIC; } /* abort the function */ indegs[j] = -1; /* otherwise mark vertex as processed */ map[j] = i; /* note step number as new identifier */ for (p = vl->vec +2, k = j; --k >= 0; ) p += *p +1; /* find descript. of processed vertex */ for (*q++ = k = *p++; --k >= 0; ) { indegs[*p -1]--; /* remove edges from the processed */ *q++ = *p++; /* vertex from the in-degree vector */ } /* and copy them to the buffer */ } /* (reorder node descriptions) */ for (p = vl->vec +2, q = buf, i = vl->vec[0]; --i >= 0; ) { for (*p++ = k = *q++; --k >= 0; q++) *p++ = map[*q -1]; /* traverse the vertex descriptions */ } /* and set the new vertex identifiers */ free(map); /* delete work buffers */ return 0; /* return `ok' */ } /* vl_topsort() */ /*---------------------------------------------------------------------- Adjacency Matrix Functions ----------------------------------------------------------------------*/ void am_delete (ADJMAT *am) { /* --- delete an adjacency matrix */ int i; /* loop variable */ for (i = am->size; --i >= 0;) /* delete the lines of the matrix */ if (am->mat[i]) free(am->mat[i]); free(am->mat); /* delete the lines vector */ free(am); /* and the matrix body */ } /* am_delete() */ /*--------------------------------------------------------------------*/ ADJMAT* am_create (int size) { /* --- create an adjacency matrix */ int i; /* loop variable */ ADJMAT *am; /* created adjacency matrix */ am = (ADJMAT*)malloc(sizeof(ADJMAT)); if (!am) return NULL; /* allocate memory for body */ am->mat = (int**)calloc(size, sizeof(int*)); if (!am->mat) { free(am); return NULL; } am->size = size; /* allocate memory for lines vector */ am->vtcnt = am->edcnt = 0; /* and initialize fields */ for (i = size; --i >= 0; ) { /* traverse the lines vector */ am->mat[i] = (int*)malloc(size *sizeof(int)); if (!am->mat[i]) { am_delete(am); return NULL; } } /* allocate the matrix lines */ return am; /* return the created matrix */ } /* am_create() */ /*--------------------------------------------------------------------*/ int am_adapt (ADJMAT *am, int size) { /* --- check and adapt an adj. matrix */ int i; /* loop variable */ void *new; /* new (enlarged) vector */ int tmp; /* temporary buffer */ if (am->size >= size) /* if the matrix is large enough, */ return 0; /* abort the function */ tmp = am->size +BS_MATRIX; /* compute new vector size */ if (tmp > size) size = tmp; /* check against given size */ new = realloc(am->mat, size *sizeof(int*)); if (!new) return -1; /* reallocate lines vector */ am->mat = new; /* and set new vector */ for (i = am->size; i < size; i++) am->mat[i] = NULL; /* clear new vector elements */ for (i = size; --i >= 0; ) { /* traverse matrix lines */ am->mat[i] = (int*)realloc(am->mat[i], size *sizeof(int)); if (!am->mat[i]) break; /* (re)allocate the matrix lines */ } /* (enlarge line vectors) */ if (i >= 0) { /* if an error occured */ for (i = am->size; i < size; i++) if (am->mat[i]) free(am->mat[i]); return -1; /* traverse new matrix lines, */ } /* remove then, and abort */ am->size = size; /* set new matrix size */ return 0; /* return `ok' */ } /* am_adapt() */ /*--------------------------------------------------------------------*/ void am_show (ADJMAT *am) { /* --- show an adjacency matrix */ int i, j; /* loop variables */ for (i = 0; i < am->vtcnt; i++) { /* traverse lines of matrix */ printf("%d", am->mat[i][0]); /* print first column of line */ for (j = 1; j < am->vtcnt; j++) /* traverse remaining columns */ printf(" %d", am->mat[i][j]); /* print column value */ printf("\n"); /* terminate output line */ } /* after each matrix line */ } /* am_show() */ /*--------------------------------------------------------------------*/ int am_addvert (ADJMAT *am, int cnt) { /* --- add vertices to an adj. matrix */ int i; /* loop variable */ if (am_adapt(am, am->vtcnt +cnt) != 0) /* adapt the matrix */ return E_NOMEM; /* (enlarge it, if necessary) */ while (--cnt >= 0) { /* traverse new vertices */ for (i = ++am->vtcnt; --i >= 0; ) { am->mat[i][am->vtcnt] = 0;/* traverse lines columns and */ am->mat[am->vtcnt][i] = 0;/* clear the additional line */ } /* and the additional column */ } return 0; /* return `ok' */ } /* am_addvert() */ /*--------------------------------------------------------------------*/ int am_addedge (ADJMAT *am, int src, int dst) { /* --- add an edge to an adj. matrix */ if ((src <= 0) || (src > am->vtcnt) || (dst <= 0) || (dst > am->vtcnt)) return E_ILLID; /* check vertex indices */ am->mat[src][dst]++; /* set corresponding matrix element */ am->edcnt++; /* increment edge counter */ return 0; /* return `ok' */ } /* am_addedge() */ /*--------------------------------------------------------------------*/ int am_topsort (ADJMAT *am) { /* --- sort graph topologically */ int i, j, k; /* loop variables */ int *indegs; /* in-degrees of vertices */ int *map; /* mapping for vertex numbers */ int *p; /* to traverse the matrix lines */ int **mat; /* buffer for matrix lines */ i = (int)((sizeof(int*) > sizeof(int)) ? sizeof(int*) : sizeof(int)); k = am->vtcnt *((int)sizeof(int) +i); map = (int*)calloc(1, k); /* compute work buffer size and */ if (!map) return E_NOMEM; /* allocate memory for work buffers */ indegs = map +am->vtcnt; /* and organize it (2 vectors in 1) */ for (i = am->vtcnt; --i >= 0; ) { for (p = am->mat[i], j = 0; j < am->vtcnt; j++) indegs[j] += *p++; /* traverse matrix columns and */ } /* determine in-degrees of vertices */ for (i = 1; i <= am->vtcnt; i++) { /* traverse vertex identifiers */ for (j = am->vtcnt; --j >= 0; ) /* traverse in-degree vector */ if (indegs[j] == 0) break;/* look for a vertex with no predec. */ if (j < 0) { /* if there is no such vertex, */ free(map); return E_CYCLIC; } /* abort the function */ indegs[j] = -1; /* otherwise mark vertex as processed */ map[j] = i; /* note step number as new identifier */ for (p = am->mat[j], k = 0; k < am->vtcnt; k++) indegs[k] -= *p++; /* remove edges from the processed */ } /* vertex from the in-degree vector */ for (i = am->vtcnt; --i >= 0; ) { for (p = am->mat[i], j = am->vtcnt; --j >= 0; ) indegs[j] = p[j]; /* copy matrix line to buffer */ for (j = am->vtcnt; --j >= 0; ) p[map[j]-1] = indegs[j]; /* copy matrix line back and at the */ } /* same time reorder the columns */ mat = (int**)indegs; /* reuse vector as a line buffer */ for (i = am->vtcnt; --i >= 0; ) mat[i] = am->mat[i]; /* copy matrix lines to buffer */ for (i = am->vtcnt; --i >= 0; ) am->mat[map[i]-1] = mat[i]; /* copy back and reorder matrix lines */ free(map); /* delete work buffers */ return 0; /* return `ok' */ } /* am_topsort() */ /*---------------------------------------------------------------------- Adjacency List Functions ----------------------------------------------------------------------*/ ADJLIST* al_create (void) { /* --- create an adjacency list */ return (ADJLIST*)calloc(1, sizeof(ADJLIST)); } /* al_create() */ /*--------------------------------------------------------------------*/ void al_delete (ADJLIST *al) { /* --- delete an adjacency list */ ALVERT *vert; /* to traverse the vertex list */ ALEDGE *edge; /* to traverse the edge lists */ void *tmp; /* buffer for deletion */ for (vert = al->verts; vert; ) { /* traverse vertices */ for (edge = vert->edges; edge; ) { /* traverse edges */ tmp = edge; edge = edge->succ; free(tmp); } tmp = vert; vert = vert->succ; free(tmp); } /* delete all edges and vertices */ } /* al_delete() */ /*--------------------------------------------------------------------*/ void al_show (ADJLIST *al) { /* --- show an adjacency list */ ALVERT *vert; /* to traverse the vertex list */ ALEDGE *edge; /* to traverse the edge lists */ for (vert = al->verts; vert; vert = vert->succ) { printf("[%d]", vert->id); /* traverse vertices */ for (edge = vert->edges; edge; edge = edge->succ) printf("->%d", edge->id); /* traverse edges and */ printf("\n"); /* print their identifiers */ } /* after each vertex terminate line */ } /* al_show() */ /*--------------------------------------------------------------------*/ int al_addvert (ADJLIST *al, int cnt) { /* --- add vertices to an adj. list */ ALVERT *vert, **end; /* list of created vertices */ ALVERT *tmp; /* buffer for creation/deletion */ int i; /* loop variable */ vert = NULL; end = | /* init. list of created vertices */ for (i = 1; i <= cnt; i++) { /* traverse vertices to add */ *end = tmp = (ALVERT*)malloc(sizeof(ALVERT)); if (!tmp) { /* allocate a new vertex */ while (vert) { tmp = vert; vert = vert->succ; free(tmp); } return E_NOMEM; /* if an error occurred, */ } /* delete list of vertices and abort */ tmp->id = al->vtcnt +i; /* otherwise initialize fields */ tmp->edges = NULL; /* no edges from this vertex yet */ end = &tmp->succ; /* get address of successor pointer */ } /* to append new vertices */ *end = al->verts; /* append the old vertex list to the */ al->verts = vert; /* new and set the new vertex list */ al->vtcnt += cnt; /* increment vertex counter */ return 0; /* return `ok' */ } /* al_addvert() */ /*--------------------------------------------------------------------*/ int al_addedge (ADJLIST *al, int src, int dst) { /* --- add an edge to an adj. list */ ALVERT *vert; /* to traverse the vertex list */ ALEDGE *edge; /* created edge */ if ((src <= 0) || (src > al->vtcnt) || (dst <= 0) || (dst > al->vtcnt)) return E_ILLID; /* check vertex indices */ edge = (ALEDGE*)malloc(sizeof(ALEDGE)); if (!edge) return E_NOMEM; /* allocate memory for a new edge */ vert = al->verts; /* find source vertex of edge */ while (vert->id != src) vert = vert->succ; edge->id = dst; /* initialize vertex identifier, */ edge->succ = vert->edges; /* append the old edge list to the */ vert->edges = edge; /* new edge and set the new edge list */ al->edcnt++; /* increment edge counter */ return 0; /* return `ok' */ } /* al_addedge() */ /*--------------------------------------------------------------------*/ int al_topsort (ADJLIST *al) { /* --- sort graph topologically */ int i, j; /* loop variables */ int *indegs; /* in-degrees of vertices */ int *map; /* mapping for vertex numbers */ ALVERT *vert; /* to traverse the vertex list */ ALEDGE *edge; /* to traverse the edge lists */ map = (int*)calloc(2 *al->vtcnt, sizeof(int)); if (!map) return E_NOMEM; /* allocate memory for work buffers */ indegs = map +al->vtcnt; /* and organize it (2 vectors in 1) */ for (vert = al->verts; vert; vert = vert->succ) { for (edge = vert->edges; edge; edge = edge->succ) indegs[edge->id -1]++; /* traverse vertices and edges and */ } /* determine in-degrees of vertices */ for (i = 1; i <= al->vtcnt; i++) { /* traverse vertex identifiers */ for (j = al->vtcnt; --j >= 0; ) /* traverse in-degree vector */ if (indegs[j] == 0) break;/* look for a vertex with no predec. */ if (j < 0) { /* if there is no such vertex, */ free(map); return E_CYCLIC; } /* abort the function */ indegs[j] = -1; /* otherwise mark vertex as processed */ map[j] = i; /* note step number as new identifier */ for (vert = al->verts; vert->id != j+1; ) vert = vert->succ; /* find processed vertex in list */ for (edge = vert->edges; edge; edge = edge->succ) indegs[edge->id -1]--; /* remove edges from the processed */ } /* vertex from the in-degree vector */ for (vert = al->verts; vert; vert = vert->succ) { vert->id = map[vert->id-1]; /* map identifiers in vertex list */ for (edge = vert->edges; edge; edge = edge->succ) edge->id = map[edge->id -1]; /* traverse edges and */ } /* set the new vertex identifiers */ free(map); /* delete work buffers */ return 0; /* return `ok' */ } /* al_topsort() */ /*---------------------------------------------------------------------- Conversion Functions ----------------------------------------------------------------------*/ LIST* sl_from_vl (LIST *vl) { /* --- create a standard list */ /* from a vertex-oriented list */ LIST *sl; /* created standard list */ int i, j; /* loop variables */ int *src, *dst; /* to traverse the lists */ sl = lst_create(i = 2 +vl->vec[1] *2); if (!sl) return NULL; /* create a list of appropriate size */ sl->cnt = i; /* and set the list length */ sl->vec[0] = vl->vec[0]; /* copy the number of vertices */ sl->vec[1] = vl->vec[1]; /* and the number of edges */ src = vl->vec +2; /* get pointer to first vertex data */ dst = sl->vec +2; /* and pointer to first edge data */ for (i = 1; i <= vl->vec[0]; i++) { /* traverse vertices */ for (j = *src++; --j >= 0; ) { /* traverse edges */ *dst++ = i; *dst++ = *src++; } } /* store vertices of current edge */ return sl; /* return the created list */ } /* sl_from_vl() */ /*--------------------------------------------------------------------*/ LIST* sl_from_am (ADJMAT *am) { /* --- create a standard list */ /* from an adjacency matrix */ LIST *sl; /* created standard list */ int i, j, k; /* loop variables, counters */ int *p; /* to traverse the standard list */ sl = lst_create(i = 2 +am->edcnt *2); if (!sl) return NULL; /* create a list of appropriate size */ sl->cnt = i; /* set the list length */ sl->vec[0] = am->vtcnt; /* set the number of vertices */ sl->vec[1] = am->edcnt; /* and the number of edges */ p = sl->vec +2; /* get pointer to first edge */ for (i = 0; i < am->vtcnt; i++) /* traverse lines */ for (j = 0; j < am->vtcnt; j++) /* traverse columns */ for (k = am->mat[i][j]; --k >= 0; ) { *p++ = i+1; *p++ = j+1; } /* enter edge into list */ return sl; /* return the created list */ } /* sl_from_am() */ /*--------------------------------------------------------------------*/ LIST* sl_from_al (ADJLIST *al) { /* --- create a standard list */ /* from an adjacency list */ LIST *sl; /* created standard list */ int i; /* temporary buffer */ int *p; /* to traverse the standard list */ ALVERT *vert; /* to traverse the vertices */ ALEDGE *edge; /* to traverse the edges */ sl = lst_create(i = 2 +al->edcnt *2); if (!sl) return NULL; /* create a list of appropriate size */ sl->cnt = i; /* set the list length */ sl->vec[0] = al->vtcnt; /* set the number of vertices */ sl->vec[1] = al->edcnt; /* and the number of edges */ p = sl->vec +2; /* get pointer to first edge */ for (vert = al->verts; vert; vert = vert->succ) { for (edge = vert->edges; edge; edge = edge->succ) { *p++ = vert->id; *p++ = edge->id; } } /* enter edges into the list */ return sl; /* return the created list */ } /* sl_from_al() */ /*--------------------------------------------------------------------*/ LIST* vl_from_sl (LIST *sl) { /* --- create a vertex-oriented list */ /* from a standard list */ LIST *vl; /* created vertex-oriented list */ int i; /* loop variable, buffer */ int *s, *p, *q; /* to traverse the lists */ vl = lst_create(i = 2 +sl->vec[0] +sl->vec[1]); if (!vl) return NULL; /* create a list of appropriate size */ vl->cnt = i; /* set the list length */ vl->vec[0] = sl->vec[0]; /* set the number of vertices */ vl->vec[1] = sl->vec[1]; /* and the number of edges */ qsort(sl->vec +2, sl->vec[1], 2 *sizeof(int), sl_edcmp); s = sl->vec +2; /* get pointer to first edge data */ q = vl->vec +2; /* and pointer to first vertex data */ for (i = 1; i <= sl->vec[0]; i++) { p = q++; /* set pointers for next vertex */ while (*s == i) { *q++ = *++s; s++; } *p = (int)(q -p) -1; /* set destinations vertices */ } /* and out-degree of vertex i */ return vl; /* return the created list */ } /* vl_from_sl() */ /*--------------------------------------------------------------------*/ LIST* vl_from_am (ADJMAT *am) { /* --- create a vertex-oriented list */ /* from an adjacency matrix */ LIST *vl; /* created vertex-oriented list */ int i, j, k; /* loop variables */ int *p, *q; /* to traverse vertex-oriented list */ vl = lst_create(i = 2 +am->vtcnt +am->edcnt); if (!vl) return NULL; /* create a list of appropriate size */ vl->cnt = i; /* set the list length */ vl->vec[0] = am->vtcnt; /* set the number of vertices */ vl->vec[1] = am->edcnt; /* and the number of edges */ q = vl->vec +2; /* get pointer for first vertex */ for (i = 0; i < am->vtcnt; i++) { /* traverse matrix lines */ p = q++; *p = 0; /* set pointers for next vertex */ for (j = 0; j < am->vtcnt; j++) { /* traverse columns of line */ *p += k = am->mat[i][j]; /* add number of edges to out-degree */ while (--k >= 0) *q++ = j+1; } /* enter as many vertex ids */ } /* as the edge counter indicates */ return vl; /* return the created list */ } /* vl_from_am() */ /*--------------------------------------------------------------------*/ LIST* vl_from_al (ADJLIST *al) { /* --- create a vertex-oriented list */ /* from an adjacency matrix */ LIST *vl; /* created vertex-oriented list */ int i; /* temporary buffer */ int *p, *q; /* to traverse vertex-oriented list */ ALVERT *vert; /* to traverse the vertices */ ALEDGE *edge; /* to traverse the edges */ vl = lst_create(i = 2 +al->vtcnt +al->edcnt); if (!vl) return NULL; /* create a list of appropriate size */ vl->cnt = i; /* set the list length */ vl->vec[0] = al->vtcnt; /* set the number of vertices */ vl->vec[1] = al->edcnt; /* and the number of edges */ q = vl->vec +2; /* get pointer for first vertex */ for (vert = al->verts; vert; vert = vert->succ) { p = q++; /* set pointers for next vertex */ for (edge = vert->edges; edge; edge = edge->succ) *q++ = edge->id; /* enter edges into the list */ *p = (int)(q -p) -1; /* and set the out-degree for */ } /* the corresponding source vertex */ return vl; /* return the created list */ } /* vl_from_al() */ /*--------------------------------------------------------------------*/ ADJMAT* am_from_sl (LIST *sl) { /* --- create an adjacency matrix */ /* from a standard list */ ADJMAT *am; /* created adjacency matrix */ int i, j; /* loop variables */ int *p; /* to traverse standard list */ am = am_create(sl->vec[0]); /* create an adjacency matrix */ if (!am) return NULL; /* with vec[0] lines and columns */ am->vtcnt = sl->vec[0]; /* set the number of vertices */ am->edcnt = sl->vec[1]; /* and the number of edges */ for (i = am->vtcnt; --i >= 0; ) /* traverse lines of matrix */ for (j = am->vtcnt; --j >= 0; ) /* traverse columns of line */ am->mat[i][j] = 0; /* clear matrix element */ p = sl->vec +2; /* get pointer to first edge */ for (i = sl->vec[1]; --i >= 0; p += 2) /* traverse edges and */ am->mat[p[0]-1][p[1]-1]++; /* set corresponding matrix elements */ return am; /* return the created matrix */ } /* am_from_sl() */ /*--------------------------------------------------------------------*/ ADJMAT* am_from_vl (LIST *vl) { /* --- create matrix from v.o. list */ ADJMAT *am; /* created adjacency matrix */ int i, j; /* loop variables */ int *p; /* to traverse standard list */ am = am_create(vl->vec[0]); /* create an adjacency matrix */ if (!am) return NULL; /* with vec[0] lines and columns */ am->vtcnt = vl->vec[0]; /* set the number of vertices */ am->edcnt = vl->vec[1]; /* and the number of edges */ for (i = am->vtcnt; --i >= 0; ) /* traverse lines of matrix */ for (j = am->vtcnt; --j >= 0; ) /* traverse columns of line */ am->mat[i][j] = 0; /* clear matrix element */ p = vl->vec +2; /* get pointer to first vertex data */ for (i = 0; i < vl->vec[0]; i++) { /* traverse vertices */ for (j = *p++; --j >= 0; p++) /* traverse edges */ am->mat[i][*p-1]++; /* set matrix element */ } /* corresponding to the current edge */ return am; /* return the created matrix */ } /* am_from_vl() */ /*--------------------------------------------------------------------*/ ADJMAT* am_from_al (ADJLIST *al) { /* --- create an adjacency matrix */ /* from an adjacency list */ ADJMAT *am; /* created adjacency matrix */ int i, j; /* loop variables */ ALVERT *vert; /* to traverse the vertices */ ALEDGE *edge; /* to traverse the edges */ am = am_create(al->vtcnt); /* create an adjacency matrix */ if (!am) return NULL; /* with vtcnt lines and columns */ am->vtcnt = al->vtcnt; /* set the number of vertices */ am->edcnt = al->edcnt; /* and the number of edges */ for (i = am->vtcnt; --i >= 0; ) /* traverse lines of matrix */ for (j = am->vtcnt; --j >= 0; ) /* traverse columns of line */ am->mat[i][j] = 0; /* clear matrix element */ for (vert = al->verts; vert; vert = vert->succ) { for (edge = vert->edges; edge; edge = edge->succ) am->mat[vert->id -1][edge->id -1]++; } /* enter edges into matrix */ return am; /* return the created matrix */ } /* am_from_al() */ /*--------------------------------------------------------------------*/ ADJLIST* al_from_sl (LIST *sl) { /* --- create an adjacency list */ /* from a standard list */ ADJLIST *al; /* created adjacency list */ int i; /* loop variable */ int *p; /* to traverse standard list */ al = al_create(); /* create an adjacency list */ if (!al) return NULL; /* and add sufficient vertices */ if (al_addvert(al, sl->vec[0]) != 0) { al_delete(al); return NULL; } p = sl->vec +2; /* get pointer to first edge */ for (i = sl->vec[1]; --i >= 0; p += 2) { if (al_addedge(al, p[0], p[1]) != 0) { al_delete(al); return NULL; } } /* traverse and add edges */ return al; /* return created adjacency list */ } /* al_from_sl() */ /*--------------------------------------------------------------------*/ ADJLIST* al_from_vl (LIST *vl) { /* --- create an adjacency list */ /* from a vertex-oriented list */ ADJLIST *al; /* created adjacency list */ int i, j; /* loop variables */ int *p; /* to traverse vertex-oriented list */ al = al_create(); /* create an adjacency list */ if (!al) return NULL; /* and add sufficient vertices */ if (al_addvert(al, vl->vec[0]) != 0) { al_delete(al); return NULL; } p = vl->vec +2; /* get pointer to first vertex data */ for (i = 1; i <= vl->vec[0]; i++) { /* traverse vertices */ for (j = *p++; --j >= 0; p++) { /* traverse edges */ if (al_addedge(al, i, *p) != 0) { al_delete(al); return NULL; } } /* add the current edge */ } /* to the adjacency list */ return al; /* return created adjacency list */ } /* al_from_vl() */ /*--------------------------------------------------------------------*/ ADJLIST* al_from_am (ADJMAT *am) { /* --- create an adjacency list */ /* from an adjacency matrix */ ADJLIST *al; /* created adjacency list */ int i, j, k; /* loop variables */ al = al_create(); /* create an adjacency list */ if (!al) return NULL; /* and add sufficient vertices */ if (al_addvert(al, am->vtcnt) != 0) { al_delete(al); return NULL; } for (i = 0; i < am->vtcnt; i++) { /* traverse vertices */ for (j = 0; j < am->vtcnt; j++) { /* traverse edges */ for (k = am->mat[i][j]; --k >= 0; ) { if (al_addedge(al, i+1, j+1) != 0) { al_delete(al); return NULL; } } /* add as many edges from i to j */ } /* to the adjacency list */ } /* as the matrix element indicates */ return al; /* return created adjacency list */ } /* al_from_am() */ /*---------------------------------------------------------------------- Main Functions ----------------------------------------------------------------------*/ void error (int code, ...) { /* --- print error message */ va_list args; /* list of variable arguments */ const char *msg; /* buffer for error message */ if ((code > 0) || (code < E_UNKNOWN)) code = E_UNKNOWN; /* check error code */ msg = errmsgs[-code]; /* get error message */ if (!msg) msg = errmsgs[-E_UNKNOWN]; fprintf(stderr, "\n%s: ", prgname); /* print program name */ va_start(args, code); /* get variable arguments */ vfprintf(stderr, msg, args); /* print error message */ va_end(args); /* end variable argument evaluation */ exit(code); /* abort programm */ } /* error() */ /*--------------------------------------------------------------------*/ int main (int argc, char *argv[]) { /* --- main function */ int i, j; /* vertex identifiers */ int vtcnt; /* number of vertices */ int edcnt; /* number of edges */ LIST *sl; /* standard list */ LIST *vl; /* vertex-oriented list */ ADJMAT *am; /* adjacency matrix */ ADJLIST *al; /* adjacency list */ prgname = argv[0]; /* note program name for error msgs. */ if (scanf("%d%d", &vtcnt, &edcnt) != 2) error(E_PARSE); /* read number of vertices and edges */ sl = lst_create(2 +edcnt *2); /* create a standard list */ if (!sl) error(E_NOMEM); /* of appropriate size */ sl_addvert(sl, vtcnt); /* add `vtcnt' vertices */ while (--edcnt >= 0) { /* traverse edge descriptions */ if (scanf("%d%d", &i, &j) != 2) error(E_PARSE); /* read vertex ids of next edge */ sl_addedge(sl, i, j); /* and add this edge */ } /* to the standard list */ printf("standard list:\n"); /* to check the scanning done, */ lst_show(sl); /* print the standard list */ /* --- representation conversions --- */ printf("\nstandard list -> vertex-oriented list:\n"); vl = vl_from_sl(sl); /* create a vertex-oriented list */ if (!vl) error(E_NOMEM); /* from the standard list */ lst_show(vl); /* print the vertex-oriented list */ printf("\nstandard list -> adjacency matrix:\n"); am = am_from_sl(sl); /* create an adjacency matrix */ if (!am) error(E_NOMEM); /* from the standard list */ am_show(am); /* print the adjacency matrix */ printf("\nstandard list -> adjacency list:\n"); al = al_from_sl(sl); /* create an adjacency list */ if (!al) error(E_NOMEM); /* from the standard list */ al_show(al); /* print the adjacency list */ printf("\nvertex-oriented list -> standard list:\n"); lst_delete(sl); /* delete the standard list */ sl = sl_from_vl(vl); /* create a standard list */ if (!sl) error(E_NOMEM); /* from the vertex-oriented list */ lst_show(sl); /* print the standard list */ printf("\nvertex-oriented list -> adjacency matrix:\n"); am_delete(am); /* delete the adjacency matrix */ am = am_from_vl(vl); /* create an adjacency matrix */ if (!am) error(E_NOMEM); /* from the vertex-oriented list */ am_show(am); /* print the adjacency matrix */ printf("\nvertex-oriented list -> adjacency list:\n"); al_delete(al); /* delete the adjacency list */ al = al_from_vl(vl); /* create an adjacency list */ if (!al) error(E_NOMEM); /* from the vertex-oriented list */ al_show(al); /* print the adjacency list */ printf("\nadjacency matrix -> standard list:\n"); lst_delete(sl); /* delete the standard list */ sl = sl_from_am(am); /* create a standard list */ if (!sl) error(E_NOMEM); /* from the adjaceny matrix */ lst_show(sl); /* print the standard list */ printf("\nadjacency matrix -> vertex-oriented list:\n"); lst_delete(vl); /* delete the vertex-oriented list */ vl = vl_from_am(am); /* create a vertex-oriented list */ if (!vl) error(E_NOMEM); /* from the adjaceny matrix */ lst_show(vl); /* print the vertex-oriented list */ printf("\nadjacency matrix -> adjacency list:\n"); al_delete(al); /* delete the adjacency list */ al = al_from_am(am); /* create an adjacency list */ if (!al) error(E_NOMEM); /* from the adjacency matrix */ al_show(al); /* print the adjacency list */ printf("\nadjacency list -> standard list:\n"); lst_delete(sl); /* delete the standard list */ sl = sl_from_al(al); /* create a standard list */ if (!sl) error(E_NOMEM); /* from the adjacency list */ lst_show(sl); /* print the standard list */ printf("\nadjacency list -> vertex-oriented list:\n"); lst_delete(vl); /* delete the vertex-oriented list */ vl = vl_from_al(al); /* create a vertex-oriented list */ if (!vl) error(E_NOMEM); /* from the adjacency list */ lst_show(vl); /* print the vertex-oriented list */ printf("\nadjacency list -> adjacency matrix:\n"); am_delete(am); /* delete the adjacency matrix */ am = am_from_al(al); /* create an adjacency matrix */ if (!am) error(E_NOMEM); /* from the adjacency list */ am_show(am); /* print the adjacency matrix */ /* --- topological sorting --- */ printf("\ntopologically sorted graphs:\n"); printf("\nstandard list\n"); i = sl_topsort(sl); /* sort graph topologically */ if (i != 0) error(i); /* using a standard list */ lst_show(sl); /* show sorted graph */ printf("\nvertex-oriented list\n"); i = vl_topsort(vl); /* sort graph topologically */ if (i != 0) error(i); /* using a vertex-oriented list */ lst_show(vl); /* show sorted graph */ printf("\nadjacency matrix\n"); i = am_topsort(am); /* sort graph topologically */ if (i != 0) error(i); /* using an adjacency list */ am_show(am); /* show sorted graph */ printf("\nadjacency list\n"); i = al_topsort(al); /* sort graph topologically */ if (i != 0) error(i); /* using an adjacency list */ al_show(al); /* show sorted graph */ /* --- clean up --- */ al_delete(al); /* delete the adjacency list */ am_delete(am); /* delete the adjacency matrix */ lst_delete(vl); /* delete the vertex-oriented list */ lst_delete(sl); /* delete the standard list */ return 0; /* return `ok' */ } /* main() */