a gathering of those who trace adjacency matrices at 3 a.m.
Recursive, rooted, and endlessly forked. Threads grow from a common trunk -- a family album of pointers with exactly one parent per child. We meet here to argue about balance factors and whether a red-black tree is really a 2-3-4 tree wearing a costume.
O(log n) · acyclic · rooted
Direction without return. The compiler's favorite shape -- topologically sortable, no cycles to trap the traversal. Build systems, task graphs, and the shape of dependency itself.
topological · directed · no cycles
An edge is no longer a pair -- it is a set. Three vertices binding together in a single relation, the ugly beautiful generalization that resists tidy diagrams. We love them anyway.
n-ary · incidence matrix · untidy
A horizontal drift of community contributions. Scroll; the one nearest the center glows.
Every rooted tree is a confession. It says: I came from somewhere. There is a single predecessor, a common origin, and the traversal that begins at the root will reach every leaf exactly once if you are careful with recursion. This is the lullaby of the tree -- its gentle promise of termination.
We argue here, in the moss, over what makes a balanced tree balanced. Is it height? Is it the ratio of left to right? Does the AVL's strict discipline suit a production workload better than the red-black's looser posture? The answer, as always, is it depends, followed by a long pull of bitter tea and a screen full of profiler output.
When a tree grows wrong, when one branch extends like a gnarled root and the others stay twigs, we say it has degenerated. We do not say it is broken. Some structures were always going to collapse toward a list; we call that honesty.
A directed acyclic graph refuses to return. It is the shape of a build system, of a version history, of a compiler's intermediate representation. Every edge is a promise: the one before must finish before the one after begins. There is no retreat, no loop of regret.
Topological sort is the act of reading a DAG aloud in an order that respects all its promises. It is, in a sense, the graph telling its own story. Kahn's algorithm removes the sources, one by one, until only the sinks remain -- a leaf-by-leaf draining of the fungal lattice.
We honor the DAG because it is unambiguous. Ambiguity is for the cyclic graphs in section four, the ones that loop forever unless you mark and sweep.
A hypergraph says: my edges connect sets, not pairs. When three vertices belong to the same relation -- a team of three, a transaction with three parties, a chord of three notes -- a pair-based graph will lie about it. It will give you three separate edges and pretend the triad is emergent.
The hypergraph does not lie. It draws a closed region around the three and names the region an edge. It is uglier to render, yes -- venn-diagrammatic, fat, hard to lay out on a plane -- and this is precisely why we love it. A hypergraph is a graph that refuses the lossy compression of pairwise simplification.
Incidence matrices replace adjacency matrices here. Rows are vertices, columns are edges, and a 1 in cell (v, e) means v is a participant in e. The matrix is sparse, rectangular, and full of stories.
We keep a bibliography.md in the root of the community repository. It is long. It contains Knuth, Tarjan, Diestel, and a surprising number of fourteenth-century treatises on divination by the casting of sticks (the original graph drawing algorithm was probably augury). Contribute entries; we read them at the monthly campfire call.