Hello.

My name is Vasyl Teliman. I'm a software engineering student from Ukraine. I'd like to participate in GSoC from the D language foundation. There was an idea of implementing a graph library for D:

https://wiki.dlang.org/GSOC_2017_Ideas#std.graph

I would like to know the opinion of the @community on this topic. Also, if someone wants to mentor this project, I would be very happy to discuss all the details with him.

Thanks in advance :)

On Saturday, 16 March 2019 at 13:42:24 UTC, Vasyl Teliman wrote:
> Hello.
>
> My name is Vasyl Teliman. I'm a software engineering student from Ukraine. I'd like to participate in GSoC from the D language foundation. There was an idea of implementing a graph library for D:
>
> https://wiki.dlang.org/GSOC_2017_Ideas#std.graph
>
> I would like to know the opinion of the @community on this topic. Also, if someone wants to mentor this project, I would be very happy to discuss all the details with him.
>
> Thanks in advance :)

Hi Vasyl,

thanks a lot for your interest in D.

I haven't worked with graphs for quite a while, but I think Dgraph [1] is still the only existing graph library written in D.
Maybe someone else knows more about this?
@community: would you like to have a better graph library?

I was just thinking about this and if you love to work on graphs, maybe we could combine this with a dub-related project (e.g. the dependencies are a DAG too, though at the moment it's a Tree [2]).

> Also, if someone wants to mentor this project,

I think the best person to ask would be Joseph Wakeling (https://github.com/WebDrake) as he's the author of Dgraph [1] and was a GSoC mentor in the past.

[1] https://github.com/WebDrake/Dgraph
[2] https://github.com/dlang/dub/blob/master/source/dub/dependencyresolver.d

On 22.03.19 11:43, Seb wrote:
> On Saturday, 16 March 2019 at 13:42:24 UTC, Vasyl Teliman wrote:
>> Hello.
>>
>> My name is Vasyl Teliman. I'm a software engineering student from Ukraine. I'd like to participate in GSoC from the D language foundation. There was an idea of implementing a graph library for D:
>>
>> https://wiki.dlang.org/GSOC_2017_Ideas#std.graph
>>
>> I would like to know the opinion of the @community on this topic. Also, if someone wants to mentor this project, I would be very happy to discuss all the details with him.
>>
>> Thanks in advance :)
> 
> Hi Vasyl,
> 
> thanks a lot for your interest in D.
> 
> I haven't worked with graphs for quite a while, but I think Dgraph [1] is still the only existing graph library written in D.
> Maybe someone else knows more about this?
> @community: would you like to have a better graph library?
> ...

Yes. It should be like std.range and std.algorithm. Have different abstract graph representations. (E.g. given a node, get a range of neighbors, or a graph given as just a range of edges, etc.) Algorithms can then transform graphs into others (e.g., lazily filter nodes and/or edges), or transform graphs into specific representations (analogous to std.array.array, e.g. an implicit edge list can be transformed into an explicit adjacency list), or combine multiple graphs to form new graphs (e.g., create a product graph). Then implement various less and more advanced graph algorithms in top of it with minimal requirements on the capabilities of the graph data structure, possibly with multiple different ways to consume the structure discovered by the algorithm. Simple examples: Some implementation of dfs could yield a lazy range of edges (with respective classification as forward/backward/cross edges), or some implementation of bfs could give you a range of ranges representing level sets, dijkstra can give you a lazy range of nodes with their respective distances to the start node ordered by distance. (For each of those, it can also make sense to report predecessors, or to simply return induced graphs, like the dfs tree or shortest-path DAG.)

Hello Vasyl and everyone,

On Friday, 22 March 2019 at 10:43:05 UTC, Seb wrote:
> I think the best person to ask would be Joseph Wakeling (https://github.com/WebDrake) as he's the author of Dgraph [1] and was a GSoC mentor in the past.

In principle I would love to, but I really don't have the time right now, and I don't think that is going to change by the time GSoC 2019 goes live :-(

A few thoughts on the more general idea:

I think the idea of a more fully featured graph library is great, but I don't think we should build a `std.graph`, as the standard library is not really the best place for something like this.

For a graph library to really be useful, it will need a much broader range of functionality than is appropriate for a standard library (look at pretty much any of the major graph frameworks used in science, e.g. igraph, or NetworkX, and they are BIG codebases).  It will also need to be flexible: it's likely that any such library will want to be flexible in how it revises its internal data structures over time, as needs and use-cases change.

So I would recommend that we focus on creating a good library, and forget getting anything into phobos.

In terms of design inspiration: it's been a long while since I last looked at Boost::Graph but my memory is of a template horror that seemed far more complex than it needed to be, and yet whose internal data structures were probably not the most efficient.  Don't take my word on this, I might be wrong (or just out of date), but it didn't seem like the best design concept to build from.  YMMV, of course ;-)

I also don't see the point in reproducing or closely mimicking a C++ API when the degree of C++ support is getting so much better.  Why not just use the existing library, or fix any blockers to doing so?

So, if we are going to do this, I would recommend:

  * implementing good underlying data structures before focusing on the user
    facing API

  * trying to create a friendly, idiomatic D API that does not too strongly mimic
    anything from other languages

  * ensuring friendly interop with Python, as a lot of people working in science
    will be using Python for their scripting, data science, and glue code

Lastly, regarding a remark in the proposal summary: who says DGraph is unmaintained? :-)  I'm not actively adding new features to it, as I don't have a personal use case, but if anyone has bugfixes or PRs, I would happily take a look.

Anyway, hope that helps, and apologies that I can't be of more active assistance,

All the best,

     -- Joe

On Wednesday, 27 March 2019 at 14:41:26 UTC, Joseph Rushton Wakeling wrote:
> [...]

Thanks for your replies, Seb, Timon and Joe.

Unfortunately, it seems that I am going to skip GSoC this year since I've got a lot of work to do recently. Nevertheless, I still have an interest in this project, so I will try to build this library anyway (although, not this summer it seems).

> So I would recommend that we focus on creating a good library, and forget getting anything into phobos.

This is not a problem at all :)

> In terms of design inspiration: it's been a long while since I last looked at Boost::Graph but my memory is of a template horror that seemed far more complex than it needed to be, and yet whose internal data structures were probably not the most efficient.

Boost::Graph is a complex library indeed. I would not like to overcomplicate the things that are relatively difficult by themselves. Still, BGL has some good ideas implemented (e.g. the ability to extend graph representation with your own containers) that might be worthwhile to add to this library.

> I also don't see the point in reproducing or closely mimicking a C++ API when the degree of C++ support is getting so much better.

Agreed.

>   * ensuring friendly interop with Python, as a lot of people working in science
>     will be using Python for their scripting, data science, and glue code

Interesting, is there any way to learn more about interop with Python for D?

--
Best wishes,
Vasyl

On Wednesday, 27 March 2019 at 15:53:59 UTC, Vasyl Teliman wrote:
> [snip]
>
> Interesting, is there any way to learn more about interop with Python for D?
>
> --
> Best wishes,
> Vasyl

Some links:
https://github.com/ariovistus/pyd
https://pyd.readthedocs.io/en/latest/
https://github.com/kaleidicassociates/autowrap