python 中有向图的单调着色

Question

一直在研究有向图单调着色算法的实现。这意味着以下规范：颜色数应最少，边开始的节点的颜色数必须小于边结束的节点的颜色数（例如：1 -> 3, 3 - > 10).如果有帮助，数据中没有循环。作为输入，我们有两个字典：{node number: {nodes that connect to it}, ... } 和 {node number: {nodes that it connects to}, ...}。

程序的结果是所需的最少颜色数。

我的代码似乎可以正常工作，但我不知道它是否真的找到了最小值，而不是任何合适的数字。这是：

import numpy as np

def check(cols, curr):
  # this is basically the same thing as in the main function, but recursive.
  if curr in new:
    for i in new[curr]:
      if cols[i] >= cols[curr]:
        cols[i] = cols[curr] - 1
        cols = check(cols, i)

  if curr in new1:
    for i in new1[curr]:
      if cols[i] <= cols[curr]:
        cols[i] = cols[curr] + 1
        cols = check(cols, i)

  return cols

def get_ans():
  cols = [-1 for i in range(ndots)] 

  for g in range(ndots):
    print(g)
    print(cols)

    
    if g in new:
      to = [cols[_] for _ in new[g]] # color of nodes connected to this one
      toi = list(new[g])             # index of nodes connected to this one
    else: 
      to = set()
      toi = set()
    if g in new1:
      fr = [cols[_] for _ in new1[g]] # color of nodes this one is connected to
      fri = list(new1[g])             # index of nodes which this one connects to
    else: 
      fr = set()
      fri = set()
    print('near', toi, fri)

    for i in range(len(fr)):
      if cols[g] == -1:
        cols[g] = ndots
        cols[fri[i]] = ndots + 1
      elif cols[fri[i]] <= cols[g]: # if the coloring inconsistency is found
        cols[fri[i]] = cols[g] + 1
        cols = check(cols, fri[i])  # check if anything has to be changed

    for i in range(len(to)):
      if cols[g] == -1:
        cols[g] = ndots
        cols[toi[i]] = ndots - 1
      elif cols[toi[i]] >= cols[g]: # if the coloring inconsistency is found
        cols[toi[i]] = cols[g] - 1
        cols = check(cols, toi[i]) # check if anything has to be changed

    # print(cols)

  return len(np.unique(cols))


ndots = 8 # number nodes
new = {0: {1, 2}, 3: {1}, 5: {1, 4, 7}, 6: {2, 4}, 4: {0}, 2: {3}, 7: {3, 6}}  
new1 = new 
new = {}
for i in new1:
  for j in new1[i]:
    if j not in new: new[j] = set()
    new[j].add(i)

temp = new
new = new1
new1 = temp

print(new)  # first dictionary
print(new1) # second dictionary

print(get_ans())

对上面的混乱表示抱歉:)。如果您对如何执行此操作有更好的想法（我想要的主要是知道它将是最小值），请帮助我，我们将不胜感激。

Answer 1

您的输入是有向无环图，因此您的节点中有一个topological order。如果按此顺序处理节点，则可以保证在处理 N 本身之前始终处理节点 N 的所有祖先。

因此，只需按此顺序遍历它们并分配

color[node] = max(color[ancestor] for ancestor in ancestors[node]) + 1
              or 0 if no ancestor exists

为您提供符合您要求的颜色。

它将为 DAG 的根赋予颜色 0。对于所有其他节点，这会将颜色设置为该节点可能具有的最低合法值。由于我们按拓扑顺序处理节点，因此我们可以确定所有祖先总是已经设置了正确的值。

注：这个算法思路通常用于求longest path到你DAG中每个节点的长度。这意味着你的问题和求最长路径的长度是一样的，你需要的颜色数总是和这个长度一样。

def monotonic_coloring(adjacencies):
    inverse_adjacencies = [set() for _ in range(len(adjacencies))]
    for node, adjacent_nodes in enumerate(adjacencies):
        for child in adjacent_nodes:
            inverse_adjacencies[child].add(node)

    unprocessed_incoming_edge_count = [
        len(inverse_adjacencies[node]) for node in range(len(adjacencies))
    ]
    without_unprocessed_incoming_edge = {
        node
        for node in range(len(adjacencies))
        if unprocessed_incoming_edge_count[node] == 0
    }
    colors = [0 for _ in range(len(adjacencies))]

    while len(without_unprocessed_incoming_edge) != 0:
        node = without_unprocessed_incoming_edge.pop()
        colors[node] = max(
            (colors[ancestor] + 1 for ancestor in inverse_adjacencies[node]),
            default=0
        )
        for child in adjacencies[node]:
            unprocessed_incoming_edge_count[child] -= 1
            if unprocessed_incoming_edge_count[child] == 0:
                without_unprocessed_incoming_edge.add(child)

    return colors

coloring1 = monotonic_coloring([
    {1, 2}, set(), {3}, {1}, {0}, {1, 4, 7}, {2, 4}, {3, 6},
])
coloring2 = monotonic_coloring([
    {1}, {3}, {3}, {4, 5}, {6}, {6}, set(), {6}, {9}, set(),
])

print(coloring1)
print(coloring2)

import numpy as np
print(len(np.unique(coloring2)))

如果我用第二张图调用你的代码，我得到输出 6，其中只需要 5 种不同的颜色。似乎主要问题是图中断开连接的部分（节点 8 和 9）。您可以使用以下输入重现此内容：

new = {0: {1}, 1: {3}, 2: {3}, 3: {4, 5}, 4: {6}, 5: {6}, 6: set(), 7: {6}, 8: {9}, 9: set()}
ndots = len(new)

通过图形传播变化的递归方法可以工作，但它的时间复杂度会很差运行因为对于错误的输入，您将不得不再次通过图形的同一部分传播大量变化又一次。

python 中有向图的单调着色

Monotonic coloring of the directed graph in python

python

graph

directed-acyclic-graphs