ds

package
v0.1.1 Latest Latest
Warning

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

 Go to latest Published: Jul 25, 2022 License: MIT Imports: 5 Imported by: 0

Documentation

Overview

Package ds provides implementations for data structures, like graphs. Any assertions regarding asymptotic behavior assume the worst-case scenario.

Index

Examples

Constants

This section is empty.

Variables

View Source 
var ErrDirected = WrapErr(ErrUndefOp, "directed graph")
View Source 
var ErrDisconnected = WrapErr(ErrUndefOp, "disconnected graph")
View Source 
var ErrDoesNotExist = errors.New("does not exist")
View Source 
var ErrExists = errors.New("already exists")
View Source 
var ErrInvLoop = errors.New("invalid loop")
View Source 
var ErrInvType = errors.New("invalid type")
View Source 
var ErrNilArg = errors.New("nil argument")
View Source 
var ErrNoEdge = WrapErr(ErrDoesNotExist, "edge")
View Source 
var ErrNoRevEdge = WrapErr(ErrDoesNotExist, "reverse edge")
View Source 
var ErrNoVtx = WrapErr(ErrDoesNotExist, "vertex")
View Source 
var ErrUndefOp = errors.New("undefined operation")
View Source 
var ErrUndirected = WrapErr(ErrUndefOp, "undirected graph")

Functions

func Cut added in v0.1.0 

func Cut[T any](s *[]T, idx int)

Cut removes an element from a slice at a given position. Memory leaks are avoided by assigning the zero value for the type of the element to the position that is going to be removed.

Source: https://github.com/golang/go/wiki/SliceTricks

func WrapErr added in v0.0.11 

func WrapErr(err error, msg string) error

WrapErr wraps an error using the fmt.Errorf function.

Types

type ByEdgeWeight added in v0.0.11 

type ByEdgeWeight []GE

ByEdgeWeight implements the sort.Interface, enabling the sorting of a list of graph edges in order of non-decreasing edge weights.

func (ByEdgeWeight) Len added in v0.0.11 

func (b ByEdgeWeight) Len() int

func (ByEdgeWeight) Less added in v0.0.11 

func (b ByEdgeWeight) Less(i, j int) bool

func (ByEdgeWeight) Swap added in v0.0.11 

func (b ByEdgeWeight) Swap(i, j int)

type DSet added in v0.0.10 

type DSet[T comparable] interface {
	/*
		MakeSet creates a new disjoint set containing a single element.
	*/
	MakeSet(x T)

	/*
		FindSet, given an element, finds the representative element of the disjoint set
		that contains the original element; a behavior that can be used to test if two
		elements belong to the same set: if so, they should have the same representative.
	*/
	FindSet(x T) T

	/*
		Union merges the disjoint sets containing the given elements, creating a new set.
	*/
	Union(x, y T)
}

DSet implementations are able to behave like a Disjoint-Set data structure, storing and operating on a collection of disjoint sets.

func NewDSet added in v0.0.10 

func NewDSet[T comparable]() DSet[T]

NewDSet returns a new DSet, using a Disjoint-Set Forest implementation.

type DSetForest added in v0.0.10 

type DSetForest[T comparable] map[T]*dsfNode[T]

DSetForest is a Disjoint-Set Forest implementation for the DSet interface, using both the union-by-rank and path compression heuristics. Due to these heuristics, a sequence of m operations on a DSetForest - with n of them being calls to MakeSet - has a total amortized running time of O(m α(n)).

The function α(n) is the inverse of the Ackermann function, and grows extremely slowly, with α(n) == 4 for pretty much any practical value of n, which makes O(m α(n)) asymptotically superlinear, ω(m), but close to linear in practice.

func (DSetForest[T]) FindSet added in v0.0.10 

func (f DSetForest[T]) FindSet(x T) T

func (DSetForest[T]) MakeSet added in v0.0.10 

func (f DSetForest[T]) MakeSet(x T)

func (DSetForest[T]) Union added in v0.0.10 

func (f DSetForest[T]) Union(x, y T)

type ErrInvalidSer added in v0.0.5 

type ErrInvalidSer struct {
	Reason error
}

ErrInvalidSer represents an error that happened during the parsing of a serialized graph.

func (ErrInvalidSer) Error added in v0.0.5 

func (e ErrInvalidSer) Error() string

func (ErrInvalidSer) Unwrap added in v0.0.5 

func (e ErrInvalidSer) Unwrap() error

type FAttrs added in v0.0.10 

type FAttrs map[string]string

FAttrs holds flat formatting attributes for any type of item in a gga data structure.

type Formattable 

type Formattable struct {
	F FAttrs
}

A Formattable holds formatting attributes, and can accept them.

func (*Formattable) AppendFmtAttr added in v0.0.6 

func (f *Formattable) AppendFmtAttr(k, v string)

AppendFmtAttr appends a new value to an existing formatting attribute. If the attribute hasn't been set yet, it is then set using the value.

func (*Formattable) ResetFmt added in v0.0.4 

func (f *Formattable) ResetFmt()

ResetFmt resets the current formatting attributes, if any.

func (*Formattable) SetFmtAttr 

func (f *Formattable) SetFmtAttr(k, v string)

SetFmtAttr records the formatting (attribute, value) pair.

type G added in v0.0.10 

type G struct {
	/*
		V is the list of vertices in the graph, ordered by vertex insertion time,
		an ordering that is respected during any internal traversals.
	*/
	V []GV
	// contains filtered or unexported fields
}

G implements a directed or undirected graph G = (V, E), using adjacency lists to achieve linear space complexity: Θ(V + E).

Due to the nature of adjacency lists, checking whether an edge (u, v) exists has O(E) time complexity. For applications that make heavy use of this operation, an adjacency matrix would be a better fit (O(1) time complexity), with the trade-off being a worse space complexity of Θ(V²).

Example (Directed) 
si := Text("initialization")
sm := Text("maintenance")
st := Text("termination")
u1 := Text("unrelated1")
u2 := Text("unrelated2")

g := NewDigraph()

g.AddVertex(&si)
g.AddVertex(&sm)
g.AddVertex(&st)
g.AddVertex(&u1)
g.AddVertex(&u2)

g.AddEdge(&si, &sm, 0)
g.AddEdge(&sm, &sm, 0)
g.AddEdge(&sm, &st, 0)

fmt.Println(g.VertexCount())

fmt.Println(g.EdgeCount())

Output:

5
3
Example (Undirected) 
wt := Text("Whiterun")
dt := Text("Dawnstar")
mt := Text("Markarth")
rt := Text("Riften")

g := NewGraph()

g.AddVertex(&wt)
g.AddVertex(&dt)
g.AddVertex(&mt)
g.AddVertex(&rt)

g.AddEdge(&wt, &dt, 0)
g.AddEdge(&dt, &wt, 0)

g.AddEdge(&wt, &mt, 0)
g.AddEdge(&mt, &wt, 0)

g.AddEdge(&dt, &mt, 0)
g.AddEdge(&mt, &dt, 0)

fmt.Println(g.VertexCount())

fmt.Println(g.EdgeCount())

Output:

4
6

func NewDigraph added in v0.1.0 

func NewDigraph() *G

NewDigraph creates a new directed graph.

func NewGraph added in v0.1.0 

func NewGraph() *G

NewGraph creates a new undirected graph.

func Parse added in v0.0.10 

func Parse(s string) (*G, func(string) int, error)

Parse is a shorthand for creating a new TextParser and then using it to parse the input.

func Transpose added in v0.1.0 

func Transpose(g *G) (*G, error)

Transpose creates a transpose graph for a directed graph, where all original edges are reversed.

func (G) Accept added in v0.0.10 

func (g G) Accept(vis GraphVisitor)

Accept accepts a graph visitor, and guides its execution using double-dispatching.

func (*G) AddEdge added in v0.1.0 

func (g *G) AddEdge(src Item, dst Item, wt float64) (int, int, error)

AddEdge adds a new weighted edge between the given Items, but only if their vertices have already been added.

func (*G) AddVertex added in v0.0.10 

func (g *G) AddVertex(i Item) (int, error)

AddVertex adds a new vertex to the graph, associated with the given Item.

func (*G) Directed added in v0.0.10 

func (g *G) Directed() bool

Directed checks whether or not the graph is directed.

func (*G) EdgeCount added in v0.0.10 

func (g *G) EdgeCount() int

EdgeCount calculates the size of the set of edges, |E|, in O(1) time.

func (*G) EdgeIndex added in v0.1.0 

func (g *G) EdgeIndex(src Item, dst Item) (int, int, bool)

EdgeIndex retrieves the index(es) of the edge associated with the given Items.

func (*G) RemoveEdge added in v0.0.10 

func (g *G) RemoveEdge(src Item, dst Item) error

RemoveEdge removes the edge associated with the given Items.

func (*G) RemoveVertex added in v0.0.10 

func (g *G) RemoveVertex(i Item) error

RemoveVertex removes the vertex associated with the given Item, along with any edges incident on it.

func (*G) String added in v0.1.0 

func (g *G) String() string

func (*G) Undirected added in v0.0.10 

func (g *G) Undirected() bool

Undirected checks whether or not the graph is undirected.

func (*G) VertexCount added in v0.0.10 

func (g *G) VertexCount() int

VertexCount calculates the size of the set of vertices, |V|, in O(1) time.

func (*G) VertexIndex added in v0.1.0 

func (g *G) VertexIndex(i Item) (int, bool)

VertexIndex retrieves the index of the vertex associated with the given Item.

type GE added in v0.0.10 

type GE struct {
	Formattable

	/*
		Src is the id of the vertex at the source / tail of the edge.
		This edge contributes to the out-degree of that vertex.
	*/
	Src int

	/*
		Dst is the id of the vertex at the destination / head of the edge.
		This edge contributes to the in-degree of that vertex.
	*/
	Dst int

	// Wt is the weight/cost associated with the edge.
	Wt float64

	/*
		Index is the position of this edge in Src's adjacency list.
		This information is useful when passing around copies of the edge.
	*/
	Index int
}

A GE represents an edge in a graph, which is a connection between two vertices, with an optional weight. The directed/undirected nature of the edge is given by the graph that owns it.

func (*GE) String added in v0.0.11 

func (e *GE) String() string

type GV added in v0.0.10 

type GV struct {
	Formattable

	// Item is the satellite data of the vertex, coming along with it wherever it goes.
	Item Item

	// Index is the index of the vertex in the list of vertices of the graph.
	Index int

	// E is the adjacency list for the vertex, listing all edges that the vertex as their source.
	E []GE
}

A GV represents a vertex in a graph.

func (*GV) Label added in v0.0.10 

func (v *GV) Label() string

func (*GV) String added in v0.0.11 

func (v *GV) String() string

type GraphVisitor 

type GraphVisitor interface {
	// VisitGraphStart is called at the beginning of the graph visit.
	VisitGraphStart(g G)

	// VisitGraphEnd is called at the end of the graph visit.
	VisitGraphEnd(g G)

	// VisitVertex is called when visiting a graph vertex.
	VisitVertex(g G, v GV)

	// VisitEdge is called when visiting a graph edge.
	VisitEdge(g G, e GE)
}

A GraphVisitor implements the Visitor pattern (https://en.wikipedia.org/wiki/Visitor_pattern) for gga graphs. A Visitor declares methods that are executed at specific points during the traversal of a data structure. This way, multiple behaviors can be attached to the data structure without having to modify it directly.

Example 
package main

import "fmt"

type person struct {
	Name string
}

func (p person) Label() string {
	return p.Name
}

type ConsoleVisitor struct{}

func (cv *ConsoleVisitor) VisitGraphStart(G) {
	fmt.Println("graph start")
}

func (cv *ConsoleVisitor) VisitGraphEnd(G) {
	fmt.Println("graph end")
}

func (cv *ConsoleVisitor) VisitVertex(g G, v GV) {
	fmt.Println("vertex", v.Label())
}

func (cv *ConsoleVisitor) VisitEdge(g G, e GE) {
	fmt.Println(
		"edge,",
		g.V[e.Src].Label(),
		"to",
		g.V[e.Dst].Label(),
	)
}

func main() {
	john := &person{"John"}
	jane := &person{"Jane"}
	jonas := &person{"Jonas"}

	g := NewDigraph()

	g.AddVertex(john)
	g.AddVertex(jane)
	g.AddVertex(jonas)

	g.AddEdge(john, jane, 0)
	g.AddEdge(jane, john, 0)
	g.AddEdge(jane, jane, 0)

	g.Accept(&ConsoleVisitor{})

}

Output:

graph start
vertex John
edge, John to Jane
vertex Jane
edge, Jane to John
edge, Jane to Jane
vertex Jonas
graph end

type Group added in v0.0.10 

type Group struct {
	Items []Item
	Id    int
}

Group groups items of a type that implements the Item interface, and also implements the Item interface itself, using an id assigned during the creation of the Group, so data structures that can hold Item implementations can also hold Group values.

Such a capability is useful for some algorithms that group items together and then create a new data structure that holds the groups as new elements (e.g.: GSCC).

func (Group) Label added in v0.0.10 

func (z Group) Label() string

type Item 

type Item interface {
	Label() string
}

An Item implementation can be used as satellite data for an item in a gga data structure. The main feature of an Item is being able to provide a label for easy identification. Some use cases would be logging and the generation of data visualizations using tools like Graphviz.

type LLQueue added in v0.0.2 

type LLQueue[T any] struct {
	list.List
}

LLQueue implements the Queue interface using a linked list.

func (*LLQueue[T]) Dequeue added in v0.0.2 

func (d *LLQueue[T]) Dequeue() (T, bool)

func (*LLQueue[T]) Empty added in v0.0.2 

func (d *LLQueue[T]) Empty() bool

func (*LLQueue[T]) Enqueue added in v0.0.2 

func (d *LLQueue[T]) Enqueue(ts ...T)

type Queue added in v0.0.2 

type Queue[T any] interface {
	// Enqueue adds an item to the end of the queue.
	Enqueue(...T)

	// Dequeue removes and then returns the item at the start of the queue, if any.
	Dequeue() (T, bool)

	// Empty checks if the queue is empty.
	Empty() bool
}

Queue implementations are able to behave like a FIFO (First In / First Out) queue.

func NewQueue added in v0.0.8 

func NewQueue[T any]() Queue[T]

NewQueue returns a new Queue, using an LLQueue implementation.

type SliceStack added in v0.0.2 

type SliceStack[T any] []T

SliceStack implements the Stack interface using a slice.

func (SliceStack[T]) Empty added in v0.0.2 

func (s SliceStack[T]) Empty() bool

func (SliceStack[T]) Peek added in v0.0.2 

func (s SliceStack[T]) Peek() (T, bool)

func (*SliceStack[T]) Pop added in v0.0.2 

func (s *SliceStack[T]) Pop() (T, bool)

func (*SliceStack[T]) Push added in v0.0.2 

func (s *SliceStack[T]) Push(ts ...T)

type Stack added in v0.0.2 

type Stack[T any] interface {
	// Push adds an item at the top of the stack.
	Push(...T)

	// Peek returns the item at the top of the stack, if any.
	Peek() (T, bool)

	// Pop removes and then returns the item at the top of the stack, if any.
	Pop() (T, bool)

	// Empty checks if the stack is empty.
	Empty() bool
}

Stack implementations are able to behave like a LIFO (Last In / First Out) stack.

func NewStack added in v0.0.8 

func NewStack[T any]() Stack[T]

NewStack returns a new Stack, using a SliceStack implementation.

type Text added in v0.0.5 

type Text string

Text trivially implements the ds.Item interface, and it is meant for both basic graphs where only strings are manipulated as vertices, and for unit testing in all packages of this module.

func (Text) Label added in v0.0.5 

func (t Text) Label() string

type TextParser added in v0.0.5 

type TextParser struct {
	// contains filtered or unexported fields
}

TextParser produces a new graph from text in the following grammar: 

Graph = GraphType ["\n" AdjEntries]
GraphType = "graph" | "digraph"
AdjEntries = AdjEntry {"\n" AdjEntry}
AdjEntry = Vertex "#" [EdgeList]
Vertex = all characters but "#", "\n", ":", ","
EdgeList = Edge {"," Edge}
Edge = Vertex [":" Weight]
Weight = float

Sample (Undirected): 

graph
a#b:4,h:8
b#a:4,c:8,h:11
c#b:8,d:7,i:2,f:4
d#c:7,e:9,f:14
e#d:9,f:10
f#c:4,d:14,e:10,g:2
g#f:2,h:1,i:6
h#a:8,b:11,g:1,i:7
i#c:2,g:6,h:7

Sample (Directed) 

digraph
1#2,4
2#5
3#5,6
4#2
5#4
6#6

func (*TextParser) Parse added in v0.0.5 

func (p *TextParser) Parse(s string) (*G, func(string) int, error)

Parse parses the input string, generating a new graph.

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.