Styjun

I struggle with the algorithm to create the order in which I will color a graph.
Let's consider the following graph:

import networkx as nx
from matplotlib import pyplot as plt

nodes = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (1, 5), (5, 6), (6, 10), 
 (6, 7), (4, 7), (3, 8), (7, 8), (8, 9), (8, 11)]

# Create the graph
G = nx.Graph()
# Add edges
G.add_edges_from(edges)
# Plot
nx.draw(G, with_labels=True, font_size = 16)
plt.show()

I want to have multiple starting point, called initial_nodes and to create the order around the adjacent nodes. For the graph above, let's consider the starting nodes as the node 2 and 7.

The order would be:

# Step 1: - Initial nodes
order = [2, 7]
# Step 2: - Nodes adjacent to the initial nodes
order = [2, 7, 1, 3, 4, 6, 8]
# Step 3: - Nodes adjacent to the nodes added in the previous step
# If they are not already present in the order...
order = [2, 7, 1, 3, 4, 6, 8, 5, 10, 9, 11]

I feel like a recursive approach should work nice, but I can't figure how to write it down. Any idea?

EDIT: All the problem described a bit further.

Current algorithm to create the order:

def create_node_order(graph, initial_nodes):
 """
 Create the node order.
 """
 # Initialization
 order = initial_nodes
 next_nodes = list()

 for node in initial_nodes:
 for adj_node in graph.adj[node].keys():
 if adj_node not in order:
 order.append(adj_node)
 next_nodes.append(adj_node)

 while len(next_nodes) != 0:

 for node in next_nodes:
 for adj_node in graph.adj[node].keys():
 if adj_node not in order:
 order.append(adj_node)
 next_nodes.append(adj_node)

 next_nodes.remove(node)

 return order

Note that is was not a requirement, or even proven to be possible, to result in an optimal coloring given the approach of iterating over "circles" "radiating" out from some start nodes. Given my understand of the algorithm described and what the requirements are, I would use something like this:

Pseudocode:

// no need for more than four colors IFF the algorithm is optimal and the graph is planar, otherwise extend
colors = [red, blue, green, yellow]
// initialize
graph = SomeSuitableDataStructure(data)
queue = [graph(2), graph(7)] // starting nodes
for node in graph.nodes:
 node.visited = False
 node.color = Undefined

while not queue.empty():
 node = queue.pop()
 node.visited = True
 node.color = first_color_not_in([n.color for n in node.neighbors()])
 for neighbor in node.neighbors():
 if not neighbor.visited: queue.push_back(neighbor)

Implementing first_color_not_in() and handling the Undefined color is left as an excercise to the reader.