Создать определенный порядок узлов для задачи раскраски графа

Question

Я борюсь с алгоритмом, чтобы создать порядок, в котором я буду раскрашивать график.Давайте рассмотрим следующий график:

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()

Я хочу иметь несколько начальных точек, называемых initial_nodes, и создать порядок вокруг соседнейузлы.Для приведенного выше графика давайте рассмотрим начальные узлы как узлы 2 и 7.

Порядок будет такой:

# 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]

Мне кажется, рекурсивный подход должен работать хорошо, но я не могу понять, как записать это.Есть идеи?

РЕДАКТИРОВАТЬ: Вся описанная проблема немного Далее .

Текущий алгоритм для создания заказа:

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

Answer 1

Обратите внимание, что это не было обязательным требованием или даже доказано, что это не может привести к оптимальной раскраске, учитывая подход итерации по "окружностям", "излучающим" из некоторых начальных узлов.Учитывая мое понимание описанного алгоритма и его требований, я бы использовал что-то вроде этого:

Псевдокод:

// 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)

Реализация first_color_not_in() и обработка цвета Undefined осталосьв качестве упражнения для читателя.