Group Group Group Group Group Group Group Group Group

raywenderlich.com Forums

Swift Algorithm Club: Graphs with Adjacency List

Learn how to implement directed and undirected graphs in Swift using adjacency lists.


This is a companion discussion topic for the original entry at https://www.raywenderlich.com/773-swift-algorithm-club-graphs-with-adjacency-list

Hi There! This is great, was just what I was looking for!
How Can I implement Apple Included A* or other pathfinding algorithm to find cheapest route? An example would be Awesome!
For Example. the Cheapest route from Singapore to Seattle.

@magonicolas thanks a lot! Our team will be writing more algorithms on stuff that you mentioned. For now you can check out: Shortest Path Weighted Algorithm

That great, Yes I have seen that, but I don’t know how to implement it on this flights example.

Also I have just download it and its not updated to swift 3 :frowning: But looks exactly as what I need to achieve! Help would be Awesome :smiley:

@magonicolas, the algorithm just got converted by a fellow contributor: SSSP

Thats great news! Thanks for letting me know, But Maybe im doing something wrong, because I can’t make it work, it is giving me a lot of errors on all clases on the SSSP.xcodeproj
Also the playground has an error, and says on line 1 that there is no such module ‘Graph’
Any clues on what I might be doing wrong?

@magonicolas yup, just open the xcworkspace project, and first run Graph target found in the schema, and then SSSP target.

Picture below:

1 Like

This is a great discussion. I do have a question which does not seem to be addressed in the article, and that revolves around value types versus reference types.

If I understand the code, all vertexes and edges will create new copies of each data structure that you are graphing. While this is fine for the example, and especially for small data like the name of a city, this will not work for larger objects.

I wonder if you could address how you would create vertexes, edges and adjacency lists with reference types instead? (or even whether you consider this an issue).

Thanks in advance, and thank you for the article.

@woolie sorry for the late reply (in a place with very very weak signal) Currently away for Chinese new year :confused:

But here’s a short answer, currently the vertices and edges are value type, but the adjacency list is a class which is reference type. So I don’t think it will be a problem. Creating a new vertex or edge will not make new copies of the data structure. We are using a collection type dictionary for the adjacency list where the key is a vertex and the value is another collection, an array which holds edges.

Adjacency list is a class so unless we make it a struct it wouldn’t make a new copy of the graph unless we do a deep copy or make it a struct. Hope that answers your question!

Might be late to reply since there isn’t internet where I am unless I go to a coffee shop :wink:

The Playground is not working, would you please re upload it again to complete the tutorial with you on the same explanation.

Thanks,

Can you be more specific? I’ve just downloaded it, I’m running it in Xcode 8.2.1, and it’s working for me. What error messages or warning messages are you seeing?

This tutorial is more than six months old so questions are no longer supported at the moment for it. We will update it as soon as possible. Thank you! :]