graphs

package
v0.0.0-...-08da8a6 Latest Latest
Warning

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

 Go to latest Published: Apr 30, 2020 License: MIT Imports: 6 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func CompareDirectedEdges 

func CompareDirectedEdges(e1, e2 interface{}) int

CompareDirectedEdges compares edges

func CompareEdges 

func CompareEdges(e1, e2 interface{}) int

CompareEdges compares edges

Types

type DirectedGraph 

type DirectedGraph struct {
	UnDirectedGraph
	// contains filtered or unexported fields
}

DirectedGraph defines a directed graph

func NewDirectedGraph 

func NewDirectedGraph(vertexCount int) *DirectedGraph

NewDirectedGraph initalises a new directed graph with vertexCount vertices.

func (*DirectedGraph) AddEdge 

func (d *DirectedGraph) AddEdge(vertex1, vertex2 int) error

AddEdge adds an edge to the graph

func (*DirectedGraph) GetCyclicPath 

func (d *DirectedGraph) GetCyclicPath() (path []int)

GetCyclicPath gets a cyclic path in the graph, if not found, return nil.

func (*DirectedGraph) GetOrder 

func (d *DirectedGraph) GetOrder() (pre, post, reversePost []int)

GetOrder get vertex orders (pre, post and reverse-post[topology])

func (*DirectedGraph) GetStronglyConnectedComponent 

func (d *DirectedGraph) GetStronglyConnectedComponent() (stronglyConnectedComponent [][]int)

GetStronglyConnectedComponent gets all strongly connected component, each component contains a set of vertices It uses Kosaraju’s algorithm. (Reverse Graph -> Reverse Post Order -> DFS)

func (*DirectedGraph) GetTopologyOrder 

func (d *DirectedGraph) GetTopologyOrder() (topology []int)

GetTopologyOrder get topology order.

func (*DirectedGraph) GetVertexInDegree 

func (d *DirectedGraph) GetVertexInDegree(vertex int) (int, error)

GetVertexInDegree gets in degree for a given vertex

func (*DirectedGraph) GetVertexOutDegree 

func (d *DirectedGraph) GetVertexOutDegree(vertex int) (int, error)

GetVertexOutDegree gets the out degree of a given vertex

func (*DirectedGraph) Reverse 

func (d *DirectedGraph) Reverse() (uv *DirectedGraph)

Reverse reversees a directed graph, a.k.a revere all edges.

type DirectedWeightedEdge 

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

DirectedWeightedEdge defines a weighted edge

func (*DirectedWeightedEdge) Compare 

func (d *DirectedWeightedEdge) Compare(d1 DirectedWeightedEdge) int

Compare compares the weight of two edges.

func (*DirectedWeightedEdge) GetFrom 

func (d *DirectedWeightedEdge) GetFrom() int

GetFrom gets the starting vertex

func (*DirectedWeightedEdge) GetTo 

func (d *DirectedWeightedEdge) GetTo() int

GetTo gets the ending vertex

func (*DirectedWeightedEdge) GetWeight 

func (d *DirectedWeightedEdge) GetWeight() float64

GetWeight gets the weight on the edge

func (*DirectedWeightedEdge) Print 

func (d *DirectedWeightedEdge) Print() string

Print prints the edge.

type DirectedWeightedGraph 

type DirectedWeightedGraph struct {
	DirectedGraph
	// contains filtered or unexported fields
}

DirectedWeightedGraph defines a directed wegithed graph

func NewDirectedWeightedGraph 

func NewDirectedWeightedGraph(vertexCount int) *DirectedWeightedGraph

NewDirectedWeightedGraph initalises a new directed weighted graph with vertexCount vertices.

func (*DirectedWeightedGraph) AddEdge 

func (d *DirectedWeightedGraph) AddEdge(from, to int, weight float64) error

AddEdge adds an edge to the directed weighted graph

func (*DirectedWeightedGraph) DijkstraShortestPath 

func (d *DirectedWeightedGraph) DijkstraShortestPath(s, v int) (path []DirectedWeightedEdge, distance float64, err error)

DijkstraShortestPath gets the shortest path (mimimum weight) from a start vertex to an end vertex

func (*DirectedWeightedGraph) GetAdjacentEdges 

func (d *DirectedWeightedGraph) GetAdjacentEdges(vertex int) ([]DirectedWeightedEdge, error)

GetAdjacentEdges gets all adjacent edges for a given vertex

func (*DirectedWeightedGraph) GetAdjacentVertices 

func (d *DirectedWeightedGraph) GetAdjacentVertices(vertex int) ([]int, error)

GetAdjacentVertices gets all adjacent vertices for a given vertex

func (*DirectedWeightedGraph) GetEdges 

func (d *DirectedWeightedGraph) GetEdges() []DirectedWeightedEdge

GetEdges prints all edges.

func (*DirectedWeightedGraph) Print 

func (d *DirectedWeightedGraph) Print() string

Print prints the graph.

func (*DirectedWeightedGraph) Reverse 

func (d *DirectedWeightedGraph) Reverse() (uv *DirectedWeightedGraph)

Reverse reversees a directed graph, a.k.a revere all edges.

type Graph 

type Graph interface {
	GetVertexCount() int
	GetEdgeCount() int
	GetAdjacentVertices(vertex int) ([]int, error)
	GetBFSPath(verext1, vertex2 int) ([]int, error)
}

Graph defines a graph interface

type TransitiveClousure 

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

TransitiveClousure presents a transitive clousure.

func NewTransitiveClousure 

func NewTransitiveClousure(dGraph Graph) *TransitiveClousure

NewTransitiveClousure creates a transitive clousure from a given directed graph.

type UnDirectedGraph 

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

UnDirectedGraph defines a undirected graph

func NewUnDirectedGraph 

func NewUnDirectedGraph(vertexCount int) *UnDirectedGraph

NewUnDirectedGraph initalises a new undirected graph with vertexCount vertices.

func (*UnDirectedGraph) AddEdge 

func (u *UnDirectedGraph) AddEdge(vertex1, vertex2 int) error

AddEdge adds an edge to the graph

func (*UnDirectedGraph) BFS 

func (u *UnDirectedGraph) BFS(startingVertex int) (vertices []int, err error)

BFS does a breadth first search starting from startingVertex in graph

func (*UnDirectedGraph) DFS 

func (u *UnDirectedGraph) DFS(startingVertex int) (vertices []int, err error)

DFS does a depth first search

func (*UnDirectedGraph) DFSRecursively 

func (u *UnDirectedGraph) DFSRecursively(startingVertex int) (vertices []int, err error)

DFSRecursively does a dfs search using rescursive method

func (*UnDirectedGraph) GetAdjacentVertices 

func (u *UnDirectedGraph) GetAdjacentVertices(vertex int) ([]int, error)

GetAdjacentVertices gets all adjacent vertices for a given vertex

func (*UnDirectedGraph) GetBFSPath 

func (u *UnDirectedGraph) GetBFSPath(startingVertex int, endingVertex int) (path []int, err error)

GetBFSPath gets the BFS path from startingVertex to endingVertex. Using BFS, the path is also the mimimum path (mimimum number of edges).

func (*UnDirectedGraph) GetBipartiteParts 

func (u *UnDirectedGraph) GetBipartiteParts() (parts [][]int)

GetBipartiteParts gets the two parties if the graph is a bi-partite graph

func (*UnDirectedGraph) GetConnectedComponents 

func (u *UnDirectedGraph) GetConnectedComponents() (connectedCompoent [][]int)

GetConnectedComponents gets all the connected component of a graph

func (*UnDirectedGraph) GetCyclicPath 

func (u *UnDirectedGraph) GetCyclicPath() (path []int)

GetCyclicPath gets a cyclic path in the graph, if not found, return nil.

func (*UnDirectedGraph) GetDFSPath 

func (u *UnDirectedGraph) GetDFSPath(startingVertex int, endingVertex int) (path []int, err error)

GetDFSPath gets the path from startingVertex to endingVertex using DFS

func (*UnDirectedGraph) GetEdgeCount 

func (u *UnDirectedGraph) GetEdgeCount() int

GetEdgeCount gets the edge count

func (*UnDirectedGraph) GetVertexCount 

func (u *UnDirectedGraph) GetVertexCount() int

GetVertexCount gets vertex count

func (*UnDirectedGraph) GetVertexDegree 

func (u *UnDirectedGraph) GetVertexDegree(vertex int) (int, error)

GetVertexDegree gets the degree of a given vertex

func (*UnDirectedGraph) HasCycle 

func (u *UnDirectedGraph) HasCycle() bool

HasCycle using union-find method to find whether there is cycle.

func (*UnDirectedGraph) Print 

func (u *UnDirectedGraph) Print() string

Print prints the graph.

type UnDirectedWeightGraph 

type UnDirectedWeightGraph struct {
	UnDirectedGraph
	// contains filtered or unexported fields
}

UnDirectedWeightGraph defines a undirected graph

func NewUnDirectedWeightedGraph 

func NewUnDirectedWeightedGraph(vertexCount int) *UnDirectedWeightGraph

NewUnDirectedWeightedGraph initalises a new undirected weighted graph with vertexCount vertices.

func (*UnDirectedWeightGraph) AddEdge 

func (u *UnDirectedWeightGraph) AddEdge(vertex1, vertex2 int, weight float64) error

AddEdge adds an edge to the graph

func (*UnDirectedWeightGraph) GetEdges 

func (u *UnDirectedWeightGraph) GetEdges() []WeightedEdge

GetEdges prints all edges.

func (*UnDirectedWeightGraph) LazyPrimMinimumSpanningTree 

func (u *UnDirectedWeightGraph) LazyPrimMinimumSpanningTree() ([]WeightedEdge, float64)

LazyPrimMinimumSpanningTree gets the mimimum spanning tree of the give directed weighted graph.

func (*UnDirectedWeightGraph) Print 

func (u *UnDirectedWeightGraph) Print() string

Print prints the graph.

type WeightedEdge 

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

WeightedEdge defines a weighted edge

func (*WeightedEdge) Compare 

func (w *WeightedEdge) Compare(w1 WeightedEdge) int

Compare compares the weight of two edges.

func (*WeightedEdge) GetOther 

func (w *WeightedEdge) GetOther(vertex int) (int, error)

GetOther gets the other vertex based on the given vertex of the edge.

func (*WeightedEdge) GetVertex1 

func (w *WeightedEdge) GetVertex1() int

GetVertex1 gets of the vertex of the edge.

func (*WeightedEdge) GetWeight 

func (w *WeightedEdge) GetWeight() float64

GetWeight gets the weight on the edge

func (*WeightedEdge) Print 

func (w *WeightedEdge) Print() string

Print prints the edge.

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.