A Graph Data Structure in Pure Swift

Last update: Dec 16, 2022

Overview

SwiftGraph

SwiftGraph is a pure Swift (no Cocoa) implementation of a graph data structure, appropriate for use on all platforms Swift supports (iOS, macOS, Linux, etc.). It includes support for weighted, unweighted, directed, and undirected graphs. It uses generics to abstract away both the type of the vertices, and the type of the weights.

It includes copious in-source documentation, unit tests, as well as search functions for doing things like breadth-first search, depth-first search, and Dijkstra's algorithm. Further, it includes utility functions for topological sort, Jarnik's algorithm to find a minimum-spanning tree, detecting a DAG (directed-acyclic-graph), enumerating all cycles, and more.

Installation

SwiftGraph 3.0 and above requires Swift 5 (Xcode 10.2). Use SwiftGraph 2.0 for Swift 4.2 (Xcode 10.1) support, SwiftGraph 1.5.1 for Swift 4.1 (Xcode 9), SwiftGraph 1.4.1 for Swift 3 (Xcode 8), SwiftGraph 1.0.6 for Swift 2 (Xcode 7), and SwiftGraph 1.0.0 for Swift 1.2 (Xcode 6.3) support. SwiftGraph supports GNU/Linux and is tested on it.

CocoaPods

Use the CocoaPod SwiftGraph.

Carthage

Add the following to your Cartfile:

github "davecom/SwiftGraph" ~> 3.1

Swift Package Manager (SPM)

Use this repository as your dependency.

Manual

Copy all of the sources in the Sources folder into your project.

Tips and Tricks

To get a sense of how to use SwiftGraph, checkout the unit tests
Inserting an edge by vertex indices is much faster than inserting an edge by vertex objects that need to have their indices looked up
Generally, looking for the index of a vertex is O(n) time, with n being the number of vertices in the graph
SwiftGraph includes the functions bfs() and dfs() for finding a route between one vertex and another in a graph and dijkstra() for finding shortest paths in a weighted graph
A sample Mac app that implements the Nine Tails problem is included - just change the target of the project to SwiftGraphSampleApp to build it

Example

For more detail, checkout the Documentation section, but this example building up a weighted graph of American cities and doing some operations on it, should get you started.

let cityGraph: WeightedGraph<String, Int> = WeightedGraph<String, Int>(vertices: ["Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"])

cityGraph is a WeightedGraph with String vertices and Int weights on its edges.

cityGraph.addEdge(from: "Seattle", to:"Chicago", weight:2097)
cityGraph.addEdge(from: "Seattle", to:"Chicago", weight:2097)
cityGraph.addEdge(from: "Seattle", to: "Denver", weight:1331)
cityGraph.addEdge(from: "Seattle", to: "San Francisco", weight:807)
cityGraph.addEdge(from: "San Francisco", to: "Denver", weight:1267)
cityGraph.addEdge(from: "San Francisco", to: "Los Angeles", weight:381)
cityGraph.addEdge(from: "Los Angeles", to: "Denver", weight:1015)
cityGraph.addEdge(from: "Los Angeles", to: "Kansas City", weight:1663)
cityGraph.addEdge(from: "Los Angeles", to: "Dallas", weight:1435)
cityGraph.addEdge(from: "Denver", to: "Chicago", weight:1003)
cityGraph.addEdge(from: "Denver", to: "Kansas City", weight:599)
cityGraph.addEdge(from: "Kansas City", to: "Chicago", weight:533)
cityGraph.addEdge(from: "Kansas City", to: "New York", weight:1260)
cityGraph.addEdge(from: "Kansas City", to: "Atlanta", weight:864)
cityGraph.addEdge(from: "Kansas City", to: "Dallas", weight:496)
cityGraph.addEdge(from: "Chicago", to: "Boston", weight:983)
cityGraph.addEdge(from: "Chicago", to: "New York", weight:787)
cityGraph.addEdge(from: "Boston", to: "New York", weight:214)
cityGraph.addEdge(from: "Atlanta", to: "New York", weight:888)
cityGraph.addEdge(from: "Atlanta", to: "Dallas", weight:781)
cityGraph.addEdge(from: "Atlanta", to: "Houston", weight:810)
cityGraph.addEdge(from: "Atlanta", to: "Miami", weight:661)
cityGraph.addEdge(from: "Houston", to: "Miami", weight:1187)
cityGraph.addEdge(from: "Houston", to: "Dallas", weight:239)

Convenience methods are used to add WeightedEdge connections between various vertices.

let (distances, pathDict) = cityGraph.dijkstra(root: "New York", startDistance: 0)
var nameDistance: [String: Int?] = distanceArrayToVertexDict(distances: distances, graph: cityGraph)
// shortest distance from New York to San Francisco
let temp = nameDistance["San Francisco"] 
// path between New York and San Francisco
let path: [WeightedEdge<Int>] = pathDictToPath(from: cityGraph.indexOfVertex("New York")!, to: cityGraph.indexOfVertex("San Francisco")!, pathDict: pathDict)
let stops: [String] = cityGraph.edgesToVertices(edges: path)

The shortest paths are found between various vertices in the graph using Dijkstra's algorithm.

let mst = cityGraph.mst()

The minimum spanning tree is found connecting all of the vertices in the graph.

let cycles = cityGraph.detectCycles()

All of the cycles in cityGraph are found.

let isADAG = cityGraph.isDAG

isADAG is false because cityGraph is not found to be a Directed Acyclic Graph.

let result = cityGraph.findAll(from: "New York") { v in
    return v.characters.first == "S"
}

A breadth-first search is performed, starting from New York, for all cities in cityGraph that start with the letter "S."

SwiftGraph contains many more useful features, but hopefully this example was a nice quickstart.

Documentation

There is a large amount of documentation in the source code using the latest Apple documentation technique—so you should be able to just alt-click a method name to get a lot of great information about it in Xcode. We also use Jazzy to produce HTML Docs. In addition, here's an overview of each of SwiftGraph's components:

Edges

Edges connect the vertices in your graph to one another.

Edge (Protocol) - A protocol that all edges in a graph must conform to. An edge is a connection between two vertices in the graph. The vertices are specified by their index in the graph which is an integer. All Edges must be Codable.
UnweightedEdge - This is a concrete implementation of Edge for unweighted graphs.
WeightedEdge - This is a concrete implementation of Edge for weighted graphs. Weights are a generic type - they can be anything that implements Comparable, Numeric and Codable. Typical weight types are Int and Float.

Graphs

Graphs are the data structures at the heart of SwiftGraph. All vertices are assigned an integer index when they are inserted into a graph and it's generally faster to refer to them by their index than by the vertex's actual object.

Graphs implement the standard Swift protocols Collection (for iterating through all vertices and for grabbing a vertex by its index through a subscript) and Codable . For instance, the following example prints all vertices in a Graph on separate lines:

for v in g {  // g is a Graph<String>
    print(v)
}

And we can grab a specific vertex by its index using a subscript

print(g[23]) // g is a Graph<String>

Note: At this time, graphs are not thread-safe. However, once a graph is constructed, if you will only be doing lookups and searches through it (no removals of vertices/edges and no additions of vertices/edges) then you should be able to do that from multiple threads. A fully thread-safe graph implementation is a possible future direction.

Graph (Protocol) - This is the base protocol for all graphs. Generally, you should use one of its canonical class implementations, UnweightedGraph or WeightedGraph, instead of rolling your own adopter, because they offer significant built-in functionality. The vertices in a Graph (defined as a generic at graph creation time) can be of any type that conforms to Equatable and Codable. All Graphs are Codable. Graph has methods for:
- Adding a vertex
- Getting the index of a vertex
- Finding the neighbors of an index/vertex
- Finding the edges of an index/vertex
- Checking if an edge from one index/vertex to another index/vertex exists
- Checking if a vertex is in the graph
- Adding an edge
- Removing all edges between two indexes/vertices
- Removing a particular vertex (all other edge relationships are automatically updated at the same time (because the indices of their connections changes) so this is slow - O(v + e) where v is the number of vertices and e is the number of edges)
UnweightedGraph - A generic class implementation of Graph that adds convenience methods for adding and removing edges of type UnweightedEdge. UnweightedGraph is generic over the type of the vertices.
WeightedGraph - A generic class implementation of Graph that adds convenience methods for adding and removing edges of type WeightedEdge. WeightedGraph also adds a method for returning a list of tuples containing all of the neighbor vertices of an index along with their respective weights. WeightedGraph is generic over the types of the vertices and its weights.
UniqueElementsGraph - a Graph implementation with support for union operations that ensures all vertices and edges in a graph are unique.

Search

Search methods are defined in extensions of Graph and WeightedGraph in Search.swift.

bfs() (method on Graph) - Finds a path from one vertex to another in a Graph using a breadth-first search. Returns an array of Edges going from the source vertex to the destination vertex or an empty array if no path could be found. A version of this method takes a function, goalTest(), that operates on a vertex and returns a boolean to indicate whether it is a goal for the search. It returns a path to the first vertex that returns true from goalTest().
dfs() (method on Graph) - Finds a path from one vertex to another in a Graph using a depth-first search. Returns an array of Edges going from the source vertex to the destination vertex or an empty array if no path could be found. A version of this method takes a function, goalTest(), that operates on a vertex and returns a boolean to indicate whether it is a goal for the search. It returns a path to the first vertex that returns true from goalTest().
findAll() Uses a breadth-first search to find all connected vertices from the starting vertex that return true when run through a goalTest() function. Paths to the connected vertices are returned in an array, which is empty if no vertices are found.
dijkstra() (method on WeightedGraph) - Finds the shortest path from a starting vertex to every other vertex in a WeightedGraph. Returns a tuple who's first element is an array of the distances to each vertex in the graph arranged by index. The second element of the tuple is a dictionary mapping graph indices to the previous Edge that gets them there in the shortest time from the staring vertex. Using this dictionary and the function pathDictToPath(), you can find the shortest path from the starting vertex to any other connected vertex. See the dijkstra() unit tests in DijkstraGraphTests.swift for a demo of this.
Graph traversal versions of bfs() and dfs() that allow a visit function to execute at each stop

Sort & Miscellaneous

An extension to Graph in Sort.swift provides facilities for topological sort and detecting a DAG.

topologicalSort() - Does a topological sort of the vertices in a given graph if possible (returns nil if it finds a cycle). Returns a sorted list of the vertices. Runs in O(n) time.
isDAG - A property that uses topologicalSort() to determine whether a graph is a DAG (directed-acyclic graph). Runs in O(n) time.

An extension to WeightedGraph in MST.swift can find a minimum-spanning tree from a weighted graph.

mst() - Uses Jarnik's Algorithm (aka Prim's Algorithm) to find the tree made of minimum cumulative weight that connects all vertices in a weighted graph. This assumes the graph is completely undirected and connected. If the graph has directed edges, it may not return the right answer. Also, if the graph is not fully connected it will create the tree for the connected component that the starting vertex is a part of. Returns an array of WeightedEdges that compose the tree. Use utility functions totalWeight() and printMST() to examine the returned MST. Runs in O(n lg n) time.

An extension to Graph in Cycles.swift finds all of the cycles in a graph.

detectCycles() - Uses an algorithm developed by Liu/Wang to find all of the cycles in a graph. Optionally, this method can take one parameter, upToLength, that specifies a length at which to stop searching for cycles. For instance, if upToLength is 3, detectCycles() will find all of the 1 vertex cycles (self-cycles, vertices with edges to themselves), and 3 vertex cycles (connection to another vertex and back again, present in all undirected graphs with more than 1 vertex). There is no such thing as a 2 vertex cycle.

An extension to Graph in Reversed.swift reverses all of the edges in a graph.

Authorship, License, & Contributors

SwiftGraph is written by David Kopec and other contributors (see CONTRIBUTORS.md). It is released under the Apache License (see LICENSE). You can find my email address on my GitHub profile page. I encourage you to submit pull requests and open issues here on GitHub.

I would like to thank all of the contributors who have helped improve SwiftGraph over the years, and have kept me motivated. Contributing to SwiftGraph, in-line with the Apache license, means also releasing your contribution under the same license as the original project. However, the Apache license is permissive, and you are free to include SwiftGraph in a commercial, closed source product as long as you give it & its author credit (in fact SwiftGraph has already found its way into several products). See LICENSE for details.

If you use SwiftGraph in your product, please let me know by getting in touch with me. It's just cool to know.

Future Direction

Future directions for this project to take could include:

More utility functions
A thread safe implementation of Graph
More extensive performance testing
GraphML and Other Format Support

Comments

Codable support

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.

opened by yoiang 17
Implement Graph Union operation
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.
opened by ferranpujolcamins 11
Directed pseudo forest

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

opened by ferranpujolcamins 10
Function to find cycles

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
enhancement

opened by ZevEisenberg 10
[WIP] Search interface rework
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:

Implement GraphTraverser and get a bunch of non-optimized convenience methods for free.

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?
opened by ferranpujolcamins 9
Graph constructors

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

opened by ferranpujolcamins 8
Dfs side effect

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

opened by ferranpujolcamins 8
Change project structure to allow for installation via Carthage
This PR does the following things:

Creates a framework target for all the code that was originally in the app target, except for the app delegate.

Moves unit tests into a test bundle that points at this new framework instead of the sample app.

Makes that framework build-able on any apple platform (macos, ios, tvos, watchos).

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.
opened by klundberg 7
Improve performance of topological sort

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!

opened by dabbott 6
Swift 5 Support

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.

opened by davecom 6
Protocol-based Implementation
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)
opened by ghost 6
Comparison of `WeightedEdge` should take into consideration whether the edges are directed
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?
opened by tbbruno 1
Parallelize cycle finding

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

opened by ZevEisenberg 3
Graphviz encodable

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.

opened by ferranpujolcamins 7