Tag Archives: coloring maps

Optimizing Graph Coloring with Reinforcement Learning

Posted on by
Reply

This is what I will be working for a while. Restart is difficult, but necessary.

Why use Reinforcement Learning for Graph coloring?

In my Python application, that works on 3-regular planar graph, deciding which is the order of the edges to remove can be non-trivial. A naive approach randomly picks edges from F2 faces, F3, F4 or F5. This is the approach I used :-(. It leads to impasses when rebuilding the map. See https://4coloring.wordpress.com/2014/08/27/four-color-theorem-experimenting-impasses-as-in-life/

But a reinforcement learning agent can learn to make better selections over time to reduce color conflicts, I hope :-), and shed light on some properties of the graph that can be used in the proof.

The code will be here: https://github.com/stefanutti/maps-coloring-python

Remove one edge at a time from F2, F3, F4, or F5 faces. These faces represent the basic unavoidable set. This process will reduce the map to three faces, including the ocean as the external area. Afterward, I will restore the edges in reverse order, consistently working with 3-regular planar graphs. I will consider Tait coloring of the edges and apply, when necessary, Kempe’s chain color switching to the edges.

Remove edges a then restore them

For the Agent:

  • Environment initialization = The starting uncolored 3-regular planar graphs
  • Action = Select the edge to remove from the 3-regular planar graphs
  • State = The updated 3-regular planar graphs
  • Reward = +1 if Random Kempe’s chain color switching was not necessary, -1 otherwise

Color Voronoi graphs

Posted on by
1

To color Voronoi graphs using the algorithm here https://github.com/stefanutti/maps-coloring-python, it is necessary to do some adjustments first:

  • Transform it into a 3-regular graph, by adding a frame and modifying the vertices with more than 3 edges, as shown below
  • Consider the surrounding area (out of the frame) as part of the map (the ocean) and color also that

It is known that we can also suppose that exactly three edges meet at each vertex since maps that have vertexes with more than three edges can be easily simplified without affecting the search of the coloring. In other words, if you can find a coloring for the map on the right, you can use the same coloring for the original map on the left.

Here is an example of these steps applied to the following Voronoi diagram. Three vertices have a degree greater than three.

Voronoi to 3-regular graph

Four color theorem: experimenting impasses (as in life)

Posted on by
1

I still think a solution may be found in Kempe chain color swapping … for maps without F2, F3 and F4 faces (or even without this restriction).

Or at least I want to try.

kempe-chain-impasse-v2

How you can solve the impasses (To be finished):

To explain the possible cases, without lack of generality, I can assume to start with these colors: e1=red, e2=green, e3=blue, e4=red. e4 may also be colored in green, the reasoning will not change much.

  1. If e3 and e4 are not colored … there is no impasse → OK
  2. If e3 is the same color ex should be (blu in the example) and e4 is non colored
    1. If one of the two possible chains starting from e3: (b, r)-chain or (b, g)-chain does not end at e1 or e2
      1. Use it to swap the color of e3 and solve the impasse → OK
    2. If both end at e1 or e2
      1. Try to deroute one of the two chains, using another kempe chain color swapping along the way, to fall into one the the solvable cases (2.A)
        1. If the derouted original chain does not longer end at e1 or e2, then apply the original kempe chain color swapping and solve the impasse → OK
        2. If deroute does not work
          1. … TBV: It seems that swapping colors around solve all type of impasses
  3. If e3 is the same color ex should be, and e4 is also colored
    1. In this case the chain (…-e3–e4-…) = (b, r)-chain would simply swap the colors of e3 and e4 and therefore will not solve the impasse. It is better to use the other (b, g)-chain, starting from e3
      1. If this chain does not end at e2 (e1 is not a possible end because the chain is blue and green), use it to swap the color of e3 and solve the impasse → OK
      2. If it ends at e2
        1. Try to deroute the chain, using another kempe chain color swapping along the way, to fall into one the the solvable cases
        2. If deroute does not work
          1. … TBV: It seems that swapping colors around solve all type of impasses

A deroute of a chain appears as in the next picture. Consider that deroutes may not work because Chain-B color swapping may change one or more of the three edges e1, e2, e4, and after appying the Chain-B swap, the chain starting with a3, may still end to one to e1, e2, e4. See this post for a real example: here.

kempe-chain-deroute-v2

About swaps of a partially colored map, I’ve asked a question on mathoverflow … here.

Maybe I was wrong when, in the motivation of the question (mathoverflow), I said that “I found many examples in which Kempe chain color swapping does not work for maps with faces of type F2, F3, F4, but I did not find an example of maps with only F5 or higher“. It seems to be possible also for maps with F2, F3, F4.

I’ll continue to search for counterexample but, for what I’ve seen so far (I tryed about 50 maps) it has been always possible to solve impasses, only proceeding by swapping colors.

This is one of the map that I thought to be a counterexample, but it is not. Its signature is:

  • 1b+, 9b+, 9e+, 3b+, 5b+, 7b+, 12b+, 10b-, 11b-, 5e-, 7e-, 4b-, 3e-, 2b-, 10e-, 4e-, 6b-, 11e-, 12e+, 8b+, 8e+, 6e+, 2e+, 1e+

impasse-in-map-not-simplified

Something else to check:

  • Since once completely colored, all chains are actually loops, when it comes to the last two impasses, if you solve one impasse also the other one gets solved!

Four color theorem: work in progress

Posted on by
Reply

😦

Too many more things to do and little time:

  • Filter out duplicates. I finally found a java library to efficiently filter out all isomorphic graphs. It is a library part if the sspace project. Using it I will be able to test more complex simplified maps with lots of vertices … not risking to spend CPU time on duplicates
  • Finish the implementation of the Cahit algorithm to color the edges of a bridgeless cubic planar graph. I still need to well understand why Kempe’s chain color switching works using Cahit spiral chain method … especially when there is more than one spiral chain
  • Convert the swing application to javafx. This way I’ll be able to eliminate many third party dependencies: G, swixml, …
  • …

Bye

Four color theorem: Cahit spiral chains (step two)

Posted on by
Reply

Now the application is able to find all spiral chains of a graph.

I still need to:

  • Implement the Cahit coloring algorithm using the spiral chains
  • Add some additional features to the Java application
    • Modify the settings to color the edges
    • Manual selection of the starting vertex
    • Manual coloring of the Edges
    • …

The application can be downloaded from the github site.

About the Cahit coloring algorithm there are some things that I need to undestrand before implementing the Java code.

Four color theorem: other representations of maps

Posted on by
Reply

Here are some new representation of graphs:

Thanks to:

Four color theorem: representations of maps

Posted on by
5

For the scope of the four color problem and without lack of generality, maps can be represented in different ways. This is generally done to have a different perspective on the problem.

For example, the graph-theoretic representation of maps has become so common and important that generally the four color problem is stated and analyzed directly in terms of graph theory: http://en.wikipedia.org/wiki/Four_color_theorem.

I am trying to collect other representations that may in some way help to get a different point of view on the problem. If you know one of these representations that is not listed and wish to share, report it here. If you also have a web reference that explains or shows the representation, it would be great.

The representations have to be general and applicable to all maps with the simplification that only regular maps (no exclaves or enclaves, 3 edges meeting at each vertex, etc.) can be considered.

These are some classic representations:

  • Natural: As a 3-regular planar graph (boundaries = edges)
  • Canonical: As the dual graph of the “natural” representation (region = vertex, neighbors = edges)
  • As a straight line drawing graph (Fáry’s theorem)
  • As a graph with vertices arranged on a grid
  • As a rectilinear cartogram

Plus, I found these:

  • As a circular map
  • As a rectangular map
  • As clefs (derived from rectangular maps)
  • As pipes map (derived from the clefs representation)
  • …

New representations (answers from mathoverflow):

Here is an example of some of these representations for the original map shown:

See next post for other representations.

Counting maps

Posted on by
Reply

I’ve posted this question on mathoverflow.

Is there a formula to count how many different topological regular maps can be created with n faces (on a sphere)?

  • For “regular” I intend maps in which the boundaries form a 3-regular planar graph
  • For “different” I intend maps that cannot be topologically transformed one into another (faces have to be considered unnamed)

I’ve been looking for a formula, but it is too difficult for me. Maybe it has a simple solution but I don’t see it.

This was my best guess, but I already know that it is not correct because full of symmetries, as it can be verified manually.

General formula:

2\sum _{s_{(f-3)}=2f-5}^{2f-5+2} \text{...}\sum _{s_3=7}^{s_4} \sum _{s_2=5}^{s_3} \sum _{s_1=3}^{s_2} s_1\left(s_1-1\right)\left(s_2-3\right)\left(s_3-5\right)\text{...}\left(s_{(f-3)}-((2f-5)-2)\right)

4 faces = 2\sum _{s_1=3}^5 s_1\left(s_1-1\right)
5 faces = 2\sum _{s_2=5}^7 \sum _{s_1=3}^{s_2} s_1\left(s_1-1\right)\left(s_2-3\right)

Here are the first results that can be found manually (excluding simmetrical maps):

  • 2 faces = 0 possible regular map (an island and the ocean) (not to be counted, because not regular)
  • 3 faces = 1 possible regular map (an island with two regions and the ocean) (two islands and the ocean wouldn’t be regular)
  • 4 faces = 3 possible regular maps (can be verified adding a face from the previous map)
  • 5 faces = 16 possible regular maps (with homeomorphics eliminated)
  • …

These are all maps up to 5 faces: