Enumeración de enumeraciones

Question

¿Qué es un algoritmo eficiente para la enumeración de todos los subgrafos de un gráfico principal? En mi caso particular, el gráfico principal es un gráfico molecular, por lo que estará conectado y, por lo general, contiene menos de 100 vértices.

Editar: Estoy interesado solamente en los subgrafos conectados.

Answer 1

Esta pregunta tiene una respuesta mejor en la respuesta aceptada a this question. Evita el paso computacionalmente complejo marcado como "completes la función anterior" en la respuesta de @ ninjagecko. Puede tratar eficientemente con compuestos donde hay varios anillos.

Consulte la pregunta vinculada para obtener más información, pero aquí está el resumen. (N (v) denota el conjunto de vecinos del vértice v. En el "elegir un vértice" paso, se puede elegir cualquier vértice arbitrario.)

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)) 

Answer 2

¿Qué es un algoritmo eficiente para la enumeración de todos los subgrafos de un gráfico principal. En mi caso particular, el gráfico principal es un gráfico molecular, por lo que estará conectado y, por lo general, contiene menos de 100 vértices.

Comparación con subgraphs matemáticos:

Se podría dar a cada elemento un número de 0 a N, entonces enumerar cada subgrafo como cualquier número binario de longitud N. usted no necesitaría para escanear el gráfico en absoluto.

Si lo que realmente desea son subgrafos con cierta propiedad (totalmente conectada, etc.) que es diferente, y debe actualizar su pregunta. Como señaló un comentarista, 2^100 es muy grande, por lo que definitivamente no desea (como arriba) enumerar los subgrafos desconectados matemáticamente-correctos-pero-físicamente-aburridos. Literalmente lo tomaría, suponiendo un billón de enumeraciones por segundo, al menos 40 billones de años para enumerarlas todas.

Conectado-subgrafo generador:

Si desea algún tipo de enumeración que conserva la propiedad del DAG subgrafos bajo alguna métrica, por ejemplo, (1,2,3) -> (2,3) -> (2), (1,2,3) -> (1,2) -> (2), solo querría un algoritmo que pudiera generar todos los subgrafos CONECTADOS como un iterador (rindiendo cada elemento). Esto se puede lograr retirando recursivamente un elemento individual a la vez (opcionalmente desde el "límite"), verificando si el conjunto restante de elementos está en un caché (si no lo está agregando), cediéndolo y recursivamente. Esto funciona bien si tu molécula es muy parecida a una cadena con muy pocos ciclos. Por ejemplo, si su elemento era una estrella de 5 puntas con N elementos, solo tendría unos (100/5)^5 = 3,2 millones de resultados (menos de un segundo). Pero si comienza a agregar más de un anillo, p. compuestos aromáticos y otros, es posible que tenga un viaje difícil.

p. Ej. en 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)) 

Demostración:

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

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

Resultado:

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})