graph

package

v0.0.0-...-6b870f6 Latest Latest Go to latest Published: Mar 1, 2014 License: BSD-2-Clause Imports: 7 Imported by: 0

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/anupamk/common-utilz

Links

Open Source Insights

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

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

Source Files ¶

View all Source files

Directories ¶

Path	Synopsis
algorithms 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.
applications 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.
bfs 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.
dfs 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.
symbol_graph 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 menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL