Applying the Four Color Theorem in VISIO?

[Bald Eagle]

I'm playing with the US Map stencil, and was wondering if anyone's automated the Four Color Theorem to apply fill properties to multiple selected objects / subgroups.

https://en.wikipedia.org/wiki/Four_color_theorem

I'm thinking that this might require some VBA, unfortunately most of my coding knowledge is in C++ with a smattering of other languages.
(The last time I actually wrote a macro for an M$ product was in the mid 90's while making some cool Excel spreadsheets for the now defunct American Cyanamid.    )
http://www.nj.com/mercer/index.ssf/2014/09/owners_of_long-vacant_american_cyanamid_site_in_west_windsor_begin_discussions_on_possible_redevelop.html

[wapperdude]

I've not seen anyone do this.  Strikes me as difficult for Visio,  unless there is a method in the object model to trace a shapes border.   The bounding,  selection box would be of minimal use.   The newer versions might have the methods needed,  just don't know.

Wapperdude

[georgejost]

I'm playing with the US Map stencil, and was wondering if anyone's automated the Four Color Theorem to apply fill properties to multiple selected objects / subgroups.

Very unlikely. To do that, you'd have to understand the proof and the 1200+ isomorphic cases involved

Then you'd would have to understand visio's interfaces

Very rare to get somebody capable of the former interested in the latter

It could be, that real maps are simpler than the 1200 cases tho.

[Yacine]

Hi guys,
sorry, but I don't agree with the given answers.
The solution is not completely trivial, but definitely solvable.
Neither is it too difficult, nor is it too special. A solution could color not only maps, but all kind of graphs that need to be colored automatically. So IMHO this is a tool to develop.

In my opinion there would be 2 steps in the solution:

1) Find common borders:
Make a routine that creates a small shape (eg a rectangle). The smaller the more precise, but also the longer the processing.
Find the borders of the selection or use the whole page as canvas.
Now let the shape travel row by row over the whole canvas and check the shapes it overlaps. SpatialNeighborhood is the function to use.
Everytime the shape overlaps 2 or more shapes, you'll have found a border and can use the result of the SpatialNeigborhood to store this border either in the shapes themselves (a user or prop cell) or an adequate construct in Code (array, collection, etc.).
After having filtered out duplicates, you'll have the borders as intelligent data structure.

2) Color the shapes
a) Do it the right way and find - or work out - an algorithm to find the optimal solution.
In about a quater of an hour I did find a complete code in Pascal. This code would need to be translated in VBA, VB.NET or any other suitable language. (Sorry Paul)

b) Use a naive method by starting at shape #1.
Color its neighbors in 3 other colors and mark the colored shapes as finished.
Take the next uncolored shape and repeat the code.
If no solution is found either mark the shape as such (color, text, ...) to let the user correct the result or iterate by tracking back and choosing anoter path (color).

Thank you Bald Eagle for this challenge. I hope you'll keep up and will work out a nice solution for yourself (and the community).
Cheers,
Y.

[Bald Eagle]

Heh,
Sure thing, Yacine   
I know how some of you folks just can't be happy without such a challenge to ponder in the off moments of the day, or while in that twilight sleep where "the circus" starts.  Having a light, a pencil, and notepad next to the bed definitely makes for an easier time "getting it out" and letting the brain settle down.   Or sometimes there's just an "ah, screw it" - I wasn't going to bed anytime soon anyway"....   

I would think that one could generate some sort of connectivity diagram / table, and use some attribute about the perimeters to see if shapes are adjacent.   Then start off with some given shape, and color that A.   That leaves B, C, and D. 
Must be some way to use that as a process of elimination to puzzle out what color to use for any given shape.
"All ya gotta do is...."   

I'll see what I can understand, and what's available on StackOverflow, news.povray.com, Wolfram, etc.
http://mathworld.wolfram.com/Four-ColorTheorem.html

Glad you liked this little puzzle.      

[Bald Eagle]

https://www.youtube.com/watch?v=h-UfRyElkzc
An interesting, logical, step-wise process that could be implemented in code.


https://www.youtube.com/watch?v=YmYGFxtj2es
Looks like thing guy has whanged something together in JAVA.
Code available on SourceForge:
https://sourceforge.net/projects/maps-coloring/

[JuneTheSecond]

Yacine knows well about Visio, and Bald Eagle knows well about 4-colors.
Y+B might be the best combination.

However I think Visio is not good tool, Visio cannot shortly find a couple of adjacent shapes.
For example in the case shown picture below, SpatialNeighbors and SpatialRelation could not find  correct couples. Red shape A has only 6 adjacent green shapes around A. But SpatialNeighbors and SpatialRelatio find 12 shapes around shape A with any of VisSpatialRelationCodes. 6 red shapes have to be removed. They are touching to shape A at a point. Any magic is required. 

[Bald Eagle]

Indeed, June, I hear what you are saying.
Although I'm unfamiliar with the Spatial functions you're using, I also never thought that there would be any native "Visio-only" functions which would be able to unravel this interesting problem that has such a long and complicated history.   It's "solution" is still a matter of conjecture.

I think that it's something that might require VB, and possibly even the daisy-chaining of several tools to get the job done.  Progress with one software package may shine a light on a path in another software package.

Perhaps the first line of attack is to puzzle out a way to identify if shapes are adjacent.
In POV-Ray, I could probably try to use something like TRACE which would tell me where the edge of an object is.
I'm wondering if there's a way to use the shape operations like difference to test if objects are next to each other.
If two "countries" border each other, and I change the size by 1.001, then there ought to be a remainder upon intersecting them.  Some sort of Boolean result if there's something generated or not. "is there a _new_ shape where there was not before?"
Perhaps there are examples to be learned from in basic video-game collision detection and newer particle systems.
That Visio Guy Chris Roth worked out his polyline generating sheet.  Can it be determined programmatically if one irregular polygon borders the other within a given range?  Less than some distance normal to the edge's curve?

Maybe there's a way to use the line connecting center pins of 2 shapes and see if the bounding box of all other shapes are between them.   

June has a very disciplined mind, can see and understand the core of many problems, and has the artistic and technical skills and talent to address these things in beautiful ways.   I'm just a guy with a (donated) laptop and neurotic desire to play with math and science and computers   
Y+B+J+ ... x+y+z  will likely be the "best" combination.
In any event, there's likely to be a lot of fun and exploration and invention, and fruitful discussion along the way.

[Yacine]

So here's a proof of concept.
I implemented the 2 routines as previously described: 1) finding the borders, 2) coloring.

For the coloring I did use the first trivial idea that came in my mind:
for each shape on the page, if it is not colored, then check if its neighbors are and eliminate all the colors found, then take the first left color in the row.

In the 2 first examples it did not work perfectly, as it left some shapes (the black ones) without solution.
A backtracking algorithm could eliminate the problem.
Considering, that I did not use any "academic" algorithm at all, an already impressive result.

HOW TO USE?
Run the macro getNeighbors.

MIND:
Finding the neighbors was implemented with brute force - no intelligence involved and accordingly slow. Remove the doevents lines to increase the speed.
Play with the variable sqrSize for coarser or finer scanning results.

Enjoy and improve the code.
Cheers,
Y.

[Yacine]

.

[Yacine]

However I think Visio is not good tool, Visio cannot shortly find a couple of adjacent shapes.
For example in the case shown picture below, SpatialNeighbors and SpatialRelation could not find  correct couples. Red shape A has only 6 adjacent green shapes around A. But SpatialNeighbors and SpatialRelatio find 12 shapes around shape A with any of VisSpatialRelationCodes. 6 red shapes have to be removed. They are touching to shape A at a point. Any magic is required. 

This was easy. Consider only results, where the number of overlapped shapes equals 2.

[Bald Eagle]

"This was easy."     

Well, you certainly did make short work out of that!
I'm guessing that whatever method you employed is only supported in Visio 2013 - I only have 2007, so I can't really see what you did.

Congratulations, on excellent work, and an impressive demonstration of skill and speed!

[Yacine]

To let the interested ones play with the tool, I put the code in a stencil and added a "launcher" (the yellow master in the stencil - drag it on the drawing to start the macro).

Instead of executing the scanning and the coloring in a row, I separated them, by providing a button for each operation. So one can work on a specific part of the problem at a time.

I paid attention to save the stencil as VSS, so the V2007 people can play as well.

Cheers,
Y.

[Yacine]

Here's a first idea on how to implement backtracking. This will however still not be a guarantee to solve EVERY problem. ... but definitely better than the one shot methode.

[Visio Guy]

Fantastic discussion, guys! As an artist and scientist trapped inside an engineer's body, this is just wonderful, and I wish I had more time to look through the details of your posts!