Gráfico (tipo de datos abstractos)

Tipo de datos abstractos en informática.

Un gráfico dirigido con tres vértices (círculos azules) y tres aristas (flechas negras).

En informática , un gráfico es un tipo de datos abstracto cuyo objetivo es implementar los conceptos de gráfico no dirigido y gráfico dirigido del campo de la teoría de grafos dentro de las matemáticas .

Una estructura de datos de un gráfico consta de un conjunto finito (y posiblemente mutable) de vértices (también llamados nodos o puntos ), junto con un conjunto de pares desordenados de estos vértices para un gráfico no dirigido o un conjunto de pares ordenados para un gráfico dirigido. Estos pares se conocen como aristas (también llamadas enlaces o líneas ), y para un gráfico dirigido también se conocen como aristas pero a veces también flechas o arcos . Los vértices pueden ser parte de la estructura del gráfico o pueden ser entidades externas representadas por índices o referencias enteras .

Una estructura de datos de gráfico también puede asociar a cada arista algún valor de arista , como una etiqueta simbólica o un atributo numérico (coste, capacidad, longitud, etc.).

Operaciones

Diagrama de clases UML de un gráfico (tipo de datos abstracto)

Las operaciones básicas proporcionadas por una estructura de datos de gráficos G generalmente incluyen: ^[1]

• adyacente ( G , x , y ) : prueba si hay una arista desde el vértice x hasta el vértice y ;
• vecinos ( G , x ) : enumera todos los vértices y tales que hay una arista desde el vértice x hasta el vértice y ;
• add_vertex( G , x ) : agrega el vértice x , si no está allí;
• remove_vertex( G , x ) : elimina el vértice x , si está ahí;
• add_edge( G , x , y , z ) : agrega el borde z del vértice x al vértice y , si no está allí;
• remove_edge( G , x , y ) : elimina el borde del vértice x al vértice y , si está allí;
• get_vertex_value( G , x ) : devuelve el valor asociado con el vértice x ;
• set_vertex_value( G , x , v ) : establece el valor asociado con el vértice x a v .

Las estructuras que asocian valores a las aristas suelen proporcionar también: ^[1]

• get_edge_value( G , x , y ) : devuelve el valor asociado con el borde ( x , y );
• set_edge_value( G , x , y , v ) : establece el valor asociado con el borde ( x , y ) en v .

Estructuras de datos comunes para la representación de gráficos.

Lista de adyacencia ^[2]

Los vértices se almacenan como registros u objetos, y cada vértice almacena una lista de vértices adyacentes. Esta estructura de datos permite el almacenamiento de datos adicionales en los vértices. Se pueden almacenar datos adicionales si los bordes también se almacenan como objetos, en cuyo caso cada vértice almacena sus bordes incidentes y cada borde almacena sus vértices incidentes.

Matriz de adyacencia ^[3]

Una matriz bidimensional, en la que las filas representan los vértices de origen y las columnas representan los vértices de destino. Los datos sobre aristas y vértices deben almacenarse externamente. Solo se puede almacenar el costo de una arista entre cada par de vértices.

Matriz de incidencia ^[4]

Una matriz bidimensional, en la que las filas representan los vértices y las columnas representan las aristas. Las entradas indican la relación de incidencia entre el vértice de una fila y el borde de una columna.

La siguiente tabla muestra el costo de complejidad temporal de realizar varias operaciones en gráficos, para cada una de estas representaciones, con | V | el número de vértices y | mi | el número de aristas. ^{[ cita necesaria ]} En las representaciones matriciales, las entradas codifican el costo de seguir una ventaja. Se supone que el costo de las aristas que no están presentes es ∞.

Las listas de adyacencia generalmente se prefieren para la representación de gráficos dispersos , mientras que se prefiere una matriz de adyacencia si el gráfico es denso; es decir, el número de aristas | mi | está cerca del número de vértices al cuadrado, | V | ² , o si uno debe poder buscar rápidamente hacia arriba si hay una arista que conecta dos vértices. ^{[5] [6]}

Representación más eficiente de conjuntos de adyacencia

La complejidad temporal de las operaciones en la representación de la lista de adyacencia se puede mejorar almacenando los conjuntos de vértices adyacentes en estructuras de datos más eficientes, como tablas hash o árboles de búsqueda binarios equilibrados (la última representación requiere que los vértices se identifiquen mediante elementos de una secuencia ordenada linealmente). conjunto, como números enteros o cadenas de caracteres). Una representación de vértices adyacentes a través de tablas hash conduce a una complejidad de tiempo promedio amortizada de para probar la adyacencia de dos vértices dados y para eliminar un borde y una complejidad de tiempo promedio amortizada ^[7] de para eliminar un vértice dado x de grado . La complejidad temporal de las otras operaciones y el requisito de espacio asintótico no cambian. ${\displaystyle O(1)}$ ${\displaystyle O(\deg(x))}$ ${\displaystyle \deg(x)}$

Representaciones paralelas

La paralelización de problemas de gráficos enfrenta desafíos importantes: cálculos basados ​​en datos, problemas no estructurados, localidad deficiente y una alta proporción de acceso a datos para cálculo. ^{[8] [9]} La representación gráfica utilizada para arquitecturas paralelas juega un papel importante a la hora de afrontar esos desafíos. Las representaciones mal elegidas pueden aumentar innecesariamente el costo de comunicación del algoritmo, lo que disminuirá su escalabilidad . A continuación, se consideran las arquitecturas de memoria compartida y distribuida.

Memoria compartida

En el caso de un modelo de memoria compartida , las representaciones gráficas utilizadas para el procesamiento paralelo son las mismas que en el caso secuencial, ^[10] ya que el acceso paralelo de solo lectura a la representación gráfica (por ejemplo, una lista de adyacencia ) es eficiente en la memoria compartida.

Memoria distribuida

En el modelo de memoria distribuida , el enfoque habitual es dividir el conjunto de vértices del gráfico en conjuntos . Aquí está la cantidad de elementos de procesamiento disponibles (PE). Las particiones del conjunto de vértices luego se distribuyen a los PE con índice coincidente, además de a los bordes correspondientes. Cada PE tiene su propia representación de subgrafo , donde los bordes con un punto final en otra partición requieren atención especial. Para interfaces de comunicación estándar como MPI , el ID del PE propietario del otro punto final debe ser identificable. Durante el cálculo en algoritmos de gráficos distribuidos, pasar información a lo largo de estos bordes implica comunicación. ^[10] ${\displaystyle V}$ ${\displaystyle p}$ ${\displaystyle V_{0},\dots ,V_{p-1}}$ ${\displaystyle p}$

La partición del gráfico debe realizarse con cuidado: existe una compensación entre una comunicación baja y una partición de tamaño uniforme ^[11] Pero dividir un gráfico es un problema NP-difícil, por lo que no es factible calcularlos. En cambio, se utilizan las siguientes heurísticas.

Partición 1D: cada procesador obtiene vértices y las aristas salientes correspondientes. Esto puede entenderse como una descomposición por filas o columnas de la matriz de adyacencia. Para los algoritmos que operan en esta representación, esto requiere un paso de comunicación de todos a todos, así como tamaños de búfer de mensajes, ya que cada PE tiene potencialmente bordes de salida hacia todos los demás PE. ^[12] ${\displaystyle n/p}$ ${\displaystyle {\mathcal {O}}(m)}$

Partición 2D: cada procesador obtiene una submatriz de la matriz de adyacencia. Supongamos que los procesadores están alineados en un rectángulo , donde y son la cantidad de elementos de procesamiento en cada fila y columna, respectivamente. Luego, cada procesador obtiene una submatriz de la matriz de adyacencia de dimensión . Esto se puede visualizar como un patrón de tablero de ajedrez en una matriz. ^[12] Por lo tanto, cada unidad de procesamiento solo puede tener bordes de salida a PE en la misma fila y columna. Esto limita la cantidad de socios de comunicación para cada PE a un máximo de posibles. ${\displaystyle p=p_{r}\times p_{c}}$ ${\displaystyle p_{r}}$ ${\displaystyle p_{c}}$ ${\displaystyle (n/p_{r})\times (n/p_{c})}$ ${\displaystyle p_{r}+p_{c}-1}$ ${\displaystyle p=p_{r}\times p_{c}}$

Representaciones comprimidas

Los gráficos con billones de aristas se encuentran en el aprendizaje automático , el análisis de redes sociales y otras áreas. Se han desarrollado representaciones de gráficos comprimidos para reducir los requisitos de memoria y E/S. Se pueden aplicar técnicas generales como la codificación de Huffman , pero la lista de adyacencia o la matriz de adyacencia se pueden procesar de formas específicas para aumentar la eficiencia. ^[13]

Recorrido de gráficos

Primera búsqueda en amplitud y primera búsqueda en profundidad

La búsqueda en amplitud (BFS) y la búsqueda en profundidad (DFS) son dos enfoques estrechamente relacionados que se utilizan para explorar todos los nodos en un componente conectado determinado . Ambos comienzan con un nodo arbitrario, la " raíz ". ^[14]

Ver también

• Recorrido de gráficos para obtener más información sobre estrategias de recorrido de gráficos
• Base de datos de gráficos para persistencia de gráficos (estructura de datos)
• Reescritura de gráficos para transformaciones de gráficos basadas en reglas (estructuras de datos de gráficos)
• Software de dibujo de gráficos para software, sistemas y proveedores de sistemas para dibujar gráficos.

Referencias

1. Véase, por ejemplo, Goodrich & Tamassia (2015), Sección 13.1.2: Operaciones en gráficos, p. 360. Para un conjunto más detallado de operaciones, véase Mehlhorn, K .; Naher, S. (1999). "Capítulo 6: Gráficos y sus estructuras de datos". LEDA: una plataforma para computación combinatoria y geométrica (PDF) . Prensa de la Universidad de Cambridge. págs. 240–282.
2. Cormen et al. (2001), págs. 528–529; Goodrich y Tamassia (2015), págs. 361-362.
3. Cormen et al. (2001), págs. 529–530; Goodrich y Tamassia (2015), pág. 363.
4. Cormen et al. (2001), Ejercicio 22.1-7, pág. 531.
5. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Sección 22.1: Representaciones de gráficos". Introducción a los algoritmos (Segunda ed.). MIT Press y McGraw-Hill. págs. 527–531. ISBN 0-262-03293-7.
6. Goodrich, Michael T .; Tamassia, Roberto (2015). "Sección 13.1: Terminología y representaciones de gráficos". Diseño y aplicaciones de algoritmos . Wiley. págs. 355–364. ISBN 978-1-118-33591-8.
7. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009). Introducción a los algoritmos (3ª ed.). Instituto de Tecnología de Massachusetts. págs. 253–280. ISBN  978-0-262-03384-8.
8. Bader, David; Meyerhenke, Henning; Lijadoras, Peter; Wagner, Dorothea (enero de 2013). Partición de gráficos y agrupación de gráficos. Matemáticas Contemporáneas. vol. 588. Sociedad Matemática Estadounidense. doi :10.1090/conm/588/11709. ISBN 978-0-8218-9038-7.
9. Lumsdaine, Andrés; Gregor, Douglas; Hendrickson, Bruce; Berry, Jonathan (marzo de 2007). "Desafíos en el procesamiento de gráficos paralelos". Cartas de procesamiento paralelo . 17 (1): 5–20. doi :10.1142/s0129626407002843. ISSN  0129-6264.
10. Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martín; Dementiev, romano (2019). Algoritmos y estructuras de datos secuenciales y paralelos: la caja de herramientas básica. Publicaciones internacionales Springer. ISBN 978-3-030-25208-3.
11. "Procesamiento paralelo de gráficos" (PDF) .
12. Buluç, A.; Madduri, Kamesh (2011). "Aplicaciones". "Búsqueda paralela de amplitud primero en sistemas de memoria distribuida ". 2011 Conferencia internacional sobre informática, redes, almacenamiento y análisis de alto rendimiento. CiteSeerX 10.1.1.767.5248 . doi :10.1145/2063384.2063471. ISBN  978-1-4503-0771-0. S2CID  6540738.
13. Besta, Maciej; Hoefler, Torsten (27 de abril de 2019). "Estudio y taxonomía de compresión de gráficos sin pérdidas y representaciones de gráficos con uso eficiente del espacio". arXiv : 1806.01799 [cs.DS].
14. Purti (julio-septiembre de 2018). "Recorridos de gráficos y sus aplicaciones" (PDF) . Revista internacional de investigación y revisiones analíticas . 5 (3): 2.

enlaces externos

• Boost Graph Library: una potente biblioteca de gráficos C++ en Boost (bibliotecas C++)
• Networkx: una biblioteca de gráficos de Python
• GraphMatcher un programa java para alinear gráficos dirigidos/no dirigidos.
• GraphBLAS Una especificación para una interfaz de biblioteca para operaciones en gráficos, con un enfoque particular en gráficos dispersos.