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;
}