

A Graph is a collection of nodes
(or vertices), connected by edges (or not).
Nodes directly connected by edges are called neighbours.

In our representation of graphs, nodes are numbered and edges are represented
by the two node numbers connected by the edge separated by a dash.
Edges define the nodes being connected. Only unconnected nodes need a separate
description.

For example,

0-1 1-2 2-0 3
Describes the following graph. Note that node 3 has no neighbours



Example graph

+---+
| 3 |
+---+

  +-------------------+
  |                   |
+---+     +---+     +---+
| 0 | --- | 1 | --- | 2 |
+---+     +---+     +---+

A useful internal datastructure for a graph and for later graph algorithms is
as a mapping between each node and the set/list of its neighbours.

In the above example:

0 maps-to 1 and 2
1 maps to 2 and 0
2 maps-to 1 and 0
3 maps-to <nothing>
Graph colouring task

Colour the vertices of a given graph so that no edge is between verticies of
the same colour.

 Integers may be used to denote different colours.
 Algorithm should do better than just assigning each vertex a separate colour. The idea is to minimise the number of colours used, although no algorithm short of exhaustive search for the minimum is known at present, (and exhaustive search is not a requirement).
 Show for each edge, the colours assigned on each vertex.
 Show the total number of nodes, edges, and colours used for each graph.
Use the following graphs

Ex1

       0-1 1-2 2-0 3

+---+
| 3 |
+---+

  +-------------------+
  |                   |
+---+     +---+     +---+
| 0 | --- | 1 | --- | 2 |
+---+     +---+     +---+

Ex2

The wp articles left-side graph

   1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7


  +----------------------------------+
  |                                  |
  |                      +---+       |
  |    +-----------------| 3 | ------+----+
  |    |                 +---+       |    |
  |    |                   |         |    |
  |    |                   |         |    |
  |    |                   |         |    |
  |  +---+     +---+     +---+     +---+  |
  |  | 8 | --- | 1 | --- | 6 | --- | 4 |  |
  |  +---+     +---+     +---+     +---+  |
  |    |         |                   |    |
  |    |         |                   |    |
  |    |         |                   |    |
  |    |       +---+     +---+     +---+  |
  +----+------ | 7 | --- | 2 | --- | 5 | -+
       |       +---+     +---+     +---+
       |                   |
       +-------------------+

Ex3

The wp articles right-side graph which is the same graph as Ex2, but with
different node orderings and namings.

   1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6


  +----------------------------------+
  |                                  |
  |                      +---+       |
  |    +-----------------| 5 | ------+----+
  |    |                 +---+       |    |
  |    |                   |         |    |
  |    |                   |         |    |
  |    |                   |         |    |
  |  +---+     +---+     +---+     +---+  |
  |  | 8 | --- | 1 | --- | 4 | --- | 7 |  |
  |  +---+     +---+     +---+     +---+  |
  |    |         |                   |    |
  |    |         |                   |    |
  |    |         |                   |    |
  |    |       +---+     +---+     +---+  |
  +----+------ | 6 | --- | 3 | --- | 2 | -+
       |       +---+     +---+     +---+
       |                   |
       +-------------------+

Ex4

This is the same graph, node naming, and edge order as Ex2 except some of the edges x-y are flipped to y-x.
This might alter the node order used in the greedy algorithm leading to differing numbers of colours.

   1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7


                      +-------------------------------------------------+
                      |                                                 |
                      |                                                 |
  +-------------------+---------+                                       |
  |                   |         |                                       |
+---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+
| 4 | --- | 5 | --- | 2 | --- | 7 | --- | 1 | --- | 6 | --- | 3 | --- | 8 |
+---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+
  |         |                             |         |         |         |
  +---------+-----------------------------+---------+         |         |
            |                             |                   |         |
            |                             |                   |         |
            +-----------------------------+-------------------+         |
                                          |                             |
                                          |                             |
                                          +-----------------------------+

References

 Greedy coloring Wikipedia.
 Graph Coloring : Greedy Algorithm & Welsh Powell Algorithm by Priyank Jain.


using Random
 
"""Useful constants for the colors to be selected for nodes of the graph"""
const colors4 = ["blue", "red", "green", "yellow"]
const badcolor = "black"
@assert(!(badcolor in colors4))
 
"""
    struct graph
 
undirected simple graph
constructed from its name and a string listing of point to point connections
"""
mutable struct Graph
    name::String
    g::Dict{Int, Vector{Int}}
    nodecolor::Dict{Int, String}
    function Graph(nam::String, s::String)
        gdic = Dict{Int, Vector{Int}}()
        for p in eachmatch(r"(\d+)-(\d+)|(\d+)(?!\s*-)" , s)
            if p != nothing
                if p[3] != nothing
                    n3 = parse(Int, p[3])
                    get!(gdic, n3, [])
                else
                    n1, n2 = parse(Int, p[1]), parse(Int, p[2])
                    p1vec = get!(gdic, n1, [])
                    !(n2 in p1vec) && push!(p1vec, n2)
                    p2vec = get!(gdic, n2, [])
                    !(n1 in p2vec) && push!(p2vec, n1)
                end
            end
        end
        new(nam, gdic, Dict{Int, String}())
    end
end
 
"""
    tryNcolors!(gr::Graph, N, maxtrials)
 
Try up to maxtrials to get a coloring with <= N colors
"""
function tryNcolors!(gr::Graph, N, maxtrials)
    t, mintrial, minord = N, N + 1, Dict()
    for _ in 1:maxtrials
        empty!(gr.nodecolor)
        ordering = shuffle(collect(keys(gr.g)))
        for node in ordering
            usedneighborcolors = [gr.nodecolor[c] for c in gr.g[node] if haskey(gr.nodecolor, c)]
            gr.nodecolor[node] = badcolor
            for c in colors4[1:N]
                if !(c in usedneighborcolors)
                    gr.nodecolor[node] = c
                    break
                end
            end
        end
        t = length(unique(values(gr.nodecolor)))
        if t < mintrial
            mintrial = t
            minord = deepcopy(gr.nodecolor)
        end
    end
    if length(minord) > 0
        gr.nodecolor = minord
    end
end
 
 
"""
    prettyprintcolors(gr::graph)
 
print out the colored nodes in graph
"""
function prettyprintcolors(gr::Graph)
    println("\nColors for the graph named ", gr.name, ":")
    edgesdone = Vector{Vector{Int}}()
    for (node, neighbors) in gr.g
        if !isempty(neighbors)
            for n in neighbors
                edge = node < n ? [node, n] : [n, node]
                if !(edge in edgesdone)
                    println("    ", edge[1], "-", edge[2], " Color: ",
                        gr.nodecolor[edge[1]], ", ", gr.nodecolor[edge[2]])
                    push!(edgesdone, edge)
                end
            end
        else
            println("    ", node, ": ", gr.nodecolor[node])
        end
    end
    println("\n", length(unique(keys(gr.nodecolor))), " nodes, ",
        length(edgesdone), " edges, ",
        length(unique(values(gr.nodecolor))), " colors.")
end
 
for (name, txt) in [("Ex1", "0-1 1-2 2-0 3"),
    ("Ex2", "1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7"),
    ("Ex3", "1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6"),
    ("Ex4", "1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7")]
    exgraph = Graph(name, txt)
    tryNcolors!(exgraph, 4, 100)
    prettyprintcolors(exgraph)
end
 