Re: [eclipse-clp-users] Graph Coloring

From: Sergii Dymchenko <kit1980_at_gmail.com>
Date: Tue, 2 Apr 2013 20:06:39 -0700
OK, it looks like I just implemented a slight variation of DSATUR (
http://fr.wikipedia.org/wiki/DSATUR) heuristic (but it should be
most_constrained instead of first_fail).

Sergii.


On Tue, Apr 2, 2013 at 6:21 PM, Sergii Dymchenko <kit1980_at_gmail.com> wrote:

> 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_at_monash.edu>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_at_gmail.com> 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 - 03:06:49 CEST

This archive was generated by hypermail 2.2.0 : Sat Apr 06 2013 - 18:13:22 CEST