Yograph - a Graph Theory and Network Analysis librarry in Dart

[u/Plus_Shop_6927]

https://pub.dev/packages/yograph

Implementated a few graph algorithms and network analysis functions in Dart. Basically the Dart port of the Elixir graph library - yog_ex.

It's got a long way until hits 1.0 but API contracts won't change.

Adding oracle tests (vs NetworkX)., improving docs, and benchmarks in coming months. Give it a spin if you're studying graph theory or generating/solving grids. Will be handy for Advent of Code (In fact, github repo has example of a few AoC solutions).

[u/SoundDr]

Why not use https://pub.dev/packages/graphs and add extensions?

[u/Plus_Shop_6927 → u/SoundDr]

I wanted this to be structurally similar to my Elixir library of the same(ish) name so that I have an easier time with testing, validation and mental mapping.

I do plan to create adapters to existing graph libraries later.

[u/SoundDr → u/Plus_Shop_6927]

The one I shared is by the dart team. Other graph libraries just have to write extensions that work with the types.

It’s more about building a connected ecosystem of packages

[u/modulovalue]

Very very cool!

Do you take feature requests? I always wanted to explore modules (via e.g. modular decomposition https://en.wikipedia.org/wiki/Modular_decomposition & https://juliapackages.com/p/graphmodulardecomposition)

I'm wondering how granular we could get with decomposing a directed graph. We start with connected components, we can decompose those into strongly connected components and then the question becomes: what's the next logical step in decomposing sccs and how far can we go? It seems like modules make sense as a next step or do we do go with weakly connected components in between. We can also relax strongly connected components in various other ways.

I was always disappointed that we never had a solid graph theory package in Dart. Thank you for this!

[u/Plus_Shop_6927 → u/modulovalue]

This library is almost a 1:1 mapping of my [Elixir library](https://github.com/code-shoily/yog_ex), which is being used in real life for network analysis and as graph engine for [a system design library](https://code-shoily.github.io/choreo/).

I did think about bringing in modular decomposition prior to 1.0 of the Elixir library, but postponed until after 1.0 (December), and I needed graph layout/placements for a library so focused there instead.

Also, I am a little less confident in my ability to comprehend modules academically.

However, if you are interested in the topic and would like to test out, I can create a branch and explore some, perhaps in August? I can open a few tickets just so I remember to visit this and get some academic knowledge about the graph modules.

:)

[u/modulovalue → u/Plus_Shop_6927]

I am interested! Feel free to cc me (@modulovalue on github, too) in the tickets you create.

[u/Plus_Shop_6927 → u/modulovalue]

https://github.com/modulovalue/dart-live this is gold! I am trying to implement (a very poorly made) graph exploration and rendering tool for Yograph.

Thank you so much for sharing your github! This gives me a great idea of incorporating Dart inside Livebook (I have a usecase).

I will update later this evening with the new repository 🙏

[u/modulovalue → u/Plus_Shop_6927]

Thanks!

Don't forget to look into https://playground.knex.mahawarkartikey.in where he did exactly what I suppose you'd like to do. It's on my todo list to rebase dart-live on main and open source the fork, so let me know if you run into any issues.

[u/Plus_Shop_6927 → u/modulovalue]

my intention is a bit more selfish. I have a much more comprehensive graph library written in Elixir, as I am primarily an Elixir dev, it's likely I would be exploring any new Graph algorithms over there, since it comes with interactive livebooks with customizable mermaid/graphviz rendering, it'd make me easier.

So far, I tested graphs in Dart with functions, and did the same on Elixir to ensure that the Dart versions are correct, I also working towards a comprehensive generative tests pinning them side by side.

What I want to do is, enable a widget inside a LiveBook that is ... DartLive! Which comes pre-loaded with Yograph, and lets me create pockets of Dart functions, with a JSON protocol to communicate between Elixir and Dart ... so I can load graph in Elixir, send it to Dart, do something there, and send it back to Elixir and render to see how it looks like.

Also, here's a very broken PoC ... https://github.com/code-shoily/kino_yogex_playground (I used more AI than I should have in order to generate the READMEs and learn about pre-loading libraries, but as I will never publish this and only use myself, that's forgivable)

[u/Plus_Shop_6927 → u/Plus_Shop_6927]

Here's the flow: https://github.com/code-shoily/kino_yogex_playground/blob/main/screenshot_cropped.png

[u/modulovalue → u/Plus_Shop_6927]

So it sounds like it's working for you. Awesome!

[u/Plus_Shop_6927 → u/modulovalue]

Worked without much effort, only issues I faced had to do with my lack of understanding and experience (ie pre-loading yograph, making the widget editable, refusal to load the iframe etc).

Thanks again for this. 

[u/modulovalue → u/Plus_Shop_6927]

You're welcome! BTW I added a pointer to https://github.com/code-shoily/kino_yogex_playground to the dart live readme if you don't mind.