layout

package
v0.8.1-0...-a25970e Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 17, 2021 License: BSD-3-Clause Imports: 8 Imported by: 0

Documentation

Overview

Package layout defines functions for performing graph layout.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type EadesR2 

type EadesR2 struct {
	// Updates is the number of updates to perform.
	Updates int

	// Repulsion is the strength of the global
	// repulsive force between nodes in the
	// layout. It corresponds to C3 in the paper.
	Repulsion float64

	// Rate is the gradient descent rate. It
	// corresponds to C4 in the paper.
	Rate float64

	// Theta is the Barnes-Hut theta constant.
	Theta float64

	// Src is the source of randomness used
	// to initialize the nodes' locations. If
	// Src is nil, the global random number
	// generator is used.
	Src rand.Source
	// contains filtered or unexported fields
}

EadesR2 implements the graph layout algorithm essentially as described in "A heuristic for graph drawing", Congressus numerantium 42:149-160. The implementation here uses the Barnes-Hut approximation for global repulsion calculation, and edge weights are considered when calculating adjacent node attraction.

Example 
package main

import (
	"fmt"
	"image/color"
	"log"
	"math"

	"gonum.org/v1/gonum/graph/layout"
	"gonum.org/v1/gonum/graph/simple"
	"gonum.org/v1/plot"
	"gonum.org/v1/plot/font"
	"gonum.org/v1/plot/plotter"
	"gonum.org/v1/plot/vg"
	"gonum.org/v1/plot/vg/draw"
)

func main() {
	// Make a simple graph and render it as a PNG
	// with the EadesR2 force-directed layout.
	g := simple.NewUndirectedGraph()
	const n = 6
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			g.SetEdge(g.NewEdge(simple.Node(i), simple.Node(j)))
		}
	}

	// Use the Eades layout algorithm with reasonable defaults.
	eades := layout.EadesR2{Repulsion: 1, Rate: 0.05, Updates: 30, Theta: 0.2}

	// Make a layout optimizer with the target graph and update function.
	optimizer := layout.NewOptimizerR2(g, eades.Update)

	// Perform layout optimization.
	for optimizer.Update() {
	}

	p := plot.New()

	// Add to plot.
	p.Add(render{optimizer})
	p.HideAxes()

	// Render graph on save.
	err := p.Save(10*vg.Centimeter, 10*vg.Centimeter, "k6_eades.png")
	if err != nil {
		log.Fatal(err)
	}
}

const radius = vg.Length(15)

// render implements the plot.Plotter interface for graphs.
type render struct {
	layout.GraphR2
}

func (p render) Plot(c draw.Canvas, plt *plot.Plot) {
	nodes := p.GraphR2.Nodes()
	if nodes.Len() == 0 {
		return
	}
	var (
		xys plotter.XYs
		ids []string
	)
	if nodes.Len() >= 0 {
		xys = make(plotter.XYs, 0, nodes.Len())
		ids = make([]string, 0, nodes.Len())
	}
	for nodes.Next() {
		u := nodes.Node()
		uid := u.ID()
		ur2 := p.GraphR2.LayoutNodeR2(uid)
		xys = append(xys, plotter.XY(ur2.Coord2))
		ids = append(ids, fmt.Sprint(uid))
		to := p.GraphR2.From(uid)
		for to.Next() {
			v := to.Node()
			vid := v.ID()
			vr2 := p.GraphR2.LayoutNodeR2(vid)

			l, err := plotter.NewLine(plotter.XYs{plotter.XY(ur2.Coord2), plotter.XY(vr2.Coord2)})
			if err != nil {
				panic(err)
			}
			l.Plot(c, plt)
			if err != nil {
				panic(err)
			}
		}
	}

	n, err := plotter.NewScatter(xys)
	if err != nil {
		panic(err)
	}
	n.GlyphStyle.Shape = nodeGlyph{}
	n.GlyphStyle.Radius = radius
	n.Plot(c, plt)

	l, err := plotter.NewLabels(plotter.XYLabels{XYs: xys, Labels: ids})
	if err != nil {
		panic(err)
	}
	fnt := font.From(plot.DefaultFont, 18)
	for i := range l.TextStyle {
		l.TextStyle[i] = draw.TextStyle{
			Font: fnt, Handler: plot.DefaultTextHandler,
			XAlign: draw.XCenter, YAlign: -0.4,
		}
	}

	l.Plot(c, plt)
}

// DataRange returns the minimum and maximum X and Y values.
func (p render) DataRange() (xmin, xmax, ymin, ymax float64) {
	nodes := p.GraphR2.Nodes()
	if nodes.Len() == 0 {
		return
	}
	var xys plotter.XYs
	if nodes.Len() >= 0 {
		xys = make(plotter.XYs, 0, nodes.Len())
	}
	for nodes.Next() {
		u := nodes.Node()
		uid := u.ID()
		ur2 := p.GraphR2.LayoutNodeR2(uid)
		xys = append(xys, plotter.XY(ur2.Coord2))
	}
	return plotter.XYRange(xys)
}

// GlyphBoxes returns a slice of plot.GlyphBoxes, implementing the
// plot.GlyphBoxer interface.
func (p render) GlyphBoxes(plt *plot.Plot) []plot.GlyphBox {
	nodes := p.GraphR2.Nodes()
	if nodes.Len() == 0 {
		return nil
	}
	var b []plot.GlyphBox
	if nodes.Len() >= 0 {
		b = make([]plot.GlyphBox, 0, nodes.Len())
	}
	for i := 0; nodes.Next(); i++ {
		u := nodes.Node()
		uid := u.ID()
		ur2 := p.GraphR2.LayoutNodeR2(uid)

		b = append(b, plot.GlyphBox{})
		b[i].X = plt.X.Norm(ur2.Coord2.X)
		b[i].Y = plt.Y.Norm(ur2.Coord2.Y)
		r := radius
		b[i].Rectangle = vg.Rectangle{
			Min: vg.Point{X: -r, Y: -r},
			Max: vg.Point{X: +r, Y: +r},
		}
	}
	return b
}

// nodeGlyph is a glyph that draws a filled circle.
type nodeGlyph struct{}

// DrawGlyph implements the GlyphDrawer interface.
func (nodeGlyph) DrawGlyph(c *draw.Canvas, sty draw.GlyphStyle, pt vg.Point) {
	var p vg.Path
	c.Push()
	c.SetColor(color.White)
	p.Move(vg.Point{X: pt.X + sty.Radius, Y: pt.Y})
	p.Arc(pt, sty.Radius, 0, 2*math.Pi)
	p.Close()
	c.Fill(p)
	c.Pop()
	c.Stroke(p)
}

Output:

func (*EadesR2) Update 

func (u *EadesR2) Update(g graph.Graph, layout LayoutR2) bool

Update is the EadesR2 spatial graph update function.

type GraphR2 

type GraphR2 interface {
	graph.Graph
	LayoutNodeR2(id int64) NodeR2
}

GraphR2 is a graph with planar spatial representation of node positions.

type IsomapR2 

type IsomapR2 struct{}

IsomapR2 implements a graph layout algorithm based on the Isomap non-linear dimensionality reduction method. Coordinates of nodes are computed by finding a Torgerson multidimensional scaling of the shortest path distances between all pairs of node in the graph. The all pair shortest path distances are calculated using the Floyd-Warshall algorithm and so IsomapR2 will not scale to large graphs. Graphs with more than one connected component cannot be laid out by IsomapR2.

func (IsomapR2) Update 

func (IsomapR2) Update(g graph.Graph, layout LayoutR2) bool

Update is the IsomapR2 spatial graph update function.

type LayoutR2 

type LayoutR2 interface {
	// IsInitialized returns whether the Layout is initialized.
	IsInitialized() bool

	// SetCoord2 sets the coordinates of the node with the given
	// id to coords.
	SetCoord2(id int64, coords r2.Vec)

	// Coord2 returns the coordinated of the node with the given
	// id in the graph layout.
	Coord2(id int64) r2.Vec
}

LayoutR2 implements graph layout updates and representations.

type NodeR2 

type NodeR2 struct {
	graph.Node
	Coord2 r2.Vec
}

NodeR2 is a graph node with planar spatial representation of its position. A NodeR2 is only valid when the graph.Node is not nil.

type OptimizerR2 

type OptimizerR2 struct {

	// Updater is the function called for each call to Update.
	// It updates the OptimizerR2's spatial distribution of the
	// nodes in the backing graph.
	Updater func(graph.Graph, LayoutR2) bool
	// contains filtered or unexported fields
}

OptimizerR2 is a helper type that holds a graph and layout optimization state.

func NewOptimizerR2 

func NewOptimizerR2(g graph.Graph, update func(graph.Graph, LayoutR2) bool) OptimizerR2

NewOptimizerR2 returns a new layout optimizer. If g implements LayoutR2 the layout will be updated into g, otherwise the OptimizerR2 will hold the graph layout. A nil value for update is a valid no-op layout update function.

func (OptimizerR2) Coord2 

func (g OptimizerR2) Coord2(id int64) r2.Vec

Coord2 returns the location of the node with the given ID. The returned value is only valid if the node exists in the graph.

func (OptimizerR2) Edge 

func (g OptimizerR2) Edge(uid, vid int64) graph.Edge

Edge returns the edge from u to v, with IDs uid and vid, if such an edge exists and nil otherwise. The node v must be directly reachable from u as defined by the From method.

func (OptimizerR2) From 

func (g OptimizerR2) From(id int64) graph.Nodes

From returns all nodes that can be reached directly from the node with the given ID.

func (OptimizerR2) HasEdgeBetween 

func (g OptimizerR2) HasEdgeBetween(xid, yid int64) bool

HasEdgeBetween returns whether an edge exists between nodes with IDs xid and yid without considering direction.

func (OptimizerR2) LayoutNodeR2 

func (g OptimizerR2) LayoutNodeR2(id int64) NodeR2

LayoutNodeR2 implements the GraphR2 interface.

func (OptimizerR2) Node 

func (g OptimizerR2) Node(id int64) graph.Node

Node returns the node with the given ID if it exists in the graph, and nil otherwise.

func (OptimizerR2) Nodes 

func (g OptimizerR2) Nodes() graph.Nodes

Nodes returns all the nodes in the graph.

func (OptimizerR2) Update 

func (g OptimizerR2) Update() bool

Update updates the locations of the nodes in the graph according to the provided update function. It returns whether the update function is able to further refine the graph's node locations.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.