gm

Documentation

Overview

Package gm implements graph using adjacency list and map data structure.

Index

• type EMAP
• 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) AddEdge(e *Edge)
  • func (g *Graph) AddVertex(v *Vertex)
  • 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) GetEdgeWeight(src, dst *Vertex) float64
  • func (g Graph) GetEdges() EMAP
  • func (g Graph) GetEdgesSize() int
  • func (g Graph) GetVertices() VMAP
  • func (g Graph) GetVerticesSize() int
  • func (g Graph) ImmediateDominate(A, B *Vertex) bool
  • func (g *Graph) UpdateWeight(src, dst *Vertex, value float64)
• type VMAP
• type Vertex
  • func NewVertex(id string) *Vertex
  • func (A *Vertex) AddInVertex(B *Vertex)
  • func (A *Vertex) AddOutVertex(B *Vertex)
  • func (i *Vertex) DeleteInVertex(v *Vertex)
  • func (o *Vertex) DeleteOutVertex(v *Vertex)
  • func (v Vertex) GetInVertices() VMAP
  • func (v Vertex) GetInVerticesSize() int
  • func (v Vertex) GetOutVertices() VMAP
  • func (v Vertex) GetOutVerticesSize() int

Types

type EMAP

type EMAP map[int]*Edge

type Edge

type Edge struct {
	SrcDst map[string]string

	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 VMAP
	Edges    EMAP
}

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. Only to be used when there is no duplicate edge.

func (*Graph) AddVertex

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

AddVertex adds the vertex v to the graph g's Vertices. Only to be used when there is no duplicate vertex.

func (*Graph) Connect

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

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

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

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

GetEdgeWeight returns the weight value. Our graph does not allow the duplicate edges. If there is a duplicate edges, the value is added to the existent weight.

func (Graph) GetEdges

func (g Graph) GetEdges() EMAP

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() VMAP

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 VMAP

type VMAP map[string]*Vertex

string is just to map the ID to the Vertex. Do not map "Vertex" to string since VMAP will be used as slice and the map does not allow duplicate keys.

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 VMAP

	// slice of vertices that go out of this vertex
	OutVertices VMAP
	// contains filtered or unexported fields
}

Vertex is a vertex(node) in Graph.

func NewVertex

func NewVertex(id string) *Vertex

NewVertex returns a new Vertex.

func (*Vertex) AddInVertex

func (A *Vertex) AddInVertex(B *Vertex)

AddInVertex adds the vertex B to the vertex A's InVertices. B goes into A.

func (*Vertex) AddOutVertex

func (A *Vertex) AddOutVertex(B *Vertex)

AddOutVertex adds the vertex B to the vertex A's OutVertices. A goes out to B.

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() VMAP

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() VMAP

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