Monthly Archives: October 2014

Digraphs, Dags, and Trees in Java

Graphs are a collection of nodes connected by edges. Programmers run into graphs fairly regularly because almost any collection of things with binary relationships can be viewed as a graph. As practitioners we need to understand both graph theory (abstract structures) and graph data structures (concrete representations).

Three common families of graphs are:

This article looks at digraphs, dags, and trees from a programmer’s perspective. Where do we see them in practice? How can we recognize them? What can we do with them?

This article also includes a Java library for working with digraphs, dags, and trees. The library code is available at https://github.com/stevewedig/blog and is published to Maven for easy usage as a dependency. This is the third in a series of Java libraries I’m sharing on this blog. The first two were:

Article Outline

  1. Digraphs (directed graphs)
  2. Dags (directed-acyclic graphs)
  3. Trees
  4. A Java library for digraphs, dags, and trees
  5. Other Java graph libraries

Continue reading