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:

• Digraphs (directed graphs): Graphs with directed edges (arcs).
• Dags (directed-acyclic graphs): Digraphs that don’t contain cycles.
• Trees: Dags with a single root and where non-roots have one parent. (Technically this is a rooted tree.)

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:

• Value Objects in Java & Python
• Type Safe Heterogeneous Containers in Java

Article Outline

1. Digraphs (directed graphs)
2. Dags (directed-acyclic graphs)
3. Trees
4. A Java library for digraphs, dags, and trees
   • Why use this library?
   • Overview of library concepts
   • Id graphs
   • Node graphs
   • Partial node graphs
   • Custom node classes
   • Custom graph classes
   • Custom traversals
   • Sample graphs
   • Example applications
   • Reusable algorithms
5. Other Java graph libraries

Continue reading →