I had a wonderful experience participating in the 2022 Swift Mentorship and would like to participate in this year's GSoC. The project idea is to introduce a new Swift graph library as described here. I am looking for a mentor to work with me on this project.
In short, the project aims to add support for graph algorithms that are less dependent on the underlying data structure. This would complement swift-collections and add new primitive operations for new algorithms. In particular, to add structure graph traversal with expressive Swift syntax. I'm thinking here of something like a "BreadFirstSequence", "DepthFirstSequence" to begin with. We could benchmark the Collections already available.
I'm interested in expanding our graph algorithms, but there's a question of whether these distinctions are best expressed at the type level or if these are different algorithms that you apply to common types/protocols (e.g. -first and depth-first traversal could be algorithms exposed on a common tree protocol/type, rather than needing to be handled differently as types). So my initial reaction is that it probably makes more sense to think of these as families of algorithms on one or more concrete types initially, which we could then think about abstracting over protocols (we don't really have a tree-/graph-specific abstraction at present, so I expect that might be part of this). @nnnnnnnn or @Karoy_Lorentey probably have more specific thoughts about how this would fit together.
TL;dr, I think we'd be interested in designing and implementing these sorts of algorithms, exactly how those fit into swift-algorithms or swift-collections would have to be explored.
Yes, I agree that some exploration has to be done where exactly these type of algorithms fit best. I am also not sure about that either. On the one hand, I think that an implementation of BFS and DFS sequences seems to need a basic data structure to keep track of the visited nodes. We have a Deque in swift-collections. On the other hand, graph algorithms are about efficient traversals (dictated by the relationships), and not about storing data. In this sense Swift-algorithms is closer to the latter, but the scope of graph algorithms seems to be too specific to fit there.
We can learn a lot and be inspired by the ongoing work on graphs in C++. This talk summarizes a lot of learning from previous projects and years of experience. I believe that Swift is also in a good position to introduce a general-purpose graph library. Standing on the shoulders of giants, we also have the interfaces on the Standard library to introduce a new protocol for an adjacency list representation of a Graph. Unlike C++, Swift has powerful enumerations for exploring multi-partite graphs, and more facilities for writing expressive functional programming code for that purposes
Hi @nnnnnnnn@Karoy_Lorentey
it's been a while and i'm working on the proposal submission, what are your thoughts on where this type of project would fit.
Let me be more precise about the comment that I made about "Graph algorithms seems to be too specific to fit there". My feeling here is more about the question on how graph algorithms will grow within this package. I'd like to think that there will be more support in the future. As you can see from the link above, the C++ graph algorithms will support quite a few , and we should leave the door open for more contributions like this in Swift as well. What do you think?
This project proposal should maybe just concentrate on getting this started, and focus on investigating a general tree-/graph abstraction that is missing in Swift. Based on my own experiments, I find the abstraction of adjacency list as a random-access collection of collections to be promising in Swift as well. Something like
/// AdjList(G) is a random access collection of collections
public protocol AdjacencyList<VertexIdentifier>: RandomAccessCollection where Self.Element : Collection {
/// Type used to access the RandomAccessCollection through subscript, like ``G[u]``. Canonical example: Int, but it could be a "handle" to the vertex
associatedtype VertexIdentifier: SomeConstraintsTBD
typealias InnerCollection = Self.Element
typealias Edge = InnerCollection.Element
/// This method gives us neighbourhood access.
/// From an edge element we must have a type to reference other vertices
/// In the general case, one could think of edges as tuples (carrying not only vertex, but edge data as well) and this function as a projection onto the target vertex. This should be investigated more in depth
func target(_ edge: Edge) -> VertexIdentifier
}
With this abstraction we can introduce BreadthFirstSequence and DepthFirstSequence. From my experiments, however the only thing you need is a queue data structure. An implementation of AdjacencyList, together with the containers that store the vertex and edge data, forms a graph.
Note that we talk about an adjacency list representation of a graph because 1) Swift does not have yet a general-purpose Matrix library at the moment; 2) the adjacency list representation is more flexible to adapt to different applications.
TL;dr, I know you are probably in a busy moment. Do you think the following goals are reasonable for a GSoC project proposal?
Define a general tree-/graph abstraction. Starting with concrete types and then lifting to a protocol.
Implement structured traversal of graphs independent of the underlying data structure, e.g. breadth-first, depth-first traversals
(Optional, if time permits) Implement Dijkstra shortest path, Bellman-Ford shortest path, Topological sorting algorithms.
-first and depth-first traversal could be algorithms exposed on a common tree protocol/type, rather than needing to be handled differently as types). So my initial reaction is that it probably makes more sense to think of these as families of algorithms on one or more concrete types initially, which we could then think about abstracting over protocols (we don't really have a tree-/graph-specific abstraction at present, so I expect that might be part of this).