layout

Documentation

Overview

Package layout turns a Merkle DAG into nested circles that can be zoomed continuously, from the whole graph down to the fields inside a single node.

The layout is a containment packing: every node is a disc, and the discs beneath it are packed inside it. That makes the picture self-similar, so zooming in is not a change of screen but simply a change of scale — the same drawing viewed closer. A commit contains its tree, which contains its blobs; a transaction contains its status log, which contains its ledger entries.

Where a shared node lives

Containment needs each node to have exactly one home, which a DAG does not provide: a deduplicated blob or a nominal account may be referenced from many places. Rather than duplicating such nodes or picking a parent arbitrarily, the layout nests each node inside its immediate dominator — the deepest node through which every route from the root must pass. That placement is always truthful, because there is no way to reach the node without entering its container first.

Every graph edge that is not also a containment edge is reported separately as a Link, which a renderer can draw as an arc between two discs. For a strict tree there are no such links and the packing is exactly the tree.

Sizing

Leaves are sized from github.com/danielriddell21/merkelbrot/graph.Node.Weight and from how many payload fields they carry, so a node with more inside it is drawn larger. Every other node is sized to enclose its children plus Options.Padding. Sibling discs are arranged with the front-chain algorithm, which keeps the enclosing circle tight and therefore keeps the useful zoom range as wide as possible.

Node internals

A node's payload fields are packed as equal circles and reported as Slot values in coordinates relative to the node: an offset in units of the node's own radius, so a renderer multiplies through by [Placed.R] to draw them.

Where a node has children as well as fields, the fields are packed into a disc of their own that takes its place among the children, so text never lands on top of nested content. A childless node gives its fields the whole of its interior. Either way a renderer reveals them only once they are large enough on screen to read, which is what gives the deepest zoom level something to show.

Determinism

Packing the same graph twice always produces the same coordinates. The shuffle inside the smallest-enclosing-circle search is seeded from a constant, and every traversal follows the source's own ordering, so layouts can be compared in tests and cached safely.

Index

• type Circle
• type Link
• type Options
• type Packing
  • func Pack[K comparable](g *graph.Graph[K], opts Options) *Packing[K]
• type Placed
• type Slot

Examples

• Options (MaxDepth)
• Pack
• Pack (SharedSubtree)

Types

type Circle

type Circle struct {
	X, Y, R float64
}

Circle is a disc in layout coordinates.

type Link

type Link[K comparable] struct {
	From, To K
}

Link is a graph edge that containment could not express.

It connects a node to a child nested somewhere else, which happens whenever a child is shared and therefore lives inside its immediate dominator instead.

type Options

type Options struct {
	// LeafRadius is the radius of a childless node with no payload. Default 1.
	LeafRadius float64
	// Padding is the gap added between a node's boundary and its contents. Default
	// is a tenth of LeafRadius.
	Padding float64
	// PayloadFill is the fraction of a node's radius its payload circles occupy,
	// between 0 and 1. Default 0.72.
	PayloadFill float64
	// MaxDepth limits how many containment levels are laid out, with zero meaning
	// no limit. Nodes deeper than the limit are omitted along with their contents.
	MaxDepth int
}

Options configures Pack. The zero value is usable and picks sensible defaults.

Example (MaxDepth)

ExampleOptions_maxDepth limits the layout to the outermost levels, which is what a renderer does when it only needs an overview of a very large graph.

package main

import (
	"fmt"

	"github.com/danielriddell21/merkelbrot/graph"
	"github.com/danielriddell21/merkelbrot/layout"
)

func main() {
	g, err := graph.New(graph.NewMemorySource([]string{"a"},
		graph.Node[string]{ID: "a", Children: []string{"b"}},
		graph.Node[string]{ID: "b", Children: []string{"c"}},
		graph.Node[string]{ID: "c"},
	))
	if err != nil {
		panic(err)
	}

	p := layout.Pack(g, layout.Options{MaxDepth: 2})
	for _, n := range p.Nodes {
		fmt.Println(n.ID, "at depth", n.Depth)
	}
}

Output:
a at depth 0
b at depth 1

type Packing

type Packing[K comparable] struct {
	// Nodes holds every placed node, parents before children.
	Nodes []Placed[K]
	// Links holds the graph edges that containment does not already show.
	Links []Link[K]
	// Bounds is the circle enclosing the whole packing, centred on the origin.
	Bounds Circle
}

Packing is a laid-out graph.

func Pack

func Pack[K comparable](g *graph.Graph[K], opts Options) *Packing[K]

Pack lays the graph out as nested circles.

The result is centred on the origin. Nodes are returned parents-first, so a renderer can draw them in order and have children land on top of their containers.

Example

package main

import (
	"fmt"
	"strings"

	"github.com/danielriddell21/merkelbrot/graph"
	"github.com/danielriddell21/merkelbrot/layout"
)

func main() {
	g, err := graph.New(graph.NewMemorySource([]string{"commit"},
		graph.Node[string]{ID: "commit", Kind: "commit", Children: []string{"tree"}},
		graph.Node[string]{ID: "tree", Kind: "tree", Children: []string{"readme", "licence"}},
		graph.Node[string]{ID: "readme", Kind: "blob"},
		graph.Node[string]{ID: "licence", Kind: "blob"},
	))
	if err != nil {
		panic(err)
	}

	p := layout.Pack(g, layout.Options{})
	for _, n := range p.Nodes {
		fmt.Printf("%s%s covers %.0f%% of the view\n",
			strings.Repeat("  ", n.Depth), n.ID, 100*n.R/p.Bounds.R)
	}
}

Output:
commit covers 100% of the view
  tree covers 95% of the view
    readme covers 45% of the view
    licence covers 45% of the view

Example (SharedSubtree)

ExamplePack_sharedSubtree shows how a node reachable from two parents is nested once, inside the node that dominates both, with the remaining edges reported as links rather than duplicated geometry.

package main

import (
	"fmt"

	"github.com/danielriddell21/merkelbrot/graph"
	"github.com/danielriddell21/merkelbrot/layout"
)

func main() {
	g, err := graph.New(graph.NewMemorySource([]string{"root"},
		graph.Node[string]{ID: "root", Children: []string{"left", "right"}},
		graph.Node[string]{ID: "left", Children: []string{"shared"}},
		graph.Node[string]{ID: "right", Children: []string{"shared"}},
		graph.Node[string]{ID: "shared"},
	))
	if err != nil {
		panic(err)
	}

	p := layout.Pack(g, layout.Options{})
	for _, n := range p.Nodes {
		where := "top level"
		if n.HasParent {
			where = "inside " + n.Parent
		}
		fmt.Printf("%s: %s, shared=%t\n", n.ID, where, n.Shared)
	}
	for _, l := range p.Links {
		fmt.Printf("link: %s -> %s\n", l.From, l.To)
	}
}

Output:
root: top level, shared=false
left: inside root, shared=false
right: inside root, shared=false
shared: inside root, shared=true
link: left -> shared
link: right -> shared

type Placed

type Placed[K comparable] struct {
	Circle
	// ID is the node's ID in the source graph.
	ID K
	// Kind, Label and Hash are copied from the source node.
	Kind  string
	Label string
	Hash  []byte
	// Depth is the containment depth, zero for a top-level node.
	Depth int
	// Parent is the node this one is nested inside, valid only if HasParent.
	Parent    K
	HasParent bool
	// Shared reports whether the source node has more than one parent.
	Shared bool
	// Leaf reports whether the node contains no other nodes.
	Leaf bool
	// Payload holds the node's fields, packed inside it.
	Payload []Slot
}

Placed is a node with a position and a radius.

type Slot

type Slot struct {
	Circle
	Field graph.Field
}

Slot is one payload field positioned inside its node.

X, Y and R are relative to the node that owns the slot and are expressed in units of that node's radius, so a renderer scales them by [Placed.R].