Documentation
¶
Index ¶
- func CheckCycles(g *Graph) error
- func Tarjan(g *Graph) [][]ID
- type ErrCycleDetected
- type Graph
- func (g *Graph) AddEdge(id1, id2 ID, weight float64) error
- func (g *Graph) AddNode(nd Node) bool
- func (g *Graph) DeleteEdge(id1, id2 ID) error
- func (g *Graph) DeleteNode(id ID) bool
- func (g *Graph) Exists(id ID) bool
- func (g *Graph) Node(id ID) (Node, error)
- func (g *Graph) NodeCount() int
- func (g *Graph) Nodes() map[ID]Node
- func (g *Graph) Replace(node Node) bool
- func (g *Graph) ReplaceEdge(id1, id2 ID, weight float64) error
- func (g *Graph) Sources(id ID) (map[ID]Node, error)
- func (g *Graph) String() string
- func (g *Graph) Targets(id ID) (map[ID]Node, error)
- func (g *Graph) Weight(id1, id2 ID) (float64, error)
- type ID
- type Node
- type StringID
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Tarjan ¶
Tarjan finds the strongly connected components. In the mathematics, a directed graph is "strongly connected" if every vertex is reachable from every other node. Therefore, a graph is strongly connected if there is a path in each direction between each pair of node of a graph. Then a pair of vertices u and v is strongly connected to each other because there is a path in each direction. "Strongly connected components" of an arbitrary graph partition into sub-graphs that are themselves strongly connected. That is, "strongly connected component" of a directed graph is a sub-graph that is strongly connected. Formally, "Strongly connected components" of a graph is a maximal set of vertices C in G.V such that for all u, v ∈ C, there is a path both from u to v, and from v to u. (https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)
- Tarjan(G): 1.
- globalIndex = 0 // smallest unused index
- let S be a stack
- result = [][] 5.
- for each vertex v in G:
- if v.index is undefined:
- tarjan(G, v, globalIndex, S, result) 9.
- return result 11. 12.
- tarjan(G, v, globalIndex, S, result): 14.
- v.index = globalIndex
- v.lowLink = globalIndex
- globalIndex++
- S.push(v) 19.
- for each child vertex w of v: 21.
- if w.index is undefined:
- recursively tarjan(G, w, globalIndex, S, result)
- v.lowLink = min(v.lowLink, w.lowLink) 25.
- else if w is in S:
- v.lowLink = min(v.lowLink, w.index) 28.
- // if v is the root
- if v.lowLink == v.index: 31.
- // start a new strongly connected component
- component = [] 34.
- while True: 36.
- u = S.pop()
- component.push(u) 39.
- if u == v:
- result.push(component)
- break
Types ¶
type ErrCycleDetected ¶
type ErrCycleDetected struct {
// contains filtered or unexported fields
}
ErrCycleDetected causes when graph is cyclic.
func (ErrCycleDetected) Error ¶
func (e ErrCycleDetected) Error() string
Error is a error implementation.
type Graph ¶
type Graph struct {
// contains filtered or unexported fields
}
Graph describes the methods of graph operations. It assumes that the identifier of a Node is unique. And weight values is float64.
func (*Graph) AddEdge ¶
AddEdge adds an edge from nd1 to nd2 with the weight. It returns error if a node does not exist.
func (*Graph) AddNode ¶
AddNode adds a node to a graph, and returns false if the node already existed in the graph.
func (*Graph) DeleteEdge ¶
DeleteEdge deletes an edge from id1 to id2.
func (*Graph) DeleteNode ¶
DeleteNode deletes a node from a graph. It returns true if it got deleted. And false if it didn't get deleted.
func (*Graph) Nodes ¶
Nodes returns a map from node ID to empty struct value. Graph does not allow duplicate node ID or name.
func (*Graph) ReplaceEdge ¶
ReplaceEdge replaces an edge from id1 to id2 with the weight.
func (*Graph) Sources ¶
Sources returns the map of parent Nodes. (Nodes that come towards the argument vertex.)
type ID ¶
type ID interface {
// String returns the string ID.
String() string
}
ID is unique identifier.
func BFS ¶
BFS does breadth-first search, and returns the list of vertices. (https://en.wikipedia.org/wiki/Breadth-first_search)
- BFS(G, v): 1.
- let Q be a queue
- Q.push(v)
- label v as visited 5.
- while Q is not empty: 7.
- u = Q.dequeue() 9.
- for each vertex w adjacent to u: 11.
- if w is not visited yet:
- Q.push(w)
- label w as visited
func DFS ¶
DFS does depth-first search, and returns the list of vertices. (https://en.wikipedia.org/wiki/Depth-first_search)
- DFS(G, v): 1.
- let S be a stack
- S.push(v) 4.
- while S is not empty: 6.
- u = S.pop() 8.
- if u is not visited yet: 10.
- label u as visited 12.
- for each vertex w adjacent to u: 14.
- if w is not visited yet:
- S.push(w)
func DFSRecursion ¶
DFSRecursion does depth-first search recursively.
- DFS(G, v): 1.
- if v is visited:
- return 4.
- label v as visited 6.
- for each vertex u adjacent to v: 8.
- if u is not visited yet:
- recursive DFS(G, u)
func TopologicalSort ¶
TopologicalSort does topological sort(ordering) with DFS. It returns true if the graph is a DAG (no cycle, with a topological sort). False if the graph is not a DAG (cycle, with no topological sort).
Source Files
Directories