Обход необычного дерева в Python

Question

У меня необычный массив деревьев, подобный этому:

[[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], 
 [4, 6], [3, 6], [0, 7], [7, 6], [8, 9], [9, 6]]

Каждый элемент массива представляет собой пару, что означает, что второй элемент является последователем первого, например ::100100

[0, 1] - 0 is followed by 1
[1, 2] - 1 is followed by 2

Я пытаюсь извлечь массив следующим образом:

0 1 2 3 6    
0 1 2 4 6    
0 1 2 5 6
0 7 6
8 9 6

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

Answer 1

Вы можете сделать это, используя функцию рекурсивного генератора.Я предполагаю, что корневой узел в дереве всегда предшествует всем его дочерним элементам в исходном списке.

tree = [[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], [4, 6], [3, 6],
        [0, 7], [7, 6], [8, 9], [9, 6]]

paths = {}
for t in tree:
    if t[0] not in paths: paths[t[0]] = []
    paths[t[0]].append(tuple(t))

used = set()

def get_paths(node):
    if node[1] in paths:
        for next_node in paths[node[1]]:
            used.add(next_node)
            for path in get_paths(next_node):
                yield [node[0]] + path
    else:
        yield [node[0], node[1]]

for node in tree:
    if tuple(node) in used: continue
    for path in get_paths(node):
        print path

Вывод:

[0, 1, 2, 3, 6]
[0, 1, 2, 4, 6]
[0, 1, 2, 5, 6]
[0, 7, 6]
[8, 9, 6]

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

Если предположение о порядке узлов не выполняется, то сначала нужно найтинабор всех корневых узлов.Это можно сделать, найдя все узлы, которые не отображаются в качестве второго узла ни в одном соединении.

Answer 2

Самым простым способом, который я могу придумать, было бы создать словарь, содержащий все возможные дочерние элементы для данного родителя, например:

d = {}

for parent, child in tree:
    try:
        d[parent].append(child)
    except KeyError:
        d[parent] = [child]

с деревом = [[0, 1], [1, 2], [2, 3], [2, 4], [2,5], [5, 6], [4, 6], [ 3, 6], [0, 7], [7, 6], [8, 9], [9, 6]], это даст:

{0: [1, 7],
 1: [2],
 2: [3, 4, 5],
 3: [6],
 4: [6],
 5: [6],
 7: [6],
 8: [9],
 9: [6]}

Теперь можно рекурсивно обходить дерево следующим образом:

def printPaths(d, currentPath):
    if currentPath[-1] not in d:
        print currentPath # last node can't possibly be a parent, so stop
    else:
        for child in d[currentPath[-1]]:
            printPaths(d, currentPath + [child])


for root in d:
    printPaths(d, [root])

Я не проверял рекурсию, но она должна дать вам представление:)

Answer 3

Из того, что я понимаю по вашему вопросу, похоже, что у вас есть набор родительско-дочерних отношений в виде списка пар, который описывает дерево . Вы, кажется, сталкиваетесь с проблемами, думая, что у него есть структура, подобная связанному списку. В отличие от связанного списка, дерево является более общей формой, оно может иметь несколько узлов, которые «следуют» за данным узлом и называются его дочерними элементами.

Самый простой способ - сначала построить дерево, а затем пройти по нему от корня. Определите класс Node, который имеет два поля, одно для значения узла, а другое - список дочерних элементов. Затем вы перебираете элементы своего списка, добавляя второй элемент каждой пары в список детей узла, соответствующего первому элементу пары. После того как дерево построено, вы используете рекурсивную функцию печати, которая печатает текущий узел и вызывает себя для его дочерних элементов (если они есть). Вызов функции на корневом узле должен вывести на экран все дерево.

Я бы опубликовал некоторый код, но это выглядит как домашняя работа. Приведенного выше объяснения должно быть достаточно для начала.

Answer 4

Вот, пожалуйста. Не самый хороший код на земле, но он работает:

inputValues = [[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], [4, 6], [3, 6], [0, 7], [7, 6], [8, 9], [9, 6]]

tree = {}
numberOfChildren = {}
for (f, t) in inputValues:
  if not tree.has_key(f):
    tree[f] = []
  tree[f].append(t)
  if not numberOfChildren.has_key(t):
    numberOfChildren[t] = 0
  numberOfChildren[t] += 1

roots = [c for c in tree if c not in numberOfChildren]
permutations = []

def findPermutations(node, currentList):
  global tree
  global permutations
  if not tree.has_key(node):
    permutations.append(currentList)
    return
  for child in tree[node]:
    l = list()
    l.extend(currentList)
    l.append(child)
    findPermutations(child, l)

for r in roots:
  findPermutations(r, [r])

print permutations

Answer 5

Следующие работы - генерировать деревья, начиная с корня. Корни считаются узлами, у которых нет родителя.

import operator
def genpaths(data):
    # Initialize dictionary
    ddata = {}
    for item in data:
        ddata.setdefault(item[0], []).append(item[1])
    def genpath(root):
        "Generate paths starting with root"
        if root not in ddata:
            yield (root, )
        else:
            for child in ddata[root]:
                for path in genpath(child):
                    yield (root, ) + path

    for root in set(ddata.keys()) - set(reduce(operator.add, ddata.values())):
        for path in genpath(root):
            print path

Answer 6

Создание всех самых длинных путей из всех возможных начальных узлов:

tree = [[0, 1], [1, 2], [2, 3], ...]

dtree = {}
for (k, v) in tree:
   dtree.setdefault(k, []).append(v)

parts = [[root] for root in range(10)]

while parts:
   path = parts.pop(0)
   if path[-1] in dtree:
      for n in dtree[path[-1]]:
         parts.append(path + [n])
   else:
      print path

Если он должен создавать только пути, которые не являются частью другого, более длинного пути, начинающегося на каком-то другом узле, parts необходимо инициализировать для всех узлов, не содержащихся в [p[1] for p in tree]. И если вы хотите вместо всех путей, а не только самые длинные, в каждой итерации цикла while должен быть отпечаток.

Answer 7

Вы можете использовать функцию find_all_paths со следующей страницы: http://www.python.org/doc/essays/graphs/

Чтобы использовать это, вам нужно сделать два небольших изменения в вашем графике. Во-первых, просмотрите список ребер и создайте новое представление графа, например:

<code>    graph = {0: [1, 7],
             1: [2],
             2: [3, 4, 5],
             ...}

Во-вторых, создайте supersink (в вашем примере вы можете назвать его 10) и присоедините все вершины без ребер, ведущих от них к этому новому узлу.

Затем вы можете вызвать функцию find_all_paths(graph, 0, 10), чтобы найти все такие пути.

Answer 8

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

1. Пусть массивы = список пар
2. Пока каждый массив в массивах не будет листом:
   1. Если массив является листом (последний элемент не является первым элементом в любом массиве в массивах):
      1. Для каждого массива в массивах посмотрите, можно ли прикрепить лист к его концу
      2. После прикрепления ко всем возможным массивам удалите лист

Очевидно, вам придется проделать некоторую работу, чтобы превратить это в код, но это грубая идея.