¿Matriz dispersa funcional con buen rendimiento?

8

Mientras escribía un programa de Petri Net, me encontré con una elección sobre las estructuras de datos para representar el gráfico. Las listas de adyacencia (es decir, listas que enumeran los arcos dentro y fuera de lugares o transiciones individuales) son fáciles de implementar, pero mientras estudiaba la teoría de las redes de Petri, me cautivó la belleza del enfoque de ecuación de estado basado en matrices , que presumiblemente requeriría que use matrices dispersas.

Lo que me llevó a preguntarme: ¿hay implementaciones de matrices dispersas que proporcionen una enumeración rápida tanto en filas como en columnas? Si no, ¿hay alternativas que me permitan construir y atravesar eficientemente un gráfico bipartito en un lenguaje funcional como Erlang?

FWIW - Por 'eficientemente', en este caso, me refiero a enumerar rápidamente los incidentes de arcos en una transición o lugar dado. Sería más feliz cambiar el espacio por tiempo si hay que hacer concesiones. Dado que el gráfico no se modificará después de la construcción, no es necesario que sea particularmente eficiente para las inserciones o actualizaciones.

TIA

Andrew Matthews
fuente

Respuestas:

5

Buluç y col. (2009) proponen un formato de almacenamiento llamado bloques dispersos comprimidos que no favorece filas o columnas. Una matriz se subdivide en bloques y la lista de elementos distintos de cero en cada bloque se almacena en el orden Z-Morton. Para enumerar los nonzeros en una fila o columna, puede procesar los bloques que lo contienen, encontrando recursivamente los nonzeros en cada bloque en .norte×norteβ×βnorte/ /βO(β)

Marcus Ritt
fuente