Gráfico (tipo de datos abstractos)

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

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 .

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 ∞.

	Lista de adyacencia	Matriz de adyacencia	Matriz de incidencia
Gráfico de la tienda	${\displaystyle O(|V|+|E|)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
Agregar vértice	${\estilo de visualización O(1)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
Añadir borde	${\estilo de visualización O(1)}$	${\estilo de visualización O(1)}$	${\displaystyle O(|V|\cdot |E|)}$
Eliminar vértice	${\displaystyle O(|E|)}$	${\displaystyle O(|V|^{2})}$	${\displaystyle O(|V|\cdot |E|)}$
Quitar borde	${\displaystyle O(|V|)}$	${\estilo de visualización O(1)}$	${\displaystyle O(|V|\cdot |E|)}$
¿Son los vértices x e y adyacentes (asumiendo que se conocen sus posiciones de almacenamiento)?	${\displaystyle O(|V|)}$	${\estilo de visualización O(1)}$	${\displaystyle O(|E|)}$
Observaciones	Lento para eliminar vértices y aristas, porque necesita encontrar todos los vértices o aristas	Lento para agregar o eliminar vértices, porque la matriz debe redimensionarse/copiarse	Es lento para agregar o eliminar vértices y aristas, porque la matriz debe redimensionarse/copiarse

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]}${\estilo de visualización |E|}$${\displaystyle |V|^{2}}$

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.${\estilo de visualización O(1)}$${\displaystyle O(\deg(x))}$${\displaystyle \deg(x)}$

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.

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.

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]${\estilo de visualización V}$${\estilo de visualización p}$${\displaystyle V_{0},\dots,V_{p-1}}$${\estilo de visualización 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]${\estilo de visualización 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}}$$estilo de visualización p_{r}}$$estilo de visualización p_{c}}$${\displaystyle (n/p_{r})\times (n/p_{c})}$$estilo de visualización p_{r}+p_{c}-1$${\displaystyle p=p_{r}\times p_{c}}$

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]

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]

• 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

Wikimedia Commons tiene medios relacionados con Gráfico (tipo de datos abstractos) .

• 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.