dfs

Documentation

Overview

Package dfs implements the depth-first-search algorithm for the graphs.

The DFS is implemented using on demand calculations, meaning that only that part of the search space will be expanded as requested, iteratively expanding it if needed.

Neighbor traversal order currently is random due to the graph implementation. Specific order may be added in the future.

Example (Usage)

Small API demo based on a trie graph and a few disconnected vertices.

package main

import (
	"fmt"

	"gopkg.in/karalabe/cookiejar.v1/graph"
	"gopkg.in/karalabe/cookiejar.v1/graph/dfs"
)

func main() {
	// Create the graph
	g := graph.New(7)
	g.Connect(0, 1)
	g.Connect(1, 2)
	g.Connect(2, 3)
	g.Connect(3, 4)
	g.Connect(3, 5)

	// Create the depth first search algo structure for g and source node #2
	d := dfs.New(g, 0)

	// Get the path between #0 (source) and #2
	fmt.Println("Path 0->5:", d.Path(5))
	fmt.Println("Order:", d.Order())
	fmt.Println("Reachable #4 #6:", d.Reachable(4), d.Reachable(6))

}

Output:

Path 0->5: [0 1 2 3 5]
Order: [0 1 2 3 5 4]
Reachable #4 #6: true false

Index

• type Dfs
  • func New(g *graph.Graph, src int) *Dfs
  • func (d *Dfs) Order() []int
  • func (d *Dfs) Path(dst int) []int
  • func (d *Dfs) Reachable(dst int) bool

Examples

• Package (Usage)

Types

type Dfs

type Dfs struct {
	// contains filtered or unexported fields
}

Depth-first-search algorithm data structure.

func New

func New(g *graph.Graph, src int) *Dfs

Creates a new random-order dfs structure.

func (*Dfs) Order

func (d *Dfs) Order() []int

Generates the full order in which nodes were traversed.

func (*Dfs) Path

func (d *Dfs) Path(dst int) []int

Generates the path from the source node to the destination.

func (*Dfs) Reachable

func (d *Dfs) Reachable(dst int) bool

Checks whether a given vertex is reachable from the source.