My google search turned up much information about what people are doing with inductive graphs, but no definitions. So I ask you, StackExchange, what is an inductive graph? When I think of induction, I think of recursion. But this must be a wrong line of thinking, because cannot all graphs be constructed recursively? Thanks for clearing up my confusion.
What is an inductive graph?
4 Answers
A graph $G$ is $d$-inductive if either $G$ has at most $d$ vertices or $G$ has a vertex $u$ of degree at most $d$ such that $G \setminus\{ u\}$ is $d$-inductive. Equivalently, $G$ is $d$-inductive if its vertices can be numbered so that at most $d$ neighbors of any vertex $v$ have higher numbers than $v$.
Apart from the graph-theoretical answer, "inductive graph" has another meaning in functional programming, most notably Haskell. It's a functional representation of a graph that allows operations similar to standard inductive data types (ie lists and trees), useful for writing graph algorithms in a functional style. The idea was introduced by Martin Erwig in "Inductive Graphs and Functional Graph Algorithms" and reified in his functional graph library (fgl).
In this context, an "inductive data type" is one like a list or tree that is built up in a unique way. Since there is only one way to construct a particular list or tree, there is a single way to pattern match on it as well. Graphs, however, do not have a natural ordering of nodes or edges, and so are not inductive. (The actual structure storing the graph is just an implementation detail.)
The core concept with inductive graphs is that we can view a graph as an inductive data type, even though it was not built up this way. We can pattern match on a graph and decompose it into a single node, its vertices and the rest of the graph. However, since graphs are not inductive, there is more than one valid way to decompose a graph like this, so we lose the canonicity of actual inductive data types. This is primarily solved by parameterizing the viewing function with a specific node, letting us direct our graph decomposition as we go along.
If you want a more descriptive introduction—with pictures!—you can read a post I wrote about the idea on my blog.
Inductive graphs are efficiently implemented in terms of a persistent tree map between node ids (ints) and labels, based on big-endian patricia trees. This allows efficient operations on the immutable base, letting inductive graphs behave much like any other immutable, persistent data structure.
-
3The blog post is fantastic! Thanks for answering the question clearly and linking to the blog for further discussion. – 2015-12-23
A graph $G$ is $d$-inductive if the vertices of $G$ can be numbered so that each vertex has at most $d$ edges to higher-numbered vertices.
-
0Another name for this is a [$d$-degenerate graph](http://en.wikipedia.org/wiki/Degeneracy_%28graph_theory%29). – 2015-04-08
To be fair, I just used search engines as well. But let me know if either of these ring a bell:
Wikipedia thinks that inductive graphs may also be known as degenerate graphs:
On the other hand, the book The Theory of Graphs defines an inductive graph on page 13:
Do these line up with the sorts of inductive graphs you've been looking at?