Edge-Weighted Digraph in Swift

      4 Comments on Edge-Weighted Digraph in Swift

In this article we'll implement the edge-weighted digraph in swift. By the end of the article you'll se how simple graphs are and how useful they can be.You’ve probably heard of graphs in computer science, and you might even be dreading them a bit. After all, graphing algorithms are one of the favourite questions on technical interviews. In this article we’ll implement the edge-weighted digraph in swift. This is an essential structure that we’ll use later on when we implement the Dijkstra’s algorithm for finding the shortest path. By the end of the article you’ll se how simple graphs are and how useful they can be.

Vertices And Edges

To understand the graphs in general you’ll need to familiarise yourself with a couple of terms. There’s only a few:

  • Vertex – Is a node on a graph. In reality it can represent anything that can be connected. An airport, a city, a road junction
  • Edge – Is a link between two vertices. They come in two flavours: directed and undirected. Directed edge is always pointing the same way. It has a source and a destination. It’s like a one way street. Undirected edge can point both ways.
  • Weight – Represents the cost of the edge. If your graph represents airports, weight can represent the price of the plane ticket, for example.

Picture speaks a thousand words:

Knowing these terms we can understand the title of this article a lot better now. ‘Edge-Weighted‘ means that the graph will have edges (or connections) that have a weight (or cost), ‘Digraph‘ means that the graph will be a directed graph – the edges will point only one way.

Airports

Let’s implement this graph on a fun example. The vertices in our graph will represent airports and the edges will be direct flights between the airports. The weight will be the price of the plane ticket.

The whole code example will only use three classes. First one on the list is the vertex. This will be a trivial class to implement:

Our vertex holds a generic value and it has an array of adjacent edges (outgoing connections). We have a function for adding an edge and a function that will return an edge to a destination vertex if it exists. We’ve also implemented ‘Equatable’ so we can easily test if two vertices are equal.

The next class is the ‘DirectedEdge’ that will represent a connection between two vertices:

As you can see, this class is even simpler. It only holds the source, destination and weight of the edge. We also implemented ‘Equatable’ here.

The Graph

The actual graph is a slightly bigger class, but still quite simple to understand:

Functions are pretty self-explanatory. In the function ‘addEdge’ we’re checking if the edge already exists. If it does we’re just going to update the weight of that edge. This function assumes that the ‘source’ and ‘destination’ vertices are already in the array, just to keep things simple and clear. We can get an array of all the vertices and all the edges in the graph. We can also get an array of adjacent edges for a certain vertex. For the sake of completion we have functions that are returning the number of vertices and edges in the graph.

Test It Out

We’re going to construct a graph that looks like this:

It might look complicated, but it’s quite simple to construct it using our class:

First we create the vertices and add them to the graph. Then we add edges with the weights. Bear in mind, you have to add vertices to the graph first, and then add the edges. We can test our graph out and print some vertices and edges:

For example, we can easily print all the direct flights from London. When we run our little example the console should output something like this:

And there you go, you’ve successfully implemented your first directed graph 🙂

Conclusion

A directed graph like this one on its own is marginally useful. Their real use and power comes from graph algorithms. In one of the next articles we’ll talk about the Dijkstra’s algorithm for finding the shortest path between two vertices. Understanding how a directed graph works is essential in order for you to understand that (or any other) graph algorithm.

Graphs and graph algorithms have loads of uses, you might not even be aware of some of them. Originally they were mostly used in routers to find the cheapest route between two computers, today they can be found in your sat nav system, or even on one of those online systems that are trying to find the cheapest flight for you.

This article is an intro to the next article in which we’ll talk about the Dijkstra’s shortest path algorithm. In this article we’ve created a simple implementation of a digraph, in order to help you understand it. In the next article we’ll revisit this implementation and optimise it. I hope you’ve learned something new today and that you had some fun with graphs. You can find all the code on GitLab as well as code snippets from the article.

Have a nice day 🙂
~D;

More resources

4 thoughts on “Edge-Weighted Digraph in Swift

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.