www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [gsoc] graph library

reply Vasyl Teliman <vasniktel gmail.com> writes:
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 :)
Mar 16
parent reply Seb <seb wilzba.ch> writes:
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
Mar 22
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
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.)
Mar 22
prev sibling parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
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
Mar 27
parent reply Vasyl Teliman <vasniktel gmail.com> writes:
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
Mar 27
parent jmh530 <john.michael.hall gmail.com> writes:
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
Mar 27