grago

package module
v0.0.0-...-481c0e0 Latest Latest
Warning

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

 Go to latest Published: Feb 15, 2014 License: MIT Imports: 7 Imported by: 0

README

About grago

Implementing some graph algorithms, grago is a package for Go.

Setup
Prerequisites

Make sure you have a working Go installation with version Go 1.1.x or later. See Getting Started

To Install

Run go get github.com/Alejandro131/grago

Examples

Before starting with the code, we have to import the grago package: import "github.com/Alejandro131/grago"

Creating a graph

To create a graph, simply use the NewGraph function which accepts as arguments 3 boolean variables indicating whether the graph will be oriented, weighed and if it is weighed, whether or not there can be negative edges. The following code will create a graph that isn't oriented and is weighed with positive values only: graph := grago.NewGraph(false, true, false)

Adding nodes and edges to it

To add a node or edges, use the functions AddNode and AddLink accordingly:

graph.AddNode("alpha")
graph.AddLink("2", "alpha", 2)

Adding a link which has a node (or 2 nodes) not previously added to the graph, effectively adds the node to the graph, so you don't have to previously initialize all the nodes and add the links later, but rather construct the graph from links.

Using algorithms on the structure

There are popular algorithms in graph theory problems which you can use on the graph structure. Depending on the algorithm, you can expect differently formated output from each of the functions. Below are several examples:

To see the results of the BFS algorithm, you specify a starting node and the function will return a 2D slice with node names, representing the levels of the BFS traverse.

graph := grago.NewGraph(false, true, false)
graph.AddLink("2", "3", 2)
graph.AddLink("2", "4", 5)
graph.AddLink("3", "5", 8)
graph.AddLink("5", "4", 10)

fmt.Println(graph.BFS("2"))

// Output:
// [[2] [3 4] [5]]

To see the results of the DFS algorithm, you specify a starting node and the function will return a slice of Links, representing the edges and nodes in the order they are traversed. The string representation of a Link is start-(weight)->end.

graph := grago.NewGraph(false, true, false)
graph.AddLink("2", "3", 2)
graph.AddLink("2", "4", 5)
graph.AddLink("3", "5", 8)
graph.AddLink("5", "4", 10)

fmt.Println(graph.DFS("2"))

// Output:
// [2-(2)->3 3-(8)->5 5-(10)->4]
Minimum distance between nodes

You can find the minimum distance between a node and other nodes via the MinPaths function which returns a map with keys being node names and value the minimum distance to them.

graph := grago.NewGraph(false, true, false)
graph.AddLink("2", "3", 2)
graph.AddLink("2", "4", 5)
graph.AddLink("3", "5", 8)
graph.AddLink("5", "4", 10)

fmt.Println(graph.MinPaths("2")["5"])
fmt.Println(graph.MinPaths("3")["4"])

// Output:
// 10
// 7
Graph properties

Some graph properties can be checked in the package like whether the graph is planar.

graph := grago.NewGraph(false, true, false)
graph.AddNode("alpha")
graph.AddLink("2", "3", 2)
graph.AddLink("2", "4", 5)
graph.AddLink("3", "5", 8)
graph.AddLink("5", "4", 10)

fmt.Println(graph.IsPlanar())

graph.AddLink("2", "5", 20)
graph.AddLink("3", "4", 15)
graph.AddLink("2", "alpha", 1)
graph.AddLink("3", "alpha", 1)
graph.AddLink("4", "alpha", 1)
graph.AddLink("5", "alpha", 1)

fmt.Println(graph.IsPlanar())

// Output:
// true
// false
Other algorithms

For other available algorithms, look in the files of the package.

Exporting the graph to view in Graphviz

If you want to view the graph you have constructed visually, there is a function which exports it to the dot language format supported by Graphviz. Export receives as an argument a slice of Links which you would like to be highlighted in the graph or if you pass an empty slice, the function will return the plain graph. You also pass whether or not you want the Links to have an index attached to them so that you know the order of traverse. Another option is to group the nodes in clusters which can be passed as a slice of string slices.

Plain graph
graph := grago.NewGraph(false, true, false)
graph.AddNode("alpha")
graph.AddLink("2", "3", 2)
graph.AddLink("2", "4", 5)
graph.AddLink("3", "5", 8)
graph.AddLink("5", "4", 10)

fmt.Println(graph.Export([]grago.Link{}, false, [][]string{}))

// Output:
// graph { "alpha" "2"--"3" [label="2"]; "2"--"4" [label="5"]; "3"--"5" [label="8"]; "5"--"4" [label="10"];}

If you pass the output to Graphviz this will be the resulting image:

Highlighted DFS path from node 2 in the graph
graph := grago.NewGraph(false, true, false)
graph.AddNode("alpha")
graph.AddLink("2", "3", 2)
graph.AddLink("2", "4", 5)
graph.AddLink("3", "5", 8)
graph.AddLink("5", "4", 10)

fmt.Println(graph.Export(graph.DFS("2"), true, [][]string{}))

// Output:
// graph { "alpha" "2"--"3" [label="2 (1)" fontcolor=red color=red]; "2"--"4" [label="5"]; "3"--"5" [label="8 (2)" fontcolor=red color=red]; "5"--"4" [label="10 (3)" fontcolor=red color=red];}

If you pass the output to Graphviz this will be the resulting image:

License

The library is licensed under the MIT License.

Special Thanks

Krzysztof Kowalik - simple implementation of Priority Queue

Documentation

Overview

This package provides a basic graph structure, along with some of the popular algorithms in graph theory.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Graph 

type Graph struct {
	// Whether the graph is oriented or not takes effect on the
	// visual representation as well as edge addition to it.
	Oriented bool

	// If the graph is weighed, the weights will be shown on the
	// exported visualization, otherwise an edge between two nodes
	// will be represented by a weight of 1
	Weighed bool

	// Whether or not the graph has negative weights takes effect
	// on which algorithms to use in some cases like shorted path
	// finding.
	HasNegativeWeights bool
	// contains filtered or unexported fields
}

func NewGraph 

func NewGraph(oriented bool, weighed bool, hasNegativeWeights bool) *Graph

func ReadGraph 

func ReadGraph(in string, reversed bool) *Graph

Creates a graph, read from a string with an expected input format such as: <oriented> <weighed> <hasNegativeWeights> - booleans <node> - for adding a node <node> -- <node> [<weight>] - for adding a link If 'reversed' is true, the graph will be constructed with reversed edges.

Example 
data, _ := ioutil.ReadFile("exampleGraph.txt")
graph := ReadGraph(string(data), false)

fmt.Println(graph)

Output:

true true false
alpha
2
3
2 -- 3 2

func (g *Graph) AddLink(startNode fmt.Stringer, endNode fmt.Stringer, weight int) bool

Tries to add a link between two nodes and returns true if successful, otherwise returns false if such a link already exists.

Note: If the graph isn't oriented adding a link from A to B effectively adds a link from B to A.

func (*Graph) AddNode 

func (g *Graph) AddNode(node fmt.Stringer) bool

Tries to add a node to the graph and returns true if successful, otherwise returns false if the node already exists.

Example 
graph := NewGraph(false, true, false)

fmt.Println(graph.AddNode(stringer("a")))
fmt.Println(graph.AddNode(stringer("a")))
fmt.Println(graph.AddNode(stringer("b")))

Output:

true
false
true

func (*Graph) BFS 

func (g *Graph) BFS(start fmt.Stringer) [][]fmt.Stringer

Traverses the graph in a manner of breadth first search and returns a slice of slices of node names, representing the layers of nodes during the search, with the first layer with index 0 containing the initial node.

Example 
fmt.Println(createGrapht().BFS(stringer("2")))

Output:

[[2] [3 4] [5]]

func (*Graph) ConnectedComponents 

func (g *Graph) ConnectedComponents() [][]fmt.Stringer

Return a slice of slices where are given the nodes in each separate strongly connected component.

Example 
fmt.Println(createGraphc().ConnectedComponents())
fmt.Println(createGraphc2().ConnectedComponents())

Output:

[[3 4 5 2] [alpha]]
[[2] [3] [5] [4] [alpha]]

func (*Graph) DFS 

func (g *Graph) DFS(start fmt.Stringer) []Link

Traverses the graph in a manner of depth first search and returns a slice of links through which it goes during the search.

Example 
fmt.Println(createGrapht().DFS(stringer("2")))

Output:

[2-(2)->3 3-(8)->5 5-(10)->4]

func (Graph) EulerPath 

func (g Graph) EulerPath() []Link

Returns a slice of links representing an Eulearian path. If no such path exists, returns an empty slice. This algorithm works for undirected graphs for now.

Note: An Eulerian path is such that it traverses through every edge exactly once.

Example 
fmt.Println(createGraphsp().EulerPath())
fmt.Println(createGraphsp2().EulerPath())

Output:

[3-(8)->5 5-(10)->4 4-(5)->2 2-(2)->3]
[]

func (*Graph) Export 

func (g *Graph) Export(highlights []Link, ordered bool, clusters [][]fmt.Stringer) string

Export the graph structure in a format specified by the dot language used in graphviz, which can be loaded by the software and visualized. 'highlights' is a slice of links representing edges of the graph you would like to outline, for example the results of a DFS search and they will be colored red. 'ordered' is a boolean indicating whether or not the index of the links would be shown next to their name which is useful for distinguishing DFS from MST for example. 'clusters' is a 2d array of fmt.Stringers representing nodes that should be ordered in separate groups visually, if it's empty, the graph will be displayed as is.

Example 
graph := createGraphex()

fmt.Println(graph.Export([]Link{}, false, [][]fmt.Stringer{}))
fmt.Println(graph.Export(graph.DFS(stringer("2")), true, [][]fmt.Stringer{}))

Output:

graph {"alpha" "2" "3" "4" "5" "2"--"3" [label="2"]; "2"--"4" [label="5"]; "3"--"5" [label="8"]; "4"--"5" [label="10"]; }
graph {"2"--"3" [fontcolor=red color=red label="2 (1)"]; "3"--"5" [fontcolor=red color=red label="8 (2)"]; "5"--"4" [fontcolor=red color=red label="10 (3)"]; "alpha" "2"--"4" [label="5"]; }

func (*Graph) Floyd 

func (g *Graph) Floyd() map[fmt.Stringer]map[fmt.Stringer]int

Returns a matrix of node names, where you can find the minimum distance between two nodes, given their names.

Example 
paths := createGraphd().Floyd()

fmt.Println(paths[stringer("2")][stringer("5")])
fmt.Println(paths[stringer("3")][stringer("4")])

Output:

10
7

func (*Graph) HamiltonPath 

func (g *Graph) HamiltonPath() []Link

Returns a slice of links representing an Hamiltonian path. If no such path exists, returns an empty slice.

Note: A Hamiltonian path is such that it traverses through every vertex exactly once.

Example 
graph := createGraphsp()

fmt.Println(graph.HamiltonPath())

graph.RemoveNode(stringer("alpha"))

fmt.Println(graph.HamiltonPath())

Output:

[]
[2-(2)->3 3-(8)->5 5-(10)->4]

func (*Graph) HasCycle 

func (g *Graph) HasCycle() bool

Returns a boolean value of whether or not the graph contains atleast one cycle, which means that some edges form a closed circle.

Example 
fmt.Println(createGraphpr().HasCycle())
fmt.Println(createGraphpr2().HasCycle())
fmt.Println(createGraphpr3().HasCycle())

Output:

true
true
false

func (*Graph) IncomingLinksCount 

func (g *Graph) IncomingLinksCount(node fmt.Stringer) int

Returns the count of the links which have as an ending node the one specified as a parameter.

Note: If the graph isn't oriented the outgoing links will always match the incoming links.

Example 
graph := createGraph()

fmt.Println(graph.IncomingLinksCount(stringer("alpha")))
fmt.Println(graph.IncomingLinksCount(stringer("2")))
fmt.Println(graph.IncomingLinksCount(stringer("3")))

Output:

1
3
2

func (*Graph) IsBipartite 

func (g *Graph) IsBipartite() bool

Returns a boolean value of whether or not the graph is bipartite, which means that it's vertices can be split into two groups where there aren't any edges between vertices of the same group.

Example 
graph := createGraphpr()

fmt.Println(createGraphpr2().IsBipartite())
fmt.Println(graph.IsBipartite())

graph.AddLink(stringer("2"), stringer("5"), 20)

fmt.Println(graph.IsBipartite())

Output:

true
true
false

func (*Graph) IsPlanar 

func (g *Graph) IsPlanar() bool

Returns a boolean value of whether or not the graph is planar, which means that it can be drawn on a piece of paper with no two edges crossing.

Example 
graph := createGraphpr()
graph.RemoveNode(stringer("alpha"))

fmt.Println(graph.IsPlanar())

graph.AddLink(stringer("2"), stringer("5"), 20)
graph.AddLink(stringer("3"), stringer("4"), 15)
graph.AddLink(stringer("2"), stringer("alpha"), 1)
graph.AddLink(stringer("3"), stringer("alpha"), 1)
graph.AddLink(stringer("4"), stringer("alpha"), 1)
graph.AddLink(stringer("5"), stringer("alpha"), 1)

fmt.Println(graph.IsPlanar())

Output:

true
false

func (g *Graph) Links() []Link

Returns a slice with the all the links in the graph.

func (*Graph) MST 

func (g *Graph) MST() []Link

Returns a slice of the links constructing the minimal spanning tree for the given graph, according to Kruskal's algorithm.

Example 
fmt.Println(createGraphm().MST())

Output:

[2-(2)->3 2-(5)->4 5-(8)->3]

func (*Graph) MaxFlow 

func (g *Graph) MaxFlow(source fmt.Stringer, sink fmt.Stringer) int

Returns the maximum ammount that can flow from the source to the sink for 1 period of time according to the min-cut max-flow algorithm.

Example 
graph := createGraphmf()

fmt.Println(graph.MaxFlow(stringer("2"), stringer("5")))
fmt.Println(graph.MaxFlow(stringer("3"), stringer("4")))
fmt.Println(graph.MaxFlow(stringer("alpha"), stringer("4")))

Output:

7
10
0

func (*Graph) MinPaths 

func (g *Graph) MinPaths(start fmt.Stringer) map[fmt.Stringer]int

Returns a map bound by node name, containing the minimum distance between the given node and all of the other nodes. Internally it chooses between Dijkstra's and Ford Bellman's algorithms depending on whether the graph has negative weights or not.

Example (Dijkstra) 
graph := createGraphd()

fmt.Println(graph.MinPaths(stringer("2"))[stringer("5")])
fmt.Println(graph.MinPaths(stringer("3"))[stringer("4")])

Output:

10
7
Example (FordBellman) 
graph := createGraphNegative()

fmt.Println(graph.MinPaths(stringer("2"))[stringer("5")])
fmt.Println(graph.MinPaths(stringer("3"))[stringer("4")])

Output:

5
-3

func (*Graph) Nodes 

func (g *Graph) Nodes() []fmt.Stringer

Returns a slice with all the nodes in the graph.

Example 
fmt.Println(createGraph().Nodes())

Output:

[alpha 2 3 4 5]

func (*Graph) OutgoingLinksCount 

func (g *Graph) OutgoingLinksCount(node fmt.Stringer) int

Returns the count of the links which have as a starting node the one specified as a parameter.

Note: If the graph isn't oriented the outgoing links will always match the incoming links.

Example 
graph := createGraph()

fmt.Println(graph.OutgoingLinksCount(stringer("alpha")))
fmt.Println(graph.OutgoingLinksCount(stringer("2")))
fmt.Println(graph.OutgoingLinksCount(stringer("3")))

Output:

1
3
2

func (*Graph) ReachableNodes 

func (g *Graph) ReachableNodes(node fmt.Stringer) []fmt.Stringer

Return a slice of all nodes to which a path exists from the node provided as a parameter.

Example 
graph := createGraphc()

fmt.Println(graph.ReachableNodes(stringer("2")))
fmt.Println(graph.ReachableNodes(stringer("alpha")))

Output:

[3 4 5]
[]

func (g *Graph) RemoveLink(startNode fmt.Stringer, endNode fmt.Stringer) bool

Tries to remove the link from the graph and if successful returns true, otherwise if the link doesn't exist, returns false.

Note: If the graph isn't oriented removing the link from A to B effectively removes the link from B to A.

func (*Graph) RemoveNode 

func (g *Graph) RemoveNode(node fmt.Stringer) bool

Tries to remove the node from the graph and if successful removes all links between it and other nodes and returns true, otherwise if the node doesn't exist, returns false.

Example 
graph := NewGraph(false, true, false)

graph.AddNode(stringer("a"))

fmt.Println(graph.RemoveNode(stringer("a")))
fmt.Println(graph.RemoveNode(stringer("a")))
fmt.Println(graph.RemoveNode(stringer("b")))

Output:

true
false
false

func (*Graph) String 

func (g *Graph) String() string

A string representation of Graph, with an output format like the input format: <oriented> <weighed> <hasNegativeWeights> - booleans <node> - all nodes in the graph each on a separate line <node> -- <node> [<weight>] - for all the links

Example 
data, _ := ioutil.ReadFile("exampleGraph.txt")
graph := ReadGraph(string(data), false)

fmt.Println(graph)

Output:

true true false
alpha
2
3
2 -- 3 2

type Interface 

type Interface interface {
	Less(other interface{}) bool
}

Only items implementing this interface can be enqueued on the priority queue. 

type Link struct {
	Start   fmt.Stringer
	End     fmt.Stringer
	Weighed bool
	Weight  int
}
func NewLink(start fmt.Stringer, end fmt.Stringer, weighed bool, weight int) *Link

func (*Link) Less 

func (l *Link) Less(other interface{}) bool

Interface for the priority queue for Link

func (Link) String 

func (l Link) String() string

A string representation of Link used for output.

Example 
fmt.Println(NewLink(stringer("1"), stringer("4"), true, 23))
fmt.Println(NewLink(stringer("1"), stringer("4"), false, 321321))

Output:

1-(23)->4
1--4

type Node 

type Node struct {
	// A container for all the nodes, that this node has an
	// outgoing connection to.
	Adjacent map[fmt.Stringer]int
}

func NewNode 

func NewNode() *Node

func (*Node) AdjacentNodes 

func (n *Node) AdjacentNodes() []fmt.Stringer

Returns a slice of the nodes this node has an edge to.

Example 
node := NewNode()
node.Adjacent[stringer("2")] = 1
node.Adjacent[stringer("5")] = 234

fmt.Println(node.AdjacentNodes())

Output:

[2 5]

type Queue 

type Queue struct {
	Limit int
	// contains filtered or unexported fields
}

Queue is a threadsafe priority queue exchange. Here's a trivial example of usage: 

q := pqueue.New(0)
go func() {
    for {
        task := q.Dequeue()
        println(task.(*CustomTask).Name)
    }
}()
for i := 0; i < 100; i := 1 {
    task := CustomTask{Name: "foo", priority: rand.Intn(10)}
    q.Enqueue(&task)
}

func NewPriorityQueue 

func NewPriorityQueue(max int) (q *Queue)

New creates and initializes a new priority queue, taking a limit as a parameter. If 0 given, then queue will be unlimited.

func (*Queue) ChangeLimit 

func (q *Queue) ChangeLimit(newLimit int)

Safely changes enqueued items limit. When limit is set to 0, then queue is unlimited.

func (*Queue) Dequeue 

func (q *Queue) Dequeue() (item Interface)

Dequeue takes an item from the queue. If queue is empty then should block waiting for at least one item.

func (*Queue) Enqueue 

func (q *Queue) Enqueue(item Interface) (err error)

Enqueue puts given item to the queue.

func (*Queue) IsEmpty 

func (q *Queue) IsEmpty() bool

IsEmpty returns true if queue is empty.

func (*Queue) Len 

func (q *Queue) Len() int

Len returns number of enqueued elemnents.

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.