Skip to content

Instantly share code, notes, and snippets.

@rustyrussell
Last active June 1, 2016 10:25
Show Gist options
  • Save rustyrussell/8c23259edd1530a6273757e406ac1233 to your computer and use it in GitHub Desktop.
Save rustyrussell/8c23259edd1530a6273757e406ac1233 to your computer and use it in GitHub Desktop.
#! /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
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment