graph

package
Version: v0.0.0-...-6b870f6 Latest Latest
Warning

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

Go to latest
Published: Mar 1, 2014 License: BSD-2-Clause Imports: 7 Imported by: 0

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)

provides adjacency list based implementation of directed graphs or digraphs.

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)

commonly non-exported functions used in processing graphs.

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)

provides adjacency list based implementation of undirected graphs

this file contains the exported graph interface

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)

provides adjacency list based implementation of undirected graphs

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func ReverseAdjList

func ReverseAdjList(G GraphOps)

reverse adj-list for a given graph. required since we swithced to a slice based represenstation of adjacency list, where destination vertices are appended rather than pre-pended

Types

type Digraph

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

adjacency list representation of a Graph, which contains 'V' vertices and 'E' edges. vertices are in the range {0, V-1} for ease of processing

func CreateDigraph

func CreateDigraph(V int32) *Digraph

this function is called to create a new skeleton graph, with a specific number of vertices

func LoadDigraphFromFile

func LoadDigraphFromFile(fname string) (g *Digraph, err error)

this is a convenience interface over LoadGraph(...) to create a graph from its serialized definition stored in a file identified by 'fname'

func LoadDigraphFromReader

func LoadDigraphFromReader(src *bufio.Reader) (new_graph *Digraph, err error)

this function is called to create a graph from it's serialized definition.

func (*Digraph) AddEdge

func (G *Digraph) AddEdge(v, w int32)

in a digraph G, add an edge between vertices 'v' and 'w'.

func (*Digraph) Adj

func (G *Digraph) Adj(v int32) []int32

func (*Digraph) AverageDegree

func (G *Digraph) AverageDegree() float64

func (*Digraph) Degree

func (G *Digraph) Degree(v int32) int32

enumerate some fundamental properties of a graph

func (*Digraph) E

func (G *Digraph) E() int32

func (*Digraph) MaxDegree

func (G *Digraph) MaxDegree() int32

func (*Digraph) Reverse

func (G *Digraph) Reverse() (RevG *Digraph)

return the reverse of a digraph i.e. adjacency list of each vertex is reversed

func (*Digraph) Serialize

func (G *Digraph) Serialize() string

this function emits the graph structure in a format suitable for subsequent loading from LoadFromXXX(...) invokation

func (*Digraph) String

func (G *Digraph) String() string

pretty print a digraph structure.

func (*Digraph) V

func (G *Digraph) V() int32

type Graph

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

adjacency list representation of a Graph, which contains 'V' vertices and 'E' edges. vertices are in the range {0, V-1} for ease of processing

func LoadFromFile

func LoadFromFile(fname string) (g *Graph, err error)

this is a convenience interface over LoadGraph(...) to create a graph from its serialized definition stored in a file identified by 'fname'

func LoadFromReader

func LoadFromReader(src *bufio.Reader) (new_graph *Graph, err error)

this function is called to create a graph from it's serialized definition.

func New

func New(V int32) *Graph

this function is called to create a new skeleton graph, with a specific number of vertices

func (*Graph) AddEdge

func (G *Graph) AddEdge(v, w int32)

in a graph G, add an edge between vertices 'v' and 'w'. for undirected graphs, this operation adds v-w, and w-v edges as well

func (*Graph) Adj

func (G *Graph) Adj(v int32) []int32

func (*Graph) AverageDegree

func (G *Graph) AverageDegree() float64

func (*Graph) Degree

func (G *Graph) Degree(v int32) int32

enumerate some fundamental properties of a graph

func (*Graph) E

func (G *Graph) E() int32

func (*Graph) MaxDegree

func (G *Graph) MaxDegree() int32

func (*Graph) Serialize

func (G *Graph) Serialize() string

this function emits the graph structure in a format suitable for subsequent loading from LoadFromXXX(...) invokation

func (*Graph) String

func (G *Graph) String() string

func (*Graph) V

func (G *Graph) V() int32

type GraphOps

type GraphOps interface {
	V() int32          // number of vertices
	E() int32          // number of edges
	Adj(int32) []int32 // adjacency list
}

a set of typically used operations on graphs

Directories

Path Synopsis
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.

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