graph

Documentation

Overview

A memory-efficient graph for large datasets.

Time complexities: Storage: O(V + E) Add Node: O(1) Add Arc: O(1) Remove Node: O(E) Remove Arc: O(1)

Index

• Constants
• type Graph
  • func Import(reader io.Reader) (error, *Graph)
  • func NewGraph() *Graph
  • func (self *Graph) Add(node *Node)
  • func (self *Graph) AddArc(origin *Node, dest *Node)
  • func (self *Graph) Adjacent(origin *Node, target *Node) bool
  • func (self *Graph) Export(writer io.Writer) error
  • func (self *Graph) Get(name string) *Node
  • func (self *Graph) Neighbors(origin *Node) []*Node
  • func (graph *Graph) PageRank(n int)
  • func (self *Graph) PointingTo(dest *Node) []*Node
  • func (self *Graph) Remove(node *Node)
  • func (self *Graph) RemoveArc(origin *Node, toRemove *Node)
  • func (self *Graph) SafeGet(name string) *Node
  • func (self *Graph) String() string
• type Node
  • func NewNode(name string) *Node
  • func (self *Node) String() string

Constants

const DEFAULT_DAMPING = 0.85

const DEFAULT_ITERATIONS = 15

Types

type Graph

type Graph struct {
	Nodes map[*Node][]*Node
	Names map[string]*Node
}

Graph is memory-efficient labeled graph for large datasets.

func Import

func Import(reader io.Reader) (error, *Graph)

Import creates a graph from a gob dump in the given writer. and returns any errors that it encounters.

func NewGraph

func NewGraph() *Graph

NewGraph returns an empty graph.

func (*Graph) Add

func (self *Graph) Add(node *Node)

Add adds a node to the graph.

func (*Graph) AddArc

func (self *Graph) AddArc(origin *Node, dest *Node)

AddArc adds an arc between the origin and destination nodes.

func (*Graph) Adjacent

func (self *Graph) Adjacent(origin *Node, target *Node) bool

Adjacent returns true if the origin node has an arc to the destination node and false otherwise.

func (*Graph) Export

func (self *Graph) Export(writer io.Writer) error

Export writes a gob dump of the graph to the given writer and returns any error that it encounters.

func (*Graph) Get

func (self *Graph) Get(name string) *Node

Get returns the node with the given name or null if none exists.

func (*Graph) Neighbors

func (self *Graph) Neighbors(origin *Node) []*Node

Neighbors returns all nodes that the given node points to.

func (*Graph) PageRank

func (graph *Graph) PageRank(n int)

PageRank runs a page rank algorithm on the graph n number of times. It uses DEFAULT_DAMPING, as the damping factor, which is a reasonable value.

The algorithm is described here: http://en.wikipedia.org/wiki/PageRank

and more simply here: http://stackoverflow.com/questions/3950627/python-implementation-of-pagerank

func (*Graph) PointingTo

func (self *Graph) PointingTo(dest *Node) []*Node

PointingTo returns all nodes that have arcs to the given node

func (*Graph) Remove

func (self *Graph) Remove(node *Node)

Remove removes a node from the graph along with all arcs pointing to it.

func (*Graph) RemoveArc

func (self *Graph) RemoveArc(origin *Node, toRemove *Node)

RemoveArc removes the arc between the origin and destination nodes.

func (*Graph) SafeGet

func (self *Graph) SafeGet(name string) *Node

SafeGet returns the node with the given name or creates a new node with the given name if one does not exist.

func (*Graph) String

func (self *Graph) String() string

String creates a string representation of the graph in the following form:

node -> neighbor, neighbor, neighbor

type Node

type Node struct {
	Name string
	Rank float64
}

Node is an arbitrary element of the graph.

func NewNode

func NewNode(name string) *Node

NewNode returns a node with the given name

func (*Node) String

func (self *Node) String() string

String returns a string representation of the node, which is currently just its name.