traversal

Documentation

Overview

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Author: anupam.kapoor@gmail.com (Anupam Kapoor)

in this package we try to separate out graph traversal-order from actual procedures which use these traversals.

this file implements the shortest-path for undirected graph using the traversal api's

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Author: anupam.kapoor@gmail.com (Anupam Kapoor)

in this package we try to separate out graph traversal-order from actual procedures which use these traversals.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Author: anupam.kapoor@gmail.com (Anupam Kapoor)

this file implements various traversal orders for a given graph. although mostly applicable for digraphs, we dont enforce it for now...

Index

• Constants
• Variables
• type DFSTraversalOrder
  • func DoDFSTraversals(G graph.GraphOps) *DFSTraversalOrder
  • func (T *DFSTraversalOrder) PostOrder() []int32
  • func (T *DFSTraversalOrder) PreOrder() []int32
  • func (T *DFSTraversalOrder) ReversePost() []int32
• type Edge
  • func (edge Edge) String() string
• type GraphSubsetWalker
  • func BFSGraphSubsetWalker(G graph.GraphOps, source int32) GraphSubsetWalker
  • func DFSGraphSubsetWalker(G graph.GraphOps, source int32) GraphSubsetWalker
• type GraphWalker
  • func BFSGraphWalker(G graph.GraphOps) GraphWalker
  • func DFSGraphWalker(G graph.GraphOps) GraphWalker
• type SingleSourcePaths
  • func SingleSourceShortestPaths(g *graph.Graph, source int32) (ssp *SingleSourcePaths, sp_err error)
  • func (ssp *SingleSourcePaths) PathExists(dest int32) (yesno bool)
  • func (ssp *SingleSourcePaths) PathTo(dest int32) []int32

Constants

const (
	DO_DFS walker_style_t = iota
	DO_BFS                = iota
)

Variables

var (
	EOG  = errors.New("End Of Graph")
	EOGS = errors.New("End Of Graph Subset")
)

Types

type DFSTraversalOrder

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

func DoDFSTraversals

func DoDFSTraversals(G graph.GraphOps) *DFSTraversalOrder

func (*DFSTraversalOrder) PostOrder

func (T *DFSTraversalOrder) PostOrder() []int32

func (*DFSTraversalOrder) PreOrder

func (T *DFSTraversalOrder) PreOrder() []int32

func (*DFSTraversalOrder) ReversePost

func (T *DFSTraversalOrder) ReversePost() []int32

type Edge

type Edge struct {
	Src int32
	Dst int32
}

func (Edge) String

func (edge Edge) String() string

stringified representation of an edge v-w

type GraphSubsetWalker

type GraphSubsetWalker func() (Edge, error)

func BFSGraphSubsetWalker

func BFSGraphSubsetWalker(G graph.GraphOps, source int32) GraphSubsetWalker

this function returns a GraphSubsetWalker function. its repeated invokation traverses all edges in the subset-graph in a breadth-first-order.

an 'EOGS' or end-of-graph-subset is returned, when all edges are visited.

func DFSGraphSubsetWalker

func DFSGraphSubsetWalker(G graph.GraphOps, source int32) GraphSubsetWalker

this function returns a GraphSubsetWalker function. its repeated invokation traverses all edges in the subset-graph in a depth-first-order.

an 'EOGS' or end-of-graph-subset is returned, when all edges are visited.

type GraphWalker

type GraphWalker func() (Edge, error)

func BFSGraphWalker

func BFSGraphWalker(G graph.GraphOps) GraphWalker

this function returns a GraphWalker function type. repeated invokation of which traverses all edges of the graph in a breadth-first-order.

an 'EOG' or end-of-graph is returned when all edges are visited.

func DFSGraphWalker

func DFSGraphWalker(G graph.GraphOps) GraphWalker

this function returns a GraphWalker function type. repeated invokation of which traverses all vertices of the graph in depth-first-order.

an 'EOG' or end-of-graph is returned when all edges are visited.

type SingleSourcePaths

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

this structure represents paths to all vertices in the graph from a given source

func SingleSourceShortestPaths

func SingleSourceShortestPaths(g *graph.Graph, source int32) (ssp *SingleSourcePaths, sp_err error)

determine shortest paths from source to all other vertices in the graph.

func (*SingleSourcePaths) PathExists

func (ssp *SingleSourcePaths) PathExists(dest int32) (yesno bool)

this function returns true if a path-to a given destination node exists, false otherwise.

func (*SingleSourcePaths) PathTo

func (ssp *SingleSourcePaths) PathTo(dest int32) []int32

this function enumerates the path to a given destination from the source node. panics if no path exists...