search

apple / swift-algorithms

Commonly used sequence and collection algorithms for Swift
Apache License 2.0
5.9k stars 435 forks source link

Graph Structure #208

Open Tyler-Keith-Thompson opened 10 months ago

Tyler-Keith-Thompson commented 10 months ago

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 commented 10 months ago

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 commented 5 months ago

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.