graph

package module
v0.0.0-...-77fd953 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 12, 2016 License: MIT Imports: 3 Imported by: 0

README

graph

A graph library written in go

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func PageRank 

func PageRank()

https://en.wikipedia.org/wiki/PageRank

func ShortestPath 

func ShortestPath()

https://en.wikipedia.org/wiki/A*_search_algorithm

func TopologicalSort 

func TopologicalSort()

https://en.wikipedia.org/wiki/Topological_sorting

Types

type AdjIndex 

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

func NewAdjIndex 

func NewAdjIndex() *AdjIndex

func (*AdjIndex) AdjacentTo 

func (a *AdjIndex) AdjacentTo(v *Vertex) []*Vertex

func (*AdjIndex) EdgeAdd 

func (a *AdjIndex) EdgeAdd(e *Edge, from, to *Vertex)

func (*AdjIndex) EdgeRemove 

func (a *AdjIndex) EdgeRemove(e *Edge, from, to *Vertex)

func (*AdjIndex) Name 

func (a *AdjIndex) Name() string

func (*AdjIndex) UUID 

func (a *AdjIndex) UUID() UUID

func (*AdjIndex) UUIDString 

func (a *AdjIndex) UUIDString() string

func (*AdjIndex) VertexAdd 

func (a *AdjIndex) VertexAdd(v *Vertex)

func (*AdjIndex) VertexRemove 

func (a *AdjIndex) VertexRemove(v *Vertex)

type Edge 

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

The Edge struct.

func NewEdge 

func NewEdge(weight int) *Edge

Allocated a new Edge and returns a pointer to it. //func NewEdge(weight int, relation string) *Edge {

func (*Edge) Member 

func (e *Edge) Member(g *Graph) bool

Returns the membership status of e in g.

func (*Edge) Properties 

func (e *Edge) Properties() map[string]int

Returns a copy of the properties field of an Edge.

func (*Edge) UUID 

func (e *Edge) UUID() UUID

Returns the uuid of e as a UUID.

func (*Edge) UUIDString 

func (e *Edge) UUIDString() string

Returns the uuid of e as a string.

func (*Edge) UpdateProperties 

func (e *Edge) UpdateProperties(p map[string]int)

Replaces the properties of e with p.

func (*Edge) Vertices 

func (e *Edge) Vertices() (UUID, UUID)

Returns the from, to Vertex UUIDs as a pair.

func (*Edge) Weight 

func (e *Edge) Weight() int

Returns the weight of e.

type Graph 

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

Could make it so that the mapping of adjacency and revAdjacency is to weights. Also the adj maps don't account for multiple types of Edges connecting Vertices.

func NewGraph 

func NewGraph() *Graph

func (*Graph) AddEdge 

func (g *Graph) AddEdge(e *Edge, src, dst *Vertex) bool

Add an edge from source to destination. This is a constant time operation.

func (*Graph) AddVertex 

func (g *Graph) AddVertex(v *Vertex) bool

Add a Vertex v to g. This is a constant time operation.

func (*Graph) Adjacent 

func (g *Graph) Adjacent(v *Vertex) map[*Vertex]int

Return the adjacency map of v in g.

func (*Graph) BFS 

func (g *Graph) BFS(root *Vertex) (map[*Vertex]*Vertex, map[*Vertex]int)

The return order is (map[child]parent, map[destination]cost) This functions returns: (child -> parent *Vertex), (*Vertex -> cost). This allows a user to construct the shortest path for any *Vertex from root.

func (*Graph) DFS 

func (g *Graph) DFS(root *Vertex)

The return order is (map[child]parent, map[destination]cost)

func (*Graph) Dijkstras 

func (g *Graph) Dijkstras(root *Vertex) (map[*Vertex]*Vertex, map[*Vertex]int)

The return order is (map[child]parent, map[destination]cost)

func (*Graph) Edge 

func (g *Graph) Edge(u UUID) (*Edge, bool)

Get a *Edge by UUID from g.

func (*Graph) Edges 

func (g *Graph) Edges() map[string]*Edge

Returns a mapping of UUID.String() to *Edge in g.

func (*Graph) EdgesFrom 

func (g *Graph) EdgesFrom(v *Vertex) map[string]*Edge

Returns a mapping of UUID.String() to *Edge in g where *Edge.from == v.

func (*Graph) EdgesOf 

func (g *Graph) EdgesOf(v *Vertex) map[string]*Edge

Returns a map that is the combination of g.EdgesTo() and g.EdgesFrom().

func (*Graph) EdgesTo 

func (g *Graph) EdgesTo(v *Vertex) map[string]*Edge

Returns a mapping of UUID.String() to *Edge in g where *Edge.to == v.

func (*Graph) InDegree 

func (g *Graph) InDegree(v *Vertex) int

Get the In-degree of a Vertex. A return value of -1 indicates the Vertex has no entry in the revAdjacency map. -1 implies v does not exist.

func (*Graph) OutDegree 

func (g *Graph) OutDegree(v *Vertex) int

Get the Out-degree of a Vertex. A return value of -1 indicates the Vertex has no entry in the adjacency map. -1 implies v does not exist.

func (*Graph) RemoveEdge 

func (g *Graph) RemoveEdge(e *Edge, src, dst *Vertex) bool

Remove an Edge e between Vertex src and Vertex dst from g. always returns true. This function deletes 1 entry in each of g.adjacency and g.revAdjacency. Finally it deletes e from g.edges. This deleteion does not account for multiple Edges between two Vertices. Constant time operation.

func (*Graph) RemoveVertex 

func (g *Graph) RemoveVertex(v *Vertex) bool

Remove a Vertex v from g also removing all Edges with their source at v. Runs in time proportional to: (number of Vertices to which v is adjacent) + (number of Vertices that are adjacent to v) + (number of edges in/out of v)

func (*Graph) ReverseAdjacent 

func (g *Graph) ReverseAdjacent(v *Vertex) map[*Vertex]int

Return the reverse adjacency map of v in g.

func (*Graph) Vertex 

func (g *Graph) Vertex(u UUID) (*Vertex, bool)

Get a *Vertex by UUID from g.

func (*Graph) Vertices 

func (g *Graph) Vertices() map[string]*Vertex

Returns a mapping of UUID.String() to *Vertex in g.

type Path 

type Path struct {
	Weight int
	Path   []Edge
}

type Queue 

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

func (*Queue) Length 

func (q *Queue) Length() int

func (*Queue) Peek 

func (q *Queue) Peek() *Vertex

func (*Queue) Poll 

func (q *Queue) Poll() *Vertex

func (*Queue) Push 

func (q *Queue) Push(v *Vertex)

type Stack 

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

func (*Stack) Empty 

func (s *Stack) Empty() bool

func (*Stack) Pop 

func (s *Stack) Pop() (*Vertex, error)

func (*Stack) Push 

func (s *Stack) Push(v *Vertex)

func (*Stack) Size 

func (s *Stack) Size() int

type Vertex 

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

The Vertex struct.

func NewVertex 

func NewVertex(vtype string, key int) *Vertex

Allocates a new Vertex and return a pointer to it.

func (*Vertex) Equal 

func (v *Vertex) Equal(x *Vertex) bool

func (*Vertex) GetProperties 

func (v *Vertex) GetProperties() map[string]int

Returns a copy of the props map of v.

func (*Vertex) Key 

func (v *Vertex) Key() int

A Key method for use in search things.

func (*Vertex) Member 

func (v *Vertex) Member(g *Graph) bool

Returns the membership status of v in g.

func (*Vertex) Type 

func (v *Vertex) Type() string

func (*Vertex) UUID 

func (v *Vertex) UUID() UUID

Returns the uuid of v as a UUID which is an alias for [16]byte

func (*Vertex) UUIDString 

func (v *Vertex) UUIDString() string

Returns the string representation of the uuid for v.

func (*Vertex) UpdateProperties 

func (v *Vertex) UpdateProperties(p map[string]int) bool

Replaces v's props with the supplied p map[string]int.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.