gistfile1.c

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define	MAXREV		32
#define	MAXUSER		64
#define MAXEDGE		100
#define MAXLINE		2048 * 1024

#define	unless(a)	if (!(a))
#define	IS_MERGE(x)	(x.inedges[1] != 0)

/* flags */
#define	F_DELTA		0x00000001 /* D */
#define	F_TAG		0x00000002 /* R */
/* colors */
#define	WHITE		0x00000004
#define	GRAY		0x00000008
#define	BLACK		0x00000010

#define	SET_COLOR(n, color)	{			\
	graph->nodes[(n)].flags &= ~(WHITE|GRAY|BLACK);	\
	graph->nodes[(n)].flags |= (color);		\
    }
#define	ADD_COLOR(n, color)	{		\
	graph->nodes[(n)].flags |= (color);	\
    }
#define	CLEAR_COLOR(n, color)	{		\
	graph->nodes[(n)].flags &= ~(color);	\
    }
#define	HAS_COLOR(n, color)	(graph->nodes[(n)].flags & (color))

#define	PARTITION(n)	(graph->nodes[(n)].partition)

/* Adjacency List */
#define	ADJ(v, i)		(graph->nodes[(v)].outedges[(i)])
/* Reverset Adjacency List */
#define	RADJ(v, i)		(graph->nodes[(v)].inedges[(i)])

typedef struct node node;
struct node {
    int	flags;			/* D == delta, R == tag */
    int	partition:2;		/* bipartite testing */
    char	*rev;			/* rev */
    char	*user;			/* user name */
    char	*datetime;		/* YY/MM/DD hh:mm:ss */
    size_t	offset;			/* Where to find more info */
    int	inedges[2];		/* Incident edges, typically
				 * (parent, mparent) or (parent, nil)
				 */
    int	outedges[MAXEDGE+1];	/* Adjacency list */
};

typedef struct graph graph;
struct graph {
    node	*nodes;			/* list of nodes */
    int	num_nodes;		/* number of nodes */
    int	num_edges;		/* number of edges */
    int	num_merges;		/* number of merge nodes */
    int	max_outedges;		/* maximum outedges for a single node */
    int	size;			/* size in bytes of nodes */
};

/* queue algorithms */
typedef struct queue queue;
struct	queue {
    int	capacity;
    int	head;
    int	tail;
    int	size;
    int	*data;
};

queue *
queue_new(int size)
{
    queue	*q;

    q = calloc(1, sizeof(queue));
    q->data = calloc(size, sizeof(int));
    q->capacity = size;
    q->size = 0;
    q->head = 1;
    q->tail = 0;
    return q;
}

int
queue_succ(queue *q, int v)
{
    if (++v == q->capacity) v = 0;
    return v;
}

void
enqueue(queue *q, int v)
{
    assert(!queue_full(q));
    q->size++;
    q->tail = queue_succ(q, q->tail);
    q->data[q->tail] = v;
}

void
dequeue(queue *q)
{
    assert(!queue_empty(q));
    q->size--;
    q->head = queue_succ(q, q->head);
}

int
queue_empty(queue *q)
{
    return q->size == 0;
}

int
queue_full(queue *q)
{
    return q->size == q->capacity;
}

int
queue_head(queue *q)
{
    assert(!queue_empty(q));
    return q->data[q->head];
}

void
queue_free(queue *q)
{
    free(q->data);
    free(q);
}

/* Useful macros for building the graph */
#define	bail(msg)		{			\
	fprintf(stderr, "graph(%d): %s - %s\n",		\
		__LINE__, msg, buf);			\
	if (graph && graph->nodes) free(graph->nodes);	\
	if (graph) free(graph);				\
	return (0);					\
    }							\

#define addEdge(from, to)	{				\
	for (i = 0; i < MAXEDGE && ADJ(from, i) != 0; i++);	\
	if (i >= MAXEDGE) {					\
	    fprintf(stderr, "Too many outedges\n");		\
	    free(graph->nodes);					\
	    free(graph);					\
	    return (0);						\
	}							\
	ADJ(from, i) = to;					\
	for (i = 0; i < 2 && RADJ(to, i) != 0; i++);		\
	if (i >= MAXEDGE) {					\
	    fprintf(stderr, "Too many inedges (merges)\n");	\
	    free(graph->nodes);					\
	    free(graph);					\
	    return (0);						\
	}							\
	RADJ(to, i) = from;					\
	graph->num_edges++;					\
    }								\


graph *
build_graph(char *file)
{
    FILE	*f;
    char	*rev, *datetime, *user, *serial, *pserial, *mserial;
    int	maxnode, i, parent, merge;
    graph	*graph = 0;
    char	buf[MAXLINE];

    unless (f = fopen(file, "r")) return (0);
    unless(graph = calloc(1, sizeof(graph))) {
	bail("not enough memory");
    }
    graph->num_nodes = 0;
    while (fgets(buf, sizeof(buf), f)) {
	int	n;

	unless(buf[0] == '\001') bail("parse error");
	if (buf[1] == 'H') {
	    /* skip checksum */
	    continue;
	} else if (buf[1] == 's') {
	    fgets(buf, sizeof(buf), f);
	    unless(buf[0] == '\001' && buf[1] == 'd') {
		bail("parse error");
	    }
	    rev = buf + 5; /* skip ^A d D */
	    datetime = strchr(rev, ' ');
	    *datetime++ = 0;
	    user = strchr(datetime, ' '); /* MM/DD/YY */
	    user = strchr(user+1, ' '); /* HH:MM:SS */
	    *user++ = 0;
	    serial = strchr(user, ' ');
	    *serial++ = 0;
	    pserial = strchr(serial, ' ');
	    *pserial++ = 0;
	    *strchr(pserial, '\n') = 0;
	    n = atoi(serial);
	    if (graph->nodes == 0) {
		graph->nodes = calloc(n+1,sizeof(node));
		graph->num_nodes = n;
		graph->size = (n+1) * sizeof(node);
	    }
	    graph->nodes[n].flags = buf[3]=='D' ? F_DELTA : F_TAG;
	    graph->nodes[n].flags |= WHITE;
	    graph->nodes[n].partition = 0;
	    graph->nodes[n].rev = strdup(rev);
	    graph->nodes[n].user = strdup(user);
	    graph->nodes[n].datetime = strdup(datetime);
	    graph->nodes[n].offset = ftell(f);
	    parent = atoi(pserial);

	    if (parent) addEdge(parent, n);
	    while (fgets(buf, sizeof(buf), f)) {
		unless(buf[0] == '\001') bail("parse error");
		if (buf[1] == 'e' && buf[2] == '\n') {
		    break;
		} else if (buf[1] == 'c' && buf[2] == 'M') {
		    merge = atoi(buf+3);
		    addEdge(merge, n);
		    graph->num_merges++;
		}
	    }
	} else if (buf[1] == 'u' && buf[2] == '\n') {
	    /* we're done */
	    break;
	} else bail("parse error");
    }
    fclose(f);
    return (graph);
}

void
free_graph(graph *graph)
{
    free(graph->nodes);
    free(graph);
}

void
print_node(graph *graph, int serial)
{
    int	i;
    node	n = graph->nodes[serial];

    printf("|%d|%c|%s|%s|%s|%d| -> ( ", serial,
	   n.flags == F_DELTA ? 'D' :  n.flags == F_TAG ? 'R' : '?', n.rev,
	   n.user, n.datetime, n.offset);
/*	printf("|%d|%c|%d| -> ( ", serial, */
/*	    n.flags == F_DELTA ? 'D' :  n.flags == F_TAG ? 'R' : '?', n.offset); */

    for (i = 0; i < MAXEDGE && n.outedges[i] != 0; i++) {
	printf("%d ", n.outedges[i]);
    }
    printf(") | <- ( ");
    for (i = 0; i < 2 && n.inedges[i] != 0; i++) {
	printf("%d ", n.inedges[i]);
    }
    printf(")\n");
}

void
print_graph(graph *graph, int node)
{
    int	i;

    if (node == 0) return;
    for (i = node; i > 0; i--) {
	print_node(graph, i);
    }
}

void
print_tips(graph *graph)
{
    int	i;

    for (i = graph->num_nodes; i > 0; i--) {
	if (graph->nodes[i].outedges[0] == 0 &&
	    graph->nodes[i].flags != 0) {
	    print_node(graph, i);
	}
    }
}

void
print_roots(graph *graph)
{
    int	i;

    for (i = graph->num_nodes; i > 0; i--) {
	if (graph->nodes[i].inedges[0] == 0 &&
	    graph->nodes[i].flags != 0) {
	    print_node(graph, i);
	}
    }
}

int
bipartite(graph *graph, int s)
{
    queue	*q;
    int	u, v, j;

    q = queue_new(graph->num_nodes);
    assert(q);
    SET_COLOR(s, GRAY);
    PARTITION(s) = 1;
    enqueue(q, s);
    while (!queue_empty(q)) {
	u = queue_head(q);
	for (j = 0; (v = ADJ(u, j)) && (j < MAXEDGE); j++) {
	    if (PARTITION(u) == PARTITION(v))
		return 0;
	    else
		if (HAS_COLOR(v, WHITE)) {
		    SET_COLOR(v, GRAY);
		    PARTITION(v) = 3 - PARTITION(u);
		    enqueue(q, v);
		}
	}
	dequeue(q);
	SET_COLOR(u, BLACK);
    }
    return 1;
}

int
main(int ac, char **av)
{
    graph	*graph;

    if (av[1] == 0) {
	fprintf(stderr, "barf\n");
	exit(1);
    }
    unless (graph = build_graph(av[1])) {
	fprintf(stderr, "Could not build graph\n");
	return (1);
    }
/*	print_graph(graph, graph->num_nodes); */
    if (bipartite(graph, 0))
	printf("Graph is bipartite\n");
    else
	printf("Graph is not bipartite\n");
    fprintf(stderr,
	    "Built graph has %d nodes, %d edges, %d merge nodes (%f)\n"
	    "%d bytes of memory (sizeof(node) == %d)\n",
	    graph->num_nodes, graph->num_edges, graph->num_merges,
	    (double)(graph->num_merges)/(graph->num_nodes),
	    graph->size, sizeof(node));
    /* Weird, free is failing? */
/*	free_graph(graph); */
    return (0);
}

/* Local Variables:
 * c-indetation-style: cc-mode
 * End:
 */