104 lines
3.2 KiB
Text
104 lines
3.2 KiB
Text
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
|