Как преобразовать Направленный граф без петель (DAG) в Дерево
Используя json из вопроса, обратите внимание, что, например, следующее имеет то же значение:
json[["locations"]][["address"]][["city"]]
json[[c("locations", "address", "city")]]
и предполагает использование точки в именовании объектов unlist, как показано вопрос, который мы можем использовать Map следующим образом:
setList <- function(List, Unlist) {
nms <- names(Unlist)
Map(function(x, y) List[[x]] <<- Unlist[[y]], strsplit(nms, "\\."), nms)
List
}
setList(my_list, my_unlist)
setList(json, json_unlist)
5 ответов
Есть теоретический ответ на вопрос о графах и ответ программиста на это. Я предполагаю, что с программистской частью вы справитесь сами. Для теоретико-графического ответа:
- DAG - это набор модулей, в котором никогда не бывает, что A нужен B, и в то же время B (или одному из модулей B нужен) A, в модулях-говорят: нет круговая зависимость. Я видел циклические зависимости (поищите примеры на форумах Gentoo), так что вы не можете быть даже на 100% уверены, что у вас есть DAG, но предположим, что у вас есть. Проверить циклические зависимости не очень сложно, поэтому я рекомендую вам сделать это где-нибудь в загрузчике модуля.
- В дереве никогда не может произойти то, что A зависит от B и C и что оба B и C зависят от D (ромба), но это может произойти в DAG.
- Кроме того, дерево имеет ровно один корневой узел, но группа DAG может иметь несколько «корневых» узлов (т. е. модулей, от которых ничего не зависит). Например, такая программа, как GIMP, программа GIMP будет корневым узлом набора модулей, но для GENTOO практически любая программа с графическим интерфейсом пользователя является «корневым» узлом, а библиотеки и т.д. являются их зависимостями. (IE и Konqueror, и Kmail зависят от Qtlib, но ничего не зависит от Konqueror и ничего не зависит от Kmail)
Теоретический ответ на ваш вопрос, как указывали другие, заключается в том, что DAG не может быть преобразован в дерево , в то время как каждое дерево является DAG.
Однако (ответ высокоуровневого программиста), если вам нужно дерево для графического представления, вас интересуют только зависимости конкретного модуля, а не то, что зависит от этого модуля. Приведу пример:
A depends on B and C
B depends on D and E
C depends on D and F
Я могу » However, if you want to show what A depends on, you can show this:
A
+--B
| +--D
| +--E
+--C
+--D
+--F
As you see, you get double entries in your tree - in this case "only" D but if you do an "expand all" on the Gentoo tree, I guarantee you that your tree will have at least 1000 times the amount of nodes as there are modules. (there are at least 100 packages that depend on Qt, so everything Qt depends on will be present at least 100 times in the tree).
If you have a "large" or "complex" tree, It might be best to expand the tree dynamically, not in advance, otherwise you might have a very memory-intensive process.
The disadvantage of the tree above is that if you click open B, then D, you see that A and B depend on D, but not that also C depends on D. However, depending on your situation, this might not be important at all - if you maintain a list of loaded modules, on loading C you see that you have loaded D already, and it doesn't matter it wasn't loaded for C, but for B. It is loaded, that's all that matters. If you dynamically maintain what directly depends on a certain module, you can handle the opposite problem (unloading) as well.
However, what you can't do with a tree is what's in your final sentence: preserve topological order, i.e. if B gets loaded in the same container as C, you'll never get to load C in the same container as well. Or you might have to be put up with putting everything in one container (not that I fully understand what you mean with "loading into the same container")
Good luck!
DAG и дерево не являются тем же самым математически. Таким образом любое преобразование представляет неоднозначность. Дерево по определению не имеет никаких циклов, период.
То, что Вы ищете, для нахождения порядка загрузить модули в, Топологический вид из DAG. Если края идут от модуля до модулей, он зависит от (который я думаю, наиболее вероятно), необходимо будет загрузить модули в обратном порядке топологического вида, потому что модуль появится-before-все модули, от которых он зависит.
при представлении DAG, таким образом, что края идут от зависевшего от модулей к модулям, которые зависят от них (можно получить это путем инвертирования всех краев в графике выше), можно просто загрузить модули в порядке топологического вида.
Это во многом зависит от того, как Вы представляете свой DAG. Например, это могла быть матрица смежности ([я, j] = 1, если существует край от узла i к узлу j, еще 0), или как система указателей, или как массив узлов и массив краев....
Далее, не ясно, какое преобразование Вы пытаетесь применить. Связанный DAG дерево, таким образом, я боюсь, что необходимо разъяснить вопрос немного.
Можно только сделать это, если все поддеревья имеют единственный корневой узел.