VOL-1558 Update vendored voltha-go and other items
Result of running dep ensure. golang openolt now
builds.
Also update dockerfile to used specific alpine version
Change-Id: I1e5407e25bb0636a241a0650d1e44e5df567f44b
diff --git a/vendor/github.com/gyuho/goraph/.travis.yml b/vendor/github.com/gyuho/goraph/.travis.yml
new file mode 100644
index 0000000..4228e24
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/.travis.yml
@@ -0,0 +1,11 @@
+language: go
+
+sudo: false
+
+go:
+- 1.6
+- tip
+
+script:
+- ./test
+
diff --git a/vendor/github.com/gyuho/goraph/LICENSE b/vendor/github.com/gyuho/goraph/LICENSE
new file mode 100644
index 0000000..f7303ba
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/LICENSE
@@ -0,0 +1,22 @@
+The MIT License (MIT)
+
+Copyright (c) 2015 Gyu-Ho Lee
+Copyright (c) 2016 Google Inc
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/vendor/github.com/gyuho/goraph/README.md b/vendor/github.com/gyuho/goraph/README.md
new file mode 100644
index 0000000..0b5b590
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/README.md
@@ -0,0 +1,32 @@
+## goraph [](https://travis-ci.org/gyuho/goraph) [](https://godoc.org/github.com/gyuho/goraph)
+
+Package goraph implements graph data structure and algorithms.
+
+```
+go get -v gopkg.in/gyuho/goraph.v2;
+```
+
+<br>
+I have tutorials and visualizations of graph, tree algorithms:
+
+- [**_Binary search tree_**](https://github.com/gyuho/learn/tree/master/doc/binary_search_tree)
+- [**_Go: heap, priority queue_**](https://github.com/gyuho/learn/tree/master/doc/go_heap_priority_queue)
+- [**_Go: red black tree_**](https://github.com/gyuho/learn/tree/master/doc/go_red_black_tree)
+- [**_Go: b-tree_**](https://github.com/gyuho/learn/tree/master/doc/go_b_tree)
+- [**_Go: graph, interface_**](https://github.com/gyuho/learn/tree/master/doc/go_graph_interface)
+- [**_Go: graph, traversal_**](https://github.com/gyuho/learn/tree/master/doc/go_graph_traversal)
+- [**_Go: graph, shortest path_**](https://github.com/gyuho/learn/tree/master/doc/go_graph_shortest_path)
+- [**_Go: graph, topological sort_**](https://github.com/gyuho/learn/tree/master/doc/go_graph_topological_sort)
+- [**_Go: graph, minimum spanning tree_**](https://github.com/gyuho/learn/tree/master/doc/go_graph_minimum_spanning_tree)
+- [**_Go: graph, strongly connected components_**](https://github.com/gyuho/learn/tree/master/doc/go_graph_strongly_connected_components)
+
+<br>
+For fast query and retrieval, please check out <a href="http://google-opensource.blogspot.co.uk/2014/06/cayley-graphs-in-go.html" target="_blank">Cayley</a>.
+
+
+<br>
+<a href="http://www.youtube.com/watch?v=ImMnYq2zP4Y" target="_blank"><img src="http://img.youtube.com/vi/ImMnYq2zP4Y/0.jpg"></a>
+
+- <a href="https://www.youtube.com/channel/UCWzSgIp_DYRQnEsJuH32Fww" target="_blank">Please visit my YouTube Channel</a>
+- <a href="https://www.youtube.com/watch?v=NdfIfxTsVDo&list=PLT6aABhFfinvsSn1H195JLuHaXNS6UVhf" target="_blank">`Tree`, `Graph` Theory Algorithms (Playlist)</a>
+- <a href="https://www.youtube.com/watch?v=ImMnYq2zP4Y&list=PLT6aABhFfinvsSn1H195JLuHaXNS6UVhf&index=4" target="_blank">`Graph` : BFS, DFS</a>
diff --git a/vendor/github.com/gyuho/goraph/disjoint_set.go b/vendor/github.com/gyuho/goraph/disjoint_set.go
new file mode 100644
index 0000000..3a8085f
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/disjoint_set.go
@@ -0,0 +1,67 @@
+package goraph
+
+import "sync"
+
+// DisjointSet implements disjoint set.
+// (https://en.wikipedia.org/wiki/Disjoint-set_data_structure)
+type DisjointSet struct {
+ represent string
+ members map[string]struct{}
+}
+
+// Forests is a set of DisjointSet.
+type Forests struct {
+ mu sync.Mutex // guards the following
+ data map[*DisjointSet]struct{}
+}
+
+// NewForests creates a new Forests.
+func NewForests() *Forests {
+ set := &Forests{}
+ set.data = make(map[*DisjointSet]struct{})
+ return set
+}
+
+// MakeDisjointSet creates a DisjointSet.
+func MakeDisjointSet(forests *Forests, name string) {
+ newDS := &DisjointSet{}
+ newDS.represent = name
+ members := make(map[string]struct{})
+ members[name] = struct{}{}
+ newDS.members = members
+ forests.mu.Lock()
+ defer forests.mu.Unlock()
+ forests.data[newDS] = struct{}{}
+}
+
+// FindSet returns the DisjointSet with the represent name.
+func FindSet(forests *Forests, name string) *DisjointSet {
+ forests.mu.Lock()
+ defer forests.mu.Unlock()
+ for data := range forests.data {
+ if data.represent == name {
+ return data
+ }
+ for k := range data.members {
+ if k == name {
+ return data
+ }
+ }
+ }
+ return nil
+}
+
+// Union unions two DisjointSet, with ds1's represent.
+func Union(forests *Forests, ds1, ds2 *DisjointSet) {
+ newDS := &DisjointSet{}
+ newDS.represent = ds1.represent
+ newDS.members = ds1.members
+ for k := range ds2.members {
+ newDS.members[k] = struct{}{}
+ }
+ forests.mu.Lock()
+ defer forests.mu.Unlock()
+ forests.data[newDS] = struct{}{}
+ delete(forests.data, ds1)
+ delete(forests.data, ds2)
+}
diff --git a/vendor/github.com/gyuho/goraph/doc.go b/vendor/github.com/gyuho/goraph/doc.go
new file mode 100644
index 0000000..191d299
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/doc.go
@@ -0,0 +1,2 @@
+// Package goraph implements graph data structure and algorithms.
+package goraph // import "github.com/gyuho/goraph"
diff --git a/vendor/github.com/gyuho/goraph/graph.go b/vendor/github.com/gyuho/goraph/graph.go
new file mode 100644
index 0000000..87f87c5
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/graph.go
@@ -0,0 +1,503 @@
+package goraph
+
+import (
+ "bytes"
+ "encoding/json"
+ "fmt"
+ "io"
+ "sync"
+)
+
+// ID is unique identifier.
+type ID interface {
+ // String returns the string ID.
+ String() string
+}
+
+type StringID string
+
+func (s StringID) String() string {
+ return string(s)
+}
+
+// Node is vertex. The ID must be unique within the graph.
+type Node interface {
+ // ID returns the ID.
+ ID() ID
+ String() string
+}
+
+type node struct {
+ id string
+}
+
+var nodeCnt uint64
+
+func NewNode(id string) Node {
+ return &node{
+ id: id,
+ }
+}
+
+func (n *node) ID() ID {
+ return StringID(n.id)
+}
+
+func (n *node) String() string {
+ return n.id
+}
+
+// Edge connects between two Nodes.
+type Edge interface {
+ Source() Node
+ Target() Node
+ Weight() float64
+ String() string
+}
+
+// edge is an Edge from Source to Target.
+type edge struct {
+ src Node
+ tgt Node
+ wgt float64
+}
+
+func NewEdge(src, tgt Node, wgt float64) Edge {
+ return &edge{
+ src: src,
+ tgt: tgt,
+ wgt: wgt,
+ }
+}
+
+func (e *edge) Source() Node {
+ return e.src
+}
+
+func (e *edge) Target() Node {
+ return e.tgt
+}
+
+func (e *edge) Weight() float64 {
+ return e.wgt
+}
+
+func (e *edge) String() string {
+ return fmt.Sprintf("%s -- %.3f -→ %s\n", e.src, e.wgt, e.tgt)
+}
+
+type EdgeSlice []Edge
+
+func (e EdgeSlice) Len() int { return len(e) }
+func (e EdgeSlice) Less(i, j int) bool { return e[i].Weight() < e[j].Weight() }
+func (e EdgeSlice) Swap(i, j int) { e[i], e[j] = e[j], e[i] }
+
+// Graph describes the methods of graph operations.
+// It assumes that the identifier of a Node is unique.
+// And weight values is float64.
+type Graph interface {
+ // Init initializes a Graph.
+ Init()
+
+ // GetNodeCount returns the total number of nodes.
+ GetNodeCount() int
+
+ // GetNode finds the Node. It returns nil if the Node
+ // does not exist in the graph.
+ GetNode(id ID) Node
+
+ // GetNodes returns a map from node ID to
+ // empty struct value. Graph does not allow duplicate
+ // node ID or name.
+ GetNodes() map[ID]Node
+
+ // AddNode adds a node to a graph, and returns false
+ // if the node already existed in the graph.
+ AddNode(nd Node) bool
+
+ // DeleteNode deletes a node from a graph.
+ // It returns true if it got deleted.
+ // And false if it didn't get deleted.
+ DeleteNode(id ID) bool
+
+ // AddEdge adds an edge from nd1 to nd2 with the weight.
+ // It returns error if a node does not exist.
+ AddEdge(id1, id2 ID, weight float64) error
+
+ // ReplaceEdge replaces an edge from id1 to id2 with the weight.
+ ReplaceEdge(id1, id2 ID, weight float64) error
+
+ // DeleteEdge deletes an edge from id1 to id2.
+ DeleteEdge(id1, id2 ID) error
+
+ // GetWeight returns the weight from id1 to id2.
+ GetWeight(id1, id2 ID) (float64, error)
+
+ // GetSources returns the map of parent Nodes.
+ // (Nodes that come towards the argument vertex.)
+ GetSources(id ID) (map[ID]Node, error)
+
+ // GetTargets returns the map of child Nodes.
+ // (Nodes that go out of the argument vertex.)
+ GetTargets(id ID) (map[ID]Node, error)
+
+ // String describes the Graph.
+ String() string
+}
+
+// graph is an internal default graph type that
+// implements all methods in Graph interface.
+type graph struct {
+ mu sync.RWMutex // guards the following
+
+ // idToNodes stores all nodes.
+ idToNodes map[ID]Node
+
+ // nodeToSources maps a Node identifer to sources(parents) with edge weights.
+ nodeToSources map[ID]map[ID]float64
+
+ // nodeToTargets maps a Node identifer to targets(children) with edge weights.
+ nodeToTargets map[ID]map[ID]float64
+}
+
+// newGraph returns a new graph.
+func newGraph() *graph {
+ return &graph{
+ idToNodes: make(map[ID]Node),
+ nodeToSources: make(map[ID]map[ID]float64),
+ nodeToTargets: make(map[ID]map[ID]float64),
+ //
+ // without this
+ // panic: assignment to entry in nil map
+ }
+}
+
+// NewGraph returns a new graph.
+func NewGraph() Graph {
+ return newGraph()
+}
+
+func (g *graph) Init() {
+ // (X) g = newGraph()
+ // this only updates the pointer
+ //
+ //
+ // (X) *g = *newGraph()
+ // assignment copies lock value
+
+ g.idToNodes = make(map[ID]Node)
+ g.nodeToSources = make(map[ID]map[ID]float64)
+ g.nodeToTargets = make(map[ID]map[ID]float64)
+}
+
+func (g *graph) GetNodeCount() int {
+ g.mu.RLock()
+ defer g.mu.RUnlock()
+
+ return len(g.idToNodes)
+}
+
+func (g *graph) GetNode(id ID) Node {
+ g.mu.RLock()
+ defer g.mu.RUnlock()
+
+ return g.idToNodes[id]
+}
+
+func (g *graph) GetNodes() map[ID]Node {
+ g.mu.RLock()
+ defer g.mu.RUnlock()
+
+ return g.idToNodes
+}
+
+func (g *graph) unsafeExistID(id ID) bool {
+ _, ok := g.idToNodes[id]
+ return ok
+}
+
+func (g *graph) AddNode(nd Node) bool {
+ g.mu.Lock()
+ defer g.mu.Unlock()
+
+ if g.unsafeExistID(nd.ID()) {
+ return false
+ }
+
+ id := nd.ID()
+ g.idToNodes[id] = nd
+ return true
+}
+
+func (g *graph) DeleteNode(id ID) bool {
+ g.mu.Lock()
+ defer g.mu.Unlock()
+
+ if !g.unsafeExistID(id) {
+ return false
+ }
+
+ delete(g.idToNodes, id)
+
+ delete(g.nodeToTargets, id)
+ for _, smap := range g.nodeToTargets {
+ delete(smap, id)
+ }
+
+ delete(g.nodeToSources, id)
+ for _, smap := range g.nodeToSources {
+ delete(smap, id)
+ }
+
+ return true
+}
+
+func (g *graph) AddEdge(id1, id2 ID, weight float64) error {
+ g.mu.Lock()
+ defer g.mu.Unlock()
+
+ if !g.unsafeExistID(id1) {
+ return fmt.Errorf("%s does not exist in the graph.", id1)
+ }
+ if !g.unsafeExistID(id2) {
+ return fmt.Errorf("%s does not exist in the graph.", id2)
+ }
+
+ if _, ok := g.nodeToTargets[id1]; ok {
+ if v, ok2 := g.nodeToTargets[id1][id2]; ok2 {
+ g.nodeToTargets[id1][id2] = v + weight
+ } else {
+ g.nodeToTargets[id1][id2] = weight
+ }
+ } else {
+ tmap := make(map[ID]float64)
+ tmap[id2] = weight
+ g.nodeToTargets[id1] = tmap
+ }
+ if _, ok := g.nodeToSources[id2]; ok {
+ if v, ok2 := g.nodeToSources[id2][id1]; ok2 {
+ g.nodeToSources[id2][id1] = v + weight
+ } else {
+ g.nodeToSources[id2][id1] = weight
+ }
+ } else {
+ tmap := make(map[ID]float64)
+ tmap[id1] = weight
+ g.nodeToSources[id2] = tmap
+ }
+
+ return nil
+}
+
+func (g *graph) ReplaceEdge(id1, id2 ID, weight float64) error {
+ g.mu.Lock()
+ defer g.mu.Unlock()
+
+ if !g.unsafeExistID(id1) {
+ return fmt.Errorf("%s does not exist in the graph.", id1)
+ }
+ if !g.unsafeExistID(id2) {
+ return fmt.Errorf("%s does not exist in the graph.", id2)
+ }
+
+ if _, ok := g.nodeToTargets[id1]; ok {
+ g.nodeToTargets[id1][id2] = weight
+ } else {
+ tmap := make(map[ID]float64)
+ tmap[id2] = weight
+ g.nodeToTargets[id1] = tmap
+ }
+ if _, ok := g.nodeToSources[id2]; ok {
+ g.nodeToSources[id2][id1] = weight
+ } else {
+ tmap := make(map[ID]float64)
+ tmap[id1] = weight
+ g.nodeToSources[id2] = tmap
+ }
+ return nil
+}
+
+func (g *graph) DeleteEdge(id1, id2 ID) error {
+ g.mu.Lock()
+ defer g.mu.Unlock()
+
+ if !g.unsafeExistID(id1) {
+ return fmt.Errorf("%s does not exist in the graph.", id1)
+ }
+ if !g.unsafeExistID(id2) {
+ return fmt.Errorf("%s does not exist in the graph.", id2)
+ }
+
+ if _, ok := g.nodeToTargets[id1]; ok {
+ if _, ok := g.nodeToTargets[id1][id2]; ok {
+ delete(g.nodeToTargets[id1], id2)
+ }
+ }
+ if _, ok := g.nodeToSources[id2]; ok {
+ if _, ok := g.nodeToSources[id2][id1]; ok {
+ delete(g.nodeToSources[id2], id1)
+ }
+ }
+ return nil
+}
+
+func (g *graph) GetWeight(id1, id2 ID) (float64, error) {
+ g.mu.RLock()
+ defer g.mu.RUnlock()
+
+ if !g.unsafeExistID(id1) {
+ return 0, fmt.Errorf("%s does not exist in the graph.", id1)
+ }
+ if !g.unsafeExistID(id2) {
+ return 0, fmt.Errorf("%s does not exist in the graph.", id2)
+ }
+
+ if _, ok := g.nodeToTargets[id1]; ok {
+ if v, ok := g.nodeToTargets[id1][id2]; ok {
+ return v, nil
+ }
+ }
+ return 0.0, fmt.Errorf("there is no edge from %s to %s", id1, id2)
+}
+
+func (g *graph) GetSources(id ID) (map[ID]Node, error) {
+ g.mu.RLock()
+ defer g.mu.RUnlock()
+
+ if !g.unsafeExistID(id) {
+ return nil, fmt.Errorf("%s does not exist in the graph.", id)
+ }
+
+ rs := make(map[ID]Node)
+ if _, ok := g.nodeToSources[id]; ok {
+ for n := range g.nodeToSources[id] {
+ rs[n] = g.idToNodes[n]
+ }
+ }
+ return rs, nil
+}
+
+func (g *graph) GetTargets(id ID) (map[ID]Node, error) {
+ g.mu.RLock()
+ defer g.mu.RUnlock()
+
+ if !g.unsafeExistID(id) {
+ return nil, fmt.Errorf("%s does not exist in the graph.", id)
+ }
+
+ rs := make(map[ID]Node)
+ if _, ok := g.nodeToTargets[id]; ok {
+ for n := range g.nodeToTargets[id] {
+ rs[n] = g.idToNodes[n]
+ }
+ }
+ return rs, nil
+}
+
+func (g *graph) String() string {
+ g.mu.RLock()
+ defer g.mu.RUnlock()
+
+ buf := new(bytes.Buffer)
+ for id1, nd1 := range g.idToNodes {
+ nmap, _ := g.GetTargets(id1)
+ for id2, nd2 := range nmap {
+ weight, _ := g.GetWeight(id1, id2)
+ fmt.Fprintf(buf, "%s -- %.3f -→ %s\n", nd1, weight, nd2)
+ }
+ }
+ return buf.String()
+}
+
+// NewGraphFromJSON returns a new Graph from a JSON file.
+// Here's the sample JSON data:
+//
+// {
+// "graph_00": {
+// "S": {
+// "A": 100,
+// "B": 14,
+// "C": 200
+// },
+// "A": {
+// "S": 15,
+// "B": 5,
+// "D": 20,
+// "T": 44
+// },
+// "B": {
+// "S": 14,
+// "A": 5,
+// "D": 30,
+// "E": 18
+// },
+// "C": {
+// "S": 9,
+// "E": 24
+// },
+// "D": {
+// "A": 20,
+// "B": 30,
+// "E": 2,
+// "F": 11,
+// "T": 16
+// },
+// "E": {
+// "B": 18,
+// "C": 24,
+// "D": 2,
+// "F": 6,
+// "T": 19
+// },
+// "F": {
+// "D": 11,
+// "E": 6,
+// "T": 6
+// },
+// "T": {
+// "A": 44,
+// "D": 16,
+// "F": 6,
+// "E": 19
+// }
+// },
+// }
+//
+func NewGraphFromJSON(rd io.Reader, graphID string) (Graph, error) {
+ js := make(map[string]map[string]map[string]float64)
+ dec := json.NewDecoder(rd)
+ for {
+ if err := dec.Decode(&js); err == io.EOF {
+ break
+ } else if err != nil {
+ return nil, err
+ }
+ }
+ if _, ok := js[graphID]; !ok {
+ return nil, fmt.Errorf("%s does not exist", graphID)
+ }
+ gmap := js[graphID]
+
+ g := newGraph()
+ for id1, mm := range gmap {
+ nd1 := g.GetNode(StringID(id1))
+ if nd1 == nil {
+ nd1 = NewNode(id1)
+ if ok := g.AddNode(nd1); !ok {
+ return nil, fmt.Errorf("%s already exists", nd1)
+ }
+ }
+ for id2, weight := range mm {
+ nd2 := g.GetNode(StringID(id2))
+ if nd2 == nil {
+ nd2 = NewNode(id2)
+ if ok := g.AddNode(nd2); !ok {
+ return nil, fmt.Errorf("%s already exists", nd2)
+ }
+ }
+ g.ReplaceEdge(nd1.ID(), nd2.ID(), weight)
+ }
+ }
+
+ return g, nil
+}
diff --git a/vendor/github.com/gyuho/goraph/minimum_spanning_tree.go b/vendor/github.com/gyuho/goraph/minimum_spanning_tree.go
new file mode 100644
index 0000000..a86e279
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/minimum_spanning_tree.go
@@ -0,0 +1,287 @@
+package goraph
+
+import (
+ "container/heap"
+ "math"
+ "sort"
+)
+
+// Kruskal finds the minimum spanning tree with disjoint-set data structure.
+// (http://en.wikipedia.org/wiki/Kruskal%27s_algorithm)
+//
+// 0. Kruskal(G)
+// 1.
+// 2. A = ∅
+// 3.
+// 4. for each vertex v in G:
+// 5. MakeDisjointSet(v)
+// 6.
+// 7. edges = get all edges
+// 8. sort edges in ascending order of weight
+// 9.
+// 10. for each edge (u, v) in edges:
+// 11. if FindSet(u) ≠ FindSet(v):
+// 12. A = A ∪ {(u, v)}
+// 13. Union(u, v)
+// 14.
+// 15. return A
+//
+func Kruskal(g Graph) (map[Edge]struct{}, error) {
+
+ // A = ∅
+ A := make(map[Edge]struct{})
+
+ // disjointSet maps a member Node to a represent.
+ // (https://en.wikipedia.org/wiki/Disjoint-set_data_structure)
+ forests := NewForests()
+
+ // for each vertex v in G:
+ for _, nd := range g.GetNodes() {
+ // MakeDisjointSet(v)
+ MakeDisjointSet(forests, nd.String())
+ }
+
+ // edges = get all edges
+ edges := []Edge{}
+ foundEdge := make(map[string]struct{})
+ for id1, nd1 := range g.GetNodes() {
+ tm, err := g.GetTargets(id1)
+ if err != nil {
+ return nil, err
+ }
+ for id2, nd2 := range tm {
+ weight, err := g.GetWeight(id1, id2)
+ if err != nil {
+ return nil, err
+ }
+ edge := NewEdge(nd1, nd2, weight)
+ if _, ok := foundEdge[edge.String()]; !ok {
+ edges = append(edges, edge)
+ foundEdge[edge.String()] = struct{}{}
+ }
+ }
+
+ sm, err := g.GetSources(id1)
+ if err != nil {
+ return nil, err
+ }
+ for id3, nd3 := range sm {
+ weight, err := g.GetWeight(id3, id1)
+ if err != nil {
+ return nil, err
+ }
+ edge := NewEdge(nd3, nd1, weight)
+ if _, ok := foundEdge[edge.String()]; !ok {
+ edges = append(edges, edge)
+ foundEdge[edge.String()] = struct{}{}
+ }
+ }
+ }
+
+ // sort edges in ascending order of weight
+ sort.Sort(EdgeSlice(edges))
+
+ // for each edge (u, v) in edges:
+ for _, edge := range edges {
+ // if FindSet(u) ≠ FindSet(v):
+ if FindSet(forests, edge.Source().String()).represent != FindSet(forests, edge.Target().String()).represent {
+
+ // A = A ∪ {(u, v)}
+ A[edge] = struct{}{}
+
+ // Union(u, v)
+ // overwrite v's represent with u's represent
+ Union(forests, FindSet(forests, edge.Source().String()), FindSet(forests, edge.Target().String()))
+ }
+ }
+
+ return A, nil
+}
+
+// Prim finds the minimum spanning tree with min-heap (priority queue).
+// (http://en.wikipedia.org/wiki/Prim%27s_algorithm)
+//
+// 0. Prim(G, source)
+// 1.
+// 2. let Q be a priority queue
+// 3. distance[source] = 0
+// 4.
+// 5. for each vertex v in G:
+// 6.
+// 7. if v ≠ source:
+// 8. distance[v] = ∞
+// 9. prev[v] = undefined
+// 10.
+// 11. Q.add_with_priority(v, distance[v])
+// 12.
+// 13.
+// 14. while Q is not empty:
+// 15.
+// 16. u = Q.extract_min()
+// 17.
+// 18. for each adjacent vertex v of u:
+// 19.
+// 21. if v ∈ Q and distance[v] > weight(u, v):
+// 22. distance[v] = weight(u, v)
+// 23. prev[v] = u
+// 24. Q.decrease_priority(v, weight(u, v))
+// 25.
+// 26.
+// 27. return tree from prev
+//
+func Prim(g Graph, src ID) (map[Edge]struct{}, error) {
+
+ // let Q be a priority queue
+ minHeap := &nodeDistanceHeap{}
+
+ // distance[source] = 0
+ distance := make(map[ID]float64)
+ distance[src] = 0.0
+
+ // for each vertex v in G:
+ for id := range g.GetNodes() {
+
+ // if v ≠ src:
+ if id != src {
+ // distance[v] = ∞
+ distance[id] = math.MaxFloat64
+
+ // prev[v] = undefined
+ // prev[v] = ""
+ }
+
+ // Q.add_with_priority(v, distance[v])
+ nds := nodeDistance{}
+ nds.id = id
+ nds.distance = distance[id]
+
+ heap.Push(minHeap, nds)
+ }
+
+ heap.Init(minHeap)
+ prev := make(map[ID]ID)
+
+ // while Q is not empty:
+ for minHeap.Len() != 0 {
+
+ // u = Q.extract_min()
+ u := heap.Pop(minHeap).(nodeDistance)
+ uID := u.id
+
+ // for each adjacent vertex v of u:
+ tm, err := g.GetTargets(uID)
+ if err != nil {
+ return nil, err
+ }
+ for vID := range tm {
+
+ isExist := false
+ for _, one := range *minHeap {
+ if vID == one.id {
+ isExist = true
+ break
+ }
+ }
+
+ // weight(u, v)
+ weight, err := g.GetWeight(uID, vID)
+ if err != nil {
+ return nil, err
+ }
+
+ // if v ∈ Q and distance[v] > weight(u, v):
+ if isExist && distance[vID] > weight {
+
+ // distance[v] = weight(u, v)
+ distance[vID] = weight
+
+ // prev[v] = u
+ prev[vID] = uID
+
+ // Q.decrease_priority(v, weight(u, v))
+ minHeap.updateDistance(vID, weight)
+ heap.Init(minHeap)
+ }
+ }
+
+ sm, err := g.GetSources(uID)
+ if err != nil {
+ return nil, err
+ }
+ vID := uID
+ for uID := range sm {
+
+ isExist := false
+ for _, one := range *minHeap {
+ if vID == one.id {
+ isExist = true
+ break
+ }
+ }
+
+ // weight(u, v)
+ weight, err := g.GetWeight(uID, vID)
+ if err != nil {
+ return nil, err
+ }
+
+ // if v ∈ Q and distance[v] > weight(u, v):
+ if isExist && distance[vID] > weight {
+
+ // distance[v] = weight(u, v)
+ distance[vID] = weight
+
+ // prev[v] = u
+ prev[vID] = uID
+
+ // Q.decrease_priority(v, weight(u, v))
+ minHeap.updateDistance(vID, weight)
+ heap.Init(minHeap)
+ }
+ }
+ }
+
+ tree := make(map[Edge]struct{})
+ for k, v := range prev {
+ weight, err := g.GetWeight(v, k)
+ if err != nil {
+ return nil, err
+ }
+ tree[NewEdge(g.GetNode(v), g.GetNode(k), weight)] = struct{}{}
+ }
+ return tree, nil
+}
+
+type nodeDistance struct {
+ id ID
+ distance float64
+}
+
+// container.Heap's Interface needs sort.Interface, Push, Pop to be implemented
+
+// nodeDistanceHeap is a min-heap of nodeDistances.
+type nodeDistanceHeap []nodeDistance
+
+func (h nodeDistanceHeap) Len() int { return len(h) }
+func (h nodeDistanceHeap) Less(i, j int) bool { return h[i].distance < h[j].distance } // Min-Heap
+func (h nodeDistanceHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
+
+func (h *nodeDistanceHeap) Push(x interface{}) {
+ *h = append(*h, x.(nodeDistance))
+}
+
+func (h *nodeDistanceHeap) Pop() interface{} {
+ heapSize := len(*h)
+ lastNode := (*h)[heapSize-1]
+ *h = (*h)[0 : heapSize-1]
+ return lastNode
+}
+
+func (h *nodeDistanceHeap) updateDistance(id ID, val float64) {
+ for i := 0; i < len(*h); i++ {
+ if (*h)[i].id == id {
+ (*h)[i].distance = val
+ break
+ }
+ }
+}
diff --git a/vendor/github.com/gyuho/goraph/shortest_path.go b/vendor/github.com/gyuho/goraph/shortest_path.go
new file mode 100644
index 0000000..e6f405c
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/shortest_path.go
@@ -0,0 +1,348 @@
+package goraph
+
+import (
+ "container/heap"
+ "fmt"
+ "math"
+)
+
+// Dijkstra returns the shortest path using Dijkstra
+// algorithm with a min-priority queue. This algorithm
+// does not work with negative weight edges.
+// (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
+//
+// 0. Dijkstra(G, source, target)
+// 1.
+// 2. let Q be a priority queue
+// 3. distance[source] = 0
+// 4.
+// 5. for each vertex v in G:
+// 6.
+// 7. if v ≠ source:
+// 8. distance[v] = ∞
+// 9. prev[v] = undefined
+// 10.
+// 11. Q.add_with_priority(v, distance[v])
+// 12.
+// 13. while Q is not empty:
+// 14.
+// 15. u = Q.extract_min()
+// 16. if u == target:
+// 17. break
+// 18.
+// 19. for each child vertex v of u:
+// 20.
+// 21. alt = distance[u] + weight(u, v)
+// 22. if distance[v] > alt:
+// 23. distance[v] = alt
+// 24. prev[v] = u
+// 25. Q.decrease_priority(v, alt)
+// 26.
+// 27. reheapify(Q)
+// 28.
+// 29.
+// 30. path = []
+// 31. u = target
+// 32. while prev[u] is defined:
+// 33. path.push_front(u)
+// 34. u = prev[u]
+// 35.
+// 36. return path, prev
+//
+func Dijkstra(g Graph, source, target ID) ([]ID, map[ID]float64, error) {
+ // let Q be a priority queue
+ minHeap := &nodeDistanceHeap{}
+
+ // distance[source] = 0
+ distance := make(map[ID]float64)
+ distance[source] = 0.0
+
+ // for each vertex v in G:
+ for id := range g.GetNodes() {
+ // if v ≠ source:
+ if id != source {
+ // distance[v] = ∞
+ distance[id] = math.MaxFloat64
+
+ // prev[v] = undefined
+ // prev[v] = ""
+ }
+
+ // Q.add_with_priority(v, distance[v])
+ nds := nodeDistance{}
+ nds.id = id
+ nds.distance = distance[id]
+
+ heap.Push(minHeap, nds)
+ }
+
+ heap.Init(minHeap)
+ prev := make(map[ID]ID)
+
+ // while Q is not empty:
+ for minHeap.Len() != 0 {
+
+ // u = Q.extract_min()
+ u := heap.Pop(minHeap).(nodeDistance)
+
+ // if u == target:
+ if u.id == target {
+ break
+ }
+
+ // for each child vertex v of u:
+ cmap, err := g.GetTargets(u.id)
+ if err != nil {
+ return nil, nil, err
+ }
+ for v := range cmap {
+
+ // alt = distance[u] + weight(u, v)
+ weight, err := g.GetWeight(u.id, v)
+ if err != nil {
+ return nil, nil, err
+ }
+ alt := distance[u.id] + weight
+
+ // if distance[v] > alt:
+ if distance[v] > alt {
+
+ // distance[v] = alt
+ distance[v] = alt
+
+ // prev[v] = u
+ prev[v] = u.id
+
+ // Q.decrease_priority(v, alt)
+ minHeap.updateDistance(v, alt)
+ }
+ }
+ heap.Init(minHeap)
+ }
+
+ // path = []
+ path := []ID{}
+
+ // u = target
+ u := target
+
+ // while prev[u] is defined:
+ for {
+ if _, ok := prev[u]; !ok {
+ break
+ }
+ // path.push_front(u)
+ temp := make([]ID, len(path)+1)
+ temp[0] = u
+ copy(temp[1:], path)
+ path = temp
+
+ // u = prev[u]
+ u = prev[u]
+ }
+
+ // add the source
+ temp := make([]ID, len(path)+1)
+ temp[0] = source
+ copy(temp[1:], path)
+ path = temp
+
+ return path, distance, nil
+}
+
+// BellmanFord returns the shortest path using Bellman-Ford algorithm
+// This algorithm works with negative weight edges.
+// Time complexity is O(|V||E|).
+// (http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf)
+// It returns error when there is a negative-weight cycle.
+// A negatively-weighted cycle adds up to infinite negative-weight.
+//
+// 0. BellmanFord(G, source, target)
+// 1.
+// 2. distance[source] = 0
+// 3.
+// 4. for each vertex v in G:
+// 5.
+// 6. if v ≠ source:
+// 7. distance[v] = ∞
+// 8. prev[v] = undefined
+// 9.
+// 10.
+// 11. for 1 to |V|-1:
+// 12.
+// 13. for every edge (u, v):
+// 14.
+// 15. alt = distance[u] + weight(u, v)
+// 16. if distance[v] > alt:
+// 17. distance[v] = alt
+// 18. prev[v] = u
+// 19.
+// 20.
+// 21. for every edge (u, v):
+// 22.
+// 23. alt = distance[u] + weight(u, v)
+// 24. if distance[v] > alt:
+// 25. there is a negative-weight cycle
+// 26.
+// 27.
+// 28. path = []
+// 29. u = target
+// 30. while prev[u] is defined:
+// 31. path.push_front(u)
+// 32. u = prev[u]
+// 33.
+// 34. return path, prev
+//
+func BellmanFord(g Graph, source, target ID) ([]ID, map[ID]float64, error) {
+ // distance[source] = 0
+ distance := make(map[ID]float64)
+ distance[source] = 0.0
+
+ // for each vertex v in G:
+ for id := range g.GetNodes() {
+
+ // if v ≠ source:
+ if id != source {
+ // distance[v] = ∞
+ distance[id] = math.MaxFloat64
+
+ // prev[v] = undefined
+ // prev[v] = ""
+ }
+ }
+
+ prev := make(map[ID]ID)
+
+ // for 1 to |V|-1:
+ for i := 1; i <= g.GetNodeCount()-1; i++ {
+
+ // for every edge (u, v):
+ for id := range g.GetNodes() {
+
+ cmap, err := g.GetTargets(id)
+ if err != nil {
+ return nil, nil, err
+ }
+ u := id
+ for v := range cmap {
+ // edge (u, v)
+ weight, err := g.GetWeight(u, v)
+ if err != nil {
+ return nil, nil, err
+ }
+
+ // alt = distance[u] + weight(u, v)
+ alt := distance[u] + weight
+
+ // if distance[v] > alt:
+ if distance[v] > alt {
+ // distance[v] = alt
+ distance[v] = alt
+
+ // prev[v] = u
+ prev[v] = u
+ }
+ }
+
+ pmap, err := g.GetSources(id)
+ if err != nil {
+ return nil, nil, err
+ }
+ v := id
+ for u := range pmap {
+ // edge (u, v)
+ weight, err := g.GetWeight(u, v)
+ if err != nil {
+ return nil, nil, err
+ }
+
+ // alt = distance[u] + weight(u, v)
+ alt := distance[u] + weight
+
+ // if distance[v] > alt:
+ if distance[v] > alt {
+ // distance[v] = alt
+ distance[v] = alt
+
+ // prev[v] = u
+ prev[v] = u
+ }
+ }
+ }
+ }
+
+ // for every edge (u, v):
+ for id := range g.GetNodes() {
+
+ cmap, err := g.GetTargets(id)
+ if err != nil {
+ return nil, nil, err
+ }
+ u := id
+ for v := range cmap {
+ // edge (u, v)
+ weight, err := g.GetWeight(u, v)
+ if err != nil {
+ return nil, nil, err
+ }
+
+ // alt = distance[u] + weight(u, v)
+ alt := distance[u] + weight
+
+ // if distance[v] > alt:
+ if distance[v] > alt {
+ return nil, nil, fmt.Errorf("there is a negative-weight cycle: %v", g)
+ }
+ }
+
+ pmap, err := g.GetSources(id)
+ if err != nil {
+ return nil, nil, err
+ }
+ v := id
+ for u := range pmap {
+ // edge (u, v)
+ weight, err := g.GetWeight(u, v)
+ if err != nil {
+ return nil, nil, err
+ }
+
+ // alt = distance[u] + weight(u, v)
+ alt := distance[u] + weight
+
+ // if distance[v] > alt:
+ if distance[v] > alt {
+ return nil, nil, fmt.Errorf("there is a negative-weight cycle: %v", g)
+ }
+ }
+ }
+
+ // path = []
+ path := []ID{}
+
+ // u = target
+ u := target
+
+ // while prev[u] is defined:
+ for {
+ if _, ok := prev[u]; !ok {
+ break
+ }
+ // path.push_front(u)
+ temp := make([]ID, len(path)+1)
+ temp[0] = u
+ copy(temp[1:], path)
+ path = temp
+
+ // u = prev[u]
+ u = prev[u]
+ }
+
+ // add the source
+ temp := make([]ID, len(path)+1)
+ temp[0] = source
+ copy(temp[1:], path)
+ path = temp
+
+ return path, distance, nil
+}
diff --git a/vendor/github.com/gyuho/goraph/strongly_connected_components.go b/vendor/github.com/gyuho/goraph/strongly_connected_components.go
new file mode 100644
index 0000000..b0a11a5
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/strongly_connected_components.go
@@ -0,0 +1,195 @@
+package goraph
+
+import "sync"
+
+// 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)
+//
+// 0. Tarjan(G):
+// 1.
+// 2. globalIndex = 0 // smallest unused index
+// 3. let S be a stack
+// 4. result = [][]
+// 5.
+// 6. for each vertex v in G:
+// 7. if v.index is undefined:
+// 8. tarjan(G, v, globalIndex, S, result)
+// 9.
+// 10. return result
+// 11.
+// 12.
+// 13. tarjan(G, v, globalIndex, S, result):
+// 14.
+// 15. v.index = globalIndex
+// 16. v.lowLink = globalIndex
+// 17. globalIndex++
+// 18. S.push(v)
+// 19.
+// 20. for each child vertex w of v:
+// 21.
+// 22. if w.index is undefined:
+// 23. recursively tarjan(G, w, globalIndex, S, result)
+// 24. v.lowLink = min(v.lowLink, w.lowLink)
+// 25.
+// 26. else if w is in S:
+// 27. v.lowLink = min(v.lowLink, w.index)
+// 28.
+// 29. // if v is the root
+// 30. if v.lowLink == v.index:
+// 31.
+// 32. // start a new strongly connected component
+// 33. component = []
+// 34.
+// 35. while True:
+// 36.
+// 37. u = S.pop()
+// 38. component.push(u)
+// 39.
+// 40. if u == v:
+// 41. result.push(component)
+// 42. break
+//
+func Tarjan(g Graph) [][]ID {
+ d := newTarjanData()
+
+ // for each vertex v in G:
+ for v := range g.GetNodes() {
+ // if v.index is undefined:
+ if _, ok := d.index[v]; !ok {
+ // tarjan(G, v, globalIndex, S, result)
+ tarjan(g, v, d)
+ }
+ }
+ return d.result
+}
+
+type tarjanData struct {
+ mu sync.Mutex // guards the following
+
+ // globalIndex is the smallest unused index
+ globalIndex int
+
+ // index is an index of a node to record
+ // the order of being discovered.
+ index map[ID]int
+
+ // lowLink is the smallest index of any index
+ // reachable from v, including v itself.
+ lowLink map[ID]int
+
+ // S is the stack.
+ S []ID
+
+ // extra map to check if a vertex is in S.
+ smap map[ID]struct{}
+
+ result [][]ID
+}
+
+func newTarjanData() *tarjanData {
+ return &tarjanData{
+ globalIndex: 0,
+ index: make(map[ID]int),
+ lowLink: make(map[ID]int),
+ S: []ID{},
+ smap: make(map[ID]struct{}),
+ result: [][]ID{},
+ }
+}
+
+func tarjan(
+ g Graph,
+ id ID,
+ data *tarjanData,
+) {
+ // This is not inherently parallelizable problem,
+ // but just to make sure.
+ data.mu.Lock()
+
+ // v.index = globalIndex
+ data.index[id] = data.globalIndex
+
+ // v.lowLink = globalIndex
+ data.lowLink[id] = data.globalIndex
+
+ // globalIndex++
+ data.globalIndex++
+
+ // S.push(v)
+ data.S = append(data.S, id)
+ data.smap[id] = struct{}{}
+
+ data.mu.Unlock()
+
+ // for each child vertex w of v:
+ cmap, err := g.GetTargets(id)
+ if err != nil {
+ panic(err)
+ }
+ for w := range cmap {
+
+ // if w.index is undefined:
+ if _, ok := data.index[w]; !ok {
+
+ // recursively tarjan(G, w, globalIndex, S, result)
+ tarjan(g, w, data)
+
+ // v.lowLink = min(v.lowLink, w.lowLink)
+ data.lowLink[id] = min(data.lowLink[id], data.lowLink[w])
+
+ } else if _, ok := data.smap[w]; ok {
+ // else if w is in S:
+
+ // v.lowLink = min(v.lowLink, w.index)
+ data.lowLink[id] = min(data.lowLink[id], data.index[w])
+ }
+ }
+
+ data.mu.Lock()
+ defer data.mu.Unlock()
+
+ // if v is the root
+ // if v.lowLink == v.index:
+ if data.lowLink[id] == data.index[id] {
+ // start a new strongly connected component
+ component := []ID{}
+
+ // while True:
+ for {
+
+ // u = S.pop()
+ u := data.S[len(data.S)-1]
+ data.S = data.S[:len(data.S)-1 : len(data.S)-1]
+ delete(data.smap, u)
+
+ // component.push(u)
+ component = append(component, u)
+
+ // if u == v:
+ if u == id {
+ data.result = append(data.result, component)
+ break
+ }
+ }
+ }
+}
+
+func min(a, b int) int {
+ if a < b {
+ return a
+ }
+ return b
+}
diff --git a/vendor/github.com/gyuho/goraph/test b/vendor/github.com/gyuho/goraph/test
new file mode 100755
index 0000000..a7d8a6d
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/test
@@ -0,0 +1,24 @@
+#!/usr/bin/env bash
+
+TEST=./...;
+FMT="*.go"
+
+echo "Running tests...";
+go test -v -cover -cpu 1,2,4 $TEST;
+go test -v -cover -cpu 1,2,4 -race $TEST;
+
+echo "Checking gofmt..."
+fmtRes=$(gofmt -l -s $FMT)
+if [ -n "${fmtRes}" ]; then
+ echo -e "gofmt checking failed:\n${fmtRes}"
+ exit 255
+fi
+
+echo "Checking govet..."
+vetRes=$(go vet $TEST)
+if [ -n "${vetRes}" ]; then
+ echo -e "govet checking failed:\n${vetRes}"
+ exit 255
+fi
+
+echo "Success";
diff --git a/vendor/github.com/gyuho/goraph/topological_sort.go b/vendor/github.com/gyuho/goraph/topological_sort.go
new file mode 100644
index 0000000..b63675a
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/topological_sort.go
@@ -0,0 +1,98 @@
+package goraph
+
+// 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).
+//
+// 0. TopologicalSort(G)
+// 1.
+// 2. L = Empty list that will contain the sorted nodes
+// 3. isDAG = true
+// 4.
+// 5. for each vertex v in G:
+// 6.
+// 7. if v.color == "white":
+// 8.
+// 9. topologicalSortVisit(v, L, isDAG)
+// 10.
+// 11.
+// 12.
+// 13.
+// 14. topologicalSortVisit(v, L, isDAG)
+// 15.
+// 16. if v.color == "gray":
+// 17. isDAG = false
+// 18. return
+// 19.
+// 20. if v.color == "white":
+// 21.
+// 22. v.color = "gray":
+// 23.
+// 24. for each child vertex w of v:
+// 25. topologicalSortVisit(w, L, isDAG)
+// 26.
+// 27. v.color = "black"
+// 28. L.push_front(v)
+//
+func TopologicalSort(g Graph) ([]ID, bool) {
+
+ // L = Empty list that will contain the sorted nodes
+ L := []ID{}
+ isDAG := true
+ color := make(map[ID]string)
+ for v := range g.GetNodes() {
+ color[v] = "white"
+ }
+
+ // for each vertex v in G:
+ for v := range g.GetNodes() {
+ // if v.color == "white":
+ if color[v] == "white" {
+ // topologicalSortVisit(v, L, isDAG)
+ topologicalSortVisit(g, v, &L, &isDAG, &color)
+ }
+ }
+
+ return L, isDAG
+}
+
+func topologicalSortVisit(
+ g Graph,
+ id ID,
+ L *[]ID,
+ isDAG *bool,
+ color *map[ID]string,
+) {
+
+ // if v.color == "gray":
+ if (*color)[id] == "gray" {
+ // isDAG = false
+ *isDAG = false
+ return
+ }
+
+ // if v.color == "white":
+ if (*color)[id] == "white" {
+ // v.color = "gray":
+ (*color)[id] = "gray"
+
+ // for each child vertex w of v:
+ cmap, err := g.GetTargets(id)
+ if err != nil {
+ panic(err)
+ }
+ for w := range cmap {
+ // topologicalSortVisit(w, L, isDAG)
+ topologicalSortVisit(g, w, L, isDAG, color)
+ }
+
+ // v.color = "black"
+ (*color)[id] = "black"
+
+ // L.push_front(v)
+ temp := make([]ID, len(*L)+1)
+ temp[0] = id
+ copy(temp[1:], *L)
+ *L = temp
+ }
+}
diff --git a/vendor/github.com/gyuho/goraph/traversal.go b/vendor/github.com/gyuho/goraph/traversal.go
new file mode 100644
index 0000000..fa45c29
--- /dev/null
+++ b/vendor/github.com/gyuho/goraph/traversal.go
@@ -0,0 +1,184 @@
+package goraph
+
+// BFS does breadth-first search, and returns the list of vertices.
+// (https://en.wikipedia.org/wiki/Breadth-first_search)
+//
+// 0. BFS(G, v):
+// 1.
+// 2. let Q be a queue
+// 3. Q.push(v)
+// 4. label v as visited
+// 5.
+// 6. while Q is not empty:
+// 7.
+// 8. u = Q.dequeue()
+// 9.
+// 10. for each vertex w adjacent to u:
+// 11.
+// 12. if w is not visited yet:
+// 13. Q.push(w)
+// 14. label w as visited
+//
+func BFS(g Graph, id ID) []ID {
+ if g.GetNode(id) == nil {
+ return nil
+ }
+
+ q := []ID{id}
+ visited := make(map[ID]bool)
+ visited[id] = true
+ rs := []ID{id}
+
+ // while Q is not empty:
+ for len(q) != 0 {
+
+ u := q[0]
+ q = q[1:len(q):len(q)]
+
+ // for each vertex w adjacent to u:
+ cmap, _ := g.GetTargets(u)
+ for _, w := range cmap {
+ // if w is not visited yet:
+ if _, ok := visited[w.ID()]; !ok {
+ q = append(q, w.ID()) // Q.push(w)
+ visited[w.ID()] = true // label w as visited
+
+ rs = append(rs, w)
+ }
+ }
+ pmap, _ := g.GetSources(u)
+ for _, w := range pmap {
+ // if w is not visited yet:
+ if _, ok := visited[w.ID()]; !ok {
+ q = append(q, w.ID()) // Q.push(w)
+ visited[w.ID()] = true // label w as visited
+
+ rs = append(rs, w.ID())
+ }
+ }
+ }
+
+ return rs
+}
+
+// DFS does depth-first search, and returns the list of vertices.
+// (https://en.wikipedia.org/wiki/Depth-first_search)
+//
+// 0. DFS(G, v):
+// 1.
+// 2. let S be a stack
+// 3. S.push(v)
+// 4.
+// 5. while S is not empty:
+// 6.
+// 7. u = S.pop()
+// 8.
+// 9. if u is not visited yet:
+// 10.
+// 11. label u as visited
+// 12.
+// 13. for each vertex w adjacent to u:
+// 14.
+// 15. if w is not visited yet:
+// 16. S.push(w)
+//
+func DFS(g Graph, id ID) []ID {
+ if g.GetNode(id) == nil {
+ return nil
+ }
+
+ s := []ID{id}
+ visited := make(map[ID]bool)
+ rs := []ID{}
+
+ // while S is not empty:
+ for len(s) != 0 {
+
+ u := s[len(s)-1]
+ s = s[:len(s)-1 : len(s)-1]
+
+ // if u is not visited yet:
+ if _, ok := visited[u]; !ok {
+ // label u as visited
+ visited[u] = true
+
+ rs = append(rs, u)
+
+ // for each vertex w adjacent to u:
+ cmap, _ := g.GetTargets(u)
+ for _, w := range cmap {
+ // if w is not visited yet:
+ if _, ok := visited[w.ID()]; !ok {
+ s = append(s, w.ID()) // S.push(w)
+ }
+ }
+ pmap, _ := g.GetSources(u)
+ for _, w := range pmap {
+ // if w is not visited yet:
+ if _, ok := visited[w.ID()]; !ok {
+ s = append(s, w.ID()) // S.push(w)
+ }
+ }
+ }
+ }
+
+ return rs
+}
+
+// DFSRecursion does depth-first search recursively.
+//
+// 0. DFS(G, v):
+// 1.
+// 2. if v is visited:
+// 3. return
+// 4.
+// 5. label v as visited
+// 6.
+// 7. for each vertex u adjacent to v:
+// 8.
+// 9. if u is not visited yet:
+// 10. recursive DFS(G, u)
+//
+func DFSRecursion(g Graph, id ID) []ID {
+ if g.GetNode(id) == nil {
+ return nil
+ }
+
+ visited := make(map[ID]bool)
+ rs := []ID{}
+
+ dfsRecursion(g, id, visited, &rs)
+
+ return rs
+}
+
+func dfsRecursion(g Graph, id ID, visited map[ID]bool, rs *[]ID) {
+ // base case of recursion
+ //
+ // if v is visited:
+ if _, ok := visited[id]; ok {
+ return
+ }
+
+ // label v as visited
+ visited[id] = true
+ *rs = append(*rs, id)
+
+ // for each vertex u adjacent to v:
+ cmap, _ := g.GetTargets(id)
+ for _, u := range cmap {
+ // if u is not visited yet:
+ if _, ok := visited[u.ID()]; !ok {
+ // recursive DFS(G, u)
+ dfsRecursion(g, u.ID(), visited, rs)
+ }
+ }
+ pmap, _ := g.GetSources(id)
+ for _, u := range pmap {
+ // if u is not visited yet:
+ if _, ok := visited[u.ID()]; !ok {
+ // recursive DFS(G, u)
+ dfsRecursion(g, u.ID(), visited, rs)
+ }
+ }
+}