viz

Documentation

Overview

Package viz exports the gga graph structs to .dot files, the format supported by Graphviz (https://graphviz.org/). The main use case is the ability to visualize a graph before, during and after the execution of an algorithm.

Index

• Variables
• func DotAttrs(f ds.FAttrs) string
• func ExportViz(vi AlgoViz, w io.Writer) error
• func Quoted(i ds.Item) string
• func ResetGraphFmt(g *ds.G)
• func SetTheme(e *Exporter, t Theme)
• func Snapshot(g *ds.G, w io.Writer, t Theme)
• type AlgoViz
• type BFSViz
  • func NewBFSViz(g *ds.G, tree algo.BFTree, src int, t Theme) *BFSViz
  • func (vi *BFSViz) Traverse() error
• type CCViz
  • func NewCCViz(g *ds.G, ccs []algo.CC, t Theme) *CCViz
  • func (vi *CCViz) Traverse() error
• type DFSViz
  • func NewDFSViz(g *ds.G, f algo.DFForest, e algo.EdgeTypes, t Theme) *DFSViz
  • func (vi *DFSViz) Traverse() error
• type Exporter
  • func NewExporter() *Exporter
  • func (d *Exporter) AddExtra(s ...string)
  • func (d *Exporter) Export(g *ds.G, w io.Writer)
  • func (d *Exporter) VisitEdge(g ds.G, e ds.GE)
  • func (d *Exporter) VisitGraphEnd(ds.G)
  • func (d *Exporter) VisitGraphStart(g ds.G)
  • func (d *Exporter) VisitVertex(g ds.G, v ds.GV)
• type GSCCViz
  • func NewGSCCViz(g *ds.G, t Theme) *GSCCViz
  • func (vi *GSCCViz) Traverse() error
• type LightBreezeTheme
  • func (t LightBreezeTheme) SetEdgeFmt(attrs ds.FAttrs)
  • func (t LightBreezeTheme) SetGraphFmt(attrs ds.FAttrs)
  • func (t LightBreezeTheme) SetVertexFmt(attrs ds.FAttrs)
• type MSTViz
  • func NewMSTViz(g *ds.G, mst algo.MST, t Theme) *MSTViz
  • func (vi *MSTViz) Traverse() error
• type SCCViz
  • func NewSCCViz(g *ds.G, sccs []algo.SCC, t Theme) *SCCViz
  • func (vi *SCCViz) Traverse() error
• type TSortViz
  • func NewTSortViz(g *ds.G, ord []int, t Theme) *TSortViz
  • func (vi *TSortViz) Traverse() error
• type Theme
• type ThemedGraphViz
  • func (v *ThemedGraphViz) GetExtra() []string
  • func (v *ThemedGraphViz) GetGraph() *ds.G
  • func (v *ThemedGraphViz) GetTheme() Theme

Examples

• Exporter

Variables

var Themes = struct {
	LightBreeze LightBreezeTheme
}{}

Functions

func DotAttrs

func DotAttrs(f ds.FAttrs) string

DotAttrs converts an object holding formatting attributes to its DOT language equivalent. Full list of DOT attributes can be found here: https://graphviz.org/doc/info/attrs.html.

func ExportViz

func ExportViz(vi AlgoViz, w io.Writer) error

ExportViz guides the execution of an AlgoViz implementation and then export its results.

func Quoted

func Quoted(i ds.Item) string

Quoted adds quotes to the label of a ds.Item, which is useful for labels containing special characters.

func ResetGraphFmt

func ResetGraphFmt(g *ds.G)

ResetGraphFmt resets custom formatting attributes for every vertex and edge of a graph.

func SetTheme

func SetTheme(e *Exporter, t Theme)

SetTheme sets the default formatting of an exporter using a Theme.

func Snapshot

func Snapshot(g *ds.G, w io.Writer, t Theme)

Snapshot implements a shorthand for the quick export of a graph, using a theme.

Types

type AlgoViz

type AlgoViz interface {
	GetGraph() *ds.G
	GetExtra() []string
	GetTheme() Theme
	Traverse() error
}

An AlgoViz implementer can traverse the results of a graph algorithm, provide its input graph, and also support theming.

type BFSViz

type BFSViz struct {
	ThemedGraphViz

	Tree   algo.BFTree
	Source int

	// OnUnVertex is called when an unreachable vertex is found.
	OnUnVertex func(int, algo.BFNode)

	// OnSourceVertex is called when the source vertex is found.
	OnSourceVertex func(int, algo.BFNode)

	// OnTreeVertex is called when any tree vertex is found, including the source vertex.
	OnTreeVertex func(int, algo.BFNode)

	// OnTreeEdge is called when a tree edge is found.
	OnTreeEdge func(int, int)
}

BFSViz formats and exports a graph after the execution of the BFS algorithm. The output of the algorithm is traversed, and hooks are provided so that custom formatting can be applied to the graph, its vertices and edges.

func NewBFSViz

func NewBFSViz(g *ds.G, tree algo.BFTree, src int, t Theme) *BFSViz

NewBFSViz initializes a new BFSViz with NOOP hooks.

func (*BFSViz) Traverse

func (vi *BFSViz) Traverse() error

Traverse iterates over the results of a BFS execution, calling its hooks when appropriate.

type CCViz

type CCViz struct {
	ThemedGraphViz

	CCs []algo.CC

	// OnCCVertex is called for every vertex, along with the index of its CC.
	OnCCVertex func(int, int)

	// OnCCEdge is called for any edge connecting vertices in the same CC.
	OnCCEdge func(int, int, int)
}

CCViz formats and exports an undirected graph after the execution of any algorithm that discovers connected components. The output of the algorithm is traversed, and hooks are provided so that custom formatting can be applied to the graph, its vertices and edges.

func NewCCViz

func NewCCViz(g *ds.G, ccs []algo.CC, t Theme) *CCViz

NewCCViz initializes a new CCViz with NOOP hooks.

func (*CCViz) Traverse

func (vi *CCViz) Traverse() error

Traverse iterates over the results of any CC algorithm, calling its hooks when appropriate.

type DFSViz

type DFSViz struct {
	ThemedGraphViz

	Forest algo.DFForest
	Edges  algo.EdgeTypes

	// OnTreeVertex is called for every vertex in the graph.
	OnTreeVertex func(int, algo.DFNode)

	// OnRootVertex is called when the root of a DF tree is found.
	OnRootVertex func(int, algo.DFNode)

	// OnTreeEdge is called when a tree edge is found.
	OnTreeEdge func(int, int)

	// OnForwardEdge is called when a forward edge is found.
	OnForwardEdge func(int, int)

	// OnBackEdge is called when a back edge is found.
	OnBackEdge func(int, int)

	// OnCrossEdge is called when a cross edge is found.
	OnCrossEdge func(int, int)
}

DFSViz formats and exports a graph after the execution of the DFS algorithm. The output of the algorithm is traversed, and hooks are provided so that custom formatting can be applied to the graph, its vertices and edges.

func NewDFSViz

func NewDFSViz(g *ds.G, f algo.DFForest, e algo.EdgeTypes, t Theme) *DFSViz

NewDFSViz initializes a new DFSViz with NOOP hooks.

func (*DFSViz) Traverse

func (vi *DFSViz) Traverse() error

Traverse iterates over the results of a DFS execution, calling its hooks when appropriate.

type Exporter

type Exporter struct {
	Lines []string
	Extra []string

	DefaultGraphFmt  ds.FAttrs
	DefaultVertexFmt ds.FAttrs
	DefaultEdgeFmt   ds.FAttrs

	UndirectedArrow string
	DirectedArrow   string
}

Exporter implements the ds.GraphVisitor interface in order to traverse a ds.Graph and build a sequence of lines in the DOT language. After a successful visit, these lines can then be exported to an io.Writer by calling its Export method.

Full specification of the DOT language, by Graphviz can be found here: https://graphviz.org/doc/info/lang.html

Example

package main

import (
	"fmt"
	"os"

	"github.com/vc-souza/gga/ds"
)

type pokemon struct {
	Type string
	Name string
}

func (c pokemon) Label() string {
	return fmt.Sprintf("%s (%s)", c.Name, c.Type)
}

func main() {
	pwag := &pokemon{Type: "water", Name: "Poliwag"}
	pwl := &pokemon{Type: "water", Name: "Poliwhirl"}
	pot := &pokemon{Type: "water", Name: "Politoed"}
	pow := &pokemon{Type: "water/fighting", Name: "Poliwrath"}

	g := ds.NewDigraph()
	e := NewExporter()

	g.AddVertex(pwag)
	g.AddVertex(pwl)
	g.AddVertex(pot)
	g.AddVertex(pow)

	g.AddEdge(pwag, pwl, 0)
	g.AddEdge(pwl, pot, 0)
	g.AddEdge(pwl, pow, 0)

	e.DefaultGraphFmt = ds.FAttrs{
		"rankdir": "LR",
	}

	e.DefaultVertexFmt = ds.FAttrs{
		"style": "filled",
	}

	e.DefaultEdgeFmt = ds.FAttrs{
		"arrowhead": "open",
	}

	if i, ok := g.VertexIndex(pwag); ok {
		g.V[i].SetFmtAttr("shape", "square")
	}

	if v, e, ok := g.EdgeIndex(pwag, pwl); ok {
		g.V[v].E[e].SetFmtAttr("label", "Level 25")
	}

	if v, e, ok := g.EdgeIndex(pwl, pot); ok {
		g.V[v].E[e].SetFmtAttr("label", "Trade holding King's Rock")
	}

	if v, e, ok := g.EdgeIndex(pwl, pow); ok {
		g.V[v].E[e].SetFmtAttr("label", "Water Stone")
	}

	e.Export(g, os.Stdout)

}

Output:
strict digraph {
graph [ rankdir="LR" ]
node [ style="filled" ]
edge [ arrowhead="open" ]
"Poliwag (water)" [ shape="square" ]
"Poliwag (water)" -> "Poliwhirl (water)" [ label="Level 25" ]
"Poliwhirl (water)"
"Poliwhirl (water)" -> "Politoed (water)" [ label="Trade holding King's Rock" ]
"Poliwhirl (water)" -> "Poliwrath (water/fighting)" [ label="Water Stone" ]
"Politoed (water)"
"Poliwrath (water/fighting)"
}

func NewExporter

func NewExporter() *Exporter

NewExporter creates an initialized Exporter.

func (*Exporter) AddExtra

func (d *Exporter) AddExtra(s ...string)

AddExtra adds extra lines to the end of the DOT file, which is a feature needed by more complex visualizations that need to control more precisely how a graph is rendered, like adding invisible, structural edges, etc.

func (*Exporter) Export

func (d *Exporter) Export(g *ds.G, w io.Writer)

Export writes the data it has accumulated to an io.Writer.

func (*Exporter) VisitEdge

func (d *Exporter) VisitEdge(g ds.G, e ds.GE)

func (*Exporter) VisitGraphEnd

func (d *Exporter) VisitGraphEnd(ds.G)

func (*Exporter) VisitGraphStart

func (d *Exporter) VisitGraphStart(g ds.G)

func (*Exporter) VisitVertex

func (d *Exporter) VisitVertex(g ds.G, v ds.GV)

type GSCCViz

type GSCCViz struct {
	ThemedGraphViz

	// OnGSCCVertex is called for every vertex of the GSCC.
	OnGSCCVertex func(v int)
}

GSCCViz formats and exports a GSCC graph after it has been calculated. Its vertices are traversed, and hooks are provided so that custom formatting can be applied.

func NewGSCCViz

func NewGSCCViz(g *ds.G, t Theme) *GSCCViz

NewGSCCViz initializes a new GSCCViz with NOOP hooks.

func (*GSCCViz) Traverse

func (vi *GSCCViz) Traverse() error

Traverse iterates over the vertices of a GSCC graph, calling its hooks when appropriate.

type LightBreezeTheme

type LightBreezeTheme struct{}

func (LightBreezeTheme) SetEdgeFmt

func (t LightBreezeTheme) SetEdgeFmt(attrs ds.FAttrs)

func (LightBreezeTheme) SetGraphFmt

func (t LightBreezeTheme) SetGraphFmt(attrs ds.FAttrs)

func (LightBreezeTheme) SetVertexFmt

func (t LightBreezeTheme) SetVertexFmt(attrs ds.FAttrs)

type MSTViz

type MSTViz struct {
	ThemedGraphViz

	MST algo.MST

	// OnMSTEdge is called for any edge that is a part of an MST.
	OnMSTEdge func(int, int)
}

MSTViz formats and exports an undirected graph after the execution of any algorithm that builds a minimum spanning tree. The output of the algorithm is traversed, and hooks are provided so that custom formatting can be applied to the graph edges.

func NewMSTViz

func NewMSTViz(g *ds.G, mst algo.MST, t Theme) *MSTViz

NewMSTViz initializes a new MSTViz with NOOP hooks.

func (*MSTViz) Traverse

func (vi *MSTViz) Traverse() error

Traverse iterates over the results of any MST algorithm, calling its hooks when appropriate.

type SCCViz

type SCCViz struct {
	ThemedGraphViz

	SCCs []algo.SCC

	// OnSCCVertex is called for every vertex, along with the index of its SCC.
	OnSCCVertex func(int, int)

	// OnSCCEdge is called for any edge connecting vertices in the same SCC.
	OnSCCEdge func(int, int, int)

	// OnCrossSCCEdge is called for any edge connecting vertices in different SCCs.
	OnCrossSCCEdge func(int, int, int, int)
}

SCCViz formats and exports a directed graph after the execution of any algorithm that discovers strongly connected components. The output of the algorithm is traversed, and hooks are provided so that custom formatting can be applied to the graph, its vertices and edges.

func NewSCCViz

func NewSCCViz(g *ds.G, sccs []algo.SCC, t Theme) *SCCViz

NewSCCViz initializes a new SCCViz with NOOP hooks.

func (*SCCViz) Traverse

func (vi *SCCViz) Traverse() error

Traverse iterates over the results of any SCC algorithm, calling its hooks when appropriate.

type TSortViz

type TSortViz struct {
	ThemedGraphViz

	Order []int

	/*
		OnVertexRank is called for every vertex in the graph, along with the rank
		of the vertex in the final topological ordering of vertices.
	*/
	OnVertexRank func(int, int)

	/*
		OnOrderEdge is called for every edge that connects two contiguous vertices
		in the final topological ordering. Note that such an edge might not actually
		exist in the graph, which gives the caller the opportunity to either create
		it or take any other action.
	*/
	OnOrderEdge func(int, int, int, bool)
}

TSortViz formats and exports a directed graph after the execution of the Topological Sort algorithm. The output of the algorithm is traversed, and hooks are provided so that custom formatting can be applied to the graph, its vertices and edges.

func NewTSortViz

func NewTSortViz(g *ds.G, ord []int, t Theme) *TSortViz

NewTSortViz initializes a new TSortViz with NOOP hooks.

func (*TSortViz) Traverse

func (vi *TSortViz) Traverse() error

Traverse iterates over the results of a Topological Sort execution, calling its hooks when appropriate.

type Theme

type Theme interface {
	SetGraphFmt(ds.FAttrs)
	SetVertexFmt(ds.FAttrs)
	SetEdgeFmt(ds.FAttrs)
}

A Theme implementation is capable of setting default formatting for a graph, its vertices and edges.

type ThemedGraphViz

type ThemedGraphViz struct {
	Graph *ds.G
	Extra []string
	Theme Theme
}

ThemedGraphViz contains data that is useful for graph algorithm visualizations. When embedded, it also provides a good part of the AlgoViz interface for free.

func (*ThemedGraphViz) GetExtra

func (v *ThemedGraphViz) GetExtra() []string

func (*ThemedGraphViz) GetGraph

func (v *ThemedGraphViz) GetGraph() *ds.G

func (*ThemedGraphViz) GetTheme

func (v *ThemedGraphViz) GetTheme() Theme