algorithm - triple - superponer graficos tableau

Encuentre todos los subárboles de tamaño N en un gráfico no dirigido (11)

Dado un gráfico no dirigido, quiero generar todos los subgrafos que son árboles de tamaño N, donde el tamaño se refiere al número de bordes en el árbol.

Soy consciente de que hay muchos de ellos (exponencialmente muchos, al menos para gráficos con conectividad constante), pero está bien, ya que creo que la cantidad de nodos y aristas hace que esto sea manejable para valores al menos pequeños de N (digamos 10 o menos). ).

El algoritmo debería ser eficiente en memoria, es decir, no debería tener todos los gráficos o algún subconjunto grande de ellos en la memoria a la vez, ya que es probable que esto exceda la memoria disponible incluso para gráficos relativamente pequeños. Así que algo como DFS es deseable.

Esto es lo que estoy pensando, en pseudocódigo, dado el gráfico de inicio y la longitud deseada N :

Elija cualquier nodo arbitrario, root como punto de partida y llame a 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

Esto solo encuentra árboles que contienen la raíz inicial elegida, por lo que ahora elimine este nodo y llame a alltrees (gráfico con la raíz eliminada, N, nueva raíz elegida arbitrariamente), y repita hasta el tamaño del gráfico restante <N (ya que no hay árboles de los necesarios). el tamaño existirá).

También olvidé que cada nodo visitado (cada raíz para alguna llamada de alltree) debe marcarse, y el conjunto de hijos considerado anteriormente solo debe ser el de los niños adyacentes sin marcar. Supongo que debemos tener en cuenta el caso en el que no existen hijos sin marcar, pero la profundidad> 0, esto significa que esta "rama" no logró alcanzar la profundidad requerida y no puede formar parte del conjunto de soluciones (por lo que todo el bucle interno está asociado con esa tupla puede ser abortada).

¿Así funcionará esto? ¿Alguna falla importante? ¿Alguna forma más simple / conocida / canónica de hacer esto?

Un problema con el algoritmo descrito anteriormente es que no cumple con el requisito de eficiencia de memoria, ya que la recursión tendrá grandes conjuntos de árboles en la memoria.

A menos que esté leyendo la pregunta, las personas equivocadas parecen estar complicándola. Esto es solo "todos los caminos posibles dentro de N bordes" y está permitiendo ciclos. Esto, para dos nodos: A, B y un borde, su resultado sería: AA, AB, BA, BB

Para dos nodos, dos bordes, su resultado sería: AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB

Me gustaría recibir una tupla de "plantilla" para cada uno y aprobar

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

Esto creará todas las combinaciones posibles de vértices para un recuento de bordes dado. Lo que falta es la fábrica para generar tuplas dado un recuento de bordes.

Terminas con una lista de rutas posibles y la operación es Nodos ^ (N + 1)

Si usa listas ordenadas en lugar de tuplas, no necesita preocuparse por una fábrica para crear los objetos.

Así que tienes un gráfico con bordes e_1, e_2, ..., e_E.

Si entiendo correctamente, está buscando enumerar todos los subgrafos que son árboles y contienen N bordes.

Una solución simple es generar cada uno de los subgrafos E elegir N y verificar si son árboles. ¿Has considerado este enfoque? Por supuesto, si E es demasiado grande, entonces esto no es viable.

EDITAR:

También podemos usar el hecho de que un árbol es una combinación de árboles, es decir, que cada árbol de tamaño N puede "crecer" agregando un borde a un árbol de tamaño N-1. Sea E el conjunto de aristas del gráfico. Un algoritmo podría entonces ir algo como esto.

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

Al final de este algoritmo, T es el conjunto de todos los subárboles de tamaño N. Si el espacio es un problema, no mantenga una lista completa de los árboles, pero use una representación compacta, por ejemplo, implemente T como un árbol de decisión usando ID3 .

Creo que el problema no está bien especificado. Mencionó que el gráfico no está dirigido y que el subgrafo que está tratando de encontrar es de tamaño N. Lo que falta es el número de bordes y cada vez que los árboles están buscando un binario o puede tener varios árboles. Además, ¿está interesado en los reflejos reflejados del mismo árbol, o en otras palabras, el orden en el que los hermanos figuran en la lista es importante?

Si un solo nodo en un árbol está tratando de encontrar, se le permite tener más de 2 hermanos, lo que debería permitirse dado que no especifica ninguna restricción en el gráfico inicial y mencionó que el subgrafo resultante debe contener todos los nodos. Puede enumerar todos los subgrafos que tienen forma de arbol al realizar el recorrido primero en profundidad. Debe repetir el recorrido de la gráfica para cada hermano durante el recorrido. Cuando necesite repetir la operación para cada nodo como raíz. Desechando árboles simétricos terminarás con

N^(N-2)

árboles si su gráfico está completamente conectado o si necesita aplicar el teorema de árbol de matriz de Kirchhoff

Creo que hay un buen algoritmo (con implementación de Perl) en este sitio (busque TGE), pero si desea utilizarlo comercialmente, deberá ponerse en contacto con el autor. El algoritmo es similar al suyo en la pregunta, pero evita la explosión de recursión al hacer que el procedimiento incluya un subárbol de trabajo actual como parámetro (en lugar de un solo nodo). De esa manera, cada borde que emana del subárbol se puede incluir / excluir de forma selectiva, y recursionar en el árbol expandido (con el nuevo borde) y / o reducir el gráfico (sin el borde).

Este tipo de enfoque es típico de los algoritmos de enumeración de gráficos: por lo general, debe realizar un seguimiento de un puñado de bloques de construcción que son gráficos; Si intentas tratar solo con nodos y aristas, se vuelve intratable.

Este algoritmo es grande y no es fácil de publicar aquí. Pero aquí hay un enlace al algoritmo de búsqueda de reservas mediante el cual puede hacer lo que quiera. This archivo pdf contiene ambos algoritmos. También si entiendes ruso puedes echarle un vistazo a this .

Esto necesita una cantidad de memoria que sea proporcional a lo que se requiere para almacenar el gráfico. Devolverá cada subgrafo que sea un árbol del tamaño deseado exactamente una vez.

Ten en cuenta que acabo de escribirlo aquí. Podría haber errores. Pero la idea es que recorre los nodos uno a la vez, para cada nodo que busca todos los árboles que incluyen ese nodo, pero ninguno de los nodos que se buscaron previamente. (Debido a que ya se han agotado). La búsqueda interna se realiza de forma recursiva al enumerar los bordes en los nodos del árbol y, para cada borde, decidir si se incluye o no en su árbol. (Si haría un ciclo, o agregaría un nodo agotado, entonces no puede incluir ese borde). Si lo incluye en su árbol, los nodos usados crecerán y tendrá nuevos bordes posibles para agregar a su búsqueda.

Para reducir el uso de la memoria, los bordes que quedan por ver se manipulan en su lugar por todos los niveles de la llamada recursiva en lugar del enfoque más obvio de duplicar esos datos en cada nivel. Si se copia esa lista, el uso total de la memoria alcanzaría el tamaño del árbol multiplicado por el número de bordes en el gráfico.

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)

Para una gráfica de K _n hay aproximadamente n! Trayectorias entre cualesquiera dos pares de vértices. No he revisado tu código, pero esto es lo que haría.

Seleccione un par de vértices.
Comience desde un vértice e intente alcanzar el vértice de destino de forma recursiva (algo como dfs pero no exactamente). Creo que esto daría como resultado todos los caminos entre los vértices elegidos.
Podría hacer lo anterior para todos los pares de vértices posibles para obtener todos los caminos simples.

Parece que la siguiente solución funcionará.

Repase todas las particiones en dos partes del conjunto de todos los vértices. Luego cuente el número de bordes cuyos extremos se encuentran en diferentes partes (k); estos bordes corresponden al borde del árbol, conectan subárboles para la primera y la segunda parte. Calcula recursivamente la respuesta para ambas partes (p1, p2). Luego, la respuesta para el gráfico completo se puede calcular como la suma de todas las particiones de k * p1 * p2. Pero todos los árboles serán considerados N veces: una vez por cada borde. Por lo tanto, la suma debe dividirse por N para obtener la respuesta.

Si la memoria es el mayor problema, puede usar una solución NP-ish usando herramientas de verificación formal. Es decir, adivina un subconjunto de nodos de tamaño N y verifica si es un gráfico o no. Para ahorrar espacio puede usar un BDD (http://en.wikipedia.org/wiki/Binary_decision_diagram) para representar los nodos y bordes del gráfico original. Además, puede usar un algoritmo simbólico para verificar si el gráfico que adivinó es realmente un gráfico, por lo que no necesita construir el gráfico original (ni los gráficos de tamaño N) en ningún punto. El consumo de memoria debe ser (en big-O) log(n) (donde n es el tamaño del gráfico original) para almacenar el gráfico original, y otro log(N) para almacenar cada "gráfico pequeño" que desee. Otra herramienta (que se supone que es incluso mejor) es usar un solucionador SAT. Es decir, construya una fórmula SAT que sea verdadera si la sub-gráfica es una gráfica y se la suministre a un solucionador SAT.

Suponiendo que pueda destruir el gráfico original o hacer una copia destructiva, encontré algo que podría funcionar pero que podría ser completamente sadomaso porque no calculé su O-Ntiness. Probablemente funcionaría para pequeños subárboles.

Hazlo en pasos, en cada paso:
ordene los nodos del gráfico para obtener una lista de nodos ordenados por número de bordes adyacentes ASC
Procesa todos los nodos con el mismo número de bordes del primero.
eliminar esos nodos

Para ver un ejemplo de una gráfica de 6 nodos que encuentra todos los subgrafos de tamaño 2 (perdón por mi total falta de expresión artística):

Bueno, lo mismo iría para un gráfico más grande, pero debería hacerse en más pasos.

Asumiendo:

Número Z de aristas del nodo más ramificado.
M tamaño de subárbol deseado
S numero de pasos
Ns numero de nodos en el paso
asumiendo quicksort para ordenar los nodos

Peor caso: S * (Ns ^ 2 + M Ns Z)

Caso promedio: S * (NslogNs + M Ns (Z / 2))

El problema es: no se puede calcular el omicron real porque los nodos en cada paso disminuirán dependiendo de cómo esté la gráfica ...

Resolver todo con este enfoque podría llevar mucho tiempo en un gráfico con nodos muy conectados, sin embargo, podría paralizarse, y podría hacer uno o dos pasos, para eliminar los nodos dislocados, extraer todos los subgrafos y luego elegir otro enfoque el resto, pero habría eliminado muchos nodos del gráfico para que pudiera disminuir el tiempo de ejecución restante ...

Desafortunadamente, este enfoque beneficiaría a la GPU, no a la CPU, ya que en cada paso se incluirían MUCHOS nodos con el mismo número de bordes ... y si no se usa la paralelización, este enfoque probablemente sea malo ...

Tal vez una inversa iría mejor con la CPU, ordenar y proceder con los nodos con el número máximo de aristas ... probablemente serán menos al inicio, pero tendrá más subgrafos que extraer de cada nodo ...

Otra posibilidad es calcular el recuento de egde que ocurre menos en el gráfico y comenzar con los nodos que lo tengan, lo que aliviaría el uso de memoria y el recuento de iteraciones para extraer subgrafos ...

Tu solución tal como está no funciona, aunque creo que puede funcionar. El problema principal es que los subproblemas pueden producir árboles superpuestos, por lo que cuando tomas la unión de ellos no terminas con un árbol de tamaño n. Puede rechazar todas las soluciones donde haya una superposición, pero puede terminar haciendo mucho más trabajo del necesario.

Ya que estás bien con el tiempo de ejecución exponencial, y potencialmente estás escribiendo 2 ^ n árboles, tener algoritmos V.2 ^ V no es malo en absoluto. Entonces, la forma más sencilla de hacerlo sería generar todos los nodos y nodos de subconjuntos posibles, y luego probar cada uno de ellos si forma un árbol. Desde que se comprueba si un subconjunto de nodos forma un árbol puede tomar tiempo O (EV), potencialmente estamos hablando de tiempo V ^ 2.V ^ n, a menos que tenga un gráfico con O (1) grado. Esto se puede mejorar ligeramente al enumerar los subconjuntos de manera que dos subconjuntos sucesivos se diferencien exactamente en el intercambio de un nodo. En ese caso, solo tiene que verificar si el nuevo nodo está conectado a alguno de los nodos existentes, lo que se puede hacer en un tiempo proporcional al número de bordes salientes de un nuevo nodo manteniendo una tabla hash de todos los nodos existentes.

La siguiente pregunta es cómo enumerar todos los subconjuntos de un tamaño determinado de manera que no se intercambie más de un elemento entre subconjuntos sucesivos. Dejaré eso como un ejercicio para que lo averigües :)