Найти все поддеревья размера N в неориентированном графе

Question

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

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

Алгоритм должен быть эффективным для памяти, то есть не должен иметь в памяти все графики или некоторое большое их подмножество одновременно, поскольку это может превысить доступную память даже для относительно небольших графиков.Поэтому желательно что-то вроде DFS.

Вот что я думаю в псевдокоде, учитывая начальный граф graph и желаемую длину N:

Выберите любой произвольный узел,root в качестве отправной точки и вызов alltrees(graph, N, root)

alltrees(graph, N, root)
 given that node root has degree M, find all M-tuples with integer, non-negative values whose values sum to N (for example, for 3 children and N=2, you have (0,0,2), (0,2,0), (2,0,0), (0,1,1), (1,0,1), (1,1,0), I think)
 for each tuple (X1, X2, ... XM) above
   create a subgraph "current" initially empty
   for each integer Xi in X1...XM (the current tuple)
    if Xi is nonzero
     add edge i incident on root to the current tree
     add alltrees(graph with root removed, N-1, node adjacent to root along edge i)
   add the current tree to the set of all trees
 return the set of all trees

Это находит только деревья, содержащие выбранный начальный корень, поэтому теперь удалите этот узел и вызовите все дерево (граф с удаленным корнем, N, новый произвольно выбранныйroot), и повторяйте до тех пор, пока размер оставшегося графа

Я также забыл, что каждый посещенный узел (каждый корень для некоторого вызова всех деревьев) долженбыть отмеченным, и набор детей, рассматриваемый выше, должен быть только соседними безымянными детьми.Я предполагаю, что нам нужно учесть случай, когда нет неотмеченных потомков, но глубина> 0, это означает, что эта «ветвь» не достигла необходимой глубины и не может образовывать часть набора решений (поэтому весь внутренний цикл связан сэтот кортеж можно прервать).

Так будет ли это работать?Какие-нибудь серьезные недостатки?Какой-нибудь более простой / известный / канонический способ сделать это?

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

Answer 1

Для этого требуется объем памяти, пропорциональный тому, что требуется для хранения графика. Каждый подграф, представляющий собой дерево нужного размера, будет возвращен ровно один раз.

Имейте в виду, что я просто набрал это здесь. Там могут быть ошибки. Но идея состоит в том, что вы ходите по узлам по одному, чтобы каждый узел искал все деревья, которые включают этот узел, но ни один из узлов, которые были найдены ранее. (Потому что они уже исчерпаны.) Этот внутренний поиск выполняется рекурсивно путем перечисления ребер в узлах дерева, и для каждого ребра принимается решение, включать его в ваше дерево или нет. (Если это сделает цикл или добавит исчерпанный узел, то вы не сможете включить это ребро.) Если вы включите его в свое дерево, то используемые узлы растут, и у вас есть новые возможные ребра, которые можно добавить в поиск.

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

def find_all_trees(graph, tree_length):
    exhausted_node = set([])
    used_node = set([])
    used_edge = set([])
    current_edge_groups = []

    def finish_all_trees(remaining_length, edge_group, edge_position):
        while edge_group < len(current_edge_groups):
            edges = current_edge_groups[edge_group]
            while edge_position < len(edges):
                edge = edges[edge_position]
                edge_position += 1
                (node1, node2) = nodes(edge)
                if node1 in exhausted_node or node2 in exhausted_node:
                    continue
                node = node1
                if node1 in used_node:
                    if node2 in used_node:
                        continue
                    else:
                        node = node2
                used_node.add(node)
                used_edge.add(edge)
                edge_groups.append(neighbors(graph, node))
                if 1 == remaining_length:
                    yield build_tree(graph, used_node, used_edge)
                else:
                    for tree in finish_all_trees(remaining_length -1
                                                , edge_group, edge_position):
                        yield tree
                edge_groups.pop()
                used_edge.delete(edge)
                used_node.delete(node)
            edge_position = 0
            edge_group += 1

    for node in all_nodes(graph):
        used_node.add(node)
        edge_groups.append(neighbors(graph, node))
        for tree in finish_all_trees(tree_length, 0, 0):
            yield tree
        edge_groups.pop()
        used_node.delete(node)
        exhausted_node.add(node)

Answer 2

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

• делайте это поэтапно, на каждом шаге:
• сортируйте узлы графа, чтобы получить список узлов, отсортированных по количеству смежных ребер ASC
• обработать все узлы с одинаковым числом ребер первого
• удалить эти узлы

Например, для графика из 6 узлов найдены все размеры 2подграфы (извините за мое полное отсутствие художественного выражения):

Ну, то же самое можно сказать и о большем графике, но это должно быть сделано в несколько шагов.

Предполагая:

• Z количество ребер наиболее разветвленного узла
• M желаемый размер поддерева
• S количество шагов
• Ns количествоузлы на шаге
• при условии быстрой сортировки для сортировки узлов

В худшем случае: S * (Ns ^ 2 + M Ns Z) * ​​1036 *

Среднееcase: S * (NslogNs + M Ns (Z / 2))

Проблема заключается в том, что невозможно вычислить реальный омикрон, поскольку узлы на каждом шаге будут уменьшатьсяrease в зависимости от того, как устроен график ...

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

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

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

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

Answer 3

Если я не читаю вопрос, неправильные люди, кажется, усложняют его. Это просто «все возможные пути в пределах N ребер», и вы допускаете циклы. Это для двух узлов: A, B и одного ребра ваш результат будет: AA, AB, BA, BB

Для двух узлов, двух ребер ваш результат будет: AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB

Я бы указывал для каждого и передавал в кортеже "шаблон"

N=edge count
TempTuple = Tuple_of_N_Items ' (01,02,03,...0n) (Could also be an ordered list!)
ListOfTuple_of_N_Items ' Paths (could also be an ordered list!)
edgeDepth = N

Method (Nodes, edgeDepth, TupleTemplate, ListOfTuples, EdgeTotal)
edgeDepth -=1
For Each Node In Nodes
    if edgeDepth = 0 'Last Edge
        ListOfTuples.Add New Tuple from TupleTemplate + Node ' (x,y,z,...,Node)
    else
        NewTupleTemplate = TupleTemplate + Node ' (x,y,z,Node,...,0n)
        Method(Nodes, edgeDepth, NewTupleTemplate, ListOfTuples, EdgeTotal
next

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

В итоге вы получаете список возможных путей, и операция называется Узлы ^ (N + 1)

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

Answer 4

Если память является самой большой проблемой, вы можете использовать NP-решение, используя инструменты формальной проверки. Т.е., угадать подмножество узлов размера N и проверить, является ли это графом или нет. Чтобы сэкономить место, вы можете использовать BDD (http://en.wikipedia.org/wiki/Binary_decision_diagram) для представления узлов и ребер исходного графа. Кроме того, вы можете использовать символический алгоритм, чтобы проверить, является ли график, который вы догадались, действительно графом - так что вам не нужно создавать оригинал График (или графы размера N) в любой точке. Потребление памяти должно быть (в большом-O) log(n) (где n - размер исходного графа) для хранения исходного графа, а другой log(N) хранить каждый «маленький график», который вы хотите. Еще один инструмент (который должен быть еще лучше) - использовать SAT-решатель. То есть, построить формулу SAT, которая верна, если подграф является графом и передать его в решатель SAT.

Answer 5

Итак, у вас есть граф с ребрами e_1, e_2, ..., e_E.

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

Простое решение состоит в том, чтобы сгенерировать каждый из E, выбрать N подграфов и проверить, являются ли они деревьями. Вы рассматривали этот подход? Конечно, если E слишком велик, тогда это нежизнеспособно.

РЕДАКТИРОВАТЬ:

Мы также можем использовать тот факт, что дерево представляет собой комбинацию деревьев, то есть каждое дерево размера N можно «вырастить», добавив ребро к дереву размера N-1. Пусть E - множество ребер в графе. Алгоритм может пойти примерно так:

T = E
n = 1
while n<N
    newT = empty set
    for each tree t in T
        for each edge e in E
            if t+e is a tree of size n+1 which is not yet in newT
                add t+e to newT 
    T = newT
    n = n+1

В конце этого алгоритма T - это множество всех поддеревьев размера N. Если пространство является проблемой, не храните полный список деревьев, но используйте компактное представление, например, реализуйте T как дерево решений с использованием ID3 .

Answer 6

Я думаю, что есть хороший алгоритм (с реализацией Perl) на этом сайте (ищите TGE), но если вы хотите использовать его в коммерческих целях, вам необходимо связаться с автором.Алгоритм похож на ваш в вопросе, но позволяет избежать взрыва рекурсии, заставляя процедуру включать текущее рабочее поддерево в качестве параметра (а не отдельный узел).Таким образом, каждое ребро, исходящее из поддерева, может быть выборочно включено / исключено и рекурсивно развернуто в расширенном дереве (с новым ребром) и / или уменьшенном графе (без ребра).

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

Answer 7

Думаю, ваше решение не работает, хотя его можно заставить работать.Основная проблема заключается в том, что подзадачи могут создавать перекрывающиеся деревья, поэтому, когда вы берете их объединение, вы не получаете дерево размера n.Вы можете отклонить все решения, если есть перекрытие, но в итоге вы можете выполнить гораздо больше работы, чем необходимо.

Поскольку вы в порядке с экспоненциальной средой выполнения и потенциально можете написать 2 ^ n деревьев, имея V.2 ^ V алгоритмы совсем не плохо.Таким образом, самый простой способ сделать это - сгенерировать все возможные подмножества n узлов, а затем проверить каждый из них, формирует ли он дерево.Поскольку проверка того, может ли подмножество узлов образовывать дерево, может занять время O (EV), мы потенциально говорим о времени V ^ 2.V ^ n, если только у вас нет графика со степенью O (1).Это можно немного улучшить, перечислив подмножества таким образом, чтобы два последовательных подмножества отличались ровно в одном заменяемом узле.В этом случае вам просто нужно проверить, подключен ли новый узел к какому-либо из существующих узлов, что можно сделать за время, пропорциональное количеству исходящих ребер нового узла, сохранив хеш-таблицу всех существующих узлов.

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

Answer 8

Этот алгоритм большой и непростой для публикации здесь. Но вот ссылка на алгоритм search search , с помощью которого вы можете делать то, что хотите. Этот PDF-файл содержит оба алгоритма. Также, если вы понимаете русский язык, вы можете взглянуть на это .

Answer 9

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

Если один узел в дереве, которое вы пытаетесь найти, позволил иметь более 2 братьев и сестер, что должно быть разрешено, учитывая, что вы не указываете никаких ограничений на исходный граф, и вы упомянули, что результирующий подграф должен содержать все узлы.Вы можете перечислить все подграфы, которые имеют форму дерева, выполнив обход в глубину.Вам нужно повторить обход графика для каждого брата во время обхода.Когда вам нужно будет повторить операцию для каждого узла в качестве корня.Отбрасывая симметричные деревья, вы получите

 N^(N-2) 

деревьев, если ваш граф полностью связан сеткой или вам нужно применить Теорема Кирхгофа о матричном дереве

Answer 10

Кажется, что будет работать следующее решение.

Переберите все разбиения на две части множества всех вершин.Затем посчитайте количество ребер, окончания которых лежат в разных частях (k);эти ребра соответствуют ребрам дерева, они соединяют поддеревья для первой и второй частей.Вычислить ответ для обеих частей рекурсивно (p1, p2).Тогда ответ для всего графа можно вычислить как сумму по всем таким разбиениям k * p1 * p2.Но все деревья будут рассмотрены N раз: один раз для каждого края.Таким образом, сумма должна быть разделена на N, чтобы получить ответ.