Skip to content

Instantly share code, notes, and snippets.

@Epivalent

Epivalent/gist:7cf7647e8a52d6d8ca58106d276fa648

Last active March 20, 2025 10:38
Show Gist options
  • Save Epivalent/7cf7647e8a52d6d8ca58106d276fa648 to your computer and use it in GitHub Desktop.
Save Epivalent/7cf7647e8a52d6d8ca58106d276fa648 to your computer and use it in GitHub Desktop.
Download ZIP
ngravin-d-list-colouring-WiP.ipynb
Raw
gistfile1.txt
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from sage.all import Graph, matrix, ZZ
import unittest
# ============================================================
# Data Representation and Helper Functions
# ============================================================
def load_problem(problem_def):
"""
Parses a problem definition and returns:
- G: a Sage Graph constructed from the given vertices and edges.
- color_lists: a dictionary mapping each vertex to a set of admissible colours.
"""
G = Graph()
G.add_vertices(problem_def["vertices"])
G.add_edges(problem_def["edges"])
color_lists = {v: set(problem_def["color_lists"][v]) for v in problem_def["vertices"]}
return G, color_lists
def is_distinguished(u, v, color_lists):
"""
Checks if the pair (u, v) is distinguished by a colour.
Returns a colour c in L(u) that is not in L(v) if one exists; otherwise, returns None.
"""
for c in color_lists[u]:
if c not in color_lists[v]:
return c
return None
def has_excess_list(v, G, color_lists):
"""
Returns True if vertex v has an 'excess' list, i.e. |L(v)| > degree(v) in graph G.
"""
return len(color_lists[v]) > G.degree(v)
# ============================================================
# Greedy List-Colouring Helper
# ============================================================
def greedy_list_coloring(H, color_lists):
"""
Greedy list-colouring algorithm for graph H given color lists.
Returns a dictionary mapping vertices in H to a colour.
Assumes that a valid colouring exists.
"""
coloring = {}
order = H.vertices() # a simple order; may be improved later
for v in order:
forbidden = {coloring[u] for u in H.neighbors(v) if u in coloring}
available = color_lists[v] - forbidden
if available:
coloring[v] = min(available) # choose smallest for determinism
else:
raise ValueError(f"No available colour for vertex {v}!")
return coloring
# ============================================================
# Block Tree Computation and BFS Ordering
# ============================================================
def compute_block_tree(G):
"""
Compute the blocks and cut vertices using Sage's Tarjan implementation,
then build the block tree as a bipartite graph.
Returns:
- BT: a Graph representing the block tree.
- block_list: a list of blocks (each block is a list of vertices).
- cut_vertices: a list of cut vertices.
- block_labels: a dictionary mapping block index to its label in BT.
"""
block_list, cut_vertices = G.blocks_and_cut_vertices(algorithm='Tarjan_Boost', sort=True)
BT = Graph()
block_labels = {}
for i, block in enumerate(block_list):
label = f"B{i}"
block_labels[i] = label
BT.add_vertex(label)
for v in cut_vertices:
BT.add_vertex(v)
for i, block in enumerate(block_list):
for v in block:
if v in cut_vertices:
BT.add_edge(block_labels[i], v)
return BT, block_list, cut_vertices, block_labels
def bfs_block_order(BT, start):
"""
Perform BFS on the block tree BT starting from 'start'.
Returns a list of vertices in the order visited.
"""
order = []
visited = set()
queue = [start]
visited.add(start)
while queue:
current = queue.pop(0)
order.append(current)
for neighbor in BT.neighbors(current):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
# ============================================================
# Combinatorial Search Functions
# ============================================================
def search_distinguished_pair(G, block, cut_vertex, color_lists):
"""
Given a block (a list of vertices) and its unique cut vertex,
search for a pair (u, v) within the block (with u ≠ cut_vertex) such that
there exists a colour in L(u) that is not in L(v).
Returns (u, v, colour) if such a pair is found; otherwise, None.
"""
vertices = [v for v in block if v != cut_vertex]
for i in range(len(vertices)):
u = vertices[i]
for j in range(i + 1, len(vertices)):
v = vertices[j]
if u in G.neighbors(v): # ensure they are adjacent in the induced subgraph
c = is_distinguished(u, v, color_lists)
if c is not None:
return u, v, c
c = is_distinguished(v, u, color_lists)
if c is not None:
return v, u, c
return None
def find_good_pair(G, block, cut_vertex):
"""
In a Brooks subgraph (block with exactly one cut vertex), try to find
two vertices u and v (from block \ {cut_vertex}) that are not adjacent.
Returns (u, v) if found; otherwise, None.
"""
vertices = [v for v in block if v != cut_vertex]
for i in range(len(vertices)):
for j in range(i+1, len(vertices)):
u = vertices[i]
v = vertices[j]
if not G.has_edge(u, v):
return (u, v)
return None
# ============================================================
# Brooks Subroutine (Delta-Colouring via Constructive Brooks' Theorem)
# ============================================================
def brooks_subroutine(G, block, v0, color_lists):
"""
Attempts to delta-colour the block (a two-connected subgraph that is neither
a clique nor an odd cycle), where v0 is the unique cut vertex in the block.
Returns a dictionary mapping vertices in block to their assigned colour.
"""
H = G.subgraph(block)
try:
T = H.dfs_tree(v0)
except Exception as e:
T = H # fallback if DFS tree cannot be computed
def is_path_tree(T):
# Build a dictionary of vertex degrees in T.
degrees = {v: T.degree(v) for v in T.vertices()}
endpoints = [v for v, d in degrees.items() if d == 1]
if len(endpoints) != 2:
return False
for v, d in degrees.items():
if v not in endpoints and d != 2:
return False
return True
# Try to identify a "good pair" (two non-adjacent vertices in block\{v0})
if not is_path_tree(T):
good_pair = find_good_pair(H, block, v0)
else:
good_pair = find_good_pair(H, block, v0)
coloring = {}
if good_pair is not None:
u, v = good_pair
common_colors = color_lists[u] & color_lists[v]
if not common_colors:
raise ValueError("No common colour for good pair, which should not occur if lists are equal.")
chosen_color = next(iter(common_colors))
coloring[u] = chosen_color
coloring[v] = chosen_color
remaining_vertices = [x for x in block if x not in (u, v)]
H_prime = H.subgraph(remaining_vertices)
try:
coloring_rest = greedy_list_coloring(H_prime, color_lists)
except ValueError as e:
raise ValueError("Greedy colouring failed in Brooks subroutine: " + str(e))
coloring.update(coloring_rest)
else:
# If no good pair is found, check if H is an even cycle.
if H.is_cycle() and len(H.vertices()) % 2 == 0:
verts = H.vertices()
L = list(color_lists[verts[0]])
if len(L) < 2:
raise ValueError("Not enough colours for even cycle colouring.")
c1, c2 = L[0], L[1]
for i, v in enumerate(verts):
coloring[v] = c1 if i % 2 == 0 else c2
else:
try:
coloring = greedy_list_coloring(H, color_lists)
except ValueError as e:
raise ValueError("Greedy colouring fallback failed in Brooks subroutine: " + str(e))
return coloring
# ============================================================
# Visualization Functions
# ============================================================
def plot_block_tree(BT, filename=None):
"""
Plot the block tree. Optionally save the plot to a file if filename is provided.
"""
p = BT.plot(vertex_labels=True)
if filename:
p.save(filename)
p.show()
def plot_brooks_subgraph_with_good_pair(G, block, cut_vertex, good_pair=None, filename=None):
"""
Plot the subgraph corresponding to the block.
If a good pair is provided (a tuple of vertices), highlight them.
The cut vertex is shown in blue; good pair vertices (if any) in red;
and all other vertices in green.
"""
H = G.subgraph(block)
colors = {v: 'green' for v in H.vertices()}
if good_pair is not None:
for v in good_pair:
colors[v] = 'red'
colors[cut_vertex] = 'blue'
vertex_color_list = [colors[v] for v in H.vertices()]
p = H.plot(vertex_labels=True, vertex_colors=vertex_color_list)
if filename:
p.save(filename)
p.show()
# ============================================================
# Additional Helper Functions
# ============================================================
def recursive_deletion_coloring(G, color_lists):
"""
Implements the recursive deletion procedure.
While there is a vertex v with |L(v)| > deg(v), remove it (and push onto a stack).
Then, in reverse order, assign colours ensuring that each vertex gets a colour
from its list not used by its already coloured neighbours.
Returns a dictionary mapping vertices to their assigned colour.
"""
stack = []
G_current = G.copy()
color_lists_current = {v: set(color_lists[v]) for v in G.vertices()}
# Remove vertices with excess list.
while True:
found = False
for v in list(G_current.vertices()):
if len(color_lists_current[v]) > G_current.degree(v):
found = True
stack.append((v, color_lists_current[v].copy()))
G_current.delete_vertex(v)
break
if not found:
break
coloring = {}
while stack:
v, L_v = stack.pop()
forbidden = set()
for u in G.neighbors(v):
if u in coloring:
forbidden.add(coloring[u])
available = L_v - forbidden
if not available:
raise ValueError(f"No available colour for vertex {v} in recursive deletion!")
chosen = min(available)
coloring[v] = chosen
return coloring
def is_clique(block, G):
"""
Returns True if the induced subgraph on 'block' is a clique.
"""
H = G.subgraph(block)
n = len(H.vertices())
return len(H.edges()) == n*(n-1)/2
def is_odd_cycle(block, G):
"""
Returns True if the induced subgraph on 'block' is an odd cycle.
"""
H = G.subgraph(block)
n = len(H.vertices())
if n < 3:
return False
if not H.is_cycle():
return False
return n % 2 == 1
# ============================================================
# Main d-List Colouring Routine
# ============================================================
def d_list_coloring(G, color_lists):
"""
Main procedure for d-list colouring.
Given a graph G and a d-list assignment (color_lists) satisfying |L(v)| >= deg(v)
for each vertex v, this function either returns a valid colouring (a dictionary
mapping each vertex to a colour from its list) or raises an error.
"""
# Base case: if G is empty, return an empty colouring.
if len(G.vertices()) == 0:
return {}
# Step 1: Look for a vertex with an excess list.
for v in G.vertices():
if len(color_lists[v]) > G.degree(v):
return recursive_deletion_coloring(G, color_lists)
# Step 2: All vertices have tight lists. Compute block decomposition.
BT, block_list, cut_vertices, block_labels = compute_block_tree(G)
# Find a leaf block (i.e. one containing at most one cut vertex).
leaf_block = None
for block in block_list:
cut_count = sum(1 for v in block if v in cut_vertices)
if cut_count <= 1:
leaf_block = block
break
if leaf_block is None:
leaf_block = block_list[0]
# Choose the unique cut vertex if present; otherwise, pick an arbitrary vertex.
v0 = None
for v in leaf_block:
if v in cut_vertices:
v0 = v
break
if v0 is None:
v0 = leaf_block[0]
# Step 3: Attempt to find a distinguished pair in the leaf block.
result = search_distinguished_pair(G, leaf_block, v0, color_lists)
if result is not None:
u, v, chosen_color = result
# Colour vertex u with chosen_color.
partial_coloring = {u: chosen_color}
# Remove u from G.
G_new = G.copy()
G_new.delete_vertex(u)
# Update colour lists for neighbours of u.
color_lists_new = {w: set(color_lists[w]) for w in G_new.vertices()}
for w in G.neighbors(u):
if chosen_color in color_lists_new[w]:
color_lists_new[w].remove(chosen_color)
coloring_rest = d_list_coloring(G_new, color_lists_new)
partial_coloring.update(coloring_rest)
return partial_coloring
else:
# No distinguished pair found.
if is_clique(leaf_block, G) or is_odd_cycle(leaf_block, G):
# Reduction: colour all vertices in leaf_block except v0 using greedy colouring.
H = G.subgraph(leaf_block)
coloring_block = greedy_list_coloring(H, color_lists)
if v0 in coloring_block:
del coloring_block[v0]
# Update L(v0): remove colours used on its neighbours in the block.
used = {coloring_block[w] for w in coloring_block if w in G.neighbors(v0)}
color_lists[v0] = color_lists[v0] - used
# Remove leaf_block \ {v0} from G.
G_new = G.copy()
for v in leaf_block:
if v != v0:
G_new.delete_vertex(v)
coloring_rest = d_list_coloring(G_new, color_lists)
coloring_rest.update(coloring_block)
return coloring_rest
else:
# Otherwise, apply the Brooks subroutine on the block.
coloring_block = brooks_subroutine(G, leaf_block, v0, color_lists)
# Remove leaf_block \ {v0} from G.
G_new = G.copy()
for v in leaf_block:
if v != v0:
G_new.delete_vertex(v)
used = {coloring_block[w] for w in coloring_block if w in G.neighbors(v0)}
color_lists[v0] = color_lists[v0] - used
coloring_rest = d_list_coloring(G_new, color_lists)
coloring_rest.update(coloring_block)
return coloring_rest
# ============================================================
# Test Suite
# ============================================================
class TestDataRepresentation(unittest.TestCase):
def setUp(self):
self.problem_def = {
"vertices": [1, 2, 3, 4],
"edges": [(1,2), (2,3), (3,4), (4,1)],
"color_lists": {
1: [1,2],
2: [2,3],
3: [1,3],
4: [1,2,3]
}
}
self.G, self.color_lists = load_problem(self.problem_def)
def test_graph_structure(self):
self.assertEqual(len(self.G.vertices()), 4)
self.assertEqual(len(self.G.edges()), 4)
def test_color_lists_conversion(self):
self.assertTrue(isinstance(self.color_lists[1], set))
self.assertEqual(self.color_lists[1], {1,2})
def test_excess_list_property(self):
self.assertTrue(has_excess_list(4, self.G, self.color_lists))
self.assertFalse(has_excess_list(1, self.G, self.color_lists))
def test_distinguished_colour(self):
self.assertEqual(is_distinguished(1, 2, self.color_lists), 1)
self.assertEqual(is_distinguished(2, 3, self.color_lists), 2)
self.assertEqual(is_distinguished(3, 1, self.color_lists), 3)
self.assertEqual(is_distinguished(1, 3, self.color_lists), 2)
class TestBlockTreeAndSearch(unittest.TestCase):
def setUp(self):
problem_def = {
"vertices": list(range(1, 11)),
"edges": [
(1,2), (2,3), (3,1), # Cycle block 1
(3,4), # Articulation between blocks
(4,5), (5,6), (6,4), # Cycle block 2
(4,7), # Articulation between blocks
(7,8), (8,9), (9,7), # Cycle block 3
(7,10) # Leaf block
],
"color_lists": {
1: [1,2,3],
2: [1,2,3],
3: [1,2,3,4],
4: [1,2,3,4,5],
5: [2,3,4],
6: [2,3,4],
7: [1,2,3,4],
8: [1,3,4],
9: [1,3,4],
10: [2,3]
}
}
self.G, self.color_lists = load_problem(problem_def)
self.BT, self.block_list, self.cut_vertices, self.block_labels = compute_block_tree(self.G)
def test_blocks_and_cut_vertices(self):
for v in [3,4,7]:
self.assertIn(v, self.cut_vertices)
self.assertGreaterEqual(len(self.block_list), 3)
def test_block_tree_structure(self):
expected_nodes = set([f"B{i}" for i in range(len(self.block_list))] + self.cut_vertices)
self.assertEqual(set(self.BT.vertices()), expected_nodes)
def test_bfs_order(self):
start = self.block_labels[0]
order = bfs_block_order(self.BT, start)
self.assertEqual(set(order), set(self.BT.vertices()))
def test_search_distinguished_pair(self):
for block in self.block_list:
cuts_in_block = [v for v in block if v in self.cut_vertices]
if len(cuts_in_block) == 1:
cut_v = cuts_in_block[0]
result = search_distinguished_pair(self.G, block, cut_v, self.color_lists)
if result is not None:
u, v, c = result
self.assertTrue(u in block and v in block and c in self.color_lists[u])
def test_find_good_pair(self):
for block in self.block_list:
cuts_in_block = [v for v in block if v in self.cut_vertices]
if len(cuts_in_block) == 1:
cut_v = cuts_in_block[0]
good_pair = find_good_pair(self.G, block, cut_v)
if good_pair is not None:
u, v = good_pair
self.assertFalse(self.G.has_edge(u, v))
class TestBrooksSubroutine(unittest.TestCase):
def setUp(self):
problem_def = {
"vertices": list(range(1, 11)),
"edges": [
(1,2), (2,3), (3,1),
(3,4),
(4,5), (5,6), (6,4),
(4,7),
(7,8), (8,9), (9,7),
(7,10)
],
"color_lists": {
1: [1,2,3],
2: [1,2,3],
3: [1,2,3,4],
4: [1,2,3,4,5],
5: [2,3,4],
6: [2,3,4],
7: [1,2,3,4],
8: [1,3,4],
9: [1,3,4],
10: [2,3]
}
}
self.G, self.color_lists = load_problem(problem_def)
_, self.block_list, self.cut_vertices, _ = compute_block_tree(self.G)
def test_brooks_subroutine(self):
for block in self.block_list:
cuts_in_block = [v for v in block if v in self.cut_vertices]
if len(cuts_in_block) == 1 and len(block) > 2:
v0 = cuts_in_block[0]
try:
col = brooks_subroutine(self.G, block, v0, self.color_lists)
H = self.G.subgraph(block)
for v in H.vertices():
for w in H.neighbors(v):
if v in col and w in col:
self.assertNotEqual(col[v], col[w])
except Exception as e:
self.fail("brooks_subroutine failed: " + str(e))
class TestRecursiveDeletion(unittest.TestCase):
def setUp(self):
self.problem_def = {
"vertices": [1,2,3],
"edges": [(1,2), (2,3)],
"color_lists": {
1: [1,2,3],
2: [1,2],
3: [1,2,3]
}
}
self.G, self.color_lists = load_problem(self.problem_def)
def test_recursive_deletion_coloring(self):
coloring = recursive_deletion_coloring(self.G, self.color_lists)
for v in self.G.vertices():
for w in self.G.neighbors(v):
if v in coloring and w in coloring:
self.assertNotEqual(coloring[v], coloring[w])
class TestDListColoring(unittest.TestCase):
def setUp(self):
# A nontrivial graph example.
self.problem_def = {
"vertices": list(range(1, 16)),
"edges": [
(1,2), (2,3), (3,1), # Cycle 1
(3,4),
(4,5), (5,6), (6,4), # Cycle 2
(4,7),
(7,8), (8,9), (9,7), # Cycle 3
(7,10),
(10,11), (11,12), (12,10), # Cycle 4
(10,13),
(13,14), (14,15), (15,13) # Cycle 5
],
"color_lists": {
1: [1,2,3,4],
2: [1,2,3,4],
3: [1,2,3,4],
4: [1,2,3,4],
5: [1,2,3,4],
6: [1,2,3,4],
7: [1,2,3,4],
8: [1,2,3,4],
9: [1,2,3,4],
10: [1,2,3,4],
11: [1,2,3,4],
12: [1,2,3,4],
13: [1,2,3,4],
14: [1,2,3,4],
15: [1,2,3,4]
}
}
self.G, self.color_lists = load_problem(self.problem_def)
def test_d_list_coloring(self):
try:
coloring = d_list_coloring(self.G, self.color_lists)
for v in self.G.vertices():
for w in self.G.neighbors(v):
if v in coloring and w in coloring:
self.assertNotEqual(coloring[v], coloring[w])
except Exception as e:
self.fail("d_list_coloring failed: " + str(e))
def test_proper_colouring(self):
"""
Extra test: Verify that for every edge, the colours of its endpoints are different.
"""
coloring = d_list_coloring(self.G, self.color_lists)
for (u, v) in self.G.edges():
self.assertNotEqual(coloring[u], coloring[v], f"Edge ({u},{v}) has same colour {coloring[u]}.")
class TestVisualization(unittest.TestCase):
def setUp(self):
self.problem_def = {
"vertices": list(range(1, 11)),
"edges": [
(1,2), (2,3), (3,1),
(3,4),
(4,5), (5,6), (6,4),
(4,7),
(7,8), (8,9), (9,7),
(7,10)
],
"color_lists": {
1: [1,2,3,4],
2: [1,2,3,4],
3: [1,2,3,4],
4: [1,2,3,4],
5: [1,2,3,4],
6: [1,2,3,4],
7: [1,2,3,4],
8: [1,2,3,4],
9: [1,2,3,4],
10: [1,2,3,4]
}
}
self.G, self.color_lists = load_problem(self.problem_def)
self.BT, self.block_list, self.cut_vertices, self.block_labels = compute_block_tree(self.G)
def test_plot_block_tree(self):
try:
plot_block_tree(self.BT)
except Exception as e:
self.fail(f"plot_block_tree raised an exception: {e}")
def test_plot_brooks_subgraph_with_good_pair(self):
for block in self.block_list:
cuts_in_block = [v for v in block if v in self.cut_vertices]
if len(cuts_in_block) == 1:
cut_v = cuts_in_block[0]
good_pair = find_good_pair(self.G, block, cut_v)
try:
plot_brooks_subgraph_with_good_pair(self.G, block, cut_v, good_pair)
except Exception as e:
self.fail(f"plot_brooks_subgraph_with_good_pair raised an exception: {e}")
break
# ============================================================
# New: Run Example with Adjacency Matrix Input (without the matrix content)
# ============================================================
def load_graph_from_adjacency_matrix(adj_str):
"""
Reads a multiline string representing an adjacency matrix.
Lines starting with "adj matrix" are ignored.
Returns a Sage Graph constructed from the matrix.
"""
lines = adj_str.strip().splitlines()
data = []
for line in lines:
if "adj matrix" in line.lower():
continue
parts = line.strip().split(',')
if not parts:
continue
row = [int(x.strip()) for x in parts if x.strip() != '']
data.append(row)
M = matrix(ZZ, data)
G = Graph(M)
return G
def run_example():
# An empty multiline string for the adjacency matrix.
# Fill this variable with your adjacency matrix data.
adj_str = """\
0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
1,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,1,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,1,1,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,1,1,1,0,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,1,1,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,1,0,0,1,1
0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,1,1,0,0,1,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,1,1,0,0,1,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,1,1,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,1,1,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,1,1,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0
"""
G = load_graph_from_adjacency_matrix(adj_str)
print("Loaded graph with {} vertices and {} edges.".format(len(G.vertices()), len(G.edges())))
# Assign the standard 4-colour list [1,2,3,4] to each vertex.
color_lists = {v: [1, 2, 3, 4] for v in G.vertices()}
# Run the d-list colouring algorithm.
try:
coloring = d_list_coloring(G, color_lists)
except Exception as e:
print("d_list_coloring failed:", e)
return
print("Coloring obtained:", coloring)
# Map colour numbers to actual color names.
color_mapping = {1: "red", 2: "green", 3: "blue", 4: "yellow"}
vertex_colors = [color_mapping[coloring[v]] if v in coloring else "black" for v in G.vertices()]
# Plot the coloured graph.
p = G.plot(vertex_labels=True, vertex_colors=vertex_colors)
p.show()
# ============================================================
# Main: Run Test Suite or Example
# ============================================================
if __name__ == '__main__':
# Uncomment the following line to run the test suite:
# unittest.main()
# Otherwise, run the example with the adjacency matrix.
run_example()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment