Documentation ¶
Index ¶
- type BFSOrderingInitializer
- type BasicNodesVerticalCoordinatesAssigner
- type BrandesKopfLayersNodesHorizontalAssigner
- type CompositeLayerOrderingOptimizer
- type CycleRemover
- type DirectEdgesLayout
- type EadesGonumLayout
- type Edge
- type Force
- type ForceGraphLayout
- type Graph
- type GravityForce
- type IsomapR2GonumLayout
- type LayerOrderingInitializer
- type LayerOrderingOptimizer
- type LayeredGraph
- type Layout
- type Node
- type NodesHorizontalCoordinatesAssigner
- type NodesVerticalCoordinatesAssigner
- type RandomLayerOrderingInitializer
- type RandomLayerOrderingOptimizer
- type ScalerLayout
- type SequenceLayout
- type SimpleCycleRemover
- type SpringForce
- type StraightEdgePathAssigner
- type SugiyamaLayersStrategyGraphLayout
- type SwitchAdjacentOrderingOptimizer
- type WMedianOrderingOptimizer
- type WarfieldOrderingOptimizer
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.
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
}
type CycleRemover ¶
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 ¶
DirectEdge is straight line from center of one node to another.
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 ¶
Graph tells how to position nodes and paths for edges
func (Graph) BoundingBox ¶
BoundingBox coordinates that should fit whole graph. Does not consider edges.
func (Graph) TotalNodesHeight ¶
func (Graph) TotalNodesWidth ¶
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 ¶
func (IsomapR2GonumLayout) UpdateGraphLayout ¶
func (l IsomapR2GonumLayout) UpdateGraphLayout(g Graph)
type LayerOrderingOptimizer ¶
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 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
type RandomLayerOrderingOptimizer ¶
type RandomLayerOrderingOptimizer struct {
Epochs int
}
RandomLayerOrderingOptimizer picks best out of epochs random orderings.
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 ¶
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".
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.
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)