python - 有向无环图的高效遍历

Question

输入:

nd[0];
nd[1, 2];
nd[3, 4];
nd[0, 1];
nd[2, 3];
nd[0, 4];
nd[1, 3];
nd[0, 2];
nd[1, 4];
nd[3];
nd[1, 4];

结果树:

输出:

total_time = sum of all individual wait_time //without overlap

规则:

• 输入代码始终会生成有向无环图
• 每个节点都有一些wait_time值
• 完整的图遍历应计算整个图的总 wait_time
• 所有独立节点必须并行遍历(或者至少时间计算应该这样)
• 如果两个不同节点的wait_time发生重叠，则将考虑最大值，并且遍历时间较短的节点将移动到下一个独立节点
• 除根和叶外(可以有多个根和叶)，所有单个和成对节点都将具有 1 和 2 个传入和传出边

问题 1:如何将给定的输入代码转换为图形以便可以遍历？ (伪代码或任何类型的指导可能会有所帮助)

问题2:如何根据上述规则实现成功遍历？

之前的努力:

• 我能够使用拓扑以线性方式对节点进行排序排序，但我不确定如何才能实现这些具体目标。

• 我根据代码直觉绘制了这张图。

• 边缘上的数字只是为了阐明哪个数字导致了依赖性。

• 我正在使用 python 3

• 我之前的代码似乎没有任何意义这些问题所以我没有包括在内。

Answer 1

1. 创建图表

让a、b、c三个节点具有共同的0属性/依赖关系(到节点0)。如果a在b之前发现，并且b在c之前发现，则边缘应该是a-> b 和 b->c。

为了解决上述规则，请考虑为每个发现的数字建立一个缓存。如果节点包含 0，则将其缓存为 cache[0]。稍后，如果其他节点 b 包含 0，则必须从 cache[0] 到 b 建立一条边，并更新该缓存，以便包含 0 的后续节点从 b 获得边缘。

foreach input as node
  forall dependancy of node
    if discovered[dependancy]
      make_edge(discovered[dependancy], node)
    fi
    discovered[dependancy] = node // apply dependancy "transitivity"

现在要将图表构建为“层”，您可以从叶子(层0)开始，这里[1,4],[0,2],[0,3仅]。然后获取其输出边链接到任何叶子的节点，这里仅[1,4]。 (因为 [1,3] 在链接到作为叶子的 [3] 时，也链接到不是叶子的 [1,4] .所以排除)。然后您就构建了层 1。

While building layer n, you can only add nodes having deps to layer 0 to n-1

更紧凑的说法是针对节点，计算其偏心率(最长路径(此处到叶子))。

要按照您所做的那样打印图表，请注意，您只需按偏心度绘制节点即可，这将显示依赖性的“级别”(它们距叶子/末端有多远，请参阅中的plotByLayers)代码如下)。

计算总时间

我们不需要像上面那样麻烦地构建层。

A node can start only when all of its ancestors end.

当我们制作图表时，祖先就已经确定了。

递归是这样的

n.endAt = max(n.endAt for n in n.ancestors) + n.wait

初始化是针对根节点(没有依赖性)的，我们可以在其中保留等待时间。

nroot.endAt = nroot.wait

<小时/>

关于node.id 表示法i)x,y。 i 是输入中读取的第 i 个节点。 (它的 true id 不知何故。x,y 只是帮助我们可视化的垃圾)。

const input = `
nd[0];
nd[1, 2];
nd[3, 4];
nd[0, 1];
nd[2, 3];
nd[0, 4];
nd[1, 3];
nd[0, 2];
nd[1, 4];
nd[3];
nd[1, 4];`
function makeGraph(input) {
  const nodes = input.trim().split('\n').map((x,i) => {
    const deps = x.match(/\[(.+)\]/)[1]
    return { id: i+')'+deps, v: deps.split(',').map(x => x.trim()) }
  })
  const edges = {}
  const discovered = {}
  nodes.forEach((node, i) => {
    node.v.forEach(digit => {
      if (discovered[digit]) {
        // there is an edge
        edges[discovered[digit].id] = edges[discovered[digit].id] || []
        edges[discovered[digit].id].push(node)
      }
      // apply transitivity a->b->c
      discovered[digit] = node
    })
  }) 
  return {nodes, edges}
}

function computeEccentricity(n, edges) {
  if (typeof(n.eccentricity) !== 'undefined') {
    return n.eccentricity
  }
  if (!edges[n.id]) {// a leaf has no outgoing edges
    n.eccentricity = 0
    return 0
  }
  const distances = Object.values(edges[n.id]).map(n => computeEccentricity(n, edges))
  const min = Math.max(...distances)
  n.eccentricity = 1 + min
  return n.eccentricity
}

function plotByLayers(nodes) {
  const lvls = []
  let m = 0;
  nodes.forEach(n => {
    const i = n.eccentricity
    lvls[i] = lvls[i] || []
    lvls[i].push(n)
    m = i > m ? i: m
  })
  for(let i = m; i >=0 ; --i) {
    console.log(lvls[i].map(x => x.id))
  }
  return lvls
}
const { nodes, edges } = makeGraph(input)
nodes.forEach(n => computeEccentricity(n, edges))
plotByLayers(nodes)

// for any node, compute its ancestors.
nodes.forEach((n, i) => {
  if (edges[n.id]) {
    edges[n.id].forEach(v => {
      v.ancestors = v.ancestors || []
      v.ancestors.push(n)
    })
  }
  n.wait = 2**i // say arbitrarily that i node waits 2^i some time
})
function computeEndAt(node) {
  if (typeof(node.endAt) !== 'undefined') {
    return node.endAt
  }
  if (!node.ancestors) {
    node.endAt = 0 + node.wait
    return node.endAt
  }
  const maxEnd = Math.max(...node.ancestors.map(computeEndAt))
  node.endAt = maxEnd + node.wait
  return node.endAt
}
nodes.forEach(computeEndAt)
const longest = nodes.sort((a,b)=>b.endAt - a.endAt)[0]
console.log('awaited: ', longest.endAt, longest.id)