network

Documentation

Index

• type Graph
  • func NewGraph() *Graph
  • func (g *Graph) BFS(startNodeID int64, until func(n graph.Node, depth int) bool) graph.Node
  • func (g *Graph) DFS(startNodeID int64, until func(n graph.Node) bool) graph.Node
• type Network
  • func NewNetwork() Network
  • func (n *Network) Add(id int64) error
  • func (n *Network) CheckReachability(src, dst int64) (bool, error)
  • func (n *Network) Connect(srcID, dstID int64, duration float64) error
  • func (n *Network) Get(elementID int64) (nodeID int64, ok bool)
  • func (n *Network) ValidatePath(p []int64) (valid bool, reason error)

Types

type Graph

type Graph struct {
	*simple.WeightedDirectedGraph
}

Graph is always a weighted directed graph

func NewGraph

func NewGraph() *Graph

NewGraph must be used to initialize a graph. self pointing edges (loops) are not allowed and considered with infinite weight. The weight of a non existent edge is infinite.

func (*Graph) BFS

func (g *Graph) BFS(startNodeID int64, until func(n graph.Node, depth int) bool) graph.Node

BFS breadth-first-search algorithm, starts from given start node. invokes fn function when visiting every node, stops early if until returns true.

func (*Graph) DFS

func (g *Graph) DFS(startNodeID int64, until func(n graph.Node) bool) graph.Node

DFS depth-first-search algorithm, starts from given start node. invokes fn function when visiting every node, stops early if until returns true.

type Network

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

Network is a graph of elements

func NewNetwork

func NewNetwork() Network

NewNetwork creates a network

func (*Network) Add

func (n *Network) Add(id int64) error

Add adds an element to the network, returns error if element already exist.

func (*Network) CheckReachability

func (n *Network) CheckReachability(src, dst int64) (bool, error)

CheckReachability checks if you can reach dst from src.

func (*Network) Connect

func (n *Network) Connect(srcID, dstID int64, duration float64) error

Connect marks dst as reachable from src. returns error if src or dst are nil.

func (*Network) Get

func (n *Network) Get(elementID int64) (nodeID int64, ok bool)

Get returns the corresponding nodeID created when elementID was added.

func (*Network) ValidatePath

func (n *Network) ValidatePath(p []int64) (valid bool, reason error)

ValidatePath checks if the given path p is visitable in the given order.