graph

README

graph

A collection of simple graph data structures, used for academic purposes. More info on wiki or visual example

Nodes and edges can have values, so weighted graphs can be built using the same data structures.

AdjacencyList description

AdjacencyList is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs.

The graph is undirected with values on nodes and edges.

AdjacencyList implementation

Each node and edge can have a value interface{}.

Internally the data is stored as a map of maps map[*Node]map[*Node]interface{}.

AdjacencyListDirected

It is a AdjacencyList with 3 extra functions, that allow 1 direction edge control.

Documentation

Overview

Package graph contains a series of simple graph data structures, used for academic purposes.

Index

• type AdjacencyList
  • func (g *AdjacencyList) AddEdge(x, y *Node) error
  • func (g *AdjacencyList) AddNode(x ...*Node)
  • func (g *AdjacencyList) Adjacent(x, y *Node) (bool, error)
  • func (g *AdjacencyList) GetEdgeValue(x, y *Node) (interface{}, error)
  • func (g *AdjacencyList) GetNodeValue(x *Node) (interface{}, error)
  • func (g *AdjacencyList) LenNodes() int
  • func (g *AdjacencyList) Neighbours(x *Node) ([]*Node, error)
  • func (g *AdjacencyList) RemoveDirectedEdge(x, y *Node) error
  • func (g *AdjacencyList) RemoveEdge(x, y *Node) error
  • func (g *AdjacencyList) RemoveNode(x ...*Node)
  • func (g *AdjacencyList) SetDirectedEdgeValue(x, y *Node, v interface{}) error
  • func (g *AdjacencyList) SetEdgeValue(x, y *Node, v interface{}) error
  • func (g *AdjacencyList) SetNodeValue(x *Node, v interface{}) error
• type AdjacencyListDirected
  • func (g *AdjacencyListDirected) AddDirectedEdge(x, y *Node) error
• type Directed
• type Node
• type Undirected

Examples

• AdjacencyList

Types

type AdjacencyList

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

AdjacencyList is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs.

Example

g := AdjacencyList{}
//node values can be set at init
a, b, c, d := &Node{"A"}, &Node{"B"}, &Node{}, &Node{}

g.AddNode(a, b, c, d)
//node values can be set after init too
c.v = "C"
g.SetNodeValue(d, "D")
fmt.Println("#nodes=", g.LenNodes(), "a value=", a.v)

g.AddEdge(a, b)
g.AddEdge(a, c)
nOfA, _ := g.Neighbours(a)
fmt.Println("neighbours of A=", nOfA[0].v, nOfA[1].v)

bAndC, _ := g.Adjacent(b, c)
fmt.Println("B neighbour with C?", bAndC)

//add and Edge and set a value of it
g.SetEdgeValue(b, d, 42)
BD, _ := g.GetEdgeValue(b, d)
fmt.Println("edge value BD=", BD)

Output:

#nodes= 4 a value= A
neighbours of A= B C
B neighbour with C? false
edge value BD= 42

func (*AdjacencyList) AddEdge

func (g *AdjacencyList) AddEdge(x, y *Node) error

AddEdge Add a vertice between 2 nodes. if is a directed graph adds 2 edges (x->y and x<-y)

func (*AdjacencyList) AddNode

func (g *AdjacencyList) AddNode(x ...*Node)

AddNode Add a vertex, if doesn't exists already.

func (*AdjacencyList) Adjacent

func (g *AdjacencyList) Adjacent(x, y *Node) (bool, error)

Adjacent Check if two nodes are connected with an edge.

func (*AdjacencyList) GetEdgeValue

func (g *AdjacencyList) GetEdgeValue(x, y *Node) (interface{}, error)

GetEdgeValue Gets an edge value, if exists.

func (*AdjacencyList) GetNodeValue

func (g *AdjacencyList) GetNodeValue(x *Node) (interface{}, error)

GetNodeValue Returns the nodes value (alias x.v)

func (*AdjacencyList) LenNodes

func (g *AdjacencyList) LenNodes() int

LenNodes How many distinct nodes are in the graph.

func (*AdjacencyList) Neighbours

func (g *AdjacencyList) Neighbours(x *Node) ([]*Node, error)

Neighbours ...

func (*AdjacencyList) RemoveDirectedEdge

func (g *AdjacencyList) RemoveDirectedEdge(x, y *Node) error

RemoveDirectedEdge Remove the x->y vertice, if exists.

func (*AdjacencyList) RemoveEdge

func (g *AdjacencyList) RemoveEdge(x, y *Node) error

RemoveEdge Remove a vertice between two nodes if is a directed graph removes 2 edges (x->y and x<-y)

func (*AdjacencyList) RemoveNode

func (g *AdjacencyList) RemoveNode(x ...*Node)

RemoveNode Remove a vertex from the graph.

func (*AdjacencyList) SetDirectedEdgeValue

func (g *AdjacencyList) SetDirectedEdgeValue(x, y *Node, v interface{}) error

SetDirectedEdgeValue ...

func (*AdjacencyList) SetEdgeValue

func (g *AdjacencyList) SetEdgeValue(x, y *Node, v interface{}) error

SetEdgeValue Create or updates a vertice's value

func (*AdjacencyList) SetNodeValue

func (g *AdjacencyList) SetNodeValue(x *Node, v interface{}) error

SetNodeValue Set value of a node (alias a := Node{0.4})

type AdjacencyListDirected

type AdjacencyListDirected struct {
	AdjacencyList
}

AdjacencyListDirected Directed graphs

func (*AdjacencyListDirected) AddDirectedEdge

func (g *AdjacencyListDirected) AddDirectedEdge(x, y *Node) error

AddDirectedEdge Add the x->y vertice with default value.

type Directed

type Directed interface {
	Undirected
	AddDirectedEdge(x, y *Node) error
	RemoveDirectedEdge(x, y *Node) error
	SetDirectedEdgeValue(x, y *Node, v interface{}) error
}

Directed Common interface for all directed graph implementations

type Node

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

Node represent a vertex

type Undirected

type Undirected interface {
	Adjacent(x, y *Node) (bool, error)            // tests whether there is an edge from the vertex x to the vertex y;
	Neighbours(x *Node) ([]*Node, error)          //: lists all vertices y such that there is an edge from the vertex x to the vertex y;
	AddNode(x ...*Node)                           //: adds the vertex x, if it is not there;
	RemoveNode(x ...*Node)                        //: removes the vertex x, if it is there;
	AddEdge(x, y *Node) error                     //: adds the edge from the vertex x to the vertex y, if it is not there;
	RemoveEdge(x, y *Node) error                  //: removes the edge from the vertex x to the vertex y, if it is there;
	GetNodeValue(x *Node) (interface{}, error)    //: returns the value associated with the vertex x;
	SetNodeValue(x *Node, v interface{}) error    //: sets the value associated with the vertex x to v.
	GetEdgeValue(x, y *Node) (interface{}, error) //: returns the value associated with the edge (x, y);
	SetEdgeValue(x, y *Node, v interface{}) error //: sets the value associated with the edge (x, y) to v.
}

Undirected Common interface for all graph implementations