# Is there a lazy version of graph?

**URL:** <https://discourse.julialang.org/t/is-there-a-lazy-version-of-graph/73119>\
**Category:** Graphs\
**Tags:** lightgraphs, graphs\
**Created:** [December 15, 2021, 7:25am UTC](https://discourse.julialang.org/t/is-there-a-lazy-version-of-graph/73119 "2021-12-15T07:25:09Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![tk3369](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tk3369/32/2824_2.png) [@tk3369](https://discourse.julialang.org/u/tk3369)\
**Post date:** [December 15, 2021, 7:25am UTC](https://discourse.julialang.org/t/is-there-a-lazy-version-of-graph/73119/1 "2021-12-15T07:25:09Z")

</div>

I came across an interesting problem recently that can be solved with the shortest path algorithms from Graphs.jl. The only problem is that it takes a “long time” (julia scale 🙂 ) to build the graph because there are 250K vertices and ~1mm edges.

In my situation, the existence of these edges can be calculated on the fly. I wonder if it’s possible to build a lazy graph without having to materialize all the edges upfront. Perhaps I just pass a function that will return `true` if there’s an edge between the two vertices. My vertices are just numbered sequentially 1:n.

Does anyone know if Graphs.jl can support that or if there’s another package with such functionality? Thanks

---

<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:** [December 15, 2021, 8:46am UTC](https://discourse.julialang.org/t/is-there-a-lazy-version-of-graph/73119/2 "2021-12-15T08:46:24Z")

</div>

As far as I’m aware, there is still no package for building lazy graphs (and I think it would be an awesome feature). You can totally make a new graph type extending `AbstractGraph`, and use the functions of Graphs.jl.  
You just need to implement all the API functions, you can check [the documentation to create an alternate graph type](https://juliagraphs.org/Graphs.jl/dev/developing/#Developing-Alternate-Graph-Types). vertices are labelled by a subtype of `Integer`. Despite what claims the documentation, you should have the neighbors functions return vertices in ascending order and the vertices must form a continuous range starting from one (each vertex must be lower than `nv(g)`), otherwise some functions will not work as expected. This is especially true for `astar` implementation, where vertices are directly used for indexing.

You can implement `has_edge`, `outneighbors ` and `inneighbors` lazily.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [December 15, 2021, 8:51am UTC](https://discourse.julialang.org/t/is-there-a-lazy-version-of-graph/73119/3 "2021-12-15T08:51:41Z")

</div>

What is wrong in the docs? Doesn’t it say “ascending order”?

---

<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:** [December 15, 2021, 8:55am UTC](https://discourse.julialang.org/t/is-there-a-lazy-version-of-graph/73119/4 "2021-12-15T08:55:05Z")

</div>

Yes, but it does not speak of continous range starting from one, and ascending order is only for `AbstractSimpleGraph`, so in theory, `AbstractGraph` doesn’t require it, but I’m not sure how well this is respected in the codebase…

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [December 15, 2021, 9:01am UTC](https://discourse.julialang.org/t/is-there-a-lazy-version-of-graph/73119/5 "2021-12-15T09:01:09Z")

</div>

Ok, let’s update that

---

<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:** [December 15, 2021, 9:06am UTC](https://discourse.julialang.org/t/is-there-a-lazy-version-of-graph/73119/6 "2021-12-15T09:06:55Z")

</div>

Also, if your performance problem is only in building the graph, how do you construct it? If you add every single edge one by one, this is a very inefficient way to build it, because SimpleGraphs maintain the adjacency lists in ascending order, so it does recompute a lot of things for each edge addition. Edge addition is not constant time for SimpleGraph because of it’s internal structure. You can improve this by batching edge additions, or directly building the `fadjlist` (and `badjlist` for directed graphs) yourself.

---

<div class="post-metadata">

**Author:** ![tk3369](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tk3369/32/2824_2.png) [@tk3369](https://discourse.julialang.org/u/tk3369)\
**Post date:** [December 16, 2021, 7:41am UTC](https://discourse.julialang.org/t/is-there-a-lazy-version-of-graph/73119/7 "2021-12-16T07:41:55Z")

</div>

Quick update:  
It turns out that my performance problem came from populating the sparse array rather than constructing the graph. I use a sparse matrix to keep track of the edge distances, and the `setindex!` calls to the array took the majority of time. That’s actually a little surprising though… I will check further when I have time later.

Thanks for the ideas above and sorry about the noise 😛

Tom

P.S. I create all edges in an array and make a single call to create the graph.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [December 16, 2021, 3:55pm UTC](https://discourse.julialang.org/t/is-there-a-lazy-version-of-graph/73119/8 "2021-12-16T15:55:06Z")

</div>

Creating an empty sparse matrix and filling it with `setindex!` isn’t particular fast because the CSC format is optimised for efficient arithmetic operations and not for changes to the sparsity structure.