[WIP] SimpleLazyGraphs.jl - add vertices and edges as needed

Hello all, I’d like to introduce a small module I’ve been trying to implement called SimpleLazyGraphs.jl: GitHub - acxz/SimpleLazyGraphs.jl: Graph data structures to add vertices and edges as needed for Graphs.jl.

Effectively, this module is inspired by the following issue: a_star dynamic neighbor creation · Issue #115 · JuliaGraphs/Graphs.jl · GitHub

I’d love to gain feedback on the code that I have already written and suggestions on how to make it more Julian as this is my first time “subtyping” existing types and I’ve been learning quite a few things along the way.

I also have many questions that I’m hoping folks can help me out on.

First, I’ll describe what I’d like this package to be. Basically, I want to piggyback off of the type SimpleGraphs and use the entire functionality of it, besides two methods (inneighbors & outneighbors) I’d like “overridden” (forgive me for my OOP lingo) or should I say dispatched on my new type SimpleLazyGraph instead of the existing SimpleGraph.

As you can see in the code I’ve done that. However, as an added caveat, I’d like to also use the original functionality of SimpleGraph’s in/outneighbors method. As you can also see in the code, I had attempted to use @invoke, however, it did not work for me and I had to essentially copy and paste the implementation of SimpleGraph’s in/outneighbors methods as well as other methods that I needed to just test the functionality like add_vertex! and add_edge!. Ideally, my SimpleLazyGraph should be able to use the SimpleGraph’s version of these methods.

The second point is about the proper design of the type SimpleLazyGraph. The way I’d like to change in/outneighbors is by adding a user defined function. How can/should I do this? As of right now, the user passes in these functions when defining a SimpleLazyGraph and I say those functions inside the SimpleLazyGraph type so that my dispatched in/outneighbors functions can use them. It is important that the method signature (in terms of arguments) stays the same so that I can utilize the functionality of the Graphs.jl library, in particular the A* algorithm for my specific use case.

So while, the functionality of lazily adding to a graph works in my test/runtests.jl, my SimpleLazyGraphs.jl package doesn’t have the mechanism to run the Graphs a_star algorithm yet. I’d like to do this with as much code reuse as possible.

Thank you for reading this and I would appreciate any help to better understand how to do this task.

2 Likes

ninja edit: If you also have any suggestions on the name, or how to create lazy graphs in a more performant manner please mention that as well. Although, since I’m a bit new to creating julia packages I’d like to understand proper Julia architecture.

Looks good! Do I have to use GraphPlot.jl? ( I don’t think Graphs.jl requires GraphPlot.jl…)

Thanks! Do you believe the value prop offered by this package is useful?

I’d like to use GraphPlot on my SimpleLazyGraphs, but again similar to a_star I’d need to copy paste quite a lot of SimpleGraphs methods (as i understand currently, if anyone can show me how to get around this that would be great).

I’ll remove GraphPlot from the deps for now. Is it possible to have testing deps? If so, I’d like to move GraphPlot there.

1 Like

I’ll remove GraphPlot from the deps for now. Is it possible to have testing deps? If so, I’d like to move GraphPlot there.

Done, using the older Julia 1.1/2 style testdep for now. 5. Creating Packages · Pkg.jl

1 Like

I think understanding this thread: Composition and inheritance: the Julian way may give me the answers I need.
Maybe Graphs.jl would also need some PRs to make some of their methods dispatch on AbstractSimpleGraph instead of the concrete SimpleGraph?

For the first point, I believe I am now properly using composition.

However, I am still unsure what is the best way of going about user defined function fields. Maybe type parameterization on the function?

Edit: Yep this did the trick! See the commit: parameterize struct on input function subtype · acxz/SimpleLazyGraphs.jl@3da2660 · GitHub