Category Archives: Graph Theory

Linear Programming

In my last post on game theory, I said that you could find an optimal
probabilistic grand strategy for any two-player, simultaneous move, zero-sum game.
It’s done through something called linear programming. But linear programming
is useful for a whole lot more than just game theory.

Linear programming is a general technique for solving a huge family of
optimization problems. It’s incredibly useful for scheduling, resource
allocation, economic planning, financial portfolio management,
and a ton of of other, similar things.

The basic idea of it is that you have a linear function,
called an objective function, which describes what you’d like
to maximize. Then you have a collection of inequalities, describing
the constraints of the values in the objective function. The solution to
the problem is a set of assignments to the variables in the objective function
that provide a maximum.

Continue reading

Computing Strongly Connected Components

As promised, today I’m going to talk about how to compute the strongly connected components
of a directed graph. I’m going to go through one method, called Kosaraju’s algorithm, which is
the easiest to understand. It’s possible to do better that Kosaraju’s by a factor of 2, using
an algorithm called Tarjan’s algorithm, but Tarjan’s is really just a variation on the theme
of Kosaraju’s.

Continue reading

Colored Petri Nets

Colored Petri Nets
The big step in Petri nets – the one that really takes them from a theoretical toy to a
serious tool used by protocol developers – is the extension to colored Petri nets (CPNs). Calling them “colored” is a bit of a misnomer; the original idea was to assign colors to tokens, and allow color-based expressions on the elements of the net. But study of analysis models quickly showed
that you could go much further than that without losing the basic analyzability properties
that are so valuable. In the full development of CPNs, you can associate essentially arbitrary
collections of data with Petri net tokens, so long as you use a strong type system, and keep
appropriate restrictions on the expressions used in the net. The colors thus become
data types, describing the types of data that can be carried by tokens, and the kinds of tokens that
can located in a place in the net.

So that’s the fundamental idea of CPNs: tokens have types, and each token type has some data value associated with it. Below the fold, we’ll look at how we do that,
and what it means.

Continue reading

Counted Petri Nets, and Useless Protocol Specification Tools

There’s one variant of Petri nets, called counted Petri nets, which I’m fond of for personal reasons. As Petri net variants go, it’s a sort of sloppy but simple one, but as I said, I’m fond of it.

As a warning, there’s a bit of a diatribe beneath the fold, as I explain why I know about this obscure, strange Petri net variant.

Continue reading

Modeling Concurrency with Graphs: Petri Nets

Among many of the fascinating things that we computer scientists do with graphs
is use them as a visual representation of computing devices. There are many subtle problems that can come up in all sorts of contexts where being able to see what’s going on can make a huge difference. Graphs are, generally, the preferred metaphor for most computing tasks. For example, think of finite state machines, flowcharts, UML diagrams, etc.

One of the most interesting cases of this for one of the biggest programming problems today is visual representations of concurrency. Concurrent program is incredibly hard, and making a concurrency regime correct is a serious challenge – communicating that regime and its properties to another developer is even harder.

Which brings us to todays topic, Petri nets. Actually, I’m probably going to spend a couple of days writing about Petri nets, because they’re fun, and there are a lot of interesting variations. The use of Petri nets really isn’t just an academic exercise – they are seriously used by people in a lot of real, significant fields – for one example, they’re very commonly used to specify behaviors of network communication protocols.

Continue reading

Critical Paths, Scheduling, and PERT

Yet another example of how graphs can be used as models to solve real problems comes from the world of project management. I tend to cringe at anything that involves management; as a former IBMer, I’ve dealt with my share of paper-pushing pinheaded project managers. But used well, this demonstrates using graphs as a model for a valuable planning tool, and a really good example of how to apply math to real-world problems.

Project managers often define something called PERT charts for planning and scheduling a project and its milestones. A PERT chart is nothing but a labeled, directed graph. I’m going to talk about the simplest form of PERT, which considers only time, but not resources. More advanced versions of PERT exist that also include things like required resources, equipment, etc.

Continue reading

Using Graphs to Represent Information: Lattices and Semi-Lattices


There’s a kind of graph which is very commonly used by people like me for analysis applications, called a lattice. A lattice is a graph with special properties that make it
extremely useful for representing information in an analysis system.

Continue reading

Games and Graphs: Searching for Victory

Last time, I showed a way of using a graph to model a particular kind of puzzle via
a search graph. Games and puzzles provide a lot of examples of how we can use graphs
to model problems. Another example of this is the most basic state-space search that we do in computer science problems.

Continue reading

Puzzling Graphs: Problem Modeling with Graphs

As I’ve mentioned before, the real use of graphs is as models. Many real problems can be
described using graphs as models – that is, to translate the problem into a graph, solve some problem on the graph, and then translate the result back from the graph to the original problem. This kind of
solution is extremely common, and can come up in some unexpected places.

For example, there’s a classic chess puzzle called the Knight’s tour.
In the Knight’s tour, you have a chessboard, completely empty except for a knight on one square. You can
move the knight the way you normally can in chess, and you want to find a sequence of moves in which is
visits every square on the chessboard exactly once. There are variations of the puzzle for non-standard
chessboards – boards larger or smaller than normal, toroidal boards (where you can wrap around the left edge to the right, or the top to the botton), etc. So – given a particular board, how can you
(1) figure out if it’s possible to do a knights tour, and (2) find the sequence of moves in a tour
if one exists?

Continue reading

Graph Searches and Disjoint Sets: the Union-Find Problem

Suppose you’ve got a huge graph – millions of nodes. And you know that it’s not connected – so the graph actually consists of some number of pieces (called the connected components of the graph). And there are constantly new vertices and edges being added to the graph, but nothing is ever removed. Some questions you might want to ask about this graph at a particular point in time are:

  • How many components are there in the graph?
  • Which component is vertex X in?
  • Are vertices X and Y in the same component?
  • How many components are there?

All of these questions are variants of a classic computer science problem, called
union-find, which also comes up in an astonishing number of different contexts. The reason for the name is that in the representation of the solution, there
are two basic operations: union, and find. Basically, the division of the graph into
components is also a partition of the vertices of the graph into disjoint sets: union find
is a problem which focuses on a particular kind of disjoint set problem, where you can modify
the sets over time.

Continue reading