[gsoc] graph library

[Timon Gehr]

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.)