graph-layout/main.go

package main

import (
	"fmt"
	"image"
	"image/color"
	"log"
	"math"
	"math/rand"
	"os"
	"strings"
	"time"

	"gioui.org/app"
	"gioui.org/f32"
	"gioui.org/font/gofont"
	"gioui.org/io/key"
	"gioui.org/layout"
	"gioui.org/op"
	"gioui.org/op/clip"
	"gioui.org/op/paint"
	"gioui.org/text"
	"gioui.org/unit"
	"gioui.org/widget/material"
)

const MAX_LOOP = 100_000_000

type C = layout.Context
type D = layout.Dimensions

var darkPalette = material.Palette{
	Bg:         color.NRGBA{R: 0x28, G: 0x28, B: 0x28, A: 0xff},
	Fg:         color.NRGBA{R: 0xeb, G: 0xdb, B: 0xb2, A: 0xff},
	ContrastBg: color.NRGBA{R: 0x48, G: 0x85, B: 0x88, A: 0xff},
	ContrastFg: color.NRGBA{R: 0xeb, G: 0xdb, B: 0xb2, A: 0xff},
}

func main() {
	go func() {
		window := new(app.Window)
		window.Option(app.Title("Not-a-graph-layout-algorithm graph layout algorithm"))

		err := run(window)
		if err != nil {
			log.Fatal(err)
		}
		os.Exit(0)
	}()

	app.Main()
}

func run(window *app.Window) error {
	theme := material.NewTheme()
	theme.Palette = darkPalette
	theme.Shaper =
		text.NewShaper(text.WithCollection(gofont.Collection()))

	seed := int64(0)
	g := Graph{}
	g.random = rand.New(rand.NewSource(seed))
	g.offsets = g._offsets[:]
	g.degrees = g._degrees[:]
	g.nodes = g._nodes[:0]
	g.allocs = g._allocs[:]
	g.edges = g._edges[:0]
	g.adjacency = g._adjacency[:0]

	title := material.Body1(theme, "")
	title.Color = theme.Fg
	title.Alignment = text.Start
	title.WrapPolicy = text.WrapWords

	simPeriod := 50 * time.Millisecond
	lastStep := time.Now()
	bumpShift := 1
	lastSecond := time.Now()
	frameCnt, stepCnt := 0, 0
	fps, sps := 0, 0
	simFinishedTime := time.Now()
	simCnt := int64(0)
	var (
		stepOutput      strings.Builder
		statusText      strings.Builder
		ops             op.Ops
		screensaverMode bool = true
		finished,
		resetRequested,
		bumpRequested bool
	)
	for {
		switch e := window.Event().(type) {
		case app.DestroyEvent:
			return e.Err

		case app.FrameEvent:
			gtx := app.NewContext(&ops, e)

			// Handle input
			for {
				event, ok := e.Source.Event(
					key.Filter{Name: "B"},
					key.Filter{Name: "R"},
					key.Filter{Name: "S", Required: key.ModShift},
					key.Filter{Name: "<", Required: key.ModShift},
					key.Filter{Name: ">", Required: key.ModShift},
				)
				if !ok {
					break
				}
				switch evt := event.(type) {
				case key.Event:
					switch evt.Name {
					case "B":
						if evt.State == key.Press {
							bumpRequested = true
						}
					case "R":
						if evt.State == key.Press {
							resetRequested = true
						}
					case "S":
						if evt.State == key.Press {
							screensaverMode = !screensaverMode
						}
					case "<":
						if evt.State == key.Press {
							simPeriod += 50 * time.Millisecond
							simPeriod = min(simPeriod, 10*time.Second)
						}
					case ">":
						if evt.State == key.Press {
							simPeriod -= 50 * time.Millisecond
							simPeriod = max(simPeriod, 0)
						}
					}
				}
			}

			if resetRequested ||
				(screensaverMode && finished &&
					time.Since(simFinishedTime) >= 5*time.Second) {
				(&g).Reset()
				resetRequested = false
				finished = false
				simCnt++
			}

			if time.Since(lastStep) >= simPeriod {
				if int(g.order) == cap(g.nodes) && bumpRequested {
					bump(&g, bumpShift)
					//bumpShift++
					bumpRequested = false
				}
				stepOutput.Reset()
				stepOutput.WriteString((&g).Step())
				//statusText.WriteString((&g).Semilattice())
				lastStep = time.Now()

				addNodeAtRandom(&g)
				stepCnt++
			}

			paint.Fill(&ops, theme.Bg)

			layout.UniformInset(
				unit.Dp(10),
			).Layout(gtx, func(gtx C) D {
				return layout.Flex{
					Axis:      layout.Horizontal,
					Alignment: layout.Start,
					Spacing:   layout.SpaceEnd,
				}.Layout(gtx,
					layout.Rigid(func(gtx C) D {
						return (&g).Layout(gtx, theme)
					}),
					layout.Rigid(func(gtx C) D {
						return layout.Flex{
							Axis:      layout.Vertical,
							Alignment: layout.Start,
							Spacing:   layout.SpaceEnd,
						}.Layout(gtx,
							layout.Rigid(func(gtx C) D {
								return (&g).LayoutDist(gtx, theme)
							}),
							layout.Flexed(1.0, func(gtx C) D {
								return title.Layout(gtx)
							}),
						)
					}),
				)
			})

			if time.Since(lastSecond) >= time.Second {
				fps, sps = frameCnt, stepCnt
				frameCnt, stepCnt = 0, 0
				lastSecond = time.Now()
			}

			statusText.Reset()
			statusText.WriteString(fmt.Sprintf("seed %d, simulation %d\n", seed, simCnt+1))
			statusText.WriteString(fmt.Sprintf("simulation rate: %s per step\n", simPeriod))
			statusText.WriteString(fmt.Sprintf("fps=%d; sps=%d\n", fps, sps))

			statusText.WriteString(stepOutput.String())
			title.Text = statusText.String()

			if int(g.order) == cap(g.nodes) && !finished {
				finished = true
				simFinishedTime = time.Now()
			}
			e.Source.Execute(op.InvalidateCmd{})

			e.Frame(gtx.Ops)
			frameCnt++
		}
	}
}

func bump(g *Graph, shift int) int {
	root := -1
	for n := 0; n < int(g.order); n++ {
		if g.nodes[n] == 1 {
			root = n
			break
		}
	}
	if root < 0 {
		return root
	}
	g.nodes[root] <<= shift
	return root

	nodes := make([]NodeId, 1, g.order)
	nextNodes := make(map[NodeId]struct{}, g.order)
	nodes[0] = NodeId(root)

	for len(nodes) > 0 {
		for _, n := range nodes {
			for _, e := range g.edges[g.offsets[n]:g.offsets[n+1]] {
				nextNodes[e] = struct{}{}
			}
		}
		nodes = nodes[:len(nextNodes)]
		i := 0
		for n := range nextNodes {
			delete(nextNodes, n)
			nodes[i] = n
			i++
			if log2(g.nodes[n])+uint32(shift) >= 30 {
				log.Printf("Out-of-address-space condition for node %d", n)
				continue
			}
			g.nodes[n] <<= shift
		}
	}
	return root
}

func addNodeAtRandom(g *Graph) (order uint32) {
	if g.order == uint32(cap(g.nodes)) ||
		g.size == uint32(cap(g.edges)) {
		return g.order
	}

	/*threshold := 0.05 * float64(g.order)
	if g.random.ExpFloat64() <= threshold {
		return g.order
	}*/
	g.edges = g.edges[:cap(g.edges)]
	g.nodes = g.nodes[:cap(g.nodes)]

	i := int(g.order)
	g.nodes[i] = 1
	g.offsets[i] = EdgeId(g.size)

	for j := i + 1; j < len(g.nodes); j++ {
		g.edges[g.size] = NodeId(j)

		distance := float64(j - i)
		edgeProbability := 1 / (1 + math.Exp(0.25*distance))

		if g.random.Float64() > edgeProbability {
			continue
		}
		g.degrees[i]++
		g.size++
	}
	g.order++
	g.offsets[g.order] = EdgeId(g.size)
	g.nodes = g.nodes[:g.order]
	g.edges = g.edges[:g.size]

	return g.order
}

type NodeId uint32
type EdgeId uint32

const GraphOrder int = 128

type Graph struct {
	_adjacency [GraphOrder * (GraphOrder - 1)]NodeId
	_edges     [(GraphOrder * (GraphOrder - 1)) >> 1]NodeId
	_nodes     [GraphOrder]uint32
	_allocs    [GraphOrder]uint32
	_offsets   [GraphOrder + 1]EdgeId
	_degrees   [GraphOrder]byte

	random *rand.Rand

	adjacency []NodeId // Bidirectional adjacent node ids
	edges     []NodeId // Unidirectional adjacent node ids
	nodes     []uint32
	allocs    []uint32 // Address allocation state, per node
	offsets   []EdgeId
	degrees   []byte // Node degrees

	size   uint32 // Number of edges added to graph
	order  uint32 // Number of nodes added to graph
	source NodeId // A selected source node
	target NodeId // A selected target node
}

func (g *Graph) Reset() {
	for i := range g.offsets {
		g.offsets[i] = 0
	}
	for i := range g.nodes {
		g.nodes[i] = 0
	}
	for i := range g.allocs {
		g.allocs[i] = 0
	}
	for i := range g.edges {
		g.edges[i] = 0
	}
	g.nodes = g.nodes[:0]
	g.edges = g.edges[:0]
	g.order, g.size = 0, 0
}

func (g *Graph) Semilattice() string {
	var b strings.Builder
	for n := 0; n < len(g.nodes); n++ {
		b.WriteString(fmt.Sprintf("nodeAddr=%d neighbors=", g.nodes[n]))

		for _, e := range g.edges[g.offsets[n]:g.offsets[n+1]] {
			if uint32(e) >= g.order {
				continue
			}
			b.WriteString(fmt.Sprintf("%d, ", g.nodes[e]))
		}
		b.WriteString("\n")
	}
	return b.String()
}

func (g *Graph) Step() string {
	for n := range g.nodes {
		if g.allocs[n] == 0 {
			g.allocs[n] = 1 // Seed allocator
		}
		shift := log2(g.nodes[n]) + 1

		if log2(g.allocs[n])+shift >= 30 {
			log.Printf("Out-of-address-space condition for node %d", n)
			continue
		}
		edges := g.edges[g.offsets[n]:g.offsets[n+1]]

		shiftStart := 1
		// Shift a node containing exactly one 1
		if (n == 0 || g.nodes[n] > 1) && // root or assigned
			g.nodes[n]&(g.nodes[n]-1) == 0 { // ...contains one 1

			for i := 0; i < min(shiftStart, len(edges)); i++ {
				e := edges[i]
				if uint32(e) < g.order && g.nodes[n] >= g.nodes[e] {
					g.nodes[e] = g.nodes[n] << (i + 1)
				}
			}
		}
		// Assign addresses to neighbors
		for i := shiftStart; i < len(edges); i++ {
			nextAlloc := (g.allocs[n] << shift) | g.nodes[n]
			e := edges[i]
			if uint32(e) >= g.order ||
				(g.nodes[e] != 1 && nextAlloc >= g.nodes[e]) {
				continue
			}
			g.nodes[e] = nextAlloc
			g.allocs[n]++
		}
	}
	return fmt.Sprintf("nodes=%v\nedges=%v", g.nodes, g.edges)
}

func (g *Graph) Layout(
	gtx layout.Context,
	th *material.Theme,
) D {
	squareMax := min(
		gtx.Constraints.Max.X,
		gtx.Constraints.Max.Y,
	)
	convFactor := float32(squareMax) / 65535.0
	circle := clip.Ellipse{Max: image.Pt(16, 16)}

	// Outer margin
	defer op.Offset(image.Pt(10, 10)).Push(gtx.Ops).Pop()

	var path clip.Path
	for n := 0; n < len(g.nodes); n++ {
		x1, y1 := idToPt(g.nodes[n], convFactor)

		for e := range g.edges[g.offsets[n]:g.offsets[n+1]] {
			if uint32(e) >= g.order {
				continue
			}
			if g.nodes[n] == 1 { // Skip orphans and roots
				continue
			}
			color := th.Fg
			if distance(g.nodes[n], g.nodes[e]) > 4 {
				color = th.ContrastBg
				color.A = 0xd0
			}
			x2, y2 := idToPt(g.nodes[e], convFactor)

			path.Begin(gtx.Ops)
			path.MoveTo(f32.Pt(float32(x1), float32(y1)))
			path.LineTo(f32.Pt(float32(x2), float32(y2)))
			paint.FillShape(gtx.Ops, color,
				clip.Stroke{
					Path:  path.End(),
					Width: float32(unit.Dp(1)),
				}.Op(),
			)
		}
		// Circle size is proportional to address length.
		length := log2(g.nodes[n])
		shift := int(length >> 3)
		scaled := circle
		scaled.Max.X = scaled.Max.X >> shift
		scaled.Max.Y = scaled.Max.Y >> shift
		halfW, halfH := scaled.Max.X>>1, scaled.Max.Y>>1

		pos := image.Pt(gtx.Dp(x1)-halfW, gtx.Dp(y1)-halfH)

		macro := op.Record(gtx.Ops)
		stack := op.Offset(pos).Push(gtx.Ops)
		nodeColor := th.Fg
		if length >= 24 {
			nodeColor = color.NRGBA{R: 0xaa, G: 0, B: 0xaa, A: 0xff}
		}
		paint.FillShape(gtx.Ops, nodeColor, scaled.Op(gtx.Ops))
		stack.Pop()
		c := macro.Stop()
		op.Defer(gtx.Ops, c)
	}
	return layout.Dimensions{Size: image.Pt(squareMax, squareMax)}
}

func (g *Graph) LayoutDist(
	gtx layout.Context,
	th *material.Theme,
) D {
	dims := f32.Pt(400, 100)
	width := gtx.Dp(unit.Dp(dims.X))
	height := gtx.Dp(unit.Dp(dims.Y))

	defer op.Affine( // Flip y-axis and scale
		f32.Affine2D{}.
			Scale(f32.Pt(dims.X/2, dims.Y/2), f32.Pt(1.0, -1.0)),
	).Push(gtx.Ops).Pop()

	barWidth := 0
	if g.order > 0 {
		pxPerBucket := float32(width) / float32(g.order)
		barWidth = gtx.Dp(unit.Dp(pxPerBucket))
	}
	color := color.NRGBA{R: 0xaa, G: 0, B: 0xaa, A: 0xff}

	maxOutDegree := 0
	for n := range g.nodes {
		d := g.offsets[n+1] - g.offsets[n]
		maxOutDegree = max(maxOutDegree, int(d))
	}
	convFactor := float64(height) / float64(maxOutDegree)

	for n := range g.nodes {
		cnt := g.offsets[n+1] - g.offsets[n]
		y := gtx.Dp(unit.Dp(float64(cnt) * convFactor))
		stack := clip.Rect{
			Min: image.Pt(n*barWidth, 0),
			Max: image.Pt((n+1)*barWidth, y),
		}.Push(gtx.Ops)

		paint.ColorOp{Color: color}.Add(gtx.Ops)
		paint.PaintOp{}.Add(gtx.Ops)
		stack.Pop()
	}
	return layout.Dimensions{Size: image.Pt(width, height)}
}

func distance(a, b uint32) uint32 {
	var s, e uint32 = 1, 2
	for s < 32 && a&(e-1) == b&(e-1) {
		s++
		e <<= 1
	}
	s -= 1
	return ones(a>>s) + ones(b>>s)
}

func ones(x uint32) uint32 {
	var c uint32
	for c = 0; x != 0; c++ {
		x &= x - 1 // clear the least significant bit set
	}
	return c
}

func idToPt(id uint32, convFactor float32) (x, y unit.Dp) {
	x0, y0 := demorton(reverse32(id))

	x, y = unit.Dp(float32(x0)*convFactor),
		unit.Dp(float32(y0)*convFactor)

	return
}

func log2(x uint32) uint32 {
	b := []uint32{0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000}
	s := []uint32{1, 2, 4, 8, 16}

	var r uint32 = 0

	for i := 4; i >= 0; i-- {
		if x&b[i] != 0 {
			x >>= s[i]
			r |= s[i]
		}
	}
	return r
}

func reverse32(x uint32) uint32 {
	var rev uint32
	var mask uint32 = 0xff

	for i := 0; i < 4; i++ {
		rshift := 8 * i
		lshift := 8 * (3 - i)
		rev |= uint32(reverse((x&mask)>>rshift)) << lshift
		mask <<= 8
	}
	return rev
}

func reverse(b uint32) byte {
	b = (b * 0x0802 & 0x22110) | (b * 0x8020 & 0x88440)
	b *= 0x10101
	b >>= 16
	return byte(b)
}

func demorton(z uint32) (x, y uint16) {
	res := (uint64(z) | (uint64(z) << 31)) & 0x5555555555555555
	res = (res | (res >> 1)) & 0x3333333333333333
	res = (res | (res >> 2)) & 0x0f0f0f0f0f0f0f0f
	res = (res | (res >> 4)) & 0x00ff00ff00ff00ff
	res = res | (res >> 8)
	x = uint16(res)
	y = uint16(res >> 32)
	return
}

func morton(x, y uint16) uint32 {
	var res uint64

	res = uint64(x) | (uint64(y) << 32)
	res = (res | (res << 8)) & 0x00ff00ff00ff00ff
	res = (res | (res << 4)) & 0x0f0f0f0f0f0f0f0f
	res = (res | (res << 2)) & 0x3333333333333333
	res = (res | (res << 1)) & 0x5555555555555555

	return uint32(res | (res >> 31))
}