Что такое эффективный алгоритм для перечисления всех подграфов родительского графа. В моем конкретном случае родительский граф является молекулярным графом, поэтому он будет связан и обычно содержит менее 100 вершин.
Изменить: меня интересуют только связанные подграфы.
Этот вопрос имеет лучший ответ в принятом ответе на этот вопрос. Он избегает вычисляемого сложного шага, обозначенного "вы заполняете выше функции" в ответе @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))
Что такое эффективный алгоритм для перечисления всех подграфов родительского графа. В моем конкретном случае родительский граф является молекулярным графом, поэтому он будет связан и обычно содержит менее 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})