A python script to verify a graph coloring. This is to aid in solving https://www.interviewcake.com/question/python/graph-coloring

bad-coloring.json

[
    [1,1],
    [2,1],
    [3,3]
]

color.py

#!/usr/bin/env python

# generate a coloring for an undirected graph where no two neighbors share the
# same color, using only degree+1 colors.

# A note on notation:
# this is a "digraph": {1:set([2,3]), 2:set(1,3), 3:set(1,2)}
# this is a "flat digraph": [[1,[2,3]],[2,[1,3]],[3,[1,2]]]
# this is a "flat graph": [[1,2],[2,3],[1,3]]

import json
import sys

# flatten a digraph.
# {1:set([2,3]), 2:set(1,3), 3:set(1,2)} -> [[1,[2,3]],[2,[1,3]],[3,[1,2]]]
def flatten(digraph):
    g = []
    for node, neighbors in digraph.iteritems():
        g.append([node, list(neighbors)])
    return g

# transform a list of edges into a directed graph representation.
# [[1,2],[2,3],[1,3]] -> {1:set([2,3]), 2:set(1,3), 3:set(1,2)}
def edges_to_digraph(edges):
    graph = {}
    for a,b in edges:
        s = graph.get(a, set())
        s.add(b)
        graph[a] = s
        s = graph.get(b, set())
        s.add(a)
        graph[b] = s
    return graph

# calculate the degree of a flattened digraph.
# [[1,[2,3]],[2,[1,3]],[3,[1,2]]] -> 2
def degree(flat_digraph):
    d = 0
    for node, neighbors in flat_digraph:
        d = max(d, len(neighbors))
    return d

# recursively color a graph.
# for a traversal, try to color the head node, then recurse.
# 'colored' are the already-colored nodes.
# 'uncolored' are the yet-to-be-colored nodes.
# 'colors' is the list of colors.
# as the function recurses, nodes will move from uncolored to colored,
# until uncolored is empty.
def recur_color(colored, uncolored, colors):
    # if there are no more uncolored nodes, we are done.
    if len(uncolored) == 0:
        return colored
    # grab the head node and try to color it.
    node, neighbors = uncolored[0]
    # construct the set of colors available to this node.
    available_colors = set(colors)
    for neighbor in neighbors:
        if neighbor in colored:
            to_remove = colored[neighbor]
            if to_remove in available_colors:
                available_colors.remove(to_remove)
    # for each available color, try continuing the recursive traversal.
    # if it fails, try the next color.
    for color in available_colors:
        colored[node] = color
        result = recur_color(colored, uncolored[1:], colors)
        if result != None:
            return result
    # oops, we ran out of colors.
    return None

# return a coloring for the flat graph.
# [[1,2],[2,3],[1,3]] -> [[1,1],[2,2],[3,3]]
def color(edges):
    digraph = edges_to_digraph(edges)
    flat = flatten(digraph)
    colors = range(1, degree(flat)+2)
    return recur_color({}, flat, colors)

if __name__ == "__main__":
    with open(sys.argv[1]) as f:
        graph = json.load(f)
    coloring = color(graph)
    if coloring is None:
        sys.stderr.write("Error: could not find a coloring for the graph.\n")
        sys.exit(2)
    print json.dumps([[node,color] for node, color in coloring.iteritems()])

gen-full-graph.py

#!/usr/bin/env python

# generate a fully-connected undirected graph (as JSON)

import sys
import json

nodecount = int(sys.argv[1])

graph = set()

for i in range(1, nodecount+1):
    neighbors = set(range(1, nodecount+1))
    neighbors.remove(i)
    for neighbor in neighbors:
        if i < neighbor:
            edge = (i,neighbor)
        else:
            edge = (neighbor,i)
        graph.add(edge)

print json.dumps(list(graph))

gen-graph.py

#!/usr/bin/env python

# generate an undirected graph (as JSON) with N nodes and of degree M.
# do this by starting with a fully-connected graph and then removing nodes until you reach degree M.

# A note on notation:
# this is a "digraph": {1:set([2,3]), 2:set(1,3), 3:set(1,2)}
# this is a "flat digraph": [[1,[2,3]],[2,[1,3]],[3,[1,2]]]
# this is a "flat graph": [[1,2],[2,3],[1,3]]

import sys
import json
import random

# generate a fully-connected flat graph with n nodes.
def fully_connected(n):
    graph = set()
    for i in range(1, n+1):
        neighbors = set(range(1, n+1))
        neighbors.remove(i)
        for neighbor in neighbors:
            if i < neighbor:
                edge = (i,neighbor)
            else:
                edge = (neighbor,i)
            graph.add(edge)
    return list(graph)

# flatten a digraph.
# {1:set([2,3]), 2:set(1,3), 3:set(1,2)} -> [[1,[2,3]],[2,[1,3]],[3,[1,2]]]
def flatten_digraph(digraph):
    g = []
    for node, neighbors in digraph.iteritems():
        g.append([node, list(neighbors)])
    return g

# transform a list of edges into a directed graph representation.
# [[1,2],[2,3],[1,3]] -> {1:set([2,3]), 2:set(1,3), 3:set(1,2)}
def flatgraph_to_digraph(edges):
    graph = {}
    for a,b in edges:
        s = graph.get(a, set())
        s.add(b)
        graph[a] = s
        s = graph.get(b, set())
        s.add(a)
        graph[b] = s
    return graph

# calculate the degree of a flat graph.
# [[1,2],[2,3],[1,3]] -> 2
def degree_flatgraph(flatgraph):
    return degree_flatdigraph(flatten_digraph(flatgraph_to_digraph(flatgraph)))

# calculate the degree of a flat digraph.
# [[1,[2,3]],[2,[1,3]],[3,[1,2]]] -> 2
def degree_flatdigraph(flatdigraph):
    d = 0
    for node, neighbors in flatdigraph:
        d = max(d, len(neighbors))
    return d

def degree_of_flatgraph_node(flatgraph, node_id):
    return len(flatgraph_to_digraph(flatgraph)[node_id])

# return a flatgraph with enough nodes removed to meet the desired degree.
def truncate(flatgraph, desired_degree):
    tries = 0
    while degree_flatgraph(flatgraph) > desired_degree and tries < 10000:
        tries += 1
        index_to_remove = random.choice(range(len(flatgraph)))
        edge = flatgraph[index_to_remove]
        if degree_of_flatgraph_node(flatgraph, edge[0]) > desired_degree and degree_of_flatgraph_node(flatgraph, edge[1]) > desired_degree:
            del flatgraph[index_to_remove]
    if tries == 10000:
        raise Exception("Infinite loop")
    return flatgraph

if __name__ == "__main__":
    nodecount = int(sys.argv[1])
    degree = int(sys.argv[2])
    print json.dumps(truncate(fully_connected(nodecount), degree))

graph.json

[
    [1,2],
    [1,3],
    [2,3]
]

ok-coloring.json

[
    [1,1],
    [2,2],
    [3,3]
]

output.txt

# verify that a coloring of an undirected graph does not share a color between any two neighbors:
$ ./verify-coloring.py graph.json ok-coloring.json 
True

$ ./verify-coloring.py graph.json bad-coloring.json 
False

# render a graph and a coloring as graphviz "dot" markup:
$ ./to-dot.py graph.json ok-coloring.json
graph {
node [style="filled", colorscheme="pastel19"];
1 -- 2;
1 -- 3;
2 -- 3;
1 [color=1];
2 [color=2];
3 [color=3];
}

# paste the above into http://www.webgraphviz.com/ or run the following to see it locally:
$ ./to-dot.py graph.json ok-coloring.json | dot -Tpng > out.png && open out.png

# generate a fully-connected undirected graph with 3 nodes:
$ ./gen-full-graph.py 3
[[1, 2], [1, 3], [2, 3]]

# generate an undirected graph with 6 nodes of degree 3:
$ ./gen-graph.py 6 3
[[1, 2], [1, 3], [4, 6], [4, 5], [1, 5], [2, 6], [3, 6], [2, 5], [3, 4]]

to-dot.py

#!/usr/bin/env python

# render a graph and a coloring as graphviz "dot" markup.
# you can then paste it into http://www.webgraphviz.com/
# or run ./to-dot.py graph.json ok-coloring.json | dot -Tpng > out.png && open out.png

import json
import sys

def dot_edges(graph):
    dot = ""
    for a,b in graph:
        dot += "%s -- %s;\n" % (a,b)
    return dot

def dot_coloring(coloring):
    dot = ""
    for node, color in coloring:
        dot += "%s [color=%s];\n" % (node, color)
    return dot

def to_dot(graph, coloring):
    dot = "graph {\n"
    dot += "node [style=\"filled\", colorscheme=\"pastel19\"];\n"
    dot += dot_edges(graph)
    dot += dot_coloring(coloring)
    dot += "}"
    return dot

if __name__ == "__main__":
    with open(sys.argv[1]) as f:
        graph = json.load(f)
    with open(sys.argv[2]) as f:
        coloring = json.load(f)
    print to_dot(graph, coloring)

verify-coloring.py

#!/usr/bin/env python

# verify that a coloring for an undirected graph does not have any neighbors with the same color.

import json
import sys

def verify_coloring(graph, coloring):
    # make a node -> color map:
    colormap = {}
    for node, color in coloring:
        colormap[node] = color
    # run through the nodes, checking the coloring
    for a, b in graph:
        if colormap[a] == colormap[b]:
            return False
    return True

if __name__ == "__main__":
    with open(sys.argv[1]) as f:
        graph = json.load(f)
    with open(sys.argv[2]) as f:
        coloring = json.load(f)
    print verify_coloring(graph, coloring)