bfstree

README

bfstree

Simple go package providing breadth-first search functions for arbitrary structs

Usage

package main

import (
	"fmt"
	"github.com/bcicen/bfstree"
)

type FlightRoute struct {
	id       int
	fromCity string
	toCity   string
}

// FlightRoute implements the bfstree.Edge interface
func (f FlightRoute) From() string { return f.fromCity }
func (f FlightRoute) To() string   { return f.toCity }

func main() {
	tree := bfstree.New(
		FlightRoute{0, "New York", "Chicago"},
		FlightRoute{1, "New York", "Los Angeles"},
		FlightRoute{2, "Los Angeles", "Houston"},
		FlightRoute{3, "Chicago", "Tokyo"},
	)

	path, err := tree.FindPath("New York", "Tokyo")
	if err != nil {
		panic(err)
	}

	fmt.Println(path)

	for n, edge := range path.Edges() {
		fmt.Printf("flight %d: %s -> %s\n", n+1, edge.From(), edge.To())
	}
}

output:

New York->Chicago->Tokyo
flight 1: New York -> Chicago
flight 2: Chicago -> Tokyo

Documentation

Index

• Variables
• type BFSTree
  • func New(edges ...Edge) *BFSTree
  • func (b *BFSTree) AddEdge(e Edge)
  • func (b *BFSTree) Edges() []Edge
  • func (b *BFSTree) FindPath(start string, end string) (path *Path, err error)
  • func (b *BFSTree) Len() int
  • func (b *BFSTree) Nodes() []string
• type Edge
• type Path
  • func (p *Path) HasNode(s string) bool
  • func (p *Path) IsCircular(edge Edge) bool
  • func (p *Path) Last() Edge
  • func (p *Path) Nodes() []string
  • func (p *Path) String() string

Variables

var (
	Debug = false // enable debug message printing
)

Types

type BFSTree

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

func New

func New(edges ...Edge) *BFSTree

func (*BFSTree) AddEdge

func (b *BFSTree) AddEdge(e Edge)

func (*BFSTree) Edges

func (b *BFSTree) Edges() []Edge

func (*BFSTree) FindPath

func (b *BFSTree) FindPath(start string, end string) (path *Path, err error)

func (*BFSTree) Len

func (b *BFSTree) Len() int

func (*BFSTree) Nodes

func (b *BFSTree) Nodes() []string

Return unique node names

type Edge

type Edge interface {
	From() string
	To() string
}

type Path

type Path struct {
	*BFSTree
}

func (*Path) HasNode

func (p *Path) HasNode(s string) bool

Return whether this path transverses a given node name

func (*Path) IsCircular

func (p *Path) IsCircular(edge Edge) bool

Return whether a given edge, if added, would result in a circular or recursive path

func (*Path) Last

func (p *Path) Last() Edge

func (*Path) Nodes

func (p *Path) Nodes() []string

Returns names for all path nodes in the order they are transversed

func (*Path) String

func (p *Path) String() string