[ANN] NestedGraphs.jl

Package Announcements
, ,
1

I would like to announce a new package for the Graphs ecosystem of julia:
NestedGraphs.jl.
NestedGraphs.jl

As the name suggests, the package provides a way to handle nested graphs.
It’s meant to offer type-stable support, although some type-instabilities are lurking, which I still didn’t have the time to tackle.

I have yet to find another package in any programming language that implements nested graphs, so please mention if you know any. It would be nice to know about any future benchmarks.

Design

The basic idea is that every NestedGraph has a representation of a flat graph flatgr, which is created by merging all involved subgraphs into a single graph. This way, you can easily call all your favorite Graphs.jl functions using this field. Moreover, there is a nested representation through which all subgraphs can be accessed. (This actually means that there is a need for 2x the space requirements).
A NestedGraph can have a recursive structure by stacking many NestedGraphs.

The real effort behind NestedGraphs is actually synchronizing the flat graph with all the subgraphs when modifications/additions/removals of vertices, edges, subgraphs, and properties take place.
Wherever I saw possible, I used a shallow-reference, not only for saving memory space but mostly for easy updates. For example, with shallow references, changing the property of a node in the flat graph will automatically change the property also in the subgraph.

Future plans

There are also the following packages underway.

  • NestedGraphsIO.jl
    Read and write a NestedGraph using graphml. Supports also attributes, i.e., a MetaGraph or NestedGraph{MetaGraph}.
  • NestedGraphMakie.jl
    Implements ngraphplot() to visualize nested graphs. However, for now, it’s very very basic.
7 Likes
2

For a practical case study, Valhalla’s tile-based route search seems similar to me, which could be used for demos ( ~ reimplementing a simple route search example in Julia) or benchmarking.
( " Valhalla is an open source routing engine and accompanying libraries for use with OpenStreetMap data. " )

The Valhalla route map data tiles are in protobuf format, which is probably relatively easier to convert to Julia Graph format than to recreate from the original OpenStreetMap data.

I don’t know how much this tile-based route search problem overlaps with this package, but
if possible, it might be worth considering this at least at the design level, so that future development enhancements along these lines are easier.

Tiles along the Route Sketch

1 Like
3

These operations are known as graph contractions.

Efficient Implementation of Graph Algorithms Using Contraction discuss the practical way to implement these type of operations in a lazy way.

As mentioned by @ImreSamu, this is useful for shortest path problems, and this technique is known as Contraction Hierarchies

1 Like
4

You can probably use Tyler.jl for tile plotting, we just have to add protobuf support for the routes.

1 Like