Gráfico (tipo de datos abstractos)

Tipos 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 que pretende 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 grafo consiste en 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 grafo no dirigido o un conjunto de pares ordenados para un grafo dirigido. Estos pares se conocen como aristas (también llamados enlaces o líneas ), y para un grafo dirigido también se conocen como aristas pero también a veces flechas o arcos . Los vértices pueden ser parte de la estructura del grafo, o pueden ser entidades externas representadas por índices enteros o referencias .

Una estructura de datos gráfica también puede asociar a cada borde algún valor de borde , como una etiqueta simbólica o un atributo numérico (costo, 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 gráfica 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á allí;
• add_edge( G , x , y , z ) : agrega la arista z del vértice x al vértice y , si no está allí;
• remove_edge( G , x , y ) : elimina la arista 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 los bordes generalmente también proporcionan: ^[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 gráfica

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 sobre los vértices. Se pueden almacenar datos adicionales si las aristas también se almacenan como objetos, en cuyo caso cada vértice almacena sus aristas incidentes y cada arista almacena sus vértices incidentes.

Matriz de adyacencia ^[3]

Matriz bidimensional en la que las filas representan los vértices de origen y las columnas los vértices de destino. Los datos sobre los bordes y los vértices deben almacenarse externamente. Solo se puede almacenar el costo de un borde entre cada par de vértices.

Matriz de incidencia ^[4]

Matriz bidimensional en la que las filas representan los vértices y las columnas las aristas. Las entradas indican la relación de incidencia entre el vértice de una fila y la arista 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 | E | el número de aristas. ^{[ cita requerida ]} En las representaciones matriciales, las entradas codifican el costo de seguir una arista. 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 una matriz de adyacencia se prefiere si el gráfico es denso; es decir, el número de aristas es cercano al número de vértices al cuadrado , o si uno debe poder buscar rápidamente si hay una arista que conecta dos vértices. ^{[5] [6]} ${\displaystyle |E|}$ ${\displaystyle |V|^{2}}$

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 binaria balanceados (la última representación requiere que los vértices se identifiquen por elementos de un conjunto ordenado linealmente, como números enteros o cadenas de caracteres). Una representación de vértices adyacentes mediante tablas hash conduce a una complejidad temporal promedio amortizada de para probar la adyacencia de dos vértices dados y para eliminar una arista y una complejidad temporal 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 grafos enfrenta desafíos significativos: cálculos basados ​​en datos, problemas no estructurados, localidad deficiente y alta relación de acceso a datos por cómputo. ^{[8] [9]} La representación gráfica utilizada para arquitecturas paralelas juega un papel importante para enfrentar 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 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 particionar el conjunto de vértices del grafo en conjuntos . Aquí, es la cantidad de elementos de procesamiento (PE) disponibles. Las particiones del conjunto de vértices se distribuyen luego 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 que posee el otro punto final tiene que ser identificable. Durante el cálculo en algoritmos de grafos 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 un equilibrio entre una comunicación baja y una partición de tamaño uniforme ^[11]. Sin embargo, la partición de un gráfico es un problema NP-hard, por lo que no es factible calcularlas. En su lugar, se utilizan las siguientes heurísticas.

Partición 1D: cada procesador obtiene vértices y sus correspondientes aristas salientes. Esto puede entenderse como una descomposición por filas o por 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 aristas salientes 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. Entonces 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 aristas salientes a los PE en la misma fila y columna. Esto limita la cantidad de socios de comunicación para cada PE a un máximo de los 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 gráficas comprimidas para reducir los requisitos de memoria y de 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 maneras específicas para aumentar la eficiencia. ^[13]

Recorrido de gráficos

Búsqueda en amplitud y búsqueda en profundidad

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

Véase también

• Recorrido gráfico para obtener más información sobre las estrategias de recorrido gráfico
• Base de datos gráfica para persistencia de gráficos (estructura de datos)
• Reescritura de gráficos para transformaciones basadas en reglas de gráficos (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 y Tamassia (2015), Sección 13.1.2: Operaciones sobre grafos, pág. 360. Para un conjunto más detallado de operaciones, véase Mehlhorn, K .; Näher, S. (1999). "Capítulo 6: Gráficos y sus estructuras de datos". LEDA: una plataforma para computación combinatoria y geométrica (PDF) . Cambridge University Press. 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 grafos". Introducción a los algoritmos (segunda edición). 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 grafos". Diseño de algoritmos y aplicaciones . 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 Tecnológico de Massachusetts. págs. 253–280. ISBN  978-0-262-03384-8.
8. Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea (enero de 2013). Partición de grafos y agrupamiento de grafos. Matemáticas contemporáneas. Vol. 588. American Mathematical Society. doi :10.1090/conm/588/11709. ISBN. 978-0-8218-9038-7.
9. Lumsdaine, Andrew; Gregor, Douglas; Hendrickson, Bruce; Berry, Jonathan (marzo de 2007). "Desafíos en el procesamiento de gráficos en paralelo". Parallel Processing Letters . 17 (1): 5–20. doi :10.1142/s0129626407002843. ISSN  0129-6264.
10. Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Algoritmos secuenciales y paralelos y estructuras de datos: la caja de herramientas básica. Springer International Publishing. ISBN 978-3-030-25208-3.
11. "Procesamiento paralelo de gráficos" (PDF) . Archivado desde el original (PDF) el 25 de agosto de 2021 . Consultado el 9 de marzo de 2020 .
12. Buluç, A.; Madduri, Kamesh (2011). "Aplicaciones". Búsqueda en amplitud paralela en sistemas de memoria distribuida . Conferencia internacional de 2011 sobre computación de alto rendimiento, redes, almacenamiento y análisis. CiteSeerX 10.1.1.767.5248 . doi :10.1145/2063384.2063471. ISBN  978-1-4503-0771-0.S2CID6540738  .​
13. Besta, Maciej; Hoefler, Torsten (27 de abril de 2019). "Estudio y taxonomía de la compresión de gráficos sin pérdida y representaciones de gráficos con uso eficiente del espacio". arXiv : 1806.01799 [cs.DS].
14. Purti (julio-septiembre de 2018). "Recorridos de grafos y sus aplicaciones" (PDF) . Revista internacional de investigaciones y revisiones analíticas . 5 (3): 2.

Enlaces externos

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