/* SWIG Graph Example
*
* Dave Beazley
*
* This code implements a few simple graph algorithms.
* Our data structures are basically as follows :
*
* 1. A linked list of nodes (containing all of the current
* nodes).
* 2. Each node has an adjacency list which is a linked list
* of all of the edges to other nodes.
*/
#include <stdio.h>
#include "graph.h"
int V = 0; /* Number of nodes */
Node *head; /* Linked list of nodes */
Node *z;
AdjList *az; /* Terminator of the adjaceny lists */
/* ------------------------------------------------------------
void init_graph()
Initializes the graph code by clearing the linked list of nodes
------------------------------------------------------------ */
void init_graph() {
Node *n, *n1;
AdjList *l, *l1;
int i;
V = 0;
if (head) {
n = head->next_node;
while (n != z) {
l = n->adj;
while (l != az) {
l1 = l->next;
free(l);
l = l1;
}
n1 = n->next_node;
free(n);
n = n1;
}
}
head = (Node *) malloc(sizeof(Node));
z = (Node *) malloc(sizeof(Node));
z->next_node = z;
head->next_node = z;
az = (AdjList *) malloc(sizeof(AdjList));
az->next = az;
az->v = 0;
}
/* --------------------------------------------------------
Node *new_node()
Creates a new node. This node is added onto the linked
list of nodes. Returns a pointer to the new node.
-------------------------------------------------------- */
Node *new_node() {
Node *t;
t = (Node *) malloc(sizeof(Node));
t->num = V++;
t->adj = az;
t->oldadj = az;
t->next_node = head->next_node;
head->next_node = t;
return t;
}
/* --------------------------------------------------------
void AddLink(Node *v1, Node *v2)
Adds a directional link between node v1 and v2. This
just adds node v2 to node v1's adjacency list. Also checks
for duplication.
--------------------------------------------------------- */
void AddLink(Node *v1, Node *v2) {
AdjList *l;
/* First make sure we don't already have this link */
l = v1->adj;
while (l != az) {
if ((Node *) l->v == v2) return;
l = l->next;
}
if (v1 == v2) return;
/* Create a new adjacency entry */
l = (AdjList *) malloc(sizeof(AdjList));
l->v = (Node *) v2;
l->next = v1->adj;
v1->adj = l;
}
/* -----------------------------------------------------------
void FreeAdjList(AdjList *l)
Frees the memory used by a adjacency list
----------------------------------------------------------- */
void FreeAdjList(AdjList *l) {
AdjList *l1;
while (l != az) {
l1 = l->next;
free(l);
l = l1;
}
}
/* -----------------------------------------------------------
PrintNodes()
A debugging function for printing out all of the nodes and
and their adjacency lists.
------------------------------------------------------------ */
void PrintNodes() {
Node *n, *v;
AdjList *l;
/* Print out all of the nodes */
n = head->next_node;
while (n != z) {
printf("Node %d : ", n->num);
l = n->adj;
while (l != az) {
v = (Node *) l->v;
printf("%d ", v->num);
l = l->next;
}
printf("\n");
n = n->next_node;
}
}
/* -------------------------------------------------------------
find_Connected(Node *n)
A function that finds all of the nodes connected to node N.
Sets the node->visit flag to 1 for each node that is connected
to n. You'll probably want to set the node->visit flags to 0
before calling this the first time.
------------------------------------------------------------- */
void find_Connected(Node *n) {
AdjList *l;
Node *v;
if (n->visit) return; /* Return if already seen this node */
n->visit = 1;
/* Walk down my adjacency list and look at those nodes */
l = n->adj;
while (l != az) {
v = (Node *) l->v;
find_Connected(v);
l = l->next;
}
}
/* --------------------------------------------------------------
Connected(Node *n)
Finds all of the nodes connected to node n. Basically this is
just the initialization code that sets all of the n->visit bytes
to 0 and calls find_Connected.
--------------------------------------------------------------- */
void Connected(Node *n) {
Node *v;
v = head->next_node;
while (v != z) {
v->visit = 0;
v = v->next_node;
}
find_Connected(n);
}
/* --------------------------------------------------------------
Closure_Step()
This function computes one step of a transitive closure
algorithm by adding more links. Basically, whereever
we have a link n1 --> n2 --> n3, this function will add
the link n1 --> n3. Call repeatedly to compute the
transitive closure.
Note : this is pretty ugly due to our choice of data structures
--------------------------------------------------------------- */
void Closure_Step() {
Node *v,*v1,*n;
AdjList *l, *l1, *l2;
int found;
n = head->next_node;
/* First save old adjacency lists and clear new ones */
while (n != z) {
n->oldadj = n->adj;
n->adj = az;
n = n->next_node;
}
/* Now go figure out who my new nodes ares */
n = head->next_node;
while (n != z) {
/* Go down my adjacency list and add arcs */
l = n->oldadj;
while (l != az) { /* Walk down my adjacency list */
v = (Node *) l->v;
l1 = v->oldadj; /* Find out who's connected to my neighbors */
while (l1 != az) {
v1 = (Node *) l1->v;
l2 = n->oldadj;
found = 0;
while (l2 != az) {
if ((Node *) l2->v == v1) found = 1;
l2 = l2->next;
}
if ((!found) && (n != v1))
AddLink(n,v1); /* Add an arc */
l1 = l1->next;
}
l = l->next;
}
n = n->next_node;
}
/* Now connect everything back up again */
n = head->next_node;
while (n != z) {
l = n->oldadj;
if (l != az) {
while (l->next != az) l = l->next;
l->next = n->adj;
n->adj = n->oldadj;
n->oldadj = az;
}
n = n->next_node;
}
}
/* ----------------------------------------------------------------
Shortest Path
The following few functions compute the shortest path between
two nodes. This is done by using a breadth-first search
algorithm. Thus, I also need to implement some sort of queuing
system as shown below
---------------------------------------------------------------- */
typedef struct q {
Node *n;
struct q *next;
struct q *prev;
} QNode;
QNode *qhead;
QNode *qtail;
/* Put something on the queue */
void queue_put(Node *n) {
QNode *q;
if (!qhead) {
qhead = (QNode *) malloc(sizeof(QNode));
qtail = (QNode *) malloc(sizeof(QNode));
qhead->next = qtail;
qtail->next = qtail;
qhead->prev = qhead;
qtail->prev = qhead;
}
q = (QNode *) malloc(sizeof(QNode));
q->n = n;
q->next = qtail;
q->prev = qtail->prev;
q->prev->next = q;
qtail->prev = q;
}
/* Take something off the queue */
Node *queue_get() {
QNode *q;
Node *n;
q = qhead->next;
if (q == qtail) return NULL;
qhead->next = q->next;
q->next->prev = qhead;
n = q->n;
free(q);
return n;
}
/* -----------------------------------------------------------
AdjList *FindShort(Node *n1, Node *n2)
Finds the shortest path between node n1 and node n2.
Returns a linked list of nodes in the path. This can easily
be expressed using the AdjList structure already defined.
----------------------------------------------------------- */
AdjList *FindShort(Node *n1, Node *n2) {
Node *v, *v1;
AdjList *l;
AdjList *path;
v = head->next_node;
while (v != z) {
v->visit = 0;
v->oldadj = az;
v = v->next_node;
}
queue_put(n1);
n1->visit = 1;
while ((v = queue_get())) {
if (v == n2)
break;
else {
l = v->adj;
while (l != az) {
v1 = (Node *) l->v;
if (!v1->visit) {
queue_put(v1);
v1->visit = 1;
v1->oldadj = (AdjList *) malloc(sizeof(AdjList));
v1->oldadj->v = v;
v1->oldadj->next = az;
}
l = l->next;
}
}
}
/* Flush out queue */
while ((v1 = queue_get()));
/* If v is non-null, then we found something */
if (v) {
/* Backtrack through parents to trace out path */
path = (AdjList *) malloc(sizeof(AdjList));
path->next = az;
path->v = n2;
while (v != n1) {
v->oldadj->next = path;
path = v->oldadj;
v->visit = 1;
v1 = (Node *) (v->oldadj->v);
v->oldadj = az;
v = v1;
}
l = (AdjList *) malloc(sizeof(AdjList));
l->v = n1;
l->next = path;
} else {
l = 0;
}
/* Go through and clean up */
v = head->next_node;
while (v != z) {
if (v->oldadj != az) free(v->oldadj);
v = v->next_node;
}
/* Return the path */
return l;
}
syntax highlighted by Code2HTML, v. 0.9.1