Documentation ¶
Index ¶
- type Edge
- type Graph
- func (graph *Graph) AddEdge(from ID, to ID, weight float64, e interface{}) error
- func (graph *Graph) AddVertex(id ID, v interface{}) error
- func (graph *Graph) AddVertexWithEdges(v Vertex) error
- func (graph *Graph) CheckIntegrity() error
- func (graph *Graph) DeleteEdge(from ID, to ID) interface{}
- func (graph *Graph) DeleteVertex(id ID) interface{}
- func (graph *Graph) Dijkstra(source ID) (dist map[ID]float64, prev map[ID]ID, err error)
- func (graph *Graph) DisableEdge(from, to ID)
- func (graph *Graph) DisablePath(path []ID)
- func (graph *Graph) DisableVertex(vertex ID)
- func (graph *Graph) GetEdge(from ID, to ID) (interface{}, error)
- func (graph *Graph) GetEdgeWeight(from ID, to ID) (float64, error)
- func (graph *Graph) GetPathWeight(path []ID) (totalWeight float64)
- func (graph *Graph) GetVertex(id ID) (vertex interface{}, err error)
- func (graph *Graph) Kisp(source, destination ID, topK int) ([]float64, [][]ID, error)
- func (graph *Graph) Reset()
- func (graph *Graph) UpdateEdgeWeight(from ID, to ID, weight float64) error
- func (graph *Graph) Yen(source, destination ID, topK int) ([]float64, [][]ID, error)
- type ID
- type Vertex
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Edge ¶
type Edge interface { // Get returns the edge's inbound vertex, outbound vertex and weight. Get() (from ID, to ID, weight float64) }
Edge interface represents an edge connecting two vertices.
type Graph ¶
type Graph struct {
// contains filtered or unexported fields
}
Graph is made up of vertices and edges. Vertices in the graph must have an unique id. Each edges in the graph connects two vertices directed with a weight.
func (*Graph) AddEdge ¶
AddEdge adds a new edge between the vertices by the input ids. Try to add an edge with -Inf weight will get an error. Try to add an edge from or to a vertex not in the graph will get an error. Try to add a duplicate edge will get an error.
func (*Graph) AddVertex ¶
AddVertex adds a new vertex into the graph. Try to add a duplicate vertex will get an error.
func (*Graph) AddVertexWithEdges ¶
AddVertexWithEdges adds a vertex value which implements Vertex interface. AddVertexWithEdges adds edges connected to the vertex at the same time, due to the Vertex interface can get the Edges.
func (*Graph) CheckIntegrity ¶
CheckIntegrity checks if any edge connects to or from unknown vertex. If the graph is integrate, nil is returned. Otherwise an error is returned.
func (*Graph) DeleteEdge ¶
DeleteEdge deletes the edge between the vertices by the input id from the graph and gets the value of edge. Try to delete an edge from or to a vertex not in the graph will get an error. Try to delete an edge between disconnected vertices will get a nil.
func (*Graph) DeleteVertex ¶
DeleteVertex deletes a vertex from the graph and gets the value of the vertex. Try to delete a vertex not in the graph will get an nil.
func (*Graph) Dijkstra ¶
Dijkstra gets the shortest path from one vertex to all other vertices in the graph. https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
func (*Graph) DisableEdge ¶
DisableEdge disables the edge for further calculation.
func (*Graph) DisablePath ¶
DisablePath disables all the vertices in the path for further calculation.
func (*Graph) DisableVertex ¶
DisableVertex disables the vertex for further calculation.
func (*Graph) GetEdge ¶
GetEdge gets the edge between the two vertices by input ids. Try to get the edge from or to a vertex not in the graph will get an error. Try to get the edge between two disconnected vertices will get an error.
func (*Graph) GetEdgeWeight ¶
GetEdgeWeight gets the weight of the edge between the two vertices by input ids. Try to get the weight of the edge from or to a vertex not in the graph will get an error. Try to get the weight of the edge between two disconnected vertices will get +Inf.
func (*Graph) GetPathWeight ¶
GetPathWeight gets the total weight along the path by input ids. It will get -Inf if the input path is nil or empty. It will get -Inf if the path contains vertex not in the graph. It will get +Inf if the path contains vertices not connected.
func (*Graph) GetVertex ¶
GetVertex get a vertex by input id. Try to get a vertex not in the graph will get an error.
func (*Graph) Kisp ¶
Kisp gets top k shortest independent path between two vertex in the graph. Independent means no vertex is shared between path.
func (*Graph) Reset ¶
func (graph *Graph) Reset()
Reset enables all vertices and edges for further calculation.
func (*Graph) UpdateEdgeWeight ¶
UpdateEdgeWeight updates the weight of the edge between vertices by the input ids. Try to update an edge with -Inf weight will get an error. Try to update an edge from or to a vertex not in the graph will get an error. Try to update an edge between disconnected vertices will get an error.