TD X-Window numero 2: grapheIO.c

/*****************************************************************************\
*                                                                             *
* 			  mini-afficheur de graphes                           *
*                                                                             *
\*****************************************************************************/

#include <stdio.h>
#include "graphe.h"

#define BUFFER_LENGTH 10000
#include <string.h>

/*****************************************************************************\
* 				Lire le graphe                                *
\*****************************************************************************/
/* Syntaxe:
 * Une entite par ligne, chaque champ separe par un blanc.
 * Syntaxe volontairement rigide pour simplifier le parsing
 * Title: T string
 * Node: N id x y label
 * Edge: E id from_id to_id
 */

Graph					/* le graphe lu */
ReadGraph(stream)
    FILE *stream;			/* fichier a lire */
{
    char buffer[BUFFER_LENGTH];
    int line_number = 0;
					/* init graph */
    Graph graph = (Graph) malloc(sizeof(struct _Graph));
    graph->title = "blank";
    graph->nodes = 0;
    graph->edges = 0;

    while (fgets(buffer, BUFFER_LENGTH, stream)) {
	line_number++;
	switch (buffer[0]) {
	    char s[BUFFER_LENGTH];
	    int x, y, from, to, id;

	case 'T':			/* title */
	    if (sscanf(buffer, "T %[^\n]", s) < 1)
		ReadGraphError(line_number, buffer);
	    graph->title = strdup(s);
	    break;

	case 'N':			/* node */
	    if (sscanf(buffer, "N %d %d %d %[^\n]", &id, &x, &y, s) < 4) {
		ReadGraphError(line_number, buffer);
	    } else {
					/* init node */
		Node node = (Node) malloc(sizeof(struct _Node));

		node->x = x;
		node->y = y;
		node->id = id;
		node->label = strdup(s);
					/* insert in graph */
		node->next = graph->nodes;
		graph->nodes = node;
		break;
	    }
	case 'E':			/* edge */
	    if (sscanf(buffer, "E %d %d %d", &id, &from, &to) < 3) {
		ReadGraphError(line_number, buffer);
	    } else {
					/* init edge */
		Edge edge = (Edge) malloc(sizeof(struct _Edge));

		edge->from_id = from;
		edge->to_id = to;
		edge->to = 0;
		edge->from = 0;
		edge->id = id;
					/* insert in graph */
		edge->next = graph->edges;
		graph->edges = edge;
		break;
	    }
		
	    break;

	default:			/* error */
	    ReadGraphError(line_number, buffer);
	}
    }
    FixReadGraph(graph);
    return graph;
}

ReadGraphError(n, s)
    int n;
    char *s;
{
    fprintf(stderr, "graph: bad line type at line %d: %s\n", n, s);
    exit(2);
}
	
/* FixReadGraph 
 * once the graph is read, update the nodes in edges from the IDs
 */

FixReadGraph(graph)
    Graph graph;
{
    Edge edge = graph->edges;
    
    while (edge) {
	Node node = graph->nodes;

	while (node) {
	    if (edge->from_id == node->id) {
		edge->from = node;
	    }
	    if (edge->to_id == node->id) {
		edge->to = node;
	    }
	    node = node->next;
	}
	if (edge->to == 0 || edge->from == 0) { /* not found */
	    fprintf(stderr, "Invalid node IDs: %d & %d for edge %d\n",
		    edge->from_id, edge->to_id, edge->id);
	    exit(1);
	}
	edge = edge->next;
    }
}

/*****************************************************************************\
* 				  PrintGraph                                  *
\*****************************************************************************/

void
PrintGraph(graph, stream)		/* prints a graph on a stream */
    Graph graph;			/* graph */
    FILE *stream;			/* stream */
{
    Node node;
    Edge edge;

					/* title */
    fprintf(stream, "T %s\n", graph->title);
					/* nodes */
    for (node = graph->nodes; node; node = node->next) {
	fprintf(stream, "N %d %d %d %s\n",
		node->id, node->x, node->y, node->label);
    }
					/* edges */
    for (edge = graph->edges; edge; edge = edge->next) {
	fprintf(stream, "N %d %d %d\n",
		edge->id, edge->from_id, edge->to_id);
    }
}

/*****************************************************************************\
* 				freeing graph                                 *
\*****************************************************************************/

FreeEdges(edge)
    Edge edge;
{
    while (edge) {
	Edge next = edge->next;
	free(edge);
	edge = next;
    }
}

FreeNodes(node)
    Node node;
{
    while (node) {
	Node next = node->next;
	free(node);
	node = next;
    }
}

FreeGraph(graph)
    Graph graph;
{
    FreeEdges(graph->edges);
    FreeNodes(graph->nodes);
    free(graph);
}

/*****************************************************************************\
* 				list of edges                                 *
\*****************************************************************************/

/* retourne la liste des edges liees au node donne */
Edge
RelatedEdges(graph, node)
    Graph graph;
    Node node;
{
    Edge edges = graph->edges;
    Edge related_edges = 0;
    while (edges)
    {
	if (edges->from == node || edges->to == node) {
	    Edge edge = (Edge) malloc(sizeof(struct _Edge));
	    bcopy(edges, edge, sizeof(struct _Edge));
	    edge->next = related_edges;
	    related_edges = edge;
	}
	edges = edges->next;
    }
    return related_edges;
}