gld

Documentation

Overview

Package gld implements graph using adjacency list and linked list data structure. This is same as the package gl except that this allows duplicate edges. There can be multiple edges from one to the other node. "Connect" and "GetEdgeWeight" are defined different. And "DeleteEdge" works different than others.

Index

• type Edge
  • func NewEdge(src, dst *Vertex, weight float64) *Edge
• type Graph
  • func JSONGraph(filename, graph string) *Graph
  • func NewGraph() *Graph
  • func ParseToGraph(str string) *Graph
  • func (g *Graph) Connect(A, B *Vertex, weight float64)
  • func (g *Graph) CreateAndAddToGraph(id string) *Vertex
  • func (g *Graph) DeleteEdge(A, B *Vertex)
  • func (g *Graph) DeleteVertex(A *Vertex)
  • func (g Graph) FindVertexByID(id interface{}) *Vertex
  • func (g Graph) GetEdgeWeight(src, dst *Vertex) []float64
  • func (g Graph) GetEdges() *list.List
  • func (g Graph) GetEdgesSize() int
  • func (g Graph) GetVertices() *list.List
  • func (g Graph) GetVerticesSize() int
  • func (g Graph) ImmediateDominate(A, B *Vertex) bool
  • func (g *Graph) UpdateWeight(src, dst *Vertex, value float64)
• type Vertex
  • func NewVertex(id string) *Vertex
  • func (v Vertex) GetInVertices() *list.List
  • func (v Vertex) GetOutVertices() *list.List

Types

type Edge

type Edge struct {
	Src *Vertex

	Dst *Vertex

	Weight float64
}

Edge is an edge(arc) in a graph that has direction from one to another vertex.

func NewEdge

func NewEdge(src, dst *Vertex, weight float64) *Edge

NewEdge returns a new edge from src to dst.

type Graph

type Graph struct {
	Vertices *list.List
	Edges    *list.List
}

Graph is a graph represented in adjacency list. Vertices and edges are stored in linked list. Look at how linked list is implemented in Go's source code. Edges only needs to be handled by a graph , not by each vertex. Vertex contains a list of incoming and outgoing vertices, as in linked list. Let's suffix with T to differentiate with other types of graphs.

func JSONGraph

func JSONGraph(filename, graph string) *Graph

JSONGraph parses JSON file to a graph.

func NewGraph

func NewGraph() *Graph

NewGraph returns a new graph.

func ParseToGraph

func ParseToGraph(str string) *Graph

ParseToGraph parses string data to return a new graph.

func (*Graph) Connect

func (g *Graph) Connect(A, B *Vertex, weight float64)

Connect connects the vertex v to A, not A to v.

func (*Graph) CreateAndAddToGraph

func (g *Graph) CreateAndAddToGraph(id string) *Vertex

CreateAndAddToGrammar finds the vertex with the ID, or create it.

func (*Graph) DeleteEdge

func (g *Graph) DeleteEdge(A, B *Vertex)

DeleteEdge deletes the edge from the vertex A to B. Note that this only delete one direction from A to B.

func (*Graph) DeleteVertex

func (g *Graph) DeleteVertex(A *Vertex)

DeleteVertex deletes a Vertex from the graph.

func (Graph) FindVertexByID

func (g Graph) FindVertexByID(id interface{}) *Vertex

FindVertexByID returns the vertex with input ID , or return nil if it doesn't exist.

func (Graph) GetEdgeWeight

func (g Graph) GetEdgeWeight(src, dst *Vertex) []float64

GetEdgeWeight returns the slice of weight values of the edge from source to destination vertex. In case we need to allow duplicate edges, we return a slice of weights.

func (Graph) GetEdges

func (g Graph) GetEdges() *list.List

GetEdges returns the edge list.

func (Graph) GetEdgesSize

func (g Graph) GetEdgesSize() int

GetEdgesSize returns the size of edge list in a graph.

func (Graph) GetVertices

func (g Graph) GetVertices() *list.List

GetVertices returns the vertex list.

func (Graph) GetVerticesSize

func (g Graph) GetVerticesSize() int

GetVerticesSize returns the size of vertex list in a graph.

func (Graph) ImmediateDominate

func (g Graph) ImmediateDominate(A, B *Vertex) bool

ImmediateDominate returns true if A immediately dominates B. That is, true if A can go to B with only one edge.

func (*Graph) UpdateWeight

func (g *Graph) UpdateWeight(src, dst *Vertex, value float64)

UpdateWeight updates the weight value.

type Vertex

type Vertex struct {
	ID    string
	Color string

	// list of vertices that goes into this vertex
	// (vertices that precede this vertex in graph)
	InVertices *list.List

	// list of vertices that go out of this vertex
	OutVertices *list.List

	// time stamp to record the distance
	// from source vertex
	StampD int64

	// another timestamp to be used in other algorithms
	StampF int64
}

Vertex is a vertex(node) in Graph.

func NewVertex

func NewVertex(id string) *Vertex

NewVertex returns a new Vertex.

func (Vertex) GetInVertices

func (v Vertex) GetInVertices() *list.List

GetInVertices returns a list of adjacent vertices that goes to vertex v.

func (Vertex) GetOutVertices

func (v Vertex) GetOutVertices() *list.List

GetOutVertices returns a list of adjacent vertices from vertex v.