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

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

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

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

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

Выберите любую произвольную node, 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

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

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

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

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

Ответ 1

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

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

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

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)

Ответ 2

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

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

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

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

Предполагая, что:

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

Худший случай: S * (Ns ^ 2 + MNsZ)

Средний случай: S * (NslogNs + MNs (Z/2))

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

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

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

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

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

Ответ 3

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

Ответ 4

Если я не читаю этот вопрос, люди, похоже, слишком импонируют. Это всего лишь "все возможные пути в пределах 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

Это создаст любую возможную комбинацию вершин для заданного количества ребер Отсутствует factory для генерации кортежей с учетом количества ребер.

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

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

Ответ 5

Для графика K _n существуют приблизительно n! пути между любыми двумя парами вершин. Я не просмотрел ваш код, но вот что я буду делать.

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

Ответ 6

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

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

Ответ 7

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

Ответ 8

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

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

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

Ответ 9

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

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

Ответ 10

Итак, у вас есть граф с ребрами 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.

Ответ 11

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

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

 N^(N-2)

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