Documentation
¶
Overview ¶
Package gsdflow implements graph, almost same as package gsd.
Index ¶
- func SameEdge(e1, e2 *Edge) bool
- func SameGraph(g1, g2 *Graph) bool
- func SameVertex(v1, v2 *Vertex) bool
- type Edge
- type Graph
- func (g *Graph) AddEdge(e *Edge)
- func (g *Graph) AddFlow(src, dst *Vertex, value float64)
- 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) FindVertexByID(id interface{}) *Vertex
- func (g Graph) GetEdge(src, dst *Vertex) *Edge
- func (g Graph) GetEdgeFlow(src, dst *Vertex) []float64
- func (g Graph) GetEdgeWeight(src, dst *Vertex) []float64
- func (g Graph) GetEdges() *slice.Sequence
- func (g Graph) GetEdgesSize() int
- func (g Graph) GetVertices() *slice.Sequence
- func (g Graph) GetVerticesSize() int
- func (g Graph) ImmediateDominate(A, B *Vertex) bool
- func (g *Graph) IsFull(src, dst *Vertex) bool
- func (g *Graph) ShowPrev(id interface{}) string
- func (g *Graph) SubFlow(src, dst *Vertex, value float64)
- func (g *Graph) Transpose() *Graph
- func (g *Graph) UpdateFlow(src, dst *Vertex, value float64)
- func (g *Graph) UpdateWeight(src, dst *Vertex, value float64)
- type Vertex
- func (i *Vertex) AddInVertex(v *Vertex)
- func (o *Vertex) AddOutVertex(v *Vertex)
- func (i *Vertex) DeleteInVertex(v *Vertex)
- func (o *Vertex) DeleteOutVertex(v *Vertex)
- func (v Vertex) GetInVertices() *slice.Sequence
- func (v Vertex) GetInVerticesSize() int
- func (v Vertex) GetOutVertices() *slice.Sequence
- func (v Vertex) GetOutVerticesSize() int
- func (v Vertex) GetPrev() *slice.Sequence
- func (v Vertex) GetPrevSize() int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func SameVertex ¶
SameVertex returns true if two vertices are the same.
Types ¶
type Edge ¶
type Edge struct {
Src *Vertex // source vertex that this edge starts from
Dst *Vertex // destination vertex that this edge goes to
Weight float64 // Used as capacify
Flow float64
}
Edge is an edge(arc) in a graph that has direction from one to another vertex.
type Graph ¶
Graph is a graph represented in adjacency list, but implemented in slice.
func JSONGraphBi ¶
JSONGraphBi connects the graph bi-directionally.
func JSONGraphT ¶
JSONGraphT parses JSON file to a graph in a reverse order. It returns the tranposed Graph of the original data.
func ParseToGraph ¶
ParseToGraph parses string data to return a new graph.
func (*Graph) CreateAndAddToGraph ¶
CreateAndAddToGrammar finds the vertex with the ID, or create it.
func (*Graph) DeleteEdge ¶
DeleteEdge deletes the edge from the vertex A to B. Note that this only delete one direction from A to B.
func (*Graph) DeleteVertex ¶
DeleteVertex removes the input vertex A from the graph g's Vertices.
func (Graph) FindVertexByID ¶
FindVertexByID returns the vertex with input ID , or return nil if it doesn't exist.
func (Graph) GetEdge ¶
GetEdge returns the Edge from src to dst Vertex. (Assume that there is no duplicate Edge for now.)
func (Graph) GetEdgeFlow ¶
GetEdgeFlow returns the slice of flow values.
func (Graph) GetEdgeWeight ¶
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) GetEdgesSize ¶
GetEdgesSize returns the size of edge slice in a graph.
func (Graph) GetVertices ¶
GetVertices returns the vertex slice.
func (Graph) GetVerticesSize ¶
GetVerticesSize returns the size of vertex slice in a graph.
func (Graph) ImmediateDominate ¶
ImmediateDominate returns true if A immediately dominates B. That is, true if A can go to B with only one edge.
func (*Graph) UpdateFlow ¶
UpdateFlow updates the flow value between vertices.
func (*Graph) UpdateWeight ¶
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
// By having this empty Sequence,
// when implementing graph algorithms
// we do not need to initialize the InVertices
// with vtx.(*gsd.Vertex).InVertices.Init()
// and do not modify the original graph
Prev *slice.Sequence
}
Vertex is a vertex(node) in Graph.
func (*Vertex) AddInVertex ¶
AddInVertex adds the vertex v to the vertex i's InVertices.
func (*Vertex) AddOutVertex ¶
AddOutVertex adds the vertex v to the vertex o's OutVertices.
func (*Vertex) DeleteInVertex ¶
DeleteInVertex removes the input vertex v from the vertex i's InVertices.
func (*Vertex) DeleteOutVertex ¶
DeleteOutVertex removes the input vertex v from the vertex o's OutVertices.
func (Vertex) GetInVertices ¶
GetInVertices returns a slice of adjacent vertices that goes to vertex v.
func (Vertex) GetInVerticesSize ¶
GetInVerticesSize returns the size of the vertex v's InVertices.
func (Vertex) GetOutVertices ¶
GetOutVertices returns a slice of adjacent vertices from vertex v.
func (Vertex) GetOutVerticesSize ¶
GetOutVerticesSize returns the size of the vertex v's OutVertices
func (Vertex) GetPrevSize ¶
GetPrevSize returns the size of the vertex v's Prev.
Source Files