Sugerencias de los algoritmos más fáciles para algunas operaciones de gráfico

Question

La fecha límite para este proyecto se está cerrando muy rápido y no tengo mucho tiempo para ocuparme de lo que queda. Entonces, en lugar de buscar los mejores algoritmos (y probablemente más complicados/lentos), estoy buscando los algoritmos más fáciles para implementar algunas operaciones en una estructura Graph.

Las operaciones que tendrá que hacer es la siguiente:

• Lista de todos los usuarios de la red gráfica dada una distancia X
• Lista de todos los usuarios de la red gráfica dada una distancia X y el tipo de relación
• calcular la trayectoria más corta entre 2 usuarios en la red gráfico dado un tipo de relación
• calcular la distancia máxima entre 2 usuarios en la red gráfico
• Calcular el mo st usuarios conectados distantes de la red gráfica

Algunas notas acerca de mi aplicación Graph:

• El nodo de borde tiene 2 propiedades, uno es de tipo char y otro int. Representan el tipo de relación y peso, respectivamente.
• El gráfico se implementa con listas vinculadas, tanto para los vértices como para los bordes. Quiero decir, cada vértice apunta al siguiente y cada vértice también apunta al encabezado de una lista vinculada diferente, los bordes para ese vértice específico.

Lo que sé de lo que tengo que hacer:

• No sé si este es el más fácil como he dicho anteriormente, pero por el camino más corto entre 2 usuarios, creo que el Dijkstra El algoritmo es lo que la gente parece recomendar muy a menudo, así que creo que voy con eso.
  • He estado buscando y buscando y me resulta difícil implementar este algoritmo, ¿alguien sabe de algún tutorial o algo fácil de entender para poder implementar este algoritmo? Si es posible, con ejemplos de código fuente C, sería de gran ayuda. Veo muchos ejemplos con anotaciones matemáticas, pero eso me confunde aún más.
  • ¿Crees que ayudaría si "convertí" el gráfico a una matriz de adyacencia para representar el peso del enlace y el tipo de relación? ¿Sería más fácil realizar el algoritmo en lugar de las listas vinculadas? Podría implementar fácilmente una función para hacer esa conversión cuando sea necesario. Estoy diciendo esto porque tuve la sensación de que sería más fácil después de leer un par de páginas sobre el tema, pero podría estar equivocado.
• No tengo ninguna idea sobre las otras 4 operaciones, sugerencias?

Answer 1

Lista de todos los usuarios de la red gráfica dada una distancia X

Una distancia X de qué? desde un nodo inicial o una distancia X entre ellos? ¿Puede dar un ejemplo? Esto puede o no ser tan simple como hacer una búsqueda BF o ejecutar Dijkstra.

Suponiendo que comienza en un nodo determinado y desea enumerar todos los nodos que tienen distancias X al nodo inicial, simplemente ejecute BFS desde el nodo inicial. Cuando esté a punto de insertar un nuevo nodo en la cola, verifique si la distancia desde el nodo inicial al nodo que desea insertar es el nuevo nodo desde + el peso del borde desde el nodo desde el que desea insertar el nuevo nodo. el nuevo nodo es < = X. Si es estrictamente más bajo, inserte el nuevo nodo y si es igual, simplemente imprima el nuevo nodo (y solo insértelo si también puede tener 0 como un peso de borde).

Lista todos los usuarios en la red gráfica dada una distancia X y el tipo de relación

Véase más arriba. Simplemente tenga en cuenta el tipo de relación en el BFS: si el tipo del elemento primario es diferente al del nodo que está intentando insertar en la cola, no lo inserte.

calcular la trayectoria más corta entre 2 usuarios en la red gráfico dado un tipo de relación

El algoritmo depende de varios factores:

• ¿Con qué frecuencia es necesario calcular ¿esta?
• ¿Cuántos nodos tiene?

Como quiera fácil, las más fáciles son las de Roy-Floyd y Dijkstra.

• El uso de Roy-Floyd es cúbico en el número de nodos, tan ineficiente. Solo use esto si puede permitirse ejecutarlo una vez y luego responder cada consulta en O (1). Use esto si puede permitirse mantener una matriz de adyacencia en la memoria.
• Dijkstra's es cuadrática en el número de nodos si desea mantenerlo simple, pero deberá ejecutarlo cada vez que desee calcular la distancia entre dos nodos. Si desea usar Dijkstra, use una lista de adyacencia.

Éstos son implementaciones C: Roy-Floyd y Dijkstra_1, Dijkstra_2. Puede encontrar mucho en google con "<algorithm name> c implementation".

Editar: Roy-Floyd está fuera de la cuestión de 18 000 nodos, como es una matriz de adyacencia. Tomaría demasiado tiempo construir y demasiada memoria. Su mejor opción es usar el algoritmo de Dijkstra para cada consulta, pero preferiblemente implementar Dijkstra usando un montón. En los enlaces que proporcioné, use un montón para encontrar el mínimo. Si ejecuta el Dijkstra clásico en cada consulta, eso también podría llevar mucho tiempo.

Otra opción es usar el algoritmo Bellman-Ford en cada consulta, lo que le dará O(Nodes*Edges) tiempo de ejecución por consulta. Sin embargo, esta es una gran sobreestima si no la implementa como se lo ordena Wikipedia. En su lugar, use una cola similar a la usada en BFS. Siempre que un nodo actualice su distancia desde la fuente, inserte ese nodo nuevamente en la cola. Esto será muy rápido en la práctica, y también funcionará para pesos negativos. Te sugiero que uses este o el Dijkstra con montones, ya que el Dijkstra clásico puede llevar mucho tiempo en 18 000 nodos.

calcular la distancia máxima entre 2 usuarios en la red gráfica

La forma más sencilla es utilizar el retroceso: probar todas las posibilidades y mantener el camino más largo encontrado. This is NP-complete, por lo que las soluciones polinomiales no existen.

Esto es realmente malo si tienes 18 000 nodos, no conozco ningún algoritmo (simple o de otro tipo) que funcione razonablemente rápido para tantos nodos. Considere aproximarlo utilizando algoritmos codiciosos.O tal vez tu gráfico tiene ciertas propiedades que puedes aprovechar. Por ejemplo, ¿es un DAG (gráfico acíclico dirigido)?

Calcular los usuarios conectados más distantes de la red gráfica

Lo que significa que quiere encontrar el diámetro de la gráfica. La forma más simple de hacer esto es encontrar las distancias entre cada dos nodos (todos los pares de caminos más cortos), ya sea ejecutar Roy-Floyd o Dijkstra entre cada dos nodos y elegir los dos con la distancia máxima).

De nuevo, esto es muy difícil de hacer rápido con su número de nodos y bordes. Me temo que no tienes suerte en estas dos últimas preguntas, a menos que tu gráfica tenga propiedades especiales que puedan explotarse.

¿Crees que ayudaría si "convertí" el gráfico a una matriz de adyacencia para representar el peso del enlace y el tipo de relación? ¿Sería más fácil realizar el algoritmo en lugar de las listas vinculadas? Podría implementar fácilmente una función para hacer esa conversión cuando sea necesario. Estoy diciendo esto porque tuve la sensación de que sería más fácil después de leer un par de páginas sobre el tema, pero podría estar equivocado.

No, la matriz de adyacencia y Roy-Floyd son una muy mala idea a menos que su aplicación esté dirigida a supercomputadores.

Answer 2

Esto supone que O(E log V) es un tiempo de ejecución aceptable, si está haciendo algo en línea, esto podría no serlo, y requeriría una maquinaria de mayor potencia.

• Lista de todos los usuarios de la red gráfica dada una distancia X

Djikstra's algorithm es bueno para esto, para un solo uso. Puede guardar el resultado para usarlo en el futuro, con un escaneo lineal a través de todos los vértices (o mejor aún, ordenar y buscar binariamente).

Lista

• todos los usuarios en la red gráfica dada una distancia X y el tipo de relación

podría ser casi el mismo que el anterior - sólo tiene que utilizar alguna función donde el peso sería infinito si es no de la relación correcta.

• calcular la trayectoria más corta entre 2 usuarios en la red gráfico dado un tipo de relación

Igual que el anterior, en esencia, simplemente determinar temprano si coinciden los dos usuarios. (Como alternativa, puede "encontrarse en el medio", y terminar antes de tiempo si usted encuentra a alguien tanto más corta del árbol de expansión ruta)

• calcular la distancia máxima entre 2 usuarios en la red gráfica

Longest path es un NP-complete problem.

• calcular los usuarios conectados más distantes en la red gráfico

Este es el diámetro de la gráfica, que se puede leer en Math World.

En cuanto a la lista de adyacencia vs pregunta de matriz de adyacencia, depende de qué tan densamente poblada esté su gráfica. Además, si desea almacenar los resultados en caché, entonces la matriz podría ser el camino a seguir.

Answer 3

El algoritmo más simple para calcular la ruta más corta entre dos nodos es Floyd-Warshall. Es solo triple anidado para bucles; Eso es.

Se calcula TODO -pairs camino más corto en O(N^3), por lo que puede hacer más trabajo de lo necesario, y tardará un tiempo si N es enorme.