# \[ANN\] NestedGraphs.jl

**URL:** <https://discourse.julialang.org/t/ann-nestedgraphs-jl/93093>\
**Category:** Package Announcements\
**Tags:** package, announcement, graphs\
**Created:** [January 17, 2023, 2:07pm UTC](https://discourse.julialang.org/t/ann-nestedgraphs-jl/93093 "2023-01-17T14:07:51Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![filchristou](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/filchristou/32/26760_2.png) [@filchristou](https://discourse.julialang.org/u/filchristou)\
**Post date:** [January 17, 2023, 2:07pm UTC](https://discourse.julialang.org/t/ann-nestedgraphs-jl/93093/1 "2023-01-17T14:07:51Z")

</div>

I would like to announce a new package for the Graphs ecosystem of julia:  
[`NestedGraphs.jl`](https://github.com/UniStuttgart-IKR/NestedGraphs.jl).

 ![NestedGraphs.jl](https://global.discourse-cdn.com/julialang/original/3X/3/f/3fdf09a23a1c41a409167db1cc500e986414a689.png)

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 `NestedGraph`s.

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](https://github.com/UniStuttgart-IKR/NestedGraphsIO.jl)  
Read and write a `NestedGraph` using [graphml](http://graphml.graphdrawing.org/). Supports also attributes, i.e., a `MetaGraph` or `NestedGraph{MetaGraph}`.
- [NestedGraphMakie.jl](https://github.com/UniStuttgart-IKR/NestedGraphMakie.jl)  
Implements `ngraphplot()` to visualize nested graphs. However, for now, it’s very very basic.

---

<div class="post-metadata">

**Author:** ![ImreSamu](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/imresamu/32/20677_2.png) [@ImreSamu](https://discourse.julialang.org/u/ImreSamu)\
**Post date:** [January 18, 2023, 6:00am UTC](https://discourse.julialang.org/t/ann-nestedgraphs-jl/93093/2 "2023-01-18T06:00:02Z")

</div>

> [@filchristou](#):
>
> 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.

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](https://github.com/valhalla/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](https://github.com/valhalla/valhalla/tree/master/proto), 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](https://global.discourse-cdn.com/julialang/original/3X/1/f/1ff9cb1cc0e966ea48e6390c45e2f40d85ecffa0.gif)

- [Why tiles? - Valhalla Docs](https://valhalla.github.io/valhalla/mjolnir/why_tiles/)
- [Tile structure - Valhalla Docs](https://valhalla.github.io/valhalla/tiles/)

---

<div class="post-metadata">

**Author:** ![etienne\_dg](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)\
**Post date:** [January 18, 2023, 12:47pm UTC](https://discourse.julialang.org/t/ann-nestedgraphs-jl/93093/3 "2023-01-18T12:47:21Z")

</div>

These operations are known as graph contractions.

[Efficient Implementation of Graph Algorithms Using Contraction](https://dl.acm.org/doi/pdf/10.1145/65950.65954) 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](https://en.wikipedia.org/wiki/Contraction_hierarchies)

---

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [January 18, 2023, 3:48pm UTC](https://discourse.julialang.org/t/ann-nestedgraphs-jl/93093/4 "2023-01-18T15:48:27Z")

</div>

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