1 Replies - 3253 Views - Last Post: 25 May 2009 - 07:33 AM

#1 Minomol  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 01-April 09

Haskell graph colouring

Post icon  Posted 01 April 2009 - 11:35 AM

I need a little help, here it is:

On the planet Gliese 581 there are two nations, which fight all the
time...as soon as one of the sides is dominant in numbers, it starts
attacking the second one. On peace discussions they decided, that the
solution is splitting the population in such way, that no adjacent
cities will have the same nation in them.(In ine city there are only
inhabitants from one nation.)

In the function input there is the adjacency of cities assigned by a
list [[m11,m21],[m12,m22],...,[m1N,m2N]], where the pairs [m1i,m2i]
says, that the cities m1i and m2i are adjacent.

The function result gives TRUE, if it is possible to inhabit all
cities, else it gives FALSE.

example:
peaceAble [[1,2],[2,3],[3,5],[4,5],[10,2],[11,3],[5,6],[8,9],[7,8],
[4,7],[5,8],[8,12]] ==> True
peaceAble [[1,2],[2,3],[3,1]] ==> False

Anyone knows?

Is This A Good Question/Topic? 0
  • +

Replies To: Haskell graph colouring

#2 blackstarzes  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 25-May 09

Re: Haskell graph colouring

Posted 25 May 2009 - 07:33 AM

The pseudocode to colur a graph would be:
1. Sort the vertices in decreasing order of degree and initially have every vertex uncolored. Sorting isn't really necessary though, i left it out because I couldn't figure out how to implement an instance of Ord :$
2. Traverse the vertices in order, giving a vertex color 1 if it is uncolored and it does not yet have a neighbor with color 1.
3. Repeat this process with colors 2, 3, etc. until no vertex is uncolored.

Hi, I'm also pretty new to functional programming, but I (think) managed to solve this. Here is a bit of an outline:

- Define a data type called vertex with its name, colour (originally -1) and adjacencies.
- Write a function that will build your vertices from the list.
- The actual solving:
I wrote 3 functions - colourGraph (takes a list of uncoloured vertices and colours them); colourVertex (takes a single vertex, a list of coloured vertices, and returns the coloured vertex); canColour (takes a coloured vertex, the colour we are tyring to apply, the index where the uncoloured vertex should be in the adjacency array of the coloured vertex and returns True or False)

The idea behind colourGraph is to cons a coloured vertex onto an already coloured portion of the graph (tail recursion). Remember that colouring an empty list of vertices is an empty list.

The colourVertex function applies a colour to a vertex by trying to colour it 0, 1, 2 etc until it finds a valid colour, based on the already coloured portion of the graph. Remember that colouring a vertex given an empty coloured portion of the graph should return a vertex with colour 0. Also remember that you need to go through each vertex in the already coloured sectin to check if the uncoloured vertex can be coloured 0, if not it needs to start again by trying to colour it 1, then 2 etc (i used a utility function here to help colourVertex out - it takes the vertex we are trying to colour, the coloured portion of the graph, the coloured portion of the graph again, the colour we are trying and returns the coloured vertex). I'll leave you to think about how exactly to implement the utility function, but I'll give you a hint - I passed the coloured portion twice so that the first bit stays the same (in case i need to try more colours) and the second bit is used in the recursion).

The canColour function just checks if the adjacency array at the given index is -1 (not next to each other) or if the colour of that coloured vertex is not the same as the colour we are wishing to try.

Now all you need to do is find the vertex with the highest numbered colour (colours range from 0 - order-1) and see if this is 2 for a two colour graph.

Good luck!

This post has been edited by blackstarzes: 25 May 2009 - 07:34 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1