graphs

package
v0.1.3 Latest Latest
Warning

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

 Go to latest Published: Jun 22, 2024 License: Apache-2.0 Imports: 11 Imported by: 0

README

Ring detection

func ExampleDigraph_FindCycle() {
	// (0)-------->(2)
	//  | ^         ^
	//  |  \        |
	//  |   ------  |
	//  |         \ |
	//  v          \|
	// (1)-------->(3)
	g := NewDigraph(4)
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 3)
	g.AddEdge(3, 0)
	g.AddEdge(3, 2)
	c := g.FindCycle()
	fmt.Println(c.Error())

	// Output: (distance=3): 0->1, 1->3, 3->0,
}

Topological sort

figure1

func ExampleDigraph_Topological() {
	dg, err := LoadDigraph(`.\testdata\no_cycle.yml`)
	if err != nil {
		panic(err)
	}
	for _, vet := range dg.Topological().Drain() {
		fmt.Printf("%d->", vet)
	}

	// Output: 5->1->3->6->4->7->0->2->
}

Bipartite

func ExampleDigraph_Bipartite() {
	dg, err := LoadDigraph(`.\testdata\no_cycle.yml`)
	if err != nil {
		panic(err)
	}
	fmt.Println(dg.Bipartite())

	// Output: []
}

Reachable

func ExampleReachable() {
	dg, err := LoadDigraph(`.\testdata\no_cycle.yml`)
	if err != nil {
		panic(err)
	}
	reach := dg.Reachable()
	fmt.Println(reach.CanReach(5, 2))
	fmt.Println(reach.CanReach(2, 5))

	// Output:
	// true
	// false
}

BFS

func ExampleBFS() {
	dg, err := LoadDigraph(`.\testdata\no_cycle.yml`)
	if err != nil {
		panic(err)
	}
	bfs := dg.BFS(1)
	fmt.Println(bfs.CanReach(5))
	fmt.Println(bfs.ShortestPathTo(2).Str(nil))

	// Output:
	// false
	// (distance=3): 1->3, 3->6, 6->2,
}

Strongly connected components

func ExampleSCC() {
	g := NewDigraph(13)
	g.AddEdge(0, 1)
	g.AddEdge(0, 5)
	g.AddEdge(5, 4)
	g.AddEdge(4, 3)
	g.AddEdge(4, 2)
	g.AddEdge(3, 2)
	g.AddEdge(2, 3)
	g.AddEdge(2, 0)
	g.AddEdge(6, 0)
	g.AddEdge(6, 4)
	g.AddEdge(6, 9)
	g.AddEdge(9, 10)
	g.AddEdge(10, 12)
	g.AddEdge(12, 9)
	g.AddEdge(9, 11)
	g.AddEdge(11, 12)
	g.AddEdge(11, 4)
	g.AddEdge(7, 6)
	g.AddEdge(7, 8)
	g.AddEdge(8, 7)
	g.AddEdge(8, 9)
	scc := g.SCC()
	fmt.Println("amount of strongly connected component:", scc.NumComponents())
	var vertices []int
	scc.IterComponent(0, func(v int) bool {
		vertices = append(vertices, v)
		return true
	})
	sort.Shell(vertices)
	fmt.Println("vertices strongly connected with 0:", vertices)
	fmt.Println(scc.IsStronglyConn(0, 6))

	// Output:
	// amount of strongly connected component: 5
	// vertices strongly connected with 0: [0 2 3 4 5]
	// false
}

Minimum spanning tree

func Example() {
	g, err := LoadWGraph("testdata/mst.yml")
	if err != nil {
		panic(err)
	}
	mst := g.Prim()
	//mst := g.LazyPrim()
	//mst := g.Kruskal()
	fmt.Println(mst.String())

	// possible output:
	// 0 : 2 7
	// 1 : 7
	// 2 : 0 3 6
	// 3 : 2
	// 4 : 5
	// 5 : 7 4
	// 6 : 2
	// 7 : 0 1 5
}

Shortest path

func ExampleWDigraph() {
	g, _ := LoadWDigraph("testdata/no_cycle.yml")
	searcher, _ := g.SearcherDijkstra()
	// searcher, _ = g.SearcherTopological()
	// searcher, _ = g.SearcherBellmanFord()
	fmt.Println(searcher.GetPath(1, 2).Str(nil))

	// Output:
	// (distance=1.02): 1->3, 3->7, 7->2,
}

Symbol graph

func ExampleSymbol() {
	g, _ := LoadGraph("./testdata/symbol_graph.yml")
	bfs := g.BFS(g.VetOf("姜文"))
	fmt.Println(bfs.ShortestPathTo(g.VetOf("梁朝伟")).Str(g.Symbol))
	fmt.Println(bfs.ShortestPathTo(g.VetOf("宋慧乔")).Str(g.Symbol))
	fmt.Println(bfs.ShortestPathTo(g.VetOf("郎雄")).Str(g.Symbol))
	fmt.Println(bfs.ShortestPathTo(g.VetOf("周星驰")).Str(g.Symbol))
	fmt.Println(bfs.ShortestPathTo(g.VetOf("梁家辉")).Str(g.Symbol))

	//(distance=12): 姜文->《让子弹飞》, 《让子弹飞》->刘嘉玲, 刘嘉玲->《阿飞正传》, 《阿飞正传》->张学友, 张学友->《东邪西毒》, 《东邪西毒》->梁朝伟,
	//(distance=12): 姜文->《让子弹飞》, 《让子弹飞》->周润发, 周润发->《卧虎藏龙》, 《卧虎藏龙》->章子怡, 章子怡->《一代宗师》, 《一代宗师》->宋慧乔,
	//(distance=8): 姜文->《让子弹飞》, 《让子弹飞》->周润发, 周润发->《卧虎藏龙》, 《卧虎藏龙》->郎雄,
	//(distance=12): 姜文->《让子弹飞》, 《让子弹飞》->刘嘉玲, 刘嘉玲->《阿飞正传》, 《阿飞正传》->张曼玉, 张曼玉->《家有喜事》, 《家有喜事》->周星驰,
	//(distance=8): 姜文->《让子弹飞》, 《让子弹飞》->周润发, 周润发->《赌神2》, 《赌神2》->梁家辉,
}

Documentation

Overview

Example 
g, err := LoadWGraph(testDir + "mst.yml")
if err != nil {
	panic(err)
}
mst := g.Prim()
//mst := g.LazyPrim()
//mst := g.Kruskal()
fmt.Println(mst.String())

// possible output:
// 0 : 2 7
// 1 : 7
// 2 : 0 3 6
// 3 : 2
// 4 : 5
// 5 : 7 4
// 6 : 2
// 7 : 0 1 5

Index

Examples

Constants

View Source 
const (
	Auto = iota
	Dijkstra
	Topological
	BellmanFord
)

Variables

View Source 
var (
	ErrVerticalNotExist = errors.New("vertical not exist")
	ErrSelfLoop         = errors.New("not support self loop")
	ErrInvalidYaml      = errors.New("input yaml file is invalid")
)

Functions

This section is empty.

Types

type BFS 

type BFS struct {
	// contains filtered or unexported fields
}
Example 
dg, err := LoadDigraph(testDir + "no_cycle.yml")
if err != nil {
	panic(err)
}
bfs := dg.BFS(1)
fmt.Println(bfs.CanReach(5))
fmt.Println(bfs.ShortestPathTo(2).Str(nil))

// false
// [TotalDistance=3] 7->2(1.00) 3->7(1.00) 1->3(1.00)

func (*BFS) CanReach 

func (bfs *BFS) CanReach(dst int) bool

CanReach check whether src can reach dst

func (*BFS) ShortestPathTo 

func (bfs *BFS) ShortestPathTo(dst int) *Path

ShortestPathTo get the shortest path to dst (ignore weight)

type Cycle 

type Cycle struct {
	*Path
}

func (*Cycle) Cycle 

func (c *Cycle) Cycle() *Cycle

func (*Cycle) Error 

func (c *Cycle) Error() string

type Digraph 

type Digraph struct {
	*Symbol
	// contains filtered or unexported fields
}

func LoadDigraph 

func LoadDigraph(filename string) (*Digraph, error)

func NewDigraph 

func NewDigraph(size uint) *Digraph

func (*Digraph) AddEdge 

func (dg *Digraph) AddEdge(from, to int)

AddEdge add a new edge

func (*Digraph) Adjacent 

func (dg *Digraph) Adjacent(v int) (adj []int)

Adjacent return a slice contains all adjacent vertices of v

func (Digraph) BFS 

func (dg Digraph) BFS(src int) *BFS

BFS save all BFS information from src

func (*Digraph) Bipartite 

func (dg *Digraph) Bipartite() (colors []bool)

Bipartite put two colors on all nodes while any connected nodes have different color

Example 
dg, err := LoadDigraph(testDir + "no_cycle.yml")
if err != nil {
	panic(err)
}
fmt.Println(dg.Bipartite())

Output:

[]

func (*Digraph) DelEdge 

func (dg *Digraph) DelEdge(src, dst int)

DelEdge delete an edge

func (*Digraph) FindCycle 

func (dg *Digraph) FindCycle() *Cycle

FindCycle find any directed cycle in dg

Example 
// (0)-------->(2)
// 	| ^	        ^
// 	|  \	    |
// 	|	------  |
// 	|		  \	|
// 	v		   \|
// (1)-------->(3)
g := NewDigraph(4)
g.AddEdge(0, 1)
g.AddEdge(0, 2)
g.AddEdge(1, 3)
g.AddEdge(3, 0)
g.AddEdge(3, 2)
c := g.FindCycle()
fmt.Println(c.Error())

// [TotalDistance=3] 0->1(1.00) 1->3(1.00) 3->0(1.00)

func (*Digraph) FindCycleFrom 

func (dg *Digraph) FindCycleFrom(v int) *Path

FindCycleFrom find any directed cycle from vertical v in dg But not include cycle that can not be accessed from v

func (*Digraph) FindNegativeEdge 

func (dg *Digraph) FindNegativeEdge() (src, dst int)

FindNegativeEdge find a negative edge. If here is no negative edge, (-1, -1) will be returned

func (*Digraph) FindNegativeEdgeFrom 

func (dg *Digraph) FindNegativeEdgeFrom(start int) (src int, dst int)

FindNegativeEdgeFrom find a reachable negative edge from the specified start vertical If here is no negative edge, (-1, -1) will be returned

func (*Digraph) GetWeight 

func (dg *Digraph) GetWeight(from, to int) float64

GetWeight get the weight of edge Zero will be returned if edge not exist

func (*Digraph) HasEdge 

func (dg *Digraph) HasEdge(from, to int) bool

HasEdge indicate whether dg contains the edge specified by params

func (*Digraph) HasVert 

func (dg *Digraph) HasVert(v int) bool

HasVert indicate whether dg contains vertical v

func (*Digraph) IsSameWith 

func (dg *Digraph) IsSameWith(other Digraph) bool

IsSameWith check whether dg is the same with other

func (*Digraph) IterAdjacent 

func (dg *Digraph) IterAdjacent(v int, fn func(int) bool)

IterAdjacent iterate all adjacent vertices of v

func (*Digraph) IterBDFSFrom 

func (dg *Digraph) IterBDFSFrom(src int, fn func(int) bool)

IterBDFSFrom iterate all reachable vertices from vertical src in RDFS order

func (*Digraph) IterEdge 

func (dg *Digraph) IterEdge(fn func(int, int) bool)

IterEdge iterate all edges in dg

func (*Digraph) IterEdgeFrom 

func (dg *Digraph) IterEdgeFrom(src int, fn func(int, int) bool)

IterEdgeFrom iterate all reachable edges from vertical src

func (*Digraph) IterVertDFS 

func (dg *Digraph) IterVertDFS(src int, fn func(int) bool)

IterVertDFS iterate all reachable vertices from vertical src in DFS order

func (*Digraph) IterVetBDFS 

func (dg *Digraph) IterVetBDFS(fn func(int) bool)

IterVetBDFS iterate all vertices in Back-DFS order

func (*Digraph) IterWAdjacent 

func (dg *Digraph) IterWAdjacent(v int, fn func(int, float64) bool)

IterWAdjacent iterate all adjacent vertices and weight of v

func (*Digraph) IterWEdge 

func (dg *Digraph) IterWEdge(fn func(int, int, float64) bool)

IterWEdge iterate all edges and their weight in dg

func (*Digraph) IterWEdgeFrom 

func (dg *Digraph) IterWEdgeFrom(src int, fn func(int, int, float64) bool)

IterWEdgeFrom iterate all reachable edges and their weight from vertical src

func (*Digraph) Marshal 

func (dg *Digraph) Marshal() ([]byte, error)

Marshal dg into yaml format

func (*Digraph) NumEdge 

func (dg *Digraph) NumEdge() uint

NumEdge get the number of edges

func (*Digraph) NumVert 

func (dg *Digraph) NumVert() uint

NumVert get the number of vertices

func (Digraph) Reachable 

func (dg Digraph) Reachable() Reachable

Reachable save all reachable information of dg

func (*Digraph) ReachableBits 

func (dg *Digraph) ReachableBits(src int) []bool

ReachableBits get a bit-map contains all reachable vertices from src

func (*Digraph) ReachableSlice 

func (dg *Digraph) ReachableSlice(src int) []int

ReachableSlice get a slice contains all reachable vertices from src

func (*Digraph) Reverse 

func (dg *Digraph) Reverse() *Digraph

Reverse all edges of dg

func (Digraph) SCC 

func (dg Digraph) SCC() *SCC

SCC calculate strong connected components of digraph with kosaraju algorithm

func (*Digraph) String 

func (dg *Digraph) String() string

func (*Digraph) Topological 

func (dg *Digraph) Topological() (order *basic.Stack[int])

Topological return a stack that will pop vertices in topological order

Example 
dg, err := LoadDigraph(testDir + "no_cycle.yml")
if err != nil {
	panic(err)
}
for _, vet := range dg.Topological().ToSlice() {
	fmt.Printf("%d->", vet)
}

Output:

5->1->3->6->4->7->0->2->

func (*Digraph) TotalWeight 

func (dg *Digraph) TotalWeight() float64

TotalWeight sum the weight of all edges

type Graph 

type Graph struct {
	*Digraph
}

Graph has no direction

func LoadGraph 

func LoadGraph(filename string) (*Graph, error)

func NewGraph 

func NewGraph(size uint) *Graph

func (*Graph) AddEdge 

func (g *Graph) AddEdge(a, b int) error

AddEdge add an edge

func (*Graph) DelEdge 

func (g *Graph) DelEdge(a, b int)

DelEdge delete an edge

func (*Graph) HasCycle 

func (g *Graph) HasCycle() bool

HasCycle check whether graph contains cycle

func (*Graph) IterEdge 

func (g *Graph) IterEdge(fn func(int, int) bool)

IterEdge iterate all no-direction edges

func (*Graph) IterEdgeFrom 

func (g *Graph) IterEdgeFrom(src int, fn func(int, int) bool)

IterEdgeFrom iterate all reachable edges from vertical src

func (*Graph) IterWEdge 

func (g *Graph) IterWEdge(fn func(int, int, float64) bool)

IterWEdge iterate all no-direction edges and their weight

func (*Graph) IterWEdgeFrom 

func (g *Graph) IterWEdgeFrom(src int, fn func(int, int, float64) bool)

IterWEdgeFrom iterate all reachable edges and their weight from vertical src

func (*Graph) NumEdge 

func (g *Graph) NumEdge() uint

NumEdge get the number of no-direction edges

func (*Graph) SubGraphs 

func (g *Graph) SubGraphs() *SubGraphs

SubGraphs calculate all sub-graphs of g

func (*Graph) TotalWeight 

func (g *Graph) TotalWeight() float64

TotalWeight sum the weight of all edges

type Path 

type Path struct {
	*basic.Stack[edge]
}

func NewPath 

func NewPath() *Path

func (*Path) Cycle 

func (p *Path) Cycle() *Cycle

func (*Path) Distance 

func (p *Path) Distance() float64

func (*Path) HasVert added in v0.1.3 

func (p *Path) HasVert(v int) bool

func (*Path) Pop 

func (p *Path) Pop() edge

func (*Path) Push 

func (p *Path) Push(from, to int, w float64)

func (*Path) Str 

func (p *Path) Str(s *Symbol) string

type PathTree 

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

PathTree is shortest path tree

func (*PathTree) CanReach 

func (spt *PathTree) CanReach(dst int) bool

CanReach check whether src can reach dst

func (*PathTree) DistanceTo 

func (spt *PathTree) DistanceTo(dst int) float64

DistanceTo get the distance from src to dst

func (*PathTree) PathTo 

func (spt *PathTree) PathTo(dst int) *Path

PathTo get the path from src to dst

type Reachable 

type Reachable [][]bool
Example 
dg, err := LoadDigraph(testDir + "no_cycle.yml")
if err != nil {
	panic(err)
}
reach := dg.Reachable()
fmt.Println(reach.CanReach(5, 2))
fmt.Println(reach.CanReach(2, 5))

Output:

true
false

func (Reachable) CanReach 

func (tc Reachable) CanReach(src, dst int) bool

CanReach check whether src can reach dst

func (Reachable) Iterate 

func (tc Reachable) Iterate(src int, fn func(v int) bool)

Iterate all reachable vertices from src

type SCC 

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

SCC is strong connected components of digraph vertices in the same component can access each other

Example 
g := NewDigraph(13)
g.AddEdge(0, 1)
g.AddEdge(0, 5)
g.AddEdge(5, 4)
g.AddEdge(4, 3)
g.AddEdge(4, 2)
g.AddEdge(3, 2)
g.AddEdge(2, 3)
g.AddEdge(2, 0)
g.AddEdge(6, 0)
g.AddEdge(6, 4)
g.AddEdge(6, 9)
g.AddEdge(9, 10)
g.AddEdge(10, 12)
g.AddEdge(12, 9)
g.AddEdge(9, 11)
g.AddEdge(11, 12)
g.AddEdge(11, 4)
g.AddEdge(7, 6)
g.AddEdge(7, 8)
g.AddEdge(8, 7)
g.AddEdge(8, 9)
scc := g.SCC()
fmt.Println("amount of strongly connected component:", scc.NumComponents())
var vertices []int
scc.IterComponent(scc.Comp(0), func(v int) bool {
	vertices = append(vertices, v)
	return true
})
sort.Shell(vertices)
fmt.Println("vertices strongly connected with 0:", vertices)
fmt.Println(scc.IsStronglyConn(0, 6))

// amount of strongly connected component: 5
// vertices strongly connected with 0: [0 2 3 4 5]
// false

func (*SCC) Comp 

func (scc *SCC) Comp(v int) int

Comp get the strongly connected component ID of vertical v

func (*SCC) IsStronglyConn 

func (scc *SCC) IsStronglyConn(src, dst int) bool

IsStronglyConn check whether src is strongly connected with dst

func (*SCC) IterComponent 

func (scc *SCC) IterComponent(c int, fn func(int) bool)

func (*SCC) NumComponents 

func (scc *SCC) NumComponents() int

NumComponents get the number of components

type Searcher 

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

func (*Searcher) GetDistance 

func (s *Searcher) GetDistance(src, dst int) float64

func (*Searcher) GetPath 

func (s *Searcher) GetPath(src, dst int) *Path

type SubGraphs 

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

func (*SubGraphs) IsConn 

func (tc *SubGraphs) IsConn(a, b int) bool

IsConn check whether a and b located in the same sub-graph

func (*SubGraphs) Iterate 

func (tc *SubGraphs) Iterate(v int, fn func(int) bool)

Iterate all vertices of sub-graph where v located

func (*SubGraphs) Locate 

func (tc *SubGraphs) Locate(v int) int

Locate get the ID of sub-graph where v located

func (*SubGraphs) NumSubGraph 

func (tc *SubGraphs) NumSubGraph() int

NumSubGraph get the number of sub-graphs

type Symbol 

type Symbol struct {
	// contains filtered or unexported fields
}
Example 
g, _ := LoadGraph("./testdata/symbol_graph.yml")
bfs := g.BFS(g.VetOf("姜文"))
fmt.Println(bfs.ShortestPathTo(g.VetOf("梁朝伟")).Str(g.Symbol))
fmt.Println(bfs.ShortestPathTo(g.VetOf("宋慧乔")).Str(g.Symbol))
fmt.Println(bfs.ShortestPathTo(g.VetOf("郎雄")).Str(g.Symbol))
fmt.Println(bfs.ShortestPathTo(g.VetOf("周星驰")).Str(g.Symbol))
fmt.Println(bfs.ShortestPathTo(g.VetOf("梁家辉")).Str(g.Symbol))

//(distance=12): 姜文->《让子弹飞》, 《让子弹飞》->刘嘉玲, 刘嘉玲->《阿飞正传》, 《阿飞正传》->张学友, 张学友->《东邪西毒》, 《东邪西毒》->梁朝伟,
//(distance=12): 姜文->《让子弹飞》, 《让子弹飞》->周润发, 周润发->《卧虎藏龙》, 《卧虎藏龙》->章子怡, 章子怡->《一代宗师》, 《一代宗师》->宋慧乔,
//(distance=8): 姜文->《让子弹飞》, 《让子弹飞》->周润发, 周润发->《卧虎藏龙》, 《卧虎藏龙》->郎雄,
//(distance=12): 姜文->《让子弹飞》, 《让子弹飞》->刘嘉玲, 刘嘉玲->《阿飞正传》, 《阿飞正传》->张曼玉, 张曼玉->《家有喜事》, 《家有喜事》->周星驰,
//(distance=8): 姜文->《让子弹飞》, 《让子弹飞》->周润发, 周润发->《赌神2》, 《赌神2》->梁家辉,

func NewSymbolGraph 

func NewSymbolGraph() *Symbol

func (*Symbol) SymbolOf 

func (sg *Symbol) SymbolOf(v int) string

func (*Symbol) VetOf 

func (sg *Symbol) VetOf(s string) int

type WDigraph 

type WDigraph struct {
	*Digraph
}

WDigraph is edge weighted digraph

Example 
g, _ := LoadWDigraph(testDir + "no_cycle.yml")
searcher, _ := g.SearcherDijkstra()
// searcher, _ := g.SearcherTopological()
// searcher, _ := g.SearcherBellmanFord()
fmt.Println(searcher.GetPath(1, 2).Str(nil))

// [TotalDistance=1.02] 1->3(0.29) 3->7(0.39) 7->2(0.34)

func LoadWDigraph 

func LoadWDigraph(filename string) (*WDigraph, error)

func NewWDigraph 

func NewWDigraph(size uint) *WDigraph

func (*WDigraph) AddEdge 

func (g *WDigraph) AddEdge(src, dst int, w float64)

AddEdge add a weighted and directed edge

func (*WDigraph) Searcher 

func (g *WDigraph) Searcher() (*Searcher, error)

func (*WDigraph) SearcherBellmanFord 

func (g *WDigraph) SearcherBellmanFord() (*Searcher, error)

func (*WDigraph) SearcherDijkstra 

func (g *WDigraph) SearcherDijkstra() (*Searcher, error)

func (*WDigraph) SearcherTopological 

func (g *WDigraph) SearcherTopological() (*Searcher, error)

func (*WDigraph) ShortestPathTree 

func (g *WDigraph) ShortestPathTree(src int, alg int) (*PathTree, error)

ShortestPathTree get the shortest path tree from src by the specified algorithm

type WGraph 

type WGraph struct {
	*Graph
}

func LoadWGraph 

func LoadWGraph(filename string) (*WGraph, error)

func NewWGraph 

func NewWGraph(size uint) *WGraph

func (*WGraph) AddEdge 

func (g *WGraph) AddEdge(src, dst int, w float64) error

func (*WGraph) Kruskal 

func (g *WGraph) Kruskal() (mst *WGraph)

Kruskal gets the minimum spanning tree by Kruskal algorithm. g MUST be a connected graph

func (*WGraph) LazyPrim 

func (g *WGraph) LazyPrim() (mst *WGraph)

LazyPrim gets the minimum spanning tree by Lazy-Prim algorithm. g MUST be a connected graph

func (*WGraph) Prim 

func (g *WGraph) Prim() (mst *WGraph)

Prim gets the minimum spanning tree by Prim algorithm. g MUST be a connected graph

func (*WGraph) ToWDigraph 

func (g *WGraph) ToWDigraph() *WDigraph

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.