Analyzing a dependency graph in Swift

I published my solution to Dave Thomas’s Transitive Dependencies programming exercise, known as a kata, to GitHub:

https://github.com/ijoshsmith/transitive-dependencies-kata

The Challenge

This exercise involves analyzing a graph data structure which contains nodes that “depend on” other nodes. A graph is represented as direct dependencies between nodes:

direct-deps

The objective is to find all of a node’s dependencies, both direct and indirect, like so:

resolved-deps

An interesting complication is that a graph might contain cyclical dependencies, where a node indirectly depends upon itself. A proper solution to this problem must be able to cope with a graph like this:

graph-problem

If this programming challenge interests you, stop reading now and solve the puzzle for yourself! Check out the kata for more information.


My Solution

My solution relies on three things:

  1. An instance of Swift’s Set<T> collection keeps track of which nodes have been visited.
  2. The higher-order function reduce accumulates nodes into a Set as they are visited.
  3. Recursion is used to visit dependencies from the reduce method’s combine logic.

Here’s how I solved this little puzzle:

dependency-resolver

You can download the Xcode project here.

About Josh Smith

Josh Smith is a musician at heart, and a software developer by obsession. He lives in Arizona, plays classical music on the piano, jazz on the guitar, and enjoys brutally long rides on his bicycle. He has a wonderful wife and thinks that, in general, life is good.
This entry was posted in Swift and tagged , . Bookmark the permalink.

One Response to Analyzing a dependency graph in Swift

  1. Pingback: Dew Drop – June 9, 2016 (#2268) | Morning Dew

Comments are closed.