From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Jan Wedekind Newsgroups: gmane.lisp.guile.user Subject: Graph coloring with Scheme Date: Fri, 14 Nov 2014 18:16:02 +0000 (GMT) Message-ID: Reply-To: Jan Wedekind NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII X-Trace: ger.gmane.org 1415989009 9094 80.91.229.3 (14 Nov 2014 18:16:49 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 14 Nov 2014 18:16:49 +0000 (UTC) To: General Guile related discussions Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Fri Nov 14 19:16:43 2014 Return-path: Envelope-to: guile-user@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XpLQI-0005xH-VI for guile-user@m.gmane.org; Fri, 14 Nov 2014 19:16:43 +0100 Original-Received: from localhost ([::1]:37503 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XpLQI-00056W-8a for guile-user@m.gmane.org; Fri, 14 Nov 2014 13:16:42 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:48493) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XpLQ3-00056J-HW for guile-user@gnu.org; Fri, 14 Nov 2014 13:16:33 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XpLPx-0008FU-5f for guile-user@gnu.org; Fri, 14 Nov 2014 13:16:27 -0500 Original-Received: from basicbox4.server-home.net ([195.137.212.26]:53713) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XpLPx-0008DY-0I for guile-user@gnu.org; Fri, 14 Nov 2014 13:16:21 -0500 Original-Received: from wedemob (unknown [149.254.182.38]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by basicbox4.server-home.net (Postfix) with ESMTPSA id 565CB1530733 for ; Fri, 14 Nov 2014 19:16:15 +0100 (CET) X-X-Sender: jan@wedemob.home User-Agent: Alpine 2.02 (DEB 1266 2009-07-14) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 195.137.212.26 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Original-Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.user:11637 Archived-At: Hi, Here is an implementation [1] of Chaitin's graph coloring algorithm using GNU Guile and Graphviz. Any feedback and suggestions are welcome. Let me know if you can make the implementation more concise ;) Regards Jan (use-modules (srfi srfi-1) (srfi srfi-26)) (define (dot graph colors) (apply string-append (append (list "graph g {") (map (lambda (color) (format #f " ~a [style=filled, fillcolor=~a];" (car color) (cdr color))) colors) (map (lambda (edge) (format #f " ~a -- ~a;" (car edge) (cdr edge))) graph) (list " }")))) (define (graphviz graph colors) (system (format #f "echo '~a' | dot -Tpng | display -" (dot graph colors)))) (define (nodes graph) (delete-duplicates (append (map car graph) (map cdr graph)))) (define (has-node? edge node) (or (eq? (car edge) node) (eq? (cdr edge) node))) (define (adjacent graph node) (nodes (filter (cut has-node? <> node) graph))) (define (remove-node graph node) (filter (lambda (edge) (not (has-node? edge node))) graph)) (define (argmin fun lst) (let* [(vals (map fun lst)) (minval (apply min vals))] (list-ref lst (- (length lst) (length (member minval vals)))))) (define (order graph nodes) (if (null? nodes) '() (let [(target (argmin (lambda (node) (length (adjacent graph node))) nodes))] (cons target (order (remove-node graph target) (delete target nodes)))))) (define (assign-colors graph nodes colors) (if (null? nodes) '() (let* [(target (car nodes)) (coloring (assign-colors (remove-node graph target) (delete target nodes) colors)) (blocked (map (cut assq-ref coloring <>) (adjacent graph target))) (available (lset-difference eq? colors blocked))] (cons (cons target (car available)) coloring)))) (define (coloring graph colors) (assign-colors graph (nodes graph) colors)) (let [(graph '((b . a) (a . c) (d . c)))] (graphviz graph (coloring graph '(red green blue)))) [1] http://wedesoft.de/graph-coloring.html