## IndexedGraphs.jl

A minimal Graphs.jl implementation of SparseMatrixCSC-based graphs with arbitrary properties
Author stecrotti
Popularity
9 Stars
Updated Last
1 Year Ago
Started In
January 2022

# IndexedGraphs.jl

Not all edges come with an index. These do

## Documentation

https://stecrotti.github.io/IndexedGraphs.jl/dev

## Overview

A Graphs.jl-compatible implementation of SparseMatrixCSC-based graphs, allowing fast access to arbitrary edge properties

• The code implements the Graphs.jl interface for directed and undirected graphs.
• Edge properties live separate from the graph, so different sets of properties can be associated to the same graph.
• In addition, it implements `inedges` and `outedges` for O(1) access to neighborhood
• Edges are indexed, and the index can be used to access edge properties very efficiently.
• `IndexedBiDirectedGraphs` store both the direct and the transposed adjancency matrix for efficient access

A number of other packages implement graph based on CSC matrix representation or similar, namely StaticGraphs, SimpleWeightedGraphs and MatrixNetworks

• StaticGraphs: No edge properties
• SimpleWeightedGraphs: Also based on `SparseMatrixCSC`, allows for numerical edge properties. However, no edge weight can be 0 (or otherwise the edge is sometimes removed), and does not allow arbitrary edge properties
• MatrixNetworks: Also based on `SparseMatrixCSC`, allows for numerical edge properties. However, no edge weight can be 0 (or otherwise the edge is sometimes removed), and does not allow arbitrary edge properties. Does not implement the Graphs interface.

## Navigating graphs

The most natural and efficient way to iterate over an `IndexedGraph` is to iterate over neighboring nodes or edges

``````A = [0 0 1;
1 0 0;
1 1 0]
g = IndexedDiGraph(A)
i = 3
out_i = outedges(g, i)
collect(out_i)
``````

outputs:

``````2-element Vector{IndexedGraphs.IndexedEdge{Int64}}:
Indexed Edge 3 => 1 with index 4
Indexed Edge 3 => 2 with index 5
``````

Edge indices, 4 and 5 in this case, can be extracted with `idx` and used to access properties stored in a separate container

``````e = first(out_i)
src(e), dst(e), idx(e)
``````

outputs:

``````(3, 1, 4)
``````

## Benchmark

Performance on Dijkstra's algorithm compared with the packages listed above, as computed here for a random symmetric weight matrix with 10^4 nodes and ~10^5 edges.

``````IndexedDiGraph:
2.840 ms (22 allocations: 547.91 KiB)
IndexedGraph:
3.131 ms (22 allocations: 547.91 KiB)
MatrixNetwork:
3.031 ms (13 allocations: 407.45 KiB)
SimpleGraph
11.935 ms (45 allocations: 1008.58 KiB)
SimpleWeightedGraph:
10.610 ms (45 allocations: 1008.58 KiB)
ValGraph (SimpleValueGraphs.Experimental):
6.620 ms (48 allocations: 1000.06 KiB)
``````

Note: For an undirected graph, `IndexedGraph` gives one unique index to each undirected edge (`i=>j` and `j=>i` have the same index). This makes the memory layout less efficient when traversing the graph (although it is very efficient to modify the properties compared with the alternatives). If no property modification is needed, as is the case with Dijkstra, it is more convenient to just employ an `IndexedDiGraph` with symmetric edges and weights.

### Used By Packages

No packages found.