Graph Structure

[Tyler-Keith-Thompson]

Apologies if this has been discussed, I looked just about everywhere I could think before creating the feature. I recently came into a need for a graph with a topological sort and was somewhat surprised to see there just don't appear to be Swift implementations that are really ready to use. There's some sparse projects that are kinda getting there...and then there's Swift Algorithm Club at least demonstrating how it could be pulled off.

To that end, I wonder if this library could benefit from an AdjacencyListGraph sequence type. I know that it'd be useful in a few different things I'm building, and building the data structure per project is a bit daunting. I'm hardly a Graph expert, but assuming general support, I'd be happy to create a draft PR for it and take on the dev effort.

[LucianoPAlmeida]

Hi,

To that end, I wonder if this library could benefit from an AdjacencyListGraph sequence type.

Given that this per description is a package of sequence and collection algorithms, along with their related types. I'm not sure a graph fits into this project since it would involve creating a different data structure which although one could argue could conform to Sequence or Collection is hard to see how a graph would sync a for exemple for sequence given a node i in an array the next element is i + 1, but for a graph given a node in a graph which is the next element? It depends of the kind of traversal you are doing in the graph so sequence and collection conformance seems to not fit well with a graph data structure IMO.

I know that it'd be useful in a few different things I'm building, and building the data structure per project is a bit daunting.

This seems like a good case for a Graph library, if there isn't one yet, a small library that implements a generic graph structure and graph specific algorithms such as topologic sort could be a good idea given that is straight forward to create a swift-package. So you would be able to reuse across all your projects =]

[fumoboy007]

I think the topological sort algorithm itself could be appropriate for this package. For example, the Swift Package Manager codebase has a generic implementation of this algorithm as a single function.

[aestriplex]

Hi all, since this issue is still open, I guess it is still to be implemented. I would start with the generic implementation suggested by @fumoboy007. In this regard, I was thinking:

• to create a data structure to represent the graph - containing the two parameters taken from the topologicalSort function (nodes: [T] and successors: (T) throws -> [T])
• to follow the “FIX ME” comment that suggests going to the iterative approach instead of the recursive one (here).

What are your thoughts on this?

[xwu]

How would you use such an API on a generic sequence or collection?

[aestriplex]

Good question. I am only speculating. One could

• limit its use to a hypothetical structure (something like) AcyclicGraph
• Or create a sequence of the type GraphSequence that extends the basic Sequence structure, in the same way that it is extended, for example, by AdjacentPairsSequence

[xwu]

As @LucianoPAlmeida has said, it doesn't sound like this API fits within the description of this package.