From a2b0bb41876d956ca7abf123858ac45aea3c5898 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Tue, 6 Aug 2013 08:15:45 +0200 Subject: Discrete : wip-worktree-state --- ...works-only-if-sorted-by-val-or-weight-asc.patch | 38 ++ 01-knapsack/1-relaxation-what-to-do-with.patch | 143 +++++++ 01-knapsack/ks_dp | Bin 0 -> 8984 bytes 01-knapsack/ks_dp-ng.c | 69 ++++ 01-knapsack/ks_dp2.c | 436 +++++++++++++++++++++ 02-graph-coloring/CP-solver.rb | 229 +++++++++++ 02-graph-coloring/README | 15 + 02-graph-coloring/data/gc_4_1.dot | 10 + 02-graph-coloring/data/gc_4_1.png | Bin 0 -> 6074 bytes 02-graph-coloring/draw | 7 + 02-graph-coloring/gc_20_1.png | Bin 0 -> 50887 bytes 11 files changed, 947 insertions(+) create mode 100644 01-knapsack/0-works-only-if-sorted-by-val-or-weight-asc.patch create mode 100644 01-knapsack/1-relaxation-what-to-do-with.patch create mode 100755 01-knapsack/ks_dp create mode 100644 01-knapsack/ks_dp2.c create mode 100755 02-graph-coloring/CP-solver.rb create mode 100644 02-graph-coloring/README create mode 100644 02-graph-coloring/data/gc_4_1.dot create mode 100644 02-graph-coloring/data/gc_4_1.png create mode 100755 02-graph-coloring/draw create mode 100644 02-graph-coloring/gc_20_1.png diff --git a/01-knapsack/0-works-only-if-sorted-by-val-or-weight-asc.patch b/01-knapsack/0-works-only-if-sorted-by-val-or-weight-asc.patch new file mode 100644 index 0000000..bb4a6e1 --- /dev/null +++ b/01-knapsack/0-works-only-if-sorted-by-val-or-weight-asc.patch @@ -0,0 +1,38 @@ +diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c +index 7830651..106328b 100644 +--- a/01-knapsack/ks_dp-ng.c ++++ b/01-knapsack/ks_dp-ng.c +@@ -120,20 +120,32 @@ static void solve(Solver* solver) + + // this computes the top-left bottom-right diagonal, + // values above this don't need to be computed ++ j = k; + min_c -= w; + lower_bound = (k - min_c); + if (lower_bound < w) + lower_bound = w; +- for (j = k; j >= lower_bound; j--, data--, up_left--) ++ ++ while (j >= lower_bound) + { + counter++; ++ /* printf(" % 4d\n", j); */ + + if (data->v < (v + up_left->v)) + { + data->i = i; + data->v = v + up_left->v; + data->w = w + up_left->w; ++ if (j == k) { ++ j -= w; ++ data -= w; ++ up_left -= w; ++ continue; ++ } + } ++ j--; ++ data--; ++ up_left--; + } + + if (debug > 2) diff --git a/01-knapsack/1-relaxation-what-to-do-with.patch b/01-knapsack/1-relaxation-what-to-do-with.patch new file mode 100644 index 0000000..cbc59e3 --- /dev/null +++ b/01-knapsack/1-relaxation-what-to-do-with.patch @@ -0,0 +1,143 @@ +diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c +index 7830651..ddb0d04 100644 +--- a/01-knapsack/ks_dp-ng.c ++++ b/01-knapsack/ks_dp-ng.c +@@ -7,12 +7,14 @@ + + #define NONE -1 + ++enum { RELAX = 0, NO_RELAX }; + enum { SORT_DESC = 0, SORT_ASC }; + enum { UNSORTED = 0, SORT_WR, SORT_VR, SORT_RW, SORT_RV}; + + static int debug; + static int sort; + static int sort_order; ++static int relax; + + typedef struct _InputItem + { +@@ -25,6 +27,7 @@ typedef struct _SolverItem { + int i; /* index of the selected item */ + int v; /* cumulated value */ + int w; /* cumulated weight */ ++ float r; /* linear relaxation best value */ + } SolverItem; + + typedef struct _Solver +@@ -87,11 +90,39 @@ item_cmp(const void *p1, const void *p2) + return 0; + } + ++static inline float relax_item(Solver* solver, SolverItem* data, int start) ++{ ++ int w; ++ int i; ++ float relax; ++ const InputItem *item; ++ ++ w = data->w; ++ relax= data->v; ++ item = &solver->items[start]; ++ for (i = start; i < solver->n; i++, item++) ++ { ++ if ((w + item->w) <= solver->k) ++ { ++ w += item->w; ++ relax += item->v; ++ } ++ else ++ { ++ relax += (item->v * ((solver->k - w) / (float)item->w)); ++ break; ++ } ++ } ++ ++ return relax; ++} ++ + static void solve(Solver* solver) + { + int n, k; + int v, w; + int i, j; ++ float r; + int min_c, lower_bound; + const InputItem *item; + SolverItem *data; +@@ -105,7 +136,16 @@ static void solve(Solver* solver) + + if (debug > 2) + { +- printf("\nformat V(i,W)\n"); ++ printf("\nformat V(i,W,r)\n"); ++ } ++ ++ /* RELAXATION */ ++ if (relax == RELAX) ++ { ++ data = solver->column; ++ r = relax_item(solver, data, 0); ++ for (j = 0; j <= k; j++, data++) ++ data->r = r; + } + + /* SOLVE */ +@@ -134,6 +174,12 @@ static void solve(Solver* solver) + data->v = v + up_left->v; + data->w = w + up_left->w; + } ++ ++ /* RELAXTION must be cached */ ++ if (relax == RELAX) ++ { ++ data->r = relax_item(solver, data, (i + 1)); ++ } + } + + if (debug > 2) +@@ -141,8 +187,8 @@ static void solve(Solver* solver) + printf("i=%d; j=k; j<=%d:\n", i, lower_bound); + data = solver->column; + for (j = 0; j <= k; j++, data++) +- printf(" %d : % 4d(% 2d % 2d)\n", +- j, data->v, data->i, data->w); ++ printf(" %d : % 4d(% 2d % 2d %.1f)\n", ++ j, data->v, data->i, data->w, data->r); + printf("\n"); + } + } +@@ -152,8 +198,8 @@ static void solve(Solver* solver) + printf("i=%d:\n", solver->n - 1); + data = solver->column; + for (j = 0; j <= k; j++, data++) +- printf(" % 4d(% 2d % 2d)\n", +- data->v, data->i, data->w); ++ printf(" % 4d(% 2d % 2d %.1f)\n", ++ data->v, data->i, data->w, data->r); + } + + if (debug > 0) +@@ -194,10 +240,11 @@ int main(int argc, char** argv, char** env) + InputItem *item; + + debug = 0; ++ relax = NO_RELAX; + sort = UNSORTED; + sort_order = SORT_DESC; + excpected_value = NONE; +- while ((opt = getopt(argc, argv, "d:e:s:S")) != -1) { ++ while ((opt = getopt(argc, argv, "d:e:s:SR")) != -1) { + switch (opt) { + case 'd': + debug = atoi(optarg); +@@ -211,6 +258,9 @@ int main(int argc, char** argv, char** env) + case 'S': + sort_order = SORT_ASC; + break; ++ case 'R': ++ relax = RELAX; ++ break; + default: /* '?' */ + fprintf(stderr, "Usage: %s [falgs] input\n", + argv[0]); diff --git a/01-knapsack/ks_dp b/01-knapsack/ks_dp new file mode 100755 index 0000000..0267f00 Binary files /dev/null and b/01-knapsack/ks_dp differ diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c index 7830651..282cecf 100644 --- a/01-knapsack/ks_dp-ng.c +++ b/01-knapsack/ks_dp-ng.c @@ -160,6 +160,75 @@ static void solve(Solver* solver) printf("loops count: %u\n", counter); } +static void reset_output(char *output, int bits) +{ + char *ch; + char *end; + + end = output + bits; + for (ch = output; ch < end; ) + { + (*ch++) = '0'; + (*ch++) = ' '; + } + ch--; + *ch = '\0'; +} + +static int print(Solver* solver) +{ + int ret; + int v, w; + char *output; + const Item *item; + const SolverData *data; + + output = calloc((solver->n * 2), sizeof(char)); + if (!output) + { + fprintf(stderr, "ERROR: output calloc\n"); + return EXIT_FAILURE; + } + reset_output(output, (solver->n * 2)); + + data = solver->column + solver->k; + printf("%d %d\n", data->v, 0); + + v = 0; + w = 0; + /* for (data = solver->column + solver->k; data->i != -1 ; data -= item->w) */ + for (data = solver->column + solver->k; data->s != -1 ; data -= item->w) + { + /* item = &solver->items[data->i]; */ + item = &solver->items[data->s]; + output[(item->i) * 2] = '1'; + if (debug > 1) + printf(" from % 6d - take % 4d (% 4d % 4d)\n", + data->v, item->i, item->v, item->w); + v += item->v; + w += item->w; + } + printf("%s\n", output); + + free(output); + + ret = EXIT_SUCCESS; + data = solver->column + solver->k; + if (v != data->v) + { + fprintf(stderr, "ERROR: value %d != %d\n", v, data->v); + ret = EXIT_FAILURE; + } + if (w > solver->k) + { + fprintf(stderr, "ERROR: weight %d > %d\n", w, solver->k); + ret = EXIT_FAILURE; + } + + return ret; + +} + static int check(Solver *solver, int excpected_value) { const SolverItem *data; diff --git a/01-knapsack/ks_dp2.c b/01-knapsack/ks_dp2.c new file mode 100644 index 0000000..a776f24 --- /dev/null +++ b/01-knapsack/ks_dp2.c @@ -0,0 +1,436 @@ +#include +#include +#include +#include +#include +#include + +enum { UNSORTED = 0, SORT_WR, SORT_VR, SORT_RW, SORT_RV}; +enum { DESC = 0, ASC }; +enum { NO_RELAX = 0, RELAX }; + +static int debug; +static int sort; +static int sort_order; +static int relax; + +typedef struct _Item +{ + int i; + int v; + int w; +} Item; + +typedef struct _SolverData { + int v; /* cumulated value */ + int w; /* cumulated weight */ + float r; /* relaxed max value */ + int i; /* index of the selected item */ +} SolverData; + +typedef struct _Solver +{ + int k; /* capacity */ + int n; /* items # */ + int sum_w; /* sum of weight of all items */ + Item *items; /* items */ + SolverData *column; /* solver column */ +} Solver; + +static int +item_cmp(const void *p1, const void *p2) +{ + int ret; + float r1, r2; + const Item *i1, *i2; + + i1 = (const Item *) p1; + i2 = (const Item *) p2; + + ret = ((sort_order == ASC) ? 1 : -1); + + if (sort == SORT_WR) + { + if (i1->w > i2->w) return ret; + if (i1->w < i2->w) return -ret; + } + else if (sort == SORT_VR) + { + if (i1->v > i2->v) return ret; + if (i1->v < i2->v) return -ret; + } + else // SORT_RW | SORT_RV + { + r1 = i1->v / (float)i1->w; + r2 = i2->v / (float)i2->w; + if (r1 > r2) return ret; + if (r1 < r2) return -ret; + } + + if (sort == SORT_RW) + { + if (i1->w > i2->w) return ret; + if (i1->w < i2->w) return -ret; + } + else if (sort == SORT_RV) + { + if (i1->v > i2->v) return ret; + if (i1->v < i2->v) return -ret; + } + else // SORT_WR | SORT_VR + { + r1 = i1->v / (float)i1->w; + r2 = i2->v / (float)i2->w; + if (r1 > r2) return ret; + if (r1 < r2) return -ret; + } + + return 0; +} + +static void reset_output(char *output, int bits) +{ + char *ch; + char *end; + + end = output + bits; + for (ch = output; ch < end; ) + { + (*ch++) = '0'; + (*ch++) = ' '; + } + ch--; + *ch = '\0'; +} + +static int print(Solver* solver) +{ + int ret; + int v, w; + char *output; + const Item *item; + const SolverData *data; + + output = calloc((solver->n * 2), sizeof(char)); + if (!output) + { + fprintf(stderr, "ERROR: output calloc\n"); + return EXIT_FAILURE; + } + reset_output(output, (solver->n * 2)); + + data = solver->column + solver->k; + printf("%d %d\n", data->v, 0); + + v = 0; + w = 0; + for (data = solver->column + solver->k; data->i != -1 ; data -= item->w) + { + item = &solver->items[data->i]; + output[(item->i) * 2] = '1'; + if (debug > 1) + printf(" from % 6d - take % 4d (% 4d % 4d)\n", + data->v, item->i, item->v, item->w); + v += item->v; + w += item->w; + } + printf("%s\n", output); + + free(output); + + ret = EXIT_SUCCESS; + data = solver->column + solver->k; + if (v != data->v) + { + fprintf(stderr, "ERROR: value %d != %d\n", v, data->v); + ret = EXIT_FAILURE; + } + if (w > solver->k) + { + fprintf(stderr, "ERROR: weight %d > %d\n", w, solver->k); + ret = EXIT_FAILURE; + } + + return ret; + +} + +static inline void relax_item(Solver* solver, SolverData* data, int start) +{ + int w; + int i; + const Item *item; + + w = data->w; + data->r = data->v; + item = &solver->items[start]; + for (i = start; i < solver->n; i++, item++) + { + if ((w + item->w) <= solver->k) + { + w += item->w; + data->r += item->v; + } + else + { + data->r += (item->v * ((solver->k - w) / (float)item->w)); + break; + } + } +} + +static void solve(Solver* solver) +{ + int n, k; + int v, w; + int i, j; + int max_c, upper_bound; + const Item *item; + SolverData *data; + const SolverData *up_left; + + unsigned int counter; + + n = solver->n; + k = solver->k; + max_c = solver->sum_w; + + /* RELAXATION */ + if (relax == RELAX) + { + data = solver->column; + for (j = 0; j <= k; j++, data++) + relax_item(solver, data, 0); + } + + if (debug > 2) + { + printf("\ncurrent V(i,s,W,r)\n"); + } + + /* SOLVE */ + counter = 0; + item = solver->items; + for (i = 0; i < n; i++, item++) + { + v = item->v; + w = item->w; + data = NULL; + data = solver->column + solver->k; + up_left = solver->column + (solver->k - w); + + // this computes the top-left bottom-right diagonal, + // values above this don't need to be computed + max_c -= w; + upper_bound = (((k - max_c) > w) ? (k - max_c) : w ); + for (j = k; j >= upper_bound; j--, data--, up_left--) + { + // FIXME + /* if ((relax == RELAX) && (data->v == (int)data->r)) */ + /* if ((relax == RELAX) && (data->v <= (int)data->r)) */ + /* if ((relax == RELAX) && (data->v < (int)data->r)) */ + /* { */ + /* /1* fprintf(stderr,"RELAX\n"); *1/ */ + /* continue; */ + /* } */ + + counter++; + + if (data->v < (v + up_left->v)) + { + data->i = i; + data->v = v + up_left->v; + data->w = w + up_left->w; + /* if (j == k) */ + /* { */ + /* for (critical = data; critical->i != -1 ; */ + /* critical -= solver->items[data->i].w) */ + /* { */ + /* critical->c = critical->i; */ + /* } */ + /* print_vector(solver, i + 1, 0); */ + /* print_vector(solver, i + 1, 1); */ + /* } */ + } + + /* RELAXTION must be cached */ + if (relax == RELAX) + { + relax_item(solver, data, (i + 1)); + } + } + + if (debug > 2) + { + printf("i=%d; j=k; j<=%d:\n", i, upper_bound); + data = solver->column; + for (j = 0; j <= k; j++, data++) + printf(" % 4d(% 2d % 2d %.1f)\n", + data->v, data->i, data->w, data->r); + printf("\n"); + } + } + + if (debug > 0) + printf("loops count: %u\n", counter); + + if (debug == 2) + { + printf("i=%d:\n", solver->n - 1); + data = solver->column; + for (j = 0; j <= k; j++, data++) + printf(" % 4d(% 2d % 2d %.1f)\n", + data->v, data->i, data->w, data->r); + } +} + +int main(int argc, char** argv, char** env) +{ + FILE *fp; + + int opt; + int ret; + int i; + uint64_t dt; + struct timespec t0; + struct timespec t1; + + Solver solver; + Item *item; + + sort = UNSORTED; + sort_order = DESC; + relax = NO_RELAX; + debug = 0; + while ((opt = getopt(argc, argv, "d:s:SR")) != -1) { + switch (opt) { + case 's': + sort = atoi(optarg); + break; + case 'd': + debug = atoi(optarg); + break; + case 'S': + sort_order = ASC; + break; + case 'R': + relax = RELAX; + break; + default: /* '?' */ + fprintf(stderr, "Usage: %s [-d level] [-s 0|1] [-S] [-R]input\n", + argv[0]); + return EXIT_FAILURE; + } + } + + if (sort > SORT_RV) sort = UNSORTED; + if (sort_order > ASC) sort = DESC; + + if (optind >= argc) { + fprintf(stderr,"input file missing\n"); + return EXIT_FAILURE; + } + + if (debug > 0) printf("%s\n", argv[optind]); + fp = fopen(argv[optind], "r"); + if (fp == NULL) + { + fprintf(stderr, "I couldn't open results.dat for reading.\n"); + return EXIT_FAILURE; + } + + /* read k and n */ + if (fscanf(fp, "%d %d\n", &solver.n, &solver.k) != 2) + { + fprintf(stderr, "ERROR: read first line\n"); + return EXIT_FAILURE; + } + if (debug > 0) printf(" K:%d N:%d\n", solver.k, solver.n); + + /* allocate */ + solver.items = calloc(solver.n, sizeof(Item)); + if (!solver.items) + { + fprintf(stderr, "ERROR: items calloc\n"); + return EXIT_FAILURE; + } + + solver.column = calloc((solver.k + 1), sizeof(SolverData)); + if (!solver.column) + { + free(solver.items); + fprintf(stderr, "ERROR: column calloc\n"); + return EXIT_FAILURE; + } + for (i = 0; i < (solver.k + 1); i++) + solver.column[i].i = -1; + + /* read items */ + solver.sum_w = 0; + item = solver.items; + for (i = 0; i < solver.n; i++, item++) + { + item->i = i; + fscanf(fp, "%d %d\n", &item->v, &item->w); + solver.sum_w += item->w; + } + fclose(fp); + + if (sort != UNSORTED) + qsort(solver.items, solver.n, sizeof(Item), item_cmp); + + if (debug > 1) + { + printf(" Items "); + if (sort == UNSORTED) + { + printf("unsorted\n"); + } + else + { + printf("sorted "); + switch(sort){ + case SORT_VR: + printf("Value,ratio(V/W)"); + break; + case SORT_WR: + printf("Weight,ratio(V/W)"); + break; + case SORT_RW: + printf("ratio(V/W),Weight"); + break; + case SORT_RV: + printf("ratio(V/W),Value"); + break; + default: + break; + } + if (sort_order == ASC) + printf(" asc\n"); + else + printf(" desc\n"); + } + item = solver.items; + printf(" index Value Weight\n"); + for (i = 0; i < solver.n; i++, item++) + printf(" % 8d % 8d % 8d\n", item->i, item->v, item->w); + } + + clock_gettime(CLOCK_MONOTONIC, &t0); + solve(&solver); + clock_gettime(CLOCK_MONOTONIC, &t1); + ret = print(&solver); + + if (debug > 0) + { + dt = ((t1.tv_sec * 1000000000) + t1.tv_nsec) - + ((t0.tv_sec * 1000000000) + t0.tv_nsec); + printf(" time %7u [ms]\n", (unsigned int)(dt/1000000)); + } + + free(solver.items); + free(solver.column); + + return ret; +} + diff --git a/02-graph-coloring/CP-solver.rb b/02-graph-coloring/CP-solver.rb new file mode 100755 index 0000000..c157c07 --- /dev/null +++ b/02-graph-coloring/CP-solver.rb @@ -0,0 +1,229 @@ +#! /usr/bin/ruby + +class Node + # + def initialize i, a + @i = i # index + @a = [a] # adjacents + @c = nil # colour + @f = 0 # finished adjacents + @l = nil + end + # + attr_reader :i, :a + attr_accessor :c, :f + # + def add a + @a << a + end + # + def to_s + "#{@i} #{@c.to_s} " + @a.to_s + end + # + def l + return @l if not @l.nil? + @l = @a.length + end + # + def blocked? + (l == @f) + end + # +end + +class Step + # + def initialize n, c + @n = n # nodes + @c = c # max color + @k = nil # current + @f = [] # failed + @p = n.select { |n| n.c.nil? } # possible + # puts @p.inspect + # @p[0].c = 666 + # puts @p[0].to_s + end + attr_reader :c, :n + def done? + @p.empty? + end + # + def sort ar + ar.sort { |a,b| + r = b.l <=> a.l + if r == 0 + b.f <=> a.f + else + r + end + } + end + # + def chose_node + b = @p.select { |n| n.blocked? } + if not b.empty? + return sort(b).shift + end + sort(@p).shift + end + # + def test c + @k.a.each do |i| + if @n[i].c == c + return false + end + end + true + end + # + def set_color c + @k.c = c + @k.a.each do |i| + @n[i].f += 1 + end + end + # + def try + while not @p.empty? + if @k.nil? + @k = chose_node + @p.delete @k + end + # puts "try #{@k.to_s}" + co = nil + cs = (@k.c.nil? ? 0 : @k.c ) + (cs..@c).each do |c| + if test c + co = c + break + end + end + if co.nil? + @f << @k + @k = nil + else + set_color co + break + end + end + # @n.each do |n| puts n.inspect end + # puts @k.inspect + # puts 'OK' + true + end + # + def next + # TODO @k might be nil !! + Step.new(@n.inject([]) {|a,n| a << n.clone}, ( (@k.c < @c) ? @c: @c+1)) + end + # +end + +class Graph + # + def initialize p, n, e + @path = p + @n = n + @e = e + @nodes = {} + @edges = [] + @steps = [] + @c = 0 + end + # + def add e + @edges << e + + a, b = *e + a = a.to_i + b = b.to_i + + n = @nodes[a] + if n.nil? + @nodes[a] = Node.new a, b + else + n.add b + end + + n = @nodes[b.to_i] + if n.nil? + @nodes[b] = Node.new b, a + else + n.add a + end + end + # + def solve + s = Step.new(@nodes.values.inject([]) {|a,n| a << n.clone}, @c) + @steps << s + while true + if @steps.empty? + puts 'unsolvable' + return + end + if @steps[-1].try + @steps << @steps[-1].next + if @steps[-1].done? + puts 'success' + return + end + else + @steps.pop + end + end + end + # + def to_s + r = "#{@p}: N:#{@n} E:#{@e}\n" + @nodes.sort_by { |k,v| k } .each do |k,v| + r += " #{v.to_s}\n" + end + r + end + # + def draw + puts "colors : #{@steps[-1].c}" + require 'paleta' + color = Paleta::Color.new(:hex, "0000ff") + colors = Paleta::Palette.generate(:type => :complementary, :from => :color, :color => color, :size => @steps[-1].c).to_array(:rgb) + df = @path+'.dot' + pf = @path+'.png' + open(df,'w') do |f| + f << "graph {\n" + f << "node [style=filled];\n" + @steps[-1].n.each do |n| + f << " #{n.i} [color=\"#{"#%02X%02X%02X" % colors[n.c]}\"]\n" + end + @edges.each do |a,b| + f << " #{a} -- #{b}\n" + end + f << "}\n" + end + system "dot -Tpng -o '#{pf}' '#{df}'" + end + # +end + +def read_graph path + puts "read #{path}…" + g = nil + open(path).read.each_line do |line| + if g.nil? + g = Graph.new path, *line.split + next + end + g.add line.split + end + puts "done." + g +end + +ARGV.each do |path| + + g = read_graph path + g.solve + puts g + g.draw +end + diff --git a/02-graph-coloring/README b/02-graph-coloring/README new file mode 100644 index 0000000..76ff5f0 --- /dev/null +++ b/02-graph-coloring/README @@ -0,0 +1,15 @@ + +break symetries (colours are interchangeable); + - max colour + 1 + +try first where you fail: + - nodes with bigger degree && less possible colour + +think about distinct graphs: + - ?? + +a step is: + - possible nodes + - failed nodes + - chosen node + diff --git a/02-graph-coloring/data/gc_4_1.dot b/02-graph-coloring/data/gc_4_1.dot new file mode 100644 index 0000000..32b343b --- /dev/null +++ b/02-graph-coloring/data/gc_4_1.dot @@ -0,0 +1,10 @@ +graph { +node [style=filled]; + 0 [color="#FFFF00"] + 1 [color="#0000FF"] + 2 [color="#FFFF00"] + 3 [color="#FFFF00"] + 0 -- 1 + 1 -- 2 + 1 -- 3 +} diff --git a/02-graph-coloring/data/gc_4_1.png b/02-graph-coloring/data/gc_4_1.png new file mode 100644 index 0000000..b783995 Binary files /dev/null and b/02-graph-coloring/data/gc_4_1.png differ diff --git a/02-graph-coloring/draw b/02-graph-coloring/draw new file mode 100755 index 0000000..656c60b --- /dev/null +++ b/02-graph-coloring/draw @@ -0,0 +1,7 @@ +#! /bin/bash + +for data in ./data/*; do + echo "draw $data …" + cat $data | sed -e '1agraph G {' -e '1d; s/ / -- /; s/$/;/' -e '$a}' | dot -Tpng -o ${data}.png +done + diff --git a/02-graph-coloring/gc_20_1.png b/02-graph-coloring/gc_20_1.png new file mode 100644 index 0000000..20eac27 Binary files /dev/null and b/02-graph-coloring/gc_20_1.png differ -- cgit v1.1-2-g2b99