graph

package module
v0.0.0-...-057c198 Latest Latest
Warning

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

 Go to latest Published: Mar 17, 2015 License: BSD-3-Clause Imports: 5 Imported by: 12

Documentation

Overview

Package graph implements graph manipulation functions.

Index

Constants

This section is empty.

Variables

View Source 
var (
	NodeExists       = errors.New("graph: node exists")
	NodeDoesNotExist = errors.New("graph: node does not exist")
	NodeIDOutOfRange = errors.New("graph: node id out of range")
	EdgeDoesNotExist = errors.New("graph: edge does not exist")
)
View Source 
var SelectorEmpty = fmt.Errorf("graph: selector empty")

SelectorEmpty is returned when an attempt is made to select an item from a Selector with no remaining selectable items.

Functions

This section is empty.

Types

type BreadthFirst 

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

BreadthFirst is a type that can perform a breadth-first search on a graph.

func NewBreadthFirst 

func NewBreadthFirst() *BreadthFirst

NewBreadthFirst creates a new BreadthFirst searcher.

func (*BreadthFirst) Reset 

func (b *BreadthFirst) Reset()

Reset clears the search queue and visited list.

func (*BreadthFirst) Search 

func (b *BreadthFirst) Search(s Node, ef EdgeFilter, nf NodeFilter, vo Visit) Node

Search searches a graph starting from node s until the NodeFilter function nf returns a value of true, traversing edges in the graph that allow the Edgefilter function ef to return true. On success the terminating node, t is returned. If vo is not nil, it is called with the start and end nodes of an edge when the end node has not already been visited.

func (*BreadthFirst) Visited 

func (b *BreadthFirst) Visited(n Node) bool

Visited returns whether the node n has been visited by the searcher.

type DepthFirst 

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

DepthFirst is a type that can perform a depth-first search on a graph.

func NewDepthFirst 

func NewDepthFirst() *DepthFirst

NewDepthFirst creates a new DepthFirst searcher.

func (*DepthFirst) Reset 

func (d *DepthFirst) Reset()

Reset clears the search stack and visited list.

func (*DepthFirst) Search 

func (d *DepthFirst) Search(s Node, ef EdgeFilter, nf NodeFilter, vo Visit) Node

Search searches a graph starting from node s until the NodeFilter function nf returns a value of true, traversing edges in the graph that allow the Edgefilter function ef to return true. On success the terminating node, t is returned. If vo is not nil, it is called with the start and end nodes of an edge when the end node has not already been visited.

func (*DepthFirst) Visited 

func (d *DepthFirst) Visited(n Node) bool

Visited returns whether the node n has been visited by the searcher.

type Edge 

type Edge interface {
	ID() int
	Weight() float64
	Nodes() (u, v Node)
	Head() Node
	Tail() Node
	// contains filtered or unexported methods
}

func NewEdge 

func NewEdge() Edge

NewEdge returns a new Edge.

func RandMinCut 

func RandMinCut(g *Undirected, iter int) (c []Edge, w float64)

func RandMinCutPar 

func RandMinCutPar(g *Undirected, iter, threads int) (c []Edge, w float64)

type EdgeFilter 

type EdgeFilter func(Edge) bool

EdgeFilter is a function type used for assessment of edges during graph traversal.

type Edges 

type Edges []Edge

Edges is a collection of edges used for internal representation of edge lists in a graph.

type Hop 

type Hop struct {
	Edge Edge
	Node Node
}

A Hop is an edge/node pair where the edge leads to the node from a neighbor.

type Node 

type Node interface {
	ID() int
	Edges() []Edge
	Degree() int
	Neighbors(EdgeFilter) []Node
	Hops(EdgeFilter) []*Hop
	// contains filtered or unexported methods
}

type NodeFilter 

type NodeFilter func(Node) bool

NodeFilter is a function type used for assessment of nodes during graph traversal.

type Nodes 

type Nodes []Node

Nodes is a collection of nodes.

func ConnectedComponents 

func ConnectedComponents(g *Undirected, ef EdgeFilter) []Nodes

ConnectedComponents returns a slice of slices of nodes. Each top level slice is the set of nodes composing a connected component of the graph. Connection is determined by traversal of edges that satisfy the edge filter ef.

func (Nodes) BuildUndirected 

func (ns Nodes) BuildUndirected(compact bool) (*Undirected, error)

BuildUndirected creates a new Undirected graph using nodes and edges specified by the set of nodes in the receiver. If edges of nodes in the receiver connect to nodes that are not, these extra nodes will be included in the resulting graph. If compact is set to true, edge IDs are chosen to minimize space consumption, but breaking edge ID consistency between the new graph and the original.

type Selector 

type Selector []WeightedItem

A Selector is a collection of weighted items that can be selected with weighted probabilities without replacement.

func (Selector) Init 

func (s Selector) Init()

Init must be called on a Selector before it is selected from. Init is idempotent.

func (Selector) Select 

func (s Selector) Select() (int, error)

Select returns the value of the Index field of the chosen WeightedItem and the item is weighted zero to prevent further selection.

func (Selector) Weight 

func (s Selector) Weight(i int, w float64)

Weight alters the weight of item i in the Selector.

type Undirected 

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

An Undirected is a container for an undirected graph representation.

func NewUndirected 

func NewUndirected() *Undirected

NewUndirected creates a new empty Undirected graph.

func (*Undirected) Add 

func (g *Undirected) Add(n Node) error

Add adds a node n to the graph. If a node with already exists in the graph with the same id an error NodeExists is returned.

func (*Undirected) AddID 

func (g *Undirected) AddID(id int) (Node, error)

AddID adds a node with a specified ID. If a node with this ID already exists, it is returned with an error NodeExists.

func (*Undirected) Connect 

func (g *Undirected) Connect(u, v Node) (Edge, error)

Connect creates a new edge joining nodes u and v with weight w. The new edge is returned on success. An error is returned if either of the nodes does not exist.

func (*Undirected) ConnectByID 

func (g *Undirected) ConnectByID(uid, vid int) (int, error)

Connect creates a new edge joining nodes with IDs uid and vid with weight w, and specifying edge flags f. The id of the new edge is returned on success. An error is returned if either of the nodes does not exist.

func (*Undirected) ConnectWith 

func (g *Undirected) ConnectWith(u, v Node, with Edge) error

ConnectWith join nodes u and v with the provided edge. An error is returned if either of the nodes does not exist.

func (*Undirected) Connected 

func (g *Undirected) Connected(u, v Node) (bool, error)

Connected returns a boolean indicating whether the nodes u and v share an edge. An error is returned if either of the nodes does not exist.

func (*Undirected) ConnectingEdges 

func (g *Undirected) ConnectingEdges(u, v Node) ([]Edge, error)

ConnectingEdges returns a slice of edges that are shared by nodes u and v. An error is returned if either of the nodes does not exist.

func (*Undirected) Delete 

func (g *Undirected) Delete(n Node) error

Delete deletes the node n from the graph. If the specified node does not exist an error, NodeDoesNotExist is returned.

func (*Undirected) DeleteByID 

func (g *Undirected) DeleteByID(id int) error

DeleteByID deletes the node with the specified from the graph. If the specified node does not exist an error, NodeDoesNotExist is returned.

func (*Undirected) DeleteEdge 

func (g *Undirected) DeleteEdge(e Edge) error

DeleteEdge deleted the edge e from the graph. An error is returned if the edge does not exist in the graph.

func (*Undirected) Edge 

func (g *Undirected) Edge(id int) Edge

Edge returns the edge with the specified ID.

func (*Undirected) Edges 

func (g *Undirected) Edges() []Edge

Edges returns the complete set of edges in the graph.

func (*Undirected) Has 

func (g *Undirected) Has(n Node) (bool, error)

Has returns a boolean indicating whether the node n exists in the graph. If the ID of n is no in [0, NextNodeID()) an error, NodeIDOutOfRange is returned.

func (*Undirected) HasNodeID 

func (g *Undirected) HasNodeID(id int) (bool, error)

HasNodeID returns a boolean indicating whether a node with ID is exists in the graph. If ID is no in [0, NextNodeID()) an error, NodeIDOutOfRange is returned.

func (*Undirected) Merge 

func (g *Undirected) Merge(dst, src Node) error

Merge merges the node src into the node dst, transfering all the edges of src to dst. The node src is then deleted. If either src or dst do not exist in the graph, an appropriate error is returned.

func (*Undirected) Neighbors 

func (g *Undirected) Neighbors(n Node, ef EdgeFilter) ([]Node, error)

Neighbours returns a slice of nodes that are reachable from the node n via edges that satisfy the criteria specified by the edge filter ef. If the node does not exist, an error NodeDoesNotExist or NodeIDOutOfRange is returned.

func (*Undirected) NewNode 

func (g *Undirected) NewNode() Node

func (*Undirected) NextEdgeID 

func (g *Undirected) NextEdgeID() int

NextEdgeID returns the next unused available edge ID.

func (*Undirected) NextNodeID 

func (g *Undirected) NextNodeID() int

NextNodeID returns the next unused available node ID. Unused IDs may be available for nodes with ID in [0, NextNodeID()) from deletion of nodes.

func (*Undirected) Node 

func (g *Undirected) Node(id int) Node

Node returns the node with the specified ID.

func (*Undirected) Nodes 

func (g *Undirected) Nodes() Nodes

Nodes returns the complete set of nodes in the graph.

func (*Undirected) Order 

func (g *Undirected) Order() int

Order returns the number of nodes in the graph.

func (*Undirected) Size 

func (g *Undirected) Size() int

Size returns the number of edges in the graph.

func (*Undirected) String 

func (g *Undirected) String() string

type Visit 

type Visit func(u, v Node)

Visit is a function type that is used by a BreadthFirst or DepthFirst to allow side-effects on visiting new nodes in a graph traversal.

type WeightedItem 

type WeightedItem struct {
	Index  int
	Weight float64
	// contains filtered or unexported fields
}

A WeightedItem is a type that can be be selected from a population with a defined probability specified by the field Weight. Index is used as an index to the actual item in another slice.

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.