graph

README

Graph

Source: Wikipedia

A graph data structure consists of a finite (and possibly mutable) set of vertices (also called nodes or points), together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges (also called links or lines), and for a directed graph are also known as arrows. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.

A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

Operation on Graphs

The basic operations provided by a graph data structure G usually include:

• adjacent(G, x, y): tests whether there is an edge from the vertex x to the vertex y;
• neighbors(G, x): lists all vertices y such that there is an edge from the vertex x to the vertex y;
• add_vertex(G, x): adds the vertex x, if it is not there;
• remove_vertex(G, x): removes the vertex x, if it is there;
• add_edge(G, x, y): adds the edge from the vertex x to the vertex y, if it is not there;
• remove_edge(G, x, y): removes the edge from the vertex x to the vertex y, if it is there;
• get_vertex_value(G, x): returns the value associated with the vertex x;
• set_vertex_value(G, x, v): sets the value associated with the vertex x to v.

Structures that associate values to the edges usually also provide:

• get_edge_value(G, x, y): returns the value associated with the edge (x, y);
• set_edge_value(G, x, y, v): sets the value associated with the edge (x, y) to v.

Graph example

Documentation

Index

• type Edge
  • func (e *Edge) String() string
• type Graph
  • func (g *Graph) AddEdge(x, y *Node) error
  • func (g *Graph) AddNode(node *Node) error
  • func (g *Graph) Adjancent(x *Node, y *Node) bool
  • func (g *Graph) GetEdgeValue(x *Node, y *Node) int
  • func (g *Graph) GetNodeValue(x *Node) string
  • func (g *Graph) Neighbors(node *Node) ([]*Node, bool)
  • func (g *Graph) RemoveEdge(x, y *Node) error
  • func (g *Graph) RemoveNode(node *Node) bool
  • func (g *Graph) SetEdgeValue(x, y *Node, value int) bool
  • func (g *Graph) SetNodeValue(x *Node, value string)
  • func (g *Graph) String()
• type Node
  • func (n *Node) String() string

Types

type Edge

type Edge struct {
	Cost   int
	ToNode *Node
}

Edge represents a link between two nodes (vertices) the Cost field is the weight between nodes, distance etc the ToNode field is the other end of the link (as the Edges map key is the first end)

func (*Edge) String

func (e *Edge) String() string

to be able to print the Edge

type Graph

type Graph struct {
	Nodes []*Node
	Edges map[*Node][]*Edge
}

Graph represents the graph structure, which has the list of Nodes and the Edges(links) between the Nodes

func (*Graph) AddEdge

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

AddEdge : adds the edge from the node x to the node y, if it is not there;

func (*Graph) AddNode

func (g *Graph) AddNode(node *Node) error

AddNode : adds a node if it's not there;

func (*Graph) Adjancent

func (g *Graph) Adjancent(x *Node, y *Node) bool

Adjancent : tests whether there is an edge from the node x to the node y;

func (*Graph) GetEdgeValue

func (g *Graph) GetEdgeValue(x *Node, y *Node) int

GetEdgeValue : returns the value associated with the edge (x, y);

func (*Graph) GetNodeValue

func (g *Graph) GetNodeValue(x *Node) string

GetNodeValue : returns the value associated with the node x;

func (*Graph) Neighbors

func (g *Graph) Neighbors(node *Node) ([]*Node, bool)

Neighbors : lists all nodes y such that there is an edge from the node x to the node y;

func (*Graph) RemoveEdge

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

RemoveEdge : removes the edge from the node x to the node y, if it is there;

func (*Graph) RemoveNode

func (g *Graph) RemoveNode(node *Node) bool

RemoveNode : removes the node by ID, if it is there;

func (*Graph) SetEdgeValue

func (g *Graph) SetEdgeValue(x, y *Node, value int) bool

SetEdgeValue : sets the value associated with the edge (x, y) to v.

func (*Graph) SetNodeValue

func (g *Graph) SetNodeValue(x *Node, value string)

SetNodeValue : sets the value associated with the node x to v.

func (*Graph) String

func (g *Graph) String()

to be able to print the graph

type Node

type Node struct {
	Value string
}

Node represents a Graph Node (vertex) where Value is a discretionary value associated to the node

func (*Node) String

func (n *Node) String() string

to be able to print the Node