graph

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

• type Graph
  • func NewGraph() *Graph
  • func (graph *Graph) Draw(name string) (err error)
  • func (graph *Graph) GetDFS() (nodes []*Node)
  • func (graph *Graph) GetNumberOfEdges() (numberOfEdges int)
  • func (graph *Graph) GetNumberOfNodes() int
  • func (graph *Graph) GetNumberOfSCComponents() int
  • func (graph *Graph) GetSCComponents() []*StronglyConnectedComponent
  • func (graph *Graph) InsertEdge(leftNode *Node, rightNode *Node)
  • func (graph *Graph) InsertNode(node *Node)
• type Node
  • func (node *Node) GetInDegree() int
  • func (node *Node) GetInNodes() []*Node
  • func (node *Node) GetOutDegree() int
  • func (node *Node) GetOutNodes() []*Node
  • func (n *Node) String() string
• type StronglyConnectedComponent
• type Value

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.