graph

README

copy from https://github.com/gyuho/goraph/tree/master/graph

Documentation

Index

• type Data
  • func New() *Data
  • func (d *Data) AddNode(nd *Node) bool
  • func (d *Data) Clone() *Data
  • func (d *Data) Connect(src, dst *Node, weight float32)
  • func (d *Data) DeleteEdge(src, dst *Node)
  • func (d *Data) DeleteNode(nd *Node)
  • func (d *Data) GetEdgeWeight(src, dst *Node) float32
  • func (d *Data) GetEdges() []Edge
  • func (d *Data) GetNodeByID(id string) *Node
  • func (d *Data) GetNodeSize() int
  • func (d *Data) Init()
  • func (d *Data) String() string
  • func (d *Data) TopologicalDag() (Nodes, bool)
  • func (d *Data) UpdateEdgeWeight(src, dst *Node, weight float32)
• type Edge
• type Node
  • func NewNode(id string) *Node
  • func (nd *Node) String() string
• type Nodes
  • func (l Nodes) Get(id string) *Node

Types

type Data

type Data struct {
	sync.Mutex

	// NodeMap is a hash-map for all Nodes in the graph.
	NodeMap map[*Node]bool
	// contains filtered or unexported fields
}

Data contains graph data, represented in adjacency list and slice. Make sure to use Pointer when we need to update the struct with receiver. (https://golang.org/doc/faq#methods_on_values_or_pointers)

func New

func New() *Data

New returns a new Data.

func (*Data) AddNode

func (d *Data) AddNode(nd *Node) bool

AddNode adds a Node to a graph Data. It returns true if the Node is added the graph Data.

func (*Data) Clone

func (d *Data) Clone() *Data

Clone clones(deep copy) the graph Data. (changing the cloned Data would not affect the original Data.) It traverses every single node with depth-first-search.

func (*Data) Connect

func (d *Data) Connect(src, dst *Node, weight float32)

Connect adds an edge from src(source) to dst(destination) Node, to a graph Data. This doese not connect from dst to src.

func (*Data) DeleteEdge

func (d *Data) DeleteEdge(src, dst *Node)

DeleteEdge deletes an Edge from src to dst from the graph Data. This does not delete Nodes.

func (*Data) DeleteNode

func (d *Data) DeleteNode(nd *Node)

DeleteNode deletes a Node from the graph Data. This deletes all the related edges too.

func (*Data) GetEdgeWeight

func (d *Data) GetEdgeWeight(src, dst *Node) float32

GetEdgeWeight returns the weight value of an edge from src to dst Node.

func (*Data) GetEdges

func (d *Data) GetEdges() []Edge

GetEdges returns all edges of a graph.

func (*Data) GetNodeByID

func (d *Data) GetNodeByID(id string) *Node

GetNodeByID finds a Node by ID.

func (*Data) GetNodeSize

func (d *Data) GetNodeSize() int

GetNodeSize returns the size of Node of the graph Data.

func (*Data) Init

func (d *Data) Init()

Init initializes the graph Data.

func (*Data) String

func (d *Data) String() string

String describes the graph Data.

func (*Data) TopologicalDag

func (d *Data) TopologicalDag() (Nodes, bool)

TopologicalDag does topological sort(ordering) with DFS. It returns true if the Graph is a DAG. (no cycle, have a topological sort) It returns false if the Graph is not a DAG. (cycle, have no topological sort) (http://en.wikipedia.org/wiki/Topological_sorting)

1  L ← Empty list that will contain the sorted nodes
2  while there are unmarked nodes do
3      select an unmarked node n
4      visit(n)
5
6  function visit(node n)
7      if n has a temporary mark then stop (not a DAG)
8      if n is not marked (i.e. has not been visited yet) then
9          mark n temporarily
10          for each node m with an edge from n to m do
11              visit(m)
12          mark n permanently
13          add n to head of L

func (*Data) UpdateEdgeWeight

func (d *Data) UpdateEdgeWeight(src, dst *Node, weight float32)

UpdateEdgeWeight overwrites the edge weight from src to dst Node.

type Edge

type Edge struct {
	Src    *Node
	Dst    *Node
	Weight float32
}

Edge connects from Src to Dst with weight.

type Node

type Node struct {

	// ID of Node is assumed to be unique among Nodes.
	ID string

	// Color is used for graph traversal.
	Color string

	sync.Mutex

	// WeightTo maps its Node to outgoing Nodes with its edge weight (outgoing edges from its Node).
	WeightTo map[*Node]float32

	// WeightFrom maps its Node to incoming Nodes with its edge weight (incoming edges to its Node).
	WeightFrom map[*Node]float32
}

Node is a Node(node) in Graph.

func NewNode

func NewNode(id string) *Node

NewNode returns a new Node.

func (*Node) String

func (nd *Node) String() string

String describes Node.

type Nodes

type Nodes []*Node

func (Nodes) Get

func (l Nodes) Get(id string) *Node