Initial commit! Pushing to show progress, potentially get insight from others.

It would be great to see if we could implement it such that the generic classes' types didn't require conforming to Codable and that it would only be necessary when wanted to the classes as Codable. However Swift's init methods as well as where clauses have limitations with extensions that I haven't figured out how to work the way I am hoping.

Also tests need cleaning and elaboration.

I'm interested in contributing graph union operation: http://mathworld.wolfram.com/GraphUnion.html It should be quite straightforward for unweighted graphs. For weighted graphs, we need to add different ways to handle weight conflicts on common edges:

• Built in "reducers": sum, average, min, max.
• Support custom reducers.
• Report conflicts as exceptions or errors (this could be modeled as a reducer too)

My only question is how to compute the disjoint set union. You store edges and nodes as Array. Is building a Set from one array, use Set.formUnion and then convert back to array a good solution? I can't find info on computational complexity for these operations.

PS: maybe it makes more sense for the weighted case to just treat edges between same nodes as distinct edges. Then add another operation that merges edges between common nodes.

In this PR I add a subclass of UniqueElementsGraph with the property that vertices have at most one outgoing edge [1].

I also introduce SwiftCheck for property testing.

[1] https://en.wikipedia.org/wiki/Pseudoforest#Directed_pseudoforests

It would be useful to have a method that finds all elementary cycles (where no vertex is repeated except for the start/end one) in a directed graph. Here's an example from Mathematica: https://mathematica.stackexchange.com/questions/9434/finding-elementary-cycles-of-directed-graphs

Introduction

This PR is the follow of PR #43.

The goals of this PR are:

• Remove code duplication and homogenize the api for DFS and BFS.
• Extend the api for DFS and BFS so an arbitrary computation can be performed over a graph (a closure is fed with the graph vertices in a DFS or BFS order).

Explanation of the changes

GraphTraverser is a protocol representing an algorithm to traverse a graph. Types implementing it implement a graph traversal algorithm in its from(_ initalVertexIndex: Int, goalTest: (Int) -> Bool, reducer: G.Reducer) -> Int? method.

An extension to GraphTraverser provides with default implementations for several convenience methods that wrap from(_ initalVertexIndex: Int, goalTest: (Int) -> Bool, reducer: G.Reducer) -> Int?.

DFS and BFS are structs conforming to GraphTraverser, so both algorithms have the same api provided by the extension. Furthermore, both for BFS and DFS, there's an extension to Graph with convenience methods to perform a search by calling a method on a graph instance.

DFSVisitOrder and BFSVisitOrder are variants of DFS and BFS that can guarantee a certain order of traversal for the neighbors of each visited vertex. I've kept them as a separate algorithm because the visit order has a performance penalty, even when the ordering closure is a no-op ({ $0 }). DFSand BFS have the withVisitOrder method to easily construct a DFSVisitOrder and BFSVisitOrder variant.

Examples

// Perform a DFS on graph from Seattle to Miami
_ = graph.dfs(from: "Seattle", to: "Miami")
_ = DFS(on: graph).from("Seattle", to: "Miami")

// Perform a BFS on graph visiting neighbors in lexicographic order
_ = BFS(on: graph)
         .withVisitOrder({ $0.sorted(by: { $0.v < $1.v }) })
         .from(index: 0, toIndex: 5)
_ = BFSVisitOrder(on: graph, withVisitOrder: { $0.sorted(by: { $0.v < $1.v }) }))
         .from(index: 0, toIndex: 5)

// Perform an abstract computation over graph in a depth-first order
_ = DFS(on: graph).from(0, goalTest: somePredicate, reducer: { print($0) })

API Changes

This PR introduces one and only one breaking api change: findAll is gone, now you must choose between findAllBFS and findAllDFS

All other changes are non-breaking changes to the api.

Performance

Swift is not Rust, so more often than not abstraction comes with a performance penalty. In this PR I've sacrificed a lot of performance in favor of less code duplication.

Below there's a table with the results of some of the performance tests compared to master, stating execution time difference (+ is bad, - is good):

| Test  | vs. master (cf9a6a0) | vs. master before latest perf. improvements (d01175e) | | ---------------------------------------------- | ------ | ---- | | testDfsInStarGraphWithGoalTestByIndex | +45% | +11% | | testBfsInStarGraphWithGoalTestByIndex | +28% | -89% | | testDfsInPathWithGoalTestByIndex | +42% | +2% | | testBfsInPathWithGoalTestByIndex |+34% | +1% | | testDfsInCompleteGraphWithGoalTestByIndex | -98% | -98% | | testBfsInCompleteGraphWithGoalTestByIndex | -4% | -26% | | testDfsInStarGraphByIndex | -42% | -62% | | testBfsInStarGraphByIndex | +118% | -86% | | testDfsInPathByIndex | +85% | +30% | | testBfsInPathByIndex | +75% | +21% |

As you can see, this PR introduces a major performance regression compared to our current master, although with some surprising big improvements on some cases. So, if performance was the only consideration we should not merge this PR.

When comparing to a commit on master before the latest merged performance improvements, we see that after merging this PR we could ship a new version with good performance improvements in most cases and only some performance drop of up to 30% in few cases.

Future Performance

This PR as is, is bad for performance. The main reason of this drop of performance is that all the methods implemented in the extension of GraphTraverser are now written as special cases of an abstract algorithm that operates with closures. Before, this algorithms had no function calls at all.

The good news is that this inefficient methods can be overwritten in DFS and BFS. For example, bfs(fromIndex: Int, toIndex: Int) -> [E] is the method which has seen its performance dropped the most. We could write a specialized version of the dfs for it, with no closures, just like it is in master now. We must decide what balance between code reuse and performance we want. I left this for future PR though.

The someone implementing a new totally new GraphTraverser can follow a progressive path:

1. Implement GraphTraverser and get a bunch of non-optimized convenience methods for free.
2. Write code using their GraphTraverser implementation, benchmark it and then decide if some methods need to be specialized for better performance.

Also if Swift ever gets more efficient abstractions we might be able to remove some of the specialized functions.

Notes

• I've tried merging the goalTest and the reducer closures of the from(_ initalVertexIndex: Int, goalTest: (Int) -> Bool, reducer: G.Reducer) -> Int? method into a single closure returning a tuple of bools, but this resulted in a slight loss of performance. It's ok since I thing the current solution with two closure is more ergonomic.
• I've tried making DFS and BFS conform to Sequence, so both can be consumed with a for in loop but it seemed to drop performance a bit.
• Can the Dijkstra's algorithm be made to conform GraphTraverser? I think we could. But shall we? The main point of GraphTraverser is to get the bunch of convenience methods it defines in its extension for free. Are those methods a sound interface to Dijkstra's algorithm?

Add performance test target running an optimized build and add performance tests for graph Constructors.

I'll be pushing our performance tests story in upcoming PRs

This PR generalizes the search algorithm so both DFS and BFS use the same core algorithm. It also introduces new methods to perform arbitrary computations over a graph.

A new struct Search is added, which is used to configure the behaviour of the core algorithm to obtain either bfs or dfs. This Search struct can be the base for a more elaborate domain specific language to configure a search algorithm, but right know I have kept things simple.

Convenience DFS and BFS type alias over Search are provided to quickly configure these specific algorithms.

The previous graph search api coded in Graph extension is mantained, but internally uses the new Search API.

This is a rather big change, I apologize for just throwing the PR withut previous discussion. But the commits are self-contained and the abstraction is introduced progressively, so I hope you can just inspect commit by commit to see what's going on. If you don't feel confident with all the changes, let me know, I will cherry-pick the ones that are ok. Let's talk :)

This PR does the following things:

1. Creates a framework target for all the code that was originally in the app target, except for the app delegate.
2. Moves unit tests into a test bundle that points at this new framework instead of the sample app.
3. Makes that framework build-able on any apple platform (macos, ios, tvos, watchos).
4. Removes some code for swift 2.x support, since the latest code in this framework already cannot be built in swift 2.3 mode.

In order to make this code fully build-able with carthage, a new version tag will need to be made at or after this commit, so that carthage can actually get these changes. Specifying 1.2.0 in a cartfile with no later versions available will make carthage get the old version without the extra framework.

This change improves the performance of topological sort by removing the linear lookups of vertices. I think it was something like O(n^4) with calls to indexOfVertex. I also try to do fewer vertex allocations by using indices everywhere, although this is relatively minor in comparison.

I didn't test exhaustively, but in my use case with ~500 vertices and ~500 edges, sorting went from 12s to 20ms!

Check all is well on Swift 5 after the final release of it ships with Xcode 10.2 and if any changes are needed. Review the changes in recent pull requests by @ZevEisenberg and @ferranpujolcamins .

Development for Swift 5/SwiftGraph 2.1 is taking place in the release2.1/swift5 branch.

Closes #21. Tests are passing.

• Add SwiftLint as a build target and format with SwiftFormat. Not all warnings are fixed, short type names in Graph, et al are the only meaningful ones. (fe470fb and 395d5ea)
• Fix Swift 4 warnings in tests (395d5ea).
• Rename the API to be in line with Swift’s API Design Guidelines. Most methods were renamed to support labels and some of them have changed entirely: findAll(from:goalTest:) was renamed to routes(from:until:); the until label was used in place of goalTest everywhere else; removeEdge(from:to:bidirectional:) was renamed to unedge(:to:bidirectional:); addEdge(from:to:directed:) was renamed to edge(:to:directed), detectCycles(upToLength:) was renamed to cycles(until:) so that it’s in line with edges, neighbors, routes; edgeExists(from:to:) was renamed to edged(from:to:); vertexInGraph(vertex:) was renamed to contains(vertex:), and a contains(edge:) was added alongside it.
• Make what previously was addVertex(:) to -> Void instead of -> Int to conform it to the rest of the API. I was also expecting to adopt method chaining but returning Self within Graph would make it impossible for classes that adopt it to be non-final, which may need to be discussed.
• Make V conform to Hashable instead of Equatable because it is used as a Dictionary.Key (1add64e, e09493f).
• Remove redundant Sequence conformance. Remove the related Iterator typealias and makeIterator method because the presence of index(of:) and makeIterator was causing a segmentation fault. I reported the issue on the Swift issue tracker: SM-6778. testSequenceTypeAndCollectionType() is still passing, so the default makeIterator() implementation is seemingly working like the previous custom implementation. May need to be double checked?
• Use mutating (e09493f, ee105f8, 1da1f83). The protocol-based implementation allowed to mark as mutating methods that were previously implemented in a class and were therefore lacking the mutation modifier. ~To work around the mutating methods in class-based implementations without needlessly constraining the protocol to class, we should refine mutating methods with the workaround (suggested by Kevin Ballard on the Swift mailing list) employed by add(edge:). Others method do not yet implement the workaround. I’ll be adding them now.~ (see b150f65)
• Scope utilities that were global and adapt them to instance methods (f8d22ae, a9d971d, c9d3fb6). distanceArrayToVertexDict was incorporated into an overload of dijkstra(root:start:) that returns a dictionary of vertices and weights instead of an array of weights; edgesToVertices(edges:graph:) was generalized to vertices(from:); pathDictToPath(from:to:pathDict:) was renamed to route(from:to:in:) and was extended; printMST(edges:graph:) was made internal and renamed to printmst(:), along with totalWeight(:) which was renamed to weight(of:).
• Update tests and sample app to use internal classes that conform to the various protocols. See Internals.swift.

• ~Due to Edge being generic, types who conform to UnweightedGraph and WeightedGraph must implement the edge(:to:) requirements by themselves as default implementations via protocol extensions cannot use an Edge initializer. This information is described in the documentation of all involved protocols, including Graph. A sample implementation is provided in Internals.swift.~ (see b150f65)
• Working with generic protocols, implementations are now free of non-ideal internals related to using Edge instead of a generic E.

Lastly, I’ll refine the documentation, ~add missing mutating methods workarounds~, ~and missing tests for newly added methods likecontains(edge:)~.

~#7 could also be on radar since I’ve now rewritten the API; instead of renaming all the ambiguous methods, we could extend the protocols with V == Int and add new signatures for the ambiguous calls; to do so, we encapsulate the logic in internal methods and use it in both methods (moreover the encapsulation is already in place with the mutating workaround). It’s not pretty, but I’m not sure I’d want to rename the API to accommodate a single type.~ (see 0dd0c16)

Let's say I have two weighted and not directed edges, connecting the same vertices, as follows:

let edgeA = WeightedEdge<Int> = WeightedEdge(u: 0, v: 1, directed: false, weight: 10)
let edgeB = WeightedEdge<Int> = WeightedEdge(u: 1, v: 0, directed: false, weight: 10)

Currently we have so that edgeA == edgeB returns false.

Shouldn't the==(_:_:) operator take into consideration whether they're directed? Or am I missing something? So in this particular scenario I would expect edgeA == edgeB to return true, as they are not directed.

In summary we would have:

let directedEdgeA = WeightedEdge<Int> = WeightedEdge(u: 0, v: 1, directed: false, weight: 10)
let directedEdgeB = WeightedEdge<Int> = WeightedEdge(u: 1, v: 0, directed: false, weight: 10)
directedEdgeA == directedEdgeB // returns `true`


let undirectedEdgeC = WeightedEdge<Int> = WeightedEdge(u: 0, v: 1, directed: true, weight: 10)
let undirectedEdgeD = WeightedEdge<Int> = WeightedEdge(u: 1, v: 0, directed: true, weight: 10)
undirectedEdgeC == undirectedEdgeD // returns `false`

If there are any worries about how changing the ==(_:_:) implementation would affect other features, should we have a separate method to compare two edges? Any thoughts on this?

Would it be possible to speed up detectCycles and detectCyclesAsEdges by making them run parts of the search in parallel? I don't know whether the algorithm is suitable for parallelization, but it could be worth looking into.

Background: I've been modifying my juggling code to deal with throwing multiple objects at the same time, and the state graphs for this technique are way bigger than for throwing a single object at once. For 3 balls, for a maximum throw height of 6, there are 110,552 cycles in the graph. I don't know how many there are for a maximum throw height of 7 because I haven't been able to run the code for long enough yet to find out.

For graphs this large, memory usage is also a concern. My current test run searching for a max throw height of 7 is up over 1 GB used.

(Much of this is academic. I don't know if I have a real-world use case for searching for cycles on graphs this large, at least not quickly. If my app needs to use them, I'll probably generate them once and bake them into the app.)

It would be great to add an encoder for the dot language of https://www.graphviz.org/ This way applications can export the graphs they build with SwiftGraph for human visualization.