truncated-graph-test.sh

#! /bin/sh

test_run()
{
    if [ "`./truncated-graph-traversal \"$1\"`" = "$2" ]; then
	echo "$2"
    else
	./truncated-graph-traversal "$1" >&2
	echo Expected "$2" >&2
	exit 1
    fi
}

# Simple case:
test_run '0:1=1,2=3 1:2=1 2:' '0,1,2=2'

# Negative loop as much as we can:
test_run '0:1=1,2=-1 1:0=-2 2:' '0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,2=-10'

# Brute force this, baby!  Fully connected.
test_run '0:0=1,1=1,2=1,3=1,4=1,5=1 1:0=1,1=1,2=1,3=1,4=1,5=1 2:0=1,1=1,2=1,3=1,4=1,5=1 3:0=1,1=1,2=1,3=1,4=1,5=1 4:0=1,1=1,2=1,3=1,4=1,5=1 5:0=1,1=1,2=1,3=1,4=1,5=1' '0,5=1'

# Fives ways to each node, but later ones always better.  This never terminates :)
test_run '0:1=476837158203125,1=381469726562500,1=286102294921875,1=190734863281250,1=95367431640625,1=0, 1:2=95367431640625,2=76293945312500,2=57220458984375,2=38146972656250,2=19073486328125,2=0, 2:3=19073486328125,3=15258789062500,3=11444091796875,3=7629394531250,3=3814697265625,3=0, 3:4=3814697265625,4=3051757812500,4=2288818359375,4=1525878906250,4=762939453125,4=0, 4:5=762939453125,5=610351562500,5=457763671875,5=305175781250,5=152587890625,5=0, 5:6=152587890625,6=122070312500,6=91552734375,6=61035156250,6=30517578125,6=0, 6:7=30517578125,7=24414062500,7=18310546875,7=12207031250,7=6103515625,7=0, 7:8=6103515625,8=4882812500,8=3662109375,8=2441406250,8=1220703125,8=0, 8:9=1220703125,9=976562500,9=732421875,9=488281250,9=244140625,9=0, 9:10=244140625,10=195312500,10=146484375,10=97656250,10=48828125,10=0, 10:11=48828125,11=39062500,11=29296875,11=19531250,11=9765625,11=0, 11:12=9765625,12=7812500,12=5859375,12=3906250,12=1953125,12=0, 12:13=1953125,13=1562500,13=1171875,13=781250,13=390625,13=0, 13:14=390625,14=312500,14=234375,14=156250,14=78125,14=0, 14:15=78125,15=62500,15=46875,15=31250,15=15625,15=0, 15:16=15625,16=12500,16=9375,16=6250,16=3125,16=0, 16:17=3125,17=2500,17=1875,17=1250,17=625,17=0, 17:18=625,18=500,18=375,18=250,18=125,18=0, 18:19=125,19=100,19=75,19=50,19=25,19=0, 19:20=25,20=20,20=15,20=10,20=5,20=0, 20:' 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20=0

echo Success

truncated-graph-traversal.c

#include <assert.h>
#include <stdint.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <ctype.h>

/* We can't use any paths longer than this, no matter how cheap. */
#define MAX_HOPS 20

struct edge {
	unsigned dst;
	int cost;
};

struct vertex {
	/* Cost for each path length. */
	int cost[MAX_HOPS+1];
	int from[MAX_HOPS+1];

	unsigned num_edges;
	struct edge *edge;
};

static void add_edge(struct vertex *v, unsigned dst, int cost)
{
	v->edge = realloc(v->edge, sizeof(struct edge *) * (v->num_edges+1));
	v->edge[v->num_edges].dst = dst;
	v->edge[v->num_edges].cost = cost;
	v->num_edges++;
}

static struct vertex *make_graph(const char *str, size_t *n)
{
	struct vertex *v = calloc(sizeof(struct vertex), 100);

	*n = 0;
	while (*str) {
		char *endp;
		size_t i;

		if (*n == 100)
			errx(1, "Too many vertices");
		if (strtol(str, &endp, 10) != *n)
			errx(1, "Expected %zu not '%s'", *n, str);
		if (*endp != ':')
			errx(1, "Expected : not '%s'", endp);
		str = endp+1;
		while (isdigit(*str)) {
			size_t e = strtol(str, &endp, 10);
			if (*endp != '=')
				errx(1, "Expected = not '%s'", endp);
			str = endp+1;
			add_edge(&v[*n], e, strtol(str, &endp, 10));
			str = endp;
			if (*str == ',')
				str++;
		}
		for (i = 0; i < MAX_HOPS+1; i++) {
			v[*n].cost[i] = INT_MAX;
			v[*n].from[i] = -1;
		}
		(*n)++;

		if (isspace(*str))
			str++;

	}
	return v;
}

static void brute_force(struct vertex *v, size_t num_v,
			int64_t cost, size_t from,
			size_t src, size_t dst, size_t hop)
{
	size_t i;

	assert(src < num_v);
	assert(dst < num_v);

	if (hop > MAX_HOPS)
		return;

	/* If we could get here cheaper, *and* with fewer hops, stop. */
	for (i = 0; i <= hop; i++) {
		if (v[src].cost[i] <= cost)
			return;
	}

	v[src].cost[hop] = cost;
	v[src].from[hop] = from;
	for (i = 0; i < v[src].num_edges; i++)
		brute_force(v, num_v, cost+v[src].edge[i].cost, src,
			    v[src].edge[i].dst, dst, hop+1);
}

static void dump_path(struct vertex *v, size_t num_v, size_t n, size_t hop)
{
	if (hop == 0) {
		printf("%zu", n);
		return;
	}
	dump_path(v, num_v, v[n].from[hop], hop-1);
	printf(",%zu", n);
}
		
int main(int argc, char *argv[])
{
	size_t i, n, best;
	struct vertex *v;

	v = make_graph(argv[1], &n);
	brute_force(v, n, 0, 0, 0, n-1, 0);

	best = 0;
	for (i = 1; i < MAX_HOPS+1; i++) {
		if (v[n-1].cost[i] < v[n-1].cost[best])
			best = i;
	}
	if (v[n-1].cost[best] == INT_MAX) {
		printf("No path from 0 to %zu\n", n-1);
		return 1;
	}
	dump_path(v, n, n-1, best);
	printf("=%i\n", v[n-1].cost[best]);
	return 0;
}