DS&A

Graph Problems

Graphs and networks are useful because they’re very general — graphs show up almost everywhere. Given that there are so many different examples of graph structures, then, it’s perhaps surprising that there aren’t actually very many different kinds of problems involving graphs.

That is, there are many computing problems which graphs can help with, but not many kinds of problem. Usually, after translating from the problem domain into the language of graphs, the problem turns out to be one of a relatively small number of “classical graph problems”.

In this post we’ll look at some of the more common ones:

• Graph traversal
• Shortest path
• Minimum spanning tree
• Topological sort
• Travelling salesman

These classical graph problems have been studied extensively, and there are already good algorithms for solving many of them.

This is fortunate, because writing graph algorithms is hard — it’s much easier to learn and implement algorithms which already exist. But to solve problems this way, we need to be able to turn computing problems into graph problems, and to recognise which graph problems they turn into.

Graph traversal

Consider the following problems:

• A special pass gives you unlimited free flights on certain routes. What destinations can you get to?
• A touchscreen display in a museum shows information about the museum exhibits in a web browser. The browser is locked down, so other pages can only be reached by clicking links; can visitors reach any inappropriate sites?
• A computer has been infected with a virus which spreads through networks, but is blocked by firewalls. Which other computers are at risk?
• To install a new software package, a package manager must install any other packages it depends on. Which other packages must be installed?
• In an image editor, the “flood fill” tool paints an entire region of pixels the same colour. Which pixels should be painted?
• Objects in a computer program are inaccessible if they cannot be reached by pointers; their memory can be freed. Which objects are still accessible?

Once we model these problems as graphs, they all look like this:

• Starting at a given node, find all the nodes reachable from it via edges.

This problem is called graph traversal. The standard algorithms are depth-first search and breadth-first search.

Shortest path

Consider the following problems:

• What’s the distance by road from London to Edinburgh?
• What’s the fastest way to drive from London to Edinburgh?(1)
• What is the cheapest combination of flights to get somewhere?
• How should computer network traffic be routed to minimise latency?
• Units in a real-time strategy game move where the player tells them to, avoiding obstacles. What path should they take?
• Foreign exchange currency traders offer various exchange rates between various currencies. What is the cheapest way to buy Swiss francs with Canadian dollars?

In these problems, the graph’s edges have distances, times, or costs — i.e. each edge has a number, called its “weight”. Once we have modelled each of these problems using weighted graphs, they all look like this:

• Find a path from a given “source” node to a given “destination” node, minimising the total edge weights.

This is the shortest path problem; “shortest” could mean shortest distance, shortest time, lowest cost, or something else. The standard algorithms include Dijkstra’s algorithm, A* search, Bellman–Ford and Floyd–Warshall.(2)

Minimum spanning tree

Consider the following problems:

• Underground fibre-optic cables must be placed to connect all parts of a city together. How can this be done with as little digging as possible?
• A set of contact points on a printed circuit board must be connected to ground, minimising the total length of conductive tracks.
• To broadcast data in a computer network, we must decide which devices should send the data to which other devices. How can this be done with minimal network congestion?

These problems can also be modelled using edge weights to represent distances, times, or costs; they all look like this:

• Find a set of edges which connects all the nodes together, minimising the total edge weights.

This is called the minimum spanning tree problem, because the resulting set of edges always forms a tree.(3) The standard solutions include Kruskal’s algorithm, Prim’s algorithm and the reverse-delete algorithm.

Usually the edges represent possible links which could be chosen when building a network, rather than a network which already exists. Note that although we get the “cheapest” way to connect everything, the solution doesn’t minimise the “costs” of paths in the resulting network.

Topological sort

Consider the following problems:

• Tasks must be scheduled, but some tasks must be completed before others can begin. What order can the tasks be completed in?
• A package manager must install some packages, but each can only be installed after any packages it depends on. What order can the packages be installed in?
• Cells in a spreadsheet are computed by formulae using the values of other cells. When a cell changes, what order should the other cells be updated in?

Once modelled as graphs, these problems all look like this:

• Put the nodes of a graph into order, so that all edges point “forwards”.

This problem is called topological sorting; it usually applies when some things need to be done and there are some constraints on which order they’re done in. The standard algorithm is a variation of depth first search.

Topological sorting is often a useful thing to do when there is some reason that cycles cannot occur — for example, when some things depend on others, and circular dependencies are forbidden.

Travelling salesman

Consider the following problems:

• A salesman must visit every town in a region; how can he travel the shortest total distance?
• A delivery company’s trucks make many deliveries each day. What order should the deliveries for a single truck be scheduled in?
• A robot arm must test several parts of an electronic device. Which order should the parts be tested in?
• A laser traces out several shapes, and must move between them quickly enough for persistence of vision to make the shapes continuously visible.(4)

These problems have distances, times or costs to minimise; they ask either for the best route visiting everything, or the best order to visit everything in. (These are two ways of saying the same thing.)

If we model these problems with weighted graphs, then they all look like this:

• Find a route visiting every node, minimising the total edge weights.

Usually there is a particular node the route should start at, and return to at the end. This is called the travelling salesman problem; there are no efficient algorithms which always give perfect solutions, but there are heuristic algorithms which find “good enough” solutions reasonably quickly.

Footnotes

1. This is not quite the same problem, since roads have different speed limits, so the distance of a route is not exactly proportional to the journey time.
2. Not all of these algorithms are suitable for all variations of the shortest path problem — perhaps we want just one path, or all paths from one “source” to every “destination”, or paths between all pairs of nodes. Breadth-first search can be used to find shortest paths in unweighted graphs. Some graphs can have negative edge weights, which not every algorithm can handle.
3. That is, the resulting edges form a graph which is connected and contains no cycles — making it a tree in the graph theoretic sense, but not necessarily the kind of tree with a root node and a parent/child relation.
4. See Recreating Asteroids with Lasers (video).

• Tags: 
• graphs, problems, algorithms