- Создание графа
Пусть a, b, c три узла, которые имеют общее свойство / депанданс 0 (для узла 0). Если a обнаружен до b, а b обнаружен до c, край должен быть a->b и b->c.
Чтобы обратиться к вышеуказанному правилу, рассмотрите кэш для каждого обнаруженного ди git. Если узел включает 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"
Теперь, чтобы построить график как «слои», вы можете начать с листьев (layer 0), здесь [1,4],[0,2],[0,3] only. Затем возьмите узлы, выходной край которых связан с любым из листьев, здесь только [1,4]. (потому что [1,3] при ссылке на [3], который является листом, также ссылается на [1,4], который не является. Так исключено). Затем вы построили слой 1.
. При построении слоя n вы можете добавлять только узлы с глубиной к слою 0 к n-1
Более компактный Можно сказать, что это для узла, для вычисления его эксцентриситета (самый длинный путь (здесь к листьям)).
Чтобы напечатать график, как вы это сделали, обратите внимание, что вы можете просто построить узлы с помощью эксцентриситета, что показать «уровень» зависимости (как далеко они находятся от листьев / конца, см. plotByLayers в коде ниже).
Вычисление общего времени
Нам не нужно go к сумме слоев зданий, как указано выше.
Узел может запускаться только тогда, когда все конец его предков.
Когда мы построили график, предки уже определены.
Таким образом, рекурсия
n.endAt = max(n.endAt for n in n.ancestors) + n.wait
Инициализация для root узлов (которые не зависят) и где мы можем просто хранить время ожидания.
nroot.endAt = nroot.wait
Относительно нотации node.id i)x,y. я - это 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)