Перечисление подграфа - PullRequest
Новая
       8

Перечисление подграфа

10 голосов
/ 13 мая 2011

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

Редактировать: меня интересуют только связанные подграфы.

Ответы [ 2 ]

4 голосов
/ 30 марта 2013

Этот вопрос имеет лучший ответ в принятом ответе на этот вопрос . Это позволяет избежать сложного в вычислительном отношении шага, помеченного «Вы заполняете вышеуказанную функцию» в ответе @ ninjagecko. Он может эффективно справляться с соединениями, где есть несколько колец.

См. Связанный вопрос для получения полной информации, но вот краткое изложение. (N (v) обозначает множество соседей вершины v. На шаге «выберите вершину» вы можете выбрать любую произвольную вершину.) 

GenerateConnectedSubgraphs(verticesNotYetConsidered, subsetSoFar, neighbors):
    if subsetSoFar is empty:
        let candidates = verticesNotYetConsidered
    else
        let candidates = verticesNotYetConsidered intersect neighbors
    if candidates is empty:
        yield subsetSoFar
    else:
        choose a vertex v from candidates
        GenerateConnectedSubgraphs(verticesNotYetConsidered - {v},
                                   subsetSoFar,
                                   neighbors)
        GenerateConnectedSubgraphs(verticesNotYetConsidered - {v},
                                   subsetSoFar union {v},
                                   neighbors union N(v))
4 голосов
/ 13 мая 2011

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

Сравнение с математическими подграфами:

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

Если вы действительно хотитеэто подграфы с определенным свойством ( полностью подключено и т. д.), которое отличается, и вам необходимо обновить свой вопрос.Как отметил комментатор, 2 ^ 100 очень велико, поэтому вам определенно не нужно (как выше) перечислять математически правильные, но физически скучные отключенные подграфы.Буквально вам потребовалось бы, предполагая миллиард перечислений в секунду, по крайней мере, 40 триллионов лет, чтобы перечислить их все.

Генератор подключенного подграфа:

Если вы хотитекакое-то перечисление, которое сохраняет свойство DAG для подграфов по некоторой метрике, например (1,2,3) -> (2,3) -> (2), (1,2,3) -> (1,2)-> (2), вам нужен алгоритм, который может генерировать все ПОДКЛЮЧЕННЫЕ подграфы в качестве итератора (получая каждый элемент).Это может быть достигнуто путем рекурсивного удаления по одному элементу за раз (необязательно из «границы»), проверки того, находится ли оставшийся набор элементов в кэше (еще добавление его), выдачи его и повторения.Это прекрасно работает, если ваша молекула очень похожа на цепь с очень небольшим количеством циклов.Например, если ваш элемент был пятиконечной звездой из N элементов, он имел бы только около (100/5) ^ 5 = 3,2 миллиона результатов (менее секунды).Но если вы начнете добавлять более одного кольца, например, ароматических соединений и других, вас может ожидать грубая поездка.

Например, на python 

class Graph(object):
    def __init__(self, vertices):
        self.vertices = frozenset(vertices)
        # add edge logic here and to methods, etc. etc.

    def subgraphs(self):
        cache = set()
        def helper(graph):
            yield graph
            for element in graph:
                if {{REMOVING ELEMENT WOULD DISCONNECT GRAPH}}:
                    # you fill in above function; easy if
                    # there is 0 or 1 ring in molecule
                    # (keep track if molecule has ring, e.g.
                    #  self.numRings, maybe even more data)
                    # if you know there are 0 rings the operation
                    #  takes O(1) time
                    continue
                subgraph = Graph(graph.vertices-{element})
                if not subgraph in cache:
                    cache.add(subgraph)
                    for s in helper(subgraph):
                        yield s
        for graph in helper(self):
            yield graph

    def __eq__(self, other):
        return self.vertices == other.vertices
    def __hash__(self):
        return hash(self.vertices)
    def __iter__(self):
        return iter(self.vertices)
    def __repr__(self):
        return 'Graph(%s)' % repr(set(self.vertices))

Демонстрация: 

G = Graph({1,2,3,4,5})

for subgraph in G.subgraphs():
    print(subgraph)

Результат: 

Graph({1, 2, 3, 4, 5})                                                                                                                                                                                                                                              
Graph({2, 3, 4, 5})
Graph({3, 4, 5})
Graph({4, 5})
Graph({5})
Graph(set())
Graph({4})
Graph({3, 5})
Graph({3})
Graph({3, 4})
Graph({2, 4, 5})
Graph({2, 5})
Graph({2})
Graph({2, 4})
Graph({2, 3, 5})
Graph({2, 3})
Graph({2, 3, 4})
Graph({1, 3, 4, 5})
Graph({1, 4, 5})
Graph({1, 5})
Graph({1})
Graph({1, 4})
Graph({1, 3, 5})
Graph({1, 3})
Graph({1, 3, 4})
Graph({1, 2, 4, 5})
Graph({1, 2, 5})
Graph({1, 2})
Graph({1, 2, 4})
Graph({1, 2, 3, 5})
Graph({1, 2, 3})
Graph({1, 2, 3, 4})
...