Four Color Theorem in Grasshopper

Hello,
it was not a so simple problem but it was interesting. I struggle a bit but here is a solution (I hope :sweat_smile:).


It uses a custom C# to do the recursion, I begin to assign a color to a face, get the adjacent not colorized, choose one colorize it depending on neighbour …
You need a Sandbox that is used to get the topology of Brep.

2 Likes

Wow, that’s amazing! I was thinking that there would be a plugin. I like patterning using Lunchbox and when I slide through random seeds, there’s sometimes awkward clumping and that made me think of the Four Color Theorem. How can the items be split out? It worked perfectly with the Lunchbox paneling but I tried it with a Voronoi and there was an error.

Hello
indeed there was many bugs, but the logic I choose has also a flaw in my algorithm because with Voronoi it doesn’t allow just 4 colors. So when I can’t I put an index = -7 (there is no logic here 4 must be better) .
Here I colorize in White the cell with problem


But it is sometimes possible to fin a seed that doesn’t rise the problem, here 87

Some add in the implementation, still need to play with seed if there are some white cells. With 300 Voronoi cells there is 25 % of case with some bad coloring.
FourColors_Legacy.gh (35.5 KB)
Happy coloring.
And I discovered the Animation menu in Slider, I neither used it since so many years !!!
Frame_

1 Like

I came across this article online which describes a simple polynomial-time algorithm for a five coloring of a graph, apparently far simpler than general four-coloring algorithm (which seems to be NP-hard and very complicated)
http://www.devx.com/dotnet/Article/32927

Quote:

In theory you could write a program to examine a map and use the 1,476 special cases to find a four-color solution, but the resulting program would be long, complicated, and impossibly hard to debug. It would probably also be fairly slow.

Despite the problems involved in writing a program to color a map in four colors, it’s not too difficult to write one that colors a map with five colors. Unless you have a strange monitor that can display only four colors at a time, five-coloring should be good enough for most applications.

1 Like

A new version with specified number of colors. This script affect an index color at each face, if it is not possible the index is equal to -1.
Here some examples with differents polygons.







3 Likes

BTW: For the 4 color clustering thingy use FF connectivity (either implicit via joining breps or explicit) and some recursion (it works):

Hello Peter
indeed I used face face connectivity it works most of the time. But with Voronoi and 4 colors it fails sometime I lower the percentage of fail by choosing new face to color which touched a maximum of already colored faces. But that’s not 100%.

It’s a matter of asking the right question.

Wrong (grey means bad things)



Right:



I’ll test some stuff (maybe //) in order to greatly accelerate the result (big N of regions: say 1K and up) and I’ll post the C# here when ready.

Just for fun (been dealing with combinatorial algorithms recently), here is a really inefficient method of N-colouring a graph based on ‘dumb’ genetic combination rules:


(video sped up 2x)

The advantage with genetics is that you require practically zero insight into the theory behind graph colouring - just let it loose and it will eventually converge on a solution :slight_smile:

Edit:
Hmm, that doesn’t work out too well for highly regular structures like the hex grid: the algorithm just ends up oscillating around local minima forever, forming these crystal defect-like boundaries.

2 Likes

Cool to see other experiments. The question of @SpatialSojourner was a good one :tada:

The forest fire method is quite robust. I added some new tesselations to test.
Gilbert tesselation


Here a pentagonal one
With 4 colors it works well

But for 3 colors it din’t find the repetive pattern.

Using Galapagos is quite effective to find the seed that lead to color all faces. Here with a voronoi with 1000 points.

I think also that this tool could be used to weave, to find some “roads” … TBC

1 Like

There’s a probability for this to become the most challenging thread of all times (performance wise). Beats Hanoi Towers by a factor of 100.

My current (a bit miserable) status: Since the right question yields 100% right results but takes a year and a half to finish (backwards recursion) for random valence region collections as shown (see info panel on top for max valence) > C# is rejected as stupid and pointless > new Plan B > variable clustering (N of colors in this occasion) > hope dies last > needs 3 milliseconds to solve the puzzle (~ 500 random regions) … but …well … there’s some failures in the menu (life sucks).

IM dollar idea: can we just stay on 2 colors? Who’s gonna notice it?

And what about one color? Less is more after all.

Moral: Porca Miseria (TBC)

Hey people,

If I understand it the right way this problem can be solved using the “WelshPowell”-Algorithm. Wihich isn’t that hard to implement.

I have done so within this plugin (QEDS)

A file (01_Conversion>FromLines) from the examples gives the following result.

Normaly the algorithm tries to find a color for neighbouring faces, where two faces are neighbours if they share a common edge. I added an option (respect duality) to define that two faces are neighbours if the share an edge OR a vertex.

That algo works when it works. For voronoi type of regions it fails to deliver the goods

Here’s the thing (In fact the main Method of the thing):

Here’s another Method (don’t ask what it is):

Moral (and current status of things performance wise) : Porca Miseria

Here a new version of n Color of faces with non similar color for adjacent faces. I add some improvements. And it seems to give good agreement for most of the uses. it no more uses SandBox.
So the script needs :

  1. Face-Face topology so it could be brep topology or mesh topology or whatever…
  2. Seed : a seed that is useful to change the patterns
  3. A number of color wanted (lowest possible =2), but with autonoumous mode the number of color will be augmented if no solutions found
  4. nextColorNotRandom, if true the next color choosen is not a random one but the lowest color number possible
  5. if autonomous set to true, the script try to find the best solution, augment the number of color if needed, change nextColorNotRandom if needed, could be stopped by using Escape touch.

I put some examples. All are solved in reasonable time. Time will surely be very long for a big number of faces or with things like a mesh cube.
The cube (here just 3 faces) is long if you ask for 2 colors, because it makes many tests with 2 colors. If you put 3 colors it is OK



Pentagons is now OK with 3 colors

Hope it is clear and useful.

nColors_Legacy.gh (260.2 KB)

6 Likes

Good algorithm.
I add/modify some changes in code to improve speed of execution => trying to avoid repetitive calculations where possible. Testing on 2000 faces shows aprox. 4 times faster code execution.
Some additional improvements can be done, but we leave that to somebody who needs this algorithm to be faster.

nColors_Legacy_2.gh (264.8 KB)

8 Likes

Wow, @laurent_delrieu @PeterFotiadis, you guys have come up with some really cool stuff… I walked away from my random pondering and come back to find some amazing responses. I’m going to have to take a look at these… the tesselation, pent, and vorinoi is :fire:

1 Like

Gilbert tessellations script is here

Forgot completely (blame advancing Alzheimer) that thread: I did at the time a working (?) solution for the 4 Vodka pints theorem (related with Tequila in fact) but what was the name of the C#? That’s the 1M question.

How do i do a custom C#??

There are many discussions of that on this forum. Can you be more specific?