dfs

package
Version: v1.0.0-...-e1490ca Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 9, 2014 License: BSD-2-Clause Imports: 2 Imported by: 0

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

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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.

Source Files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
t or T : Toggle theme light dark auto
y or Y : Canonical URL