Re: [eclipse-clp-users] Graph Coloring

From: Sergii Dymchenko <kit1980_at_...6...>
Date: Tue, 2 Apr 2013 18:21:25 -0700
Hi again,

I managed to solve my problem using this method:

Colors array :: 1..4.
Bunch of Colors[I] #\= Colors[J] constraints.
search(Colors, 0, first_fail, indomain_min, complete, []).
The answer (minimal number of colors needed) is max value in Colors.

I'm just not sure why this works correctly and if it works in general case
or for my instances only (around 100 tests with 100 nodes and around 100
tests with 1000 nodes).

The good thing is that it works fast (less than 30 sec for 100 tests of
1000 nodes on my laptop).

Sergii.


On Tue, Apr 2, 2013 at 4:34 PM, Mark Wallace <mark.wallace@...269...>wrote:

> For variable choice use first-fail and for value choice use either
> indomain_random or a user-defined labelling which rotates the colours so
> the first guess for each variable is different from the last 3 (where 4 is
> the number of colours)
>
>
>
> On 3 April 2013 10:22, Sergii Dymchenko <kit1980@...6...> wrote:
>
>> Hi!
>>
>> Any suggestions how should I approach a graph coloring problem in
>> ECLiPSe? I'd want to do graph coloring for planar graphs of hundreds of
>> nodes.
>>
>> I tried naive encoding with ic library and bunch of #\= constraints, but
>> it works forever for graphs with one hundred nodes.
>>
>> Sergii.
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Minimize network downtime and maximize team effectiveness.
>> Reduce network management and security costs.Learn how to hire
>> the most talented Cisco Certified professionals. Visit the
>> Employer Resources Portal
>> http://www.cisco.com/web/learning/employer_resources/index.html
>> _______________________________________________
>> ECLiPSe-CLP-Users mailing list
>> ECLiPSe-CLP-Users_at_lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>>
>>
>
>
> --
> Professor Mark Wallace
>
> Faculty of Information Technology
> Level 6, Building H, Monash University
> 900 Dandenong Road, Caulfield East
> VIC 3145. Australia
> (03) 9903 4276
>
Received on Wed Apr 03 2013 - 01:21:33 CEST

This archive was generated by hypermail 2.2.0 : Mon Jul 09 2018 - 02:05:30 CEST