concrete

package
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Jun 18, 2015 License: Apache-2.0 Imports: 4 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type DenseGraph 

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

A dense graph is a graph such that all IDs are in a contiguous block from 0 to TheNumberOfNodes-1. It uses an adjacency matrix and should be relatively fast for both access and writing.

This graph implements the CrunchGraph, but since it's naturally dense this is superfluous.

func NewDenseGraph 

func NewDenseGraph(numNodes int, passable bool) *DenseGraph

Creates a dense graph with the proper number of nodes. If passable is true all nodes will have an edge with unit cost, otherwise every node will start unconnected (cost of +Inf).

func (*DenseGraph) Cost 

func (g *DenseGraph) Cost(e graph.Edge) float64

func (*DenseGraph) Crunch 

func (g *DenseGraph) Crunch()

DenseGraph is naturally dense, we don't need to do anything

func (*DenseGraph) Degree 

func (g *DenseGraph) Degree(n graph.Node) int

func (*DenseGraph) DirectedEdgeList 

func (g *DenseGraph) DirectedEdgeList() []graph.Edge

func (*DenseGraph) EdgeBetween 

func (g *DenseGraph) EdgeBetween(n, neighbor graph.Node) graph.Edge

func (*DenseGraph) EdgeTo 

func (g *DenseGraph) EdgeTo(n, succ graph.Node) graph.Edge

func (*DenseGraph) Neighbors 

func (g *DenseGraph) Neighbors(n graph.Node) []graph.Node

func (*DenseGraph) NodeExists 

func (g *DenseGraph) NodeExists(n graph.Node) bool

func (*DenseGraph) NodeList 

func (g *DenseGraph) NodeList() []graph.Node

func (*DenseGraph) Predecessors 

func (g *DenseGraph) Predecessors(n graph.Node) []graph.Node

func (*DenseGraph) RemoveEdge 

func (g *DenseGraph) RemoveEdge(e graph.Edge, directed bool)

Equivalent to SetEdgeCost(edge, math.Inf(1), directed)

func (*DenseGraph) SetEdgeCost 

func (g *DenseGraph) SetEdgeCost(e graph.Edge, cost float64, directed bool)

Sets the cost of an edge. If the cost is +Inf, it will remove the edge, if directed is true, it will only remove the edge one way. If it's false it will change the cost of the edge from succ to node as well.

func (*DenseGraph) Successors 

func (g *DenseGraph) Successors(n graph.Node) []graph.Node

type DirectedGraph 

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

A Directed graph is a highly generalized MutableDirectedGraph.

In most cases it's likely more desireable to use a graph specific to your problem domain.

func NewDirectedGraph 

func NewDirectedGraph() *DirectedGraph

func (*DirectedGraph) AddDirectedEdge 

func (g *DirectedGraph) AddDirectedEdge(e graph.Edge, cost float64)

func (*DirectedGraph) AddNode 

func (g *DirectedGraph) AddNode(n graph.Node)

Adds a node to the graph. Implementation note: if you add a node close to or at the max int on your machine NewNode will become slower.

func (*DirectedGraph) Cost 

func (g *DirectedGraph) Cost(e graph.Edge) float64

func (*DirectedGraph) Degree 

func (g *DirectedGraph) Degree(n graph.Node) int

func (*DirectedGraph) EdgeBetween 

func (g *DirectedGraph) EdgeBetween(n, neigh graph.Node) graph.Edge

func (*DirectedGraph) EdgeList 

func (g *DirectedGraph) EdgeList() []graph.Edge

func (*DirectedGraph) EdgeTo 

func (g *DirectedGraph) EdgeTo(n, succ graph.Node) graph.Edge

func (*DirectedGraph) EmptyGraph 

func (g *DirectedGraph) EmptyGraph()

func (*DirectedGraph) Neighbors 

func (g *DirectedGraph) Neighbors(n graph.Node) []graph.Node

func (*DirectedGraph) NewNode 

func (g *DirectedGraph) NewNode() graph.Node

func (*DirectedGraph) NodeExists 

func (g *DirectedGraph) NodeExists(n graph.Node) bool

func (*DirectedGraph) NodeList 

func (g *DirectedGraph) NodeList() []graph.Node

func (*DirectedGraph) Predecessors 

func (g *DirectedGraph) Predecessors(n graph.Node) []graph.Node

func (*DirectedGraph) RemoveDirectedEdge 

func (g *DirectedGraph) RemoveDirectedEdge(e graph.Edge)

func (*DirectedGraph) RemoveNode 

func (g *DirectedGraph) RemoveNode(n graph.Node)

func (*DirectedGraph) Successors 

func (g *DirectedGraph) Successors(n graph.Node) []graph.Node

type Edge 

type Edge struct {
	H, T graph.Node
}

Just a collection of two nodes

func (Edge) Head 

func (e Edge) Head() graph.Node

func (Edge) Tail 

func (e Edge) Tail() graph.Node

type Graph 

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

A GonumGraph is a very generalized graph that can handle an arbitrary number of vertices and edges -- as well as act as either directed or undirected.

Internally, it uses a map of successors AND predecessors, to speed up some operations (such as getting all successors/predecessors). It also speeds up things like adding edges (assuming both edges exist).

However, its generality is also its weakness (and partially a flaw in needing to satisfy MutableGraph). For most purposes, creating your own graph is probably better. For instance, see TileGraph for an example of an immutable 2D grid of tiles that also implements the Graph interface, but would be more suitable if all you needed was a simple undirected 2D grid.

func NewGraph 

func NewGraph() *Graph

func (*Graph) AddNode 

func (g *Graph) AddNode(n graph.Node)

func (*Graph) AddUndirectedEdge 

func (g *Graph) AddUndirectedEdge(e graph.Edge, cost float64)

func (*Graph) Cost 

func (g *Graph) Cost(e graph.Edge) float64

func (*Graph) Degree 

func (g *Graph) Degree(n graph.Node) int

func (*Graph) EdgeBetween 

func (g *Graph) EdgeBetween(n, neigh graph.Node) graph.Edge

func (*Graph) EdgeList 

func (g *Graph) EdgeList() []graph.Edge

func (*Graph) EmptyGraph 

func (g *Graph) EmptyGraph()

func (*Graph) Neighbors 

func (g *Graph) Neighbors(n graph.Node) []graph.Node

func (*Graph) NewNode 

func (g *Graph) NewNode() graph.Node

func (*Graph) NodeExists 

func (g *Graph) NodeExists(n graph.Node) bool

func (*Graph) NodeList 

func (g *Graph) NodeList() []graph.Node

func (*Graph) RemoveNode 

func (g *Graph) RemoveNode(n graph.Node)

func (*Graph) RemoveUndirectedEdge 

func (g *Graph) RemoveUndirectedEdge(e graph.Edge)

type Node 

type Node int

A simple int alias.

func (Node) ID 

func (n Node) ID() int

type TileGraph 

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

func GenerateTileGraph 

func GenerateTileGraph(template string) (*TileGraph, error)

func NewTileGraph 

func NewTileGraph(dimX, dimY int, isPassable bool) *TileGraph

func (*TileGraph) CoordsToID 

func (g *TileGraph) CoordsToID(row, col int) int

func (*TileGraph) CoordsToNode 

func (g *TileGraph) CoordsToNode(row, col int) graph.Node

func (*TileGraph) Cost 

func (g *TileGraph) Cost(e graph.Edge) float64

func (*TileGraph) Degree 

func (g *TileGraph) Degree(n graph.Node) int

func (*TileGraph) Dimensions 

func (g *TileGraph) Dimensions() (rows, cols int)

func (*TileGraph) EdgeBetween 

func (g *TileGraph) EdgeBetween(n, neigh graph.Node) graph.Edge

func (*TileGraph) EdgeList 

func (g *TileGraph) EdgeList() []graph.Edge

func (*TileGraph) IDToCoords 

func (g *TileGraph) IDToCoords(id int) (row, col int)

func (*TileGraph) Neighbors 

func (g *TileGraph) Neighbors(n graph.Node) []graph.Node

func (*TileGraph) NodeExists 

func (g *TileGraph) NodeExists(n graph.Node) bool

func (*TileGraph) NodeList 

func (g *TileGraph) NodeList() []graph.Node

func (*TileGraph) PathString 

func (g *TileGraph) PathString(path []graph.Node) string

func (*TileGraph) SetPassability 

func (g *TileGraph) SetPassability(row, col int, passability bool)

func (*TileGraph) String 

func (g *TileGraph) String() string

type WeightedEdge 

type WeightedEdge struct {
	graph.Edge
	Cost float64
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.