GraphIdx

GraphIdx.jl

This is the Julia part of GraphIdx, a framework for index-based graphs. Some parts are also implemented in

The main module is

GraphIdx.GraphIdx — Module.

Index-based Graphs

Nodes

A node (sometimes also vertex called) in a graph is always represented as an integer. To be able to use a node as an index, the nodes should be within 1:n whereby n is the number of nodes. Furtheron, we always use signed integers because we might include extra information within the first (sign) bit.

Edges

By convention, a graph is considered undirected (unless specified else). Hence we only need to store one direction of every edge (u, v); by default we assume u < v.

TODO:

  • differences
  • incidence matrix

If any flow αfor an edge(u, v)has to be computed, the orientation is defined as going fromvtou` (big to small), i.e. we compute

x[u] += α
x[v] -= α

Submodules

The most important submodules are

  • Tree: Rooted Trees (including minimum spanning trees).
  • Grid: Specialized code for grid graphs.
  • LinA: Linear algebra (e.g. incidence matrix)
source

Example

Generate a random spanning tree on a 20×32 grid graph:

import GraphIdx.Grid: GridGraph
import GraphIdx.IncidenceIndex

TODO: Extend

API