layout

package
v0.0.0-...-3f18402 Latest Latest
Warning

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

 Go to latest Published: Sep 1, 2023 License: MIT Imports: 9 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type BFSOrderingInitializer 

type BFSOrderingInitializer struct{}

BFSOrderingInitializer will set order in each layer by traversing BFS from roots.

func (BFSOrderingInitializer) Init 

func (o BFSOrderingInitializer) Init(segments map[[2]uint64]bool, layers [][]uint64)

type BasicNodesVerticalCoordinatesAssigner 

type BasicNodesVerticalCoordinatesAssigner struct {
	MarginLayers   int // distance between layers
	FakeNodeHeight int
}

BasicNodesVerticalCoordinatesAssigner will check maximum height in each layer. It will keep each node vertically in the middle within each layer.

func (BasicNodesVerticalCoordinatesAssigner) NodesVerticalCoordinates 

func (s BasicNodesVerticalCoordinatesAssigner) NodesVerticalCoordinates(g Graph, lg LayeredGraph) map[uint64]int

type BrandesKopfLayersNodesHorizontalAssigner 

type BrandesKopfLayersNodesHorizontalAssigner struct {
	Delta int // distance between nodes, including fake ones
}

"Fast and Simple Horizontal Coordinate Assignment" by Ulrik Brandes and Boris Kopf, 2002 Computes horizontal coordinate in layered graph, given ordering within each layer. Produces result such that neighbors are close and long edges cross Layers are straight. Works on fully connected graphs. Assuming nodes do not have width.

func (BrandesKopfLayersNodesHorizontalAssigner) NodesHorizontalCoordinates 

func (s BrandesKopfLayersNodesHorizontalAssigner) NodesHorizontalCoordinates(_ Graph, g LayeredGraph) map[uint64]int

type CompositeLayerOrderingOptimizer 

type CompositeLayerOrderingOptimizer struct {
	Optimizers []LayerOrderingOptimizer
}

func (CompositeLayerOrderingOptimizer) Optimize 

func (o CompositeLayerOrderingOptimizer) Optimize(segments map[[2]uint64]bool, layers [][]uint64, idx int, downUp bool)

type CycleRemover 

type CycleRemover interface {
	RemoveCycles(g Graph)
	Restore(g Graph)
}

type DirectEdgesLayout 

type DirectEdgesLayout struct{}

DirectEdgesLayout are straight single line edges.

func (DirectEdgesLayout) UpdateGraphLayout 

func (l DirectEdgesLayout) UpdateGraphLayout(g Graph)

type EadesGonumLayout 

type EadesGonumLayout struct {
	Updates   int
	Repulsion float64
	Rate      float64
	Theta     float64
	ScaleX    float64
	ScaleY    float64
}

This works, but not as pretty.

func (EadesGonumLayout) UpdateGraphLayout 

func (l EadesGonumLayout) UpdateGraphLayout(g Graph)

type Edge 

type Edge struct {
	Path [][2]int // [start: {x,y}, ... finish: {x,y}]
}

Edge is path of points that edge goes through

func DirectEdge 

func DirectEdge(from, to Node) Edge

DirectEdge is straight line from center of one node to another.

type Force 

type Force interface {
	UpdateForce(g Graph, f map[uint64][2]float64)
}

Force computes forces for Nodes.

type ForceGraphLayout 

type ForceGraphLayout struct {
	Delta    float64 // how much move each step
	MaxSteps int     // limit of iterations
	Epsilon  float64 // minimal force
	Forces   []Force
}

ForceGraphLayout will simulate node movement due to forces.

func (ForceGraphLayout) UpdateGraphLayout 

func (l ForceGraphLayout) UpdateGraphLayout(g Graph)

type Graph 

type Graph struct {
	Edges map[[2]uint64]Edge
	Nodes map[uint64]Node
}

Graph tells how to position nodes and paths for edges

func (Graph) BoundingBox 

func (g Graph) BoundingBox() (minx, miny, maxx, maxy int)

BoundingBox coordinates that should fit whole graph. Does not consider edges.

func (Graph) Copy 

func (g Graph) Copy() Graph

func (Graph) Roots 

func (g Graph) Roots() []uint64

func (Graph) TotalNodesHeight 

func (g Graph) TotalNodesHeight() int

func (Graph) TotalNodesWidth 

func (g Graph) TotalNodesWidth() int

type GravityForce 

type GravityForce struct {
	K         float64 // positive K for attraction
	EdgesOnly bool    // true = only edges, false = all nodes
}

GravityForce is gravity-like repulsive (or attractive) force.

func (GravityForce) UpdateForce 

func (l GravityForce) UpdateForce(g Graph, f map[uint64][2]float64)

type IsomapR2GonumLayout 

type IsomapR2GonumLayout struct {
	Scale  float64
	ScaleX float64
	ScaleY float64
}

func (IsomapR2GonumLayout) UpdateGraphLayout 

func (l IsomapR2GonumLayout) UpdateGraphLayout(g Graph)

type LayerOrderingInitializer 

type LayerOrderingInitializer interface {
	Init(segments map[[2]uint64]bool, layers [][]uint64)
}

type LayerOrderingOptimizer 

type LayerOrderingOptimizer interface {
	Optimize(segments map[[2]uint64]bool, layers [][]uint64, idx int, downUp bool)
}

type LayeredGraph 

type LayeredGraph struct {
	Segments map[[2]uint64]bool     // segment is an edge in layered graph, can be real edge or piece of fake edge
	Dummy    map[uint64]bool        // fake nodes
	NodeYX   map[uint64][2]int      // node -> {layer, ordering in layer}
	Edges    map[[2]uint64][]uint64 // real long/short edge -> {real, fake, fake, fake, real} nodes
}

LayeredGraph is graph with dummy nodes such that there is no long edges. Short edge is between nodes in Layers next to each other. Long edge is between nodes in 1+ Layers between each other. Segment is either a short edge or a long edge. Top layer has lowest layer number.

func NewLayeredGraph 

func NewLayeredGraph(g Graph) LayeredGraph

Expects that graph g does not have cycles. This step creates fake nodes and splits long edges into segments.

func (LayeredGraph) IsInnerSegment 

func (g LayeredGraph) IsInnerSegment(segment [2]uint64) bool

IsInnerSegment tells when edge is between two Dummy nodes.

func (LayeredGraph) Layers 

func (g LayeredGraph) Layers() [][]uint64

func (LayeredGraph) LowerNeighbors 

func (g LayeredGraph) LowerNeighbors(node uint64) []uint64

LowerNeighbors are nodes in lower layer that are connected to given node.

func (LayeredGraph) String 

func (g LayeredGraph) String() string

func (LayeredGraph) UpperNeighbors 

func (g LayeredGraph) UpperNeighbors(node uint64) []uint64

UpperNeighbors are nodes in upper layer that are connected to given node.

func (LayeredGraph) Validate 

func (g LayeredGraph) Validate() error

type Layout 

type Layout interface {
	UpdateGraphLayout(g Graph)
}

Layout is something that can update graph layout

type Node 

type Node struct {
	XY [2]int // smallest x,y corner
	W  int
	H  int
}

Node is how to position node and its dimensions

func (Node) CenterXY 

func (n Node) CenterXY() [2]int

type NodesHorizontalCoordinatesAssigner 

type NodesHorizontalCoordinatesAssigner interface {
	NodesHorizontalCoordinates(g Graph, lg LayeredGraph) map[uint64]int
}

type NodesVerticalCoordinatesAssigner 

type NodesVerticalCoordinatesAssigner interface {
	NodesVerticalCoordinates(g Graph, lg LayeredGraph) map[uint64]int
}

type RandomLayerOrderingInitializer 

type RandomLayerOrderingInitializer struct{}

RandomLayerOrderingInitializer assigns random ordering in each layer

func (RandomLayerOrderingInitializer) Init 

func (o RandomLayerOrderingInitializer) Init(_ map[[2]uint64]bool, layers [][]uint64)

type RandomLayerOrderingOptimizer 

type RandomLayerOrderingOptimizer struct {
	Epochs int
}

RandomLayerOrderingOptimizer picks best out of epochs random orderings.

func (RandomLayerOrderingOptimizer) Optimize 

func (o RandomLayerOrderingOptimizer) Optimize(segments map[[2]uint64]bool, layers [][]uint64, idx int, downUp bool)

type ScalerLayout 

type ScalerLayout struct {
	Scale float64
}

ScalerLayout will scale existing layout by constant factor.

func (*ScalerLayout) UpdateGraphLayout 

func (l *ScalerLayout) UpdateGraphLayout(g Graph)

type SequenceLayout 

type SequenceLayout struct {
	Layouts []Layout
}

SequenceLayout applies sequence of layouts

func (SequenceLayout) UpdateGraphLayout 

func (s SequenceLayout) UpdateGraphLayout(g Graph)

type SimpleCycleRemover 

type SimpleCycleRemover struct {
	Reversed map[[2]uint64]bool
}

SimpleCycleRemover will keep testing for cycles, if cycle found will randomly reverse one edge in cycle. When restoring, will reverse previously reversed edges.

func NewSimpleCycleRemover 

func NewSimpleCycleRemover() SimpleCycleRemover

func (SimpleCycleRemover) RemoveCycles 

func (s SimpleCycleRemover) RemoveCycles(g Graph)

func (SimpleCycleRemover) Restore 

func (s SimpleCycleRemover) Restore(g Graph)

type SpringForce 

type SpringForce struct {
	K         float64 // has to be positive
	L         float64 // distance at rest
	EdgesOnly bool    // true = only edges, false = all nodes
}

SpringForce is linear by distance.

func (SpringForce) UpdateForce 

func (l SpringForce) UpdateForce(g Graph, f map[uint64][2]float64)

type StraightEdgePathAssigner 

type StraightEdgePathAssigner struct{}

StraightEdgePathAssigner will check node locations for each fake/real node in path and set edge path to go through middle of it.

func (StraightEdgePathAssigner) UpdateGraphLayout 

func (l StraightEdgePathAssigner) UpdateGraphLayout(g Graph, lg LayeredGraph, allNodesXY map[uint64][2]int)

type SugiyamaLayersStrategyGraphLayout 

type SugiyamaLayersStrategyGraphLayout struct {
	CycleRemover                       CycleRemover
	LevelsAssigner                     func(g Graph) LayeredGraph
	OrderingAssigner                   func(g Graph, lg LayeredGraph)
	NodesHorizontalCoordinatesAssigner NodesHorizontalCoordinatesAssigner
	NodesVerticalCoordinatesAssigner   NodesVerticalCoordinatesAssigner
	EdgePathAssigner                   func(g Graph, lg LayeredGraph, allNodesXY map[uint64][2]int)
}

Kozo Sugiyama algorithm breaks down layered graph construction in phases.

func (SugiyamaLayersStrategyGraphLayout) UpdateGraphLayout 

func (l SugiyamaLayersStrategyGraphLayout) UpdateGraphLayout(g Graph)

UpdateGraphLayout breaks down layered graph construction in phases.

type SwitchAdjacentOrderingOptimizer 

type SwitchAdjacentOrderingOptimizer struct{}

SwitchAdjacentOrderingOptimizer will try swapping two adjacent nodes in a layer will improve crossings. This is used in dot/Graphviz, Figure 3-3 in Graphviz dot paper TSE93 and called "transpose".

func (SwitchAdjacentOrderingOptimizer) Optimize 

func (o SwitchAdjacentOrderingOptimizer) Optimize(segments map[[2]uint64]bool, layers [][]uint64, y int, downUp bool)

type WMedianOrderingOptimizer 

type WMedianOrderingOptimizer struct{}

WMedianOrderingOptimizer takes median of upper (or lower) level neighbors for each node in layer. Median has property of stable vertical edges which is especially useful for "long" edges (fake nodes). Eades and Wormald, 1994 This is used in dot/Graphviz, Figure 3-2 in Graphviz dot paper TSE93.

func (WMedianOrderingOptimizer) Optimize 

func (o WMedianOrderingOptimizer) Optimize(segments map[[2]uint64]bool, layers [][]uint64, y int, downUp bool)

type WarfieldOrderingOptimizer 

type WarfieldOrderingOptimizer struct {
	Epochs                   int
	LayerOrderingInitializer LayerOrderingInitializer
	LayerOrderingOptimizer   LayerOrderingOptimizer
}

WarfieldOrderingOptimizer is heuristic based strategy for ordering optimization. Goes up and down number of iterations across all layers. Considers upper and lower fixed and permutes ordering in layer. Used in Graphviz/dot.

func (WarfieldOrderingOptimizer) Optimize 

func (o WarfieldOrderingOptimizer) Optimize(g Graph, lg LayeredGraph)

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.