gs

package
v0.0.0-...-e7df020 Latest Latest
Warning

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

Go to latest
Published: Jul 27, 2014 License: MIT Imports: 6 Imported by: 0

Documentation

Overview

Package gs implements graph using adjacency list and slice data structure.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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 *slice.Sequence
	Edges    *slice.Sequence
}

Graph is a graph represented in adjacency list, but implemented in slice.

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) AddEdge

func (g *Graph) AddEdge(e *Edge)

AddEdge adds the edge e to the graph g's Edges.

func (*Graph) AddVertex

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

AddVertex adds the vertex v to the graph g's Vertices.

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 removes the input vertex A from the graph g's Vertices.

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 can use slice.

func (Graph) GetEdges

func (g Graph) GetEdges() *slice.Sequence

GetEdges returns the edge slice.

func (Graph) GetEdgesSize

func (g Graph) GetEdgesSize() int

GetEdgesSize returns the size of edge slice in a graph.

func (Graph) GetVertices

func (g Graph) GetVertices() *slice.Sequence

GetVertices returns the vertex slice.

func (Graph) GetVerticesSize

func (g Graph) GetVerticesSize() int

GetVerticesSize returns the size of vertex slice 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 between vertices.

type Vertex

type Vertex struct {
	ID    string
	Color string

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

	// slice of vertices that go out of this vertex
	OutVertices *slice.Sequence

	// 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) AddInVertex

func (i *Vertex) AddInVertex(v *Vertex)

AddInVertex adds the vertex v to the vertex i's InVertices.

func (*Vertex) AddOutVertex

func (o *Vertex) AddOutVertex(v *Vertex)

AddOutVertex adds the vertex v to the vertex o's OutVertices.

func (*Vertex) DeleteInVertex

func (i *Vertex) DeleteInVertex(v *Vertex)

DeleteInVertex removes the input vertex v from the vertex i's InVertices.

func (*Vertex) DeleteOutVertex

func (o *Vertex) DeleteOutVertex(v *Vertex)

DeleteOutVertex removes the input vertex v from the vertex o's OutVertices.

func (Vertex) GetInVertices

func (v Vertex) GetInVertices() *slice.Sequence

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

func (Vertex) GetInVerticesSize

func (v Vertex) GetInVerticesSize() int

GetInVerticesSize returns the size of the vertex v's InVertices.

func (Vertex) GetOutVertices

func (v Vertex) GetOutVertices() *slice.Sequence

GetOutVertices returns a slice of adjacent vertices from vertex v.

func (Vertex) GetOutVerticesSize

func (v Vertex) GetOutVerticesSize() int

GetOutVerticesSize returns the size of the vertex v's OutVertices

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL