graphs

Documentation

Index

• Variables
• func TopologicalSort(g *Graph) (topologicalOrder *list.List, topologicalClasses map[string]int, err error)
• type Dot
  • func NewDotDiGraph() *Dot
  • func (g *Dot) AddDottedEdge(src, dest string) error
  • func (g *Dot) AddEdge(src, dest string) error
  • func (g *Dot) AddNode(name string) error
  • func (g *Dot) String() string
• type Edge
• type Graph
  • func NewDigraph() *Graph
  • func NewGraph() *Graph
  • func (g *Graph) AddEdge(v1, v2 string)
  • func (g *Graph) AddVertex(v string)
  • func (g *Graph) Dump()
  • func (g *Graph) EdgesIter() chan Edge
  • func (g *Graph) HalfedgesIter(v string) chan Halfedge
  • func (g *Graph) NEdges() int
  • func (g *Graph) NVertices() int
• type Halfedge
• type Set
  • func NewSet() *Set
  • func (s *Set) Add(element interface{}) bool
  • func (s *Set) Iter() chan interface{}
  • func (s *Set) Len() int

Variables

var ErrNoDAG = errors.New("graphs: graph is not a DAG")

Functions

func TopologicalSort

func TopologicalSort(g *Graph) (topologicalOrder *list.List, topologicalClasses map[string]int, err error)

Types

type Dot

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

func NewDotDiGraph

func NewDotDiGraph() *Dot

func (*Dot) AddDottedEdge

func (g *Dot) AddDottedEdge(src, dest string) error

func (*Dot) AddEdge

func (g *Dot) AddEdge(src, dest string) error

func (*Dot) AddNode

func (g *Dot) AddNode(name string) error

func (*Dot) String

func (g *Dot) String() string

type Edge

type Edge struct {
	Start string
	End   string
}

An Edge connects two vertices.

type Graph

type Graph struct {
	Adjacency map[string]*Set
	Directed  bool
}

A Graph is defined by its vertices and edges stored as an adjacency set.

func NewDigraph

func NewDigraph() *Graph

NewDigraph creates a new empty directed graph.

func NewGraph

func NewGraph() *Graph

NewGraph creates a new empty graph.

func (*Graph) AddEdge

func (g *Graph) AddEdge(v1, v2 string)

AddEdge adds an edge to the graph. The edge connects vertex v1 and vertex v2.

func (*Graph) AddVertex

func (g *Graph) AddVertex(v string)

AddVertex adds the given vertex to the graph.

func (*Graph) Dump

func (g *Graph) Dump()

Dump prints all edges with to stdout.

func (*Graph) EdgesIter

func (g *Graph) EdgesIter() chan Edge

EdgesIter returns a channel with all edges of the graph.

func (*Graph) HalfedgesIter

func (g *Graph) HalfedgesIter(v string) chan Halfedge

HalfedgesIter returns a channel with all halfedges for the given start vertex.

func (*Graph) NEdges

func (g *Graph) NEdges() int

NEdges returns the number of edges.

func (*Graph) NVertices

func (g *Graph) NVertices() int

NVertices returns the number of vertices.

type Halfedge

type Halfedge struct {
	End string
}

A Halfedge is an edge where just the end vertex is stored. The start vertex is inferred from the context.

type Set

type Set map[interface{}]struct{}

A Set is a container that contains each element just once.

func NewSet

func NewSet() *Set

NewSet creates a new empty set.

func (*Set) Add

func (s *Set) Add(element interface{}) bool

Add adds an element to the set. It returns true if the element has been added and false if the set already contained that element.

func (*Set) Iter

func (s *Set) Iter() chan interface{}

Iter returns a channel where all elements of the set are sent to.

func (*Set) Len

func (s *Set) Len() int

Len returns the number of elements.