graph

package
Version: v0.0.0-...-433e763 Latest Latest
Warning

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

Go to latest
Published: Aug 23, 2016 License: BSD-3-Clause Imports: 8 Imported by: 2

Documentation

Overview

Copyright (c) 2015-2016 The GoAnalysis Authors. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Graph

type Graph struct {
	Root  *Node            //First node added to the graph.
	Nodes map[string]*Node //All nodes in the graph.
	// contains filtered or unexported fields
}

Graph is the main data-structure representing the graph. Holding references to the root node and all nodes in the graph.

func NewGraph

func NewGraph() *Graph

NewGraph initialize and returns a pointer to a new graph object.

func (*Graph) Draw

func (graph *Graph) Draw(name string) (err error)

Draw writes the graph to file according to the Graphviz (www.graphviz.org) format and tries to compile the graph to PDF by using dot.

func (*Graph) GetDFS

func (graph *Graph) GetDFS() (nodes []*Node)

GetDFS performs depth first search in the 'graph' and returns the result in 'nodes'.

func (*Graph) GetNumberOfEdges

func (graph *Graph) GetNumberOfEdges() (numberOfEdges int)

GetNumberOfEdges returns number of edges in 'graph'.

func (*Graph) GetNumberOfNodes

func (graph *Graph) GetNumberOfNodes() int

GetNumberOfNodes returns number of nodes in 'graph'.

func (*Graph) GetNumberOfSCComponents

func (graph *Graph) GetNumberOfSCComponents() int

GetNumberOfSCComponents return number of strongly connected components in 'graph'.

func (*Graph) GetSCComponents

func (graph *Graph) GetSCComponents() []*StronglyConnectedComponent

GetSCComponents performs Tarjans algorithm to detect strongly connected components in 'graph', returns a list of lists containing nodes in each strongly connected component.

func (*Graph) InsertEdge

func (graph *Graph) InsertEdge(leftNode *Node, rightNode *Node)

InsertEdge inserts directed edge between leftNode and rightNode. It also inserts the node in the graph correctly if the node does not already exist in the graph.

func (*Graph) InsertNode

func (graph *Graph) InsertNode(node *Node)

type Node

type Node struct {
	Value //Holds node interface value.
	// contains filtered or unexported fields
}

Node represents a single node in the graph, holding the node value.

func (*Node) GetInDegree

func (node *Node) GetInDegree() int

GetInDegree returns number of ingoing edges to 'node'.

func (*Node) GetInNodes

func (node *Node) GetInNodes() []*Node

func (*Node) GetOutDegree

func (node *Node) GetOutDegree() int

GetOutDegree returns number of outgoing edges from 'node'.

func (*Node) GetOutNodes

func (node *Node) GetOutNodes() []*Node

func (*Node) String

func (n *Node) String() string

Returning back the interface function from NodeValue.

type StronglyConnectedComponent

type StronglyConnectedComponent struct {
	Nodes []*Node
}

StronglyConnectedComponent holds a set of nodes in a strongly connected components.

type Value

type Value interface {
	UID() string
	String() string
}

All node-values in a graph implements the Value interface.

Source Files

Directories

Path Synopsis
Package graph.stack provides an implementation of the Stack abstract-datastructure, basically providing the standard graph.stack operating primitives.
Package graph.stack provides an implementation of the Stack abstract-datastructure, basically providing the standard graph.stack operating primitives.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL