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 2019
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 2019
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 2019
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 2019
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 2019
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 2019