graphlib

package module
v0.2.1 Latest Latest
Warning

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

 Go to latest Published: May 17, 2024 License: Apache-2.0 Imports: 13 Imported by: 0

README

graphlib

Graphlib is a graph data structure generic library implemented by Golang, providing definitions and basic operations for undirected/directed graphs, as well as built-in common graph algorithms. Additionally, as a feature, graphlib also comes with a DAG based goroutine workflow engine (ExecGraph).😀

Features

✔️ Basic operation of the graph:

  • Create undirected/directed graphs (supports simple and multiple graphs)
  • Serialization and Deserialization of Graph Objects (JSON/YAML Format)
  • Dynamically adjust vertex (increase/decrease/modify attributes)
  • Dynamically adjust edge (increase/decrease/modify attributes)
  • Basic properties of computational graphs: connectivity, acyclicity, etc

✔️ Graph calculation:

  • Generate induced subgraph
  • Generate spanning subgraph
  • Minimum Spanning Tree
  • Calculate strongly connected components
  • Algebraic operations on graphs (intersection/union/difference/sum/product)
  • Construct matrix representations of graphs (adjacency matrix, degree matrix, weight matrix)

✔️ Graph algorithm:

  • Graph traversal (BFS, DFS)
  • Shortest path (single source, multiple sources, negative weight)
  • Calculate maximum flow
  • Bipartite matching
  • Topological sorting
  • Vertex colouring/edge colouring

✔️ DAG:

  • Support for a directed acyclic graph based goroutine workflow engine
Getting started
go get github.com/flxj/graphlib

Currently, Graphlib is in the process of development and testing, and some features are not yet fully developed. Please do not use versions below 1.0 for production environments

Create an undirected graph using the following example 👇

v1---v2
|   /
|  /   
v3         v4-----v5----v6

import(
	"fmt"
    
	"github.com/flxj/graphlib"
)

func main() {
    g, err := graphlib.NewGraph[string, int, int](false, "graph")
	if err != nil {
		fmt.Println(err)
		return
	}

	vs := []graphlib.Vertex[int, int]{
		{Key: "v1", Value: 1},
		{Key: "v2", Value: 2},
		{Key: "v3", Value: 3},
		{Key: "v4", Value: 4},
		{Key: "v5", Value: 5},
		{Key: "v6", Value: 6},
	}

	for _, v := range vs {
		if err := g.AddVertex(v); err != nil {
			fmt.Printf("add vertex error:%v\n", err)
			return
		}
	}

	es := []graphlib.Edge[int, int]{
		{Key: 1, Head: "v1", Tail: "v2"},
		{Key: 2, Head: "v1", Tail: "v3"},
		{Key: 3, Head: "v2", Tail: "v3"},
		{Key: 4, Head: "v4", Tail: "v5"},
		{Key: 5, Head: "v5", Tail: "v6"},
	}

	for _, e := range es {
		if err := g.AddEdge(e); err != nil {
			fmt.Printf("add edge error:%v\n", err)
			return
		}
	}
	
	fmt.Printf("order:%d\n", g.Order())
	fmt.Printf("size:%d\n", g.Size())

	ps, err := g.Property(graphlib.PropertySimple)
	if err != nil {
		fmt.Printf("get property simple error:%v\n", err)
		return
	}
	fmt.Printf("simple:%v\n", ps.Value)
	pc, err := g.Property(graphlib.PropertyConnected)
	if err != nil {
		fmt.Printf("get property connected error:%v\n", err)
		return
	}
	fmt.Printf("connected:%v\n", pc.Value)
	pa, err := g.Property(graphlib.PropertyAcyclic)
	if err != nil {
		fmt.Printf("get property acyclic error:%v\n", err)
		return
	}
	fmt.Printf("acyclic:%v\n", pa.Value)
}

The output is as follows:

order:6
size:5
simple:true
connected:false
acyclic:false

Create a directed graph using the following example 👇

1----> 2 ---> 3
       |
       v
4----> 5 ---> 6

import(
	"fmt"
    
	"github.com/flxj/graphlib"
)

func main(){
    g, err := graphlib.NewDigraph[int, int, int]("g")
	if err != nil {
		fmt.Printf("new graph error:%v\n", err)
		return
	}

	vs := []Vertex[int, int]{
		{Key: 1, Value: 1},
		{Key: 2, Value: 2},
		{Key: 3, Value: 3},
		{Key: 4, Value: 4},
		{Key: 5, Value: 5},
		{Key: 6, Value: 6},
	}
	for _, v := range vs {
		if err := g.AddVertex(v); err != nil {
			fmt.Printf("add vertex error:%v\n", err)
			return
		}
	}
	
	es := []Edge[int, int]{
		{Key: 1, Head: 1, Tail: 2},
		{Key: 2, Head: 2, Tail: 3},
		{Key: 3, Head: 5, Tail: 6},
		{Key: 4, Head: 4, Tail: 5},
		{Key: 5, Head: 2, Tail: 5},
	}
	for _, e := range es {
		if err := g.AddEdge(e); err != nil {
			fmt.Printf("add edge error:%v\n", err)
			return
		}
	}

	fmt.Println(gs)
	fmt.Printf("order:%d\n", g.Order())
	fmt.Printf("size:%d\n", g.Size())
	p, err := g.Property(PropertyConnected)
	if err != nil {
		fmt.Printf("get property connected error:%v\n", err)
		return
	}
	fmt.Printf("connected:%v\n", p.Value)
	if p, err = g.Property(PropertyUnilateralConnected); err != nil {
		fmt.Printf("get property connected error:%v\n", err)
		return
	}
	fmt.Printf("unidirectional connected:%v\n", p.Value)
	if p, err = g.Property(PropertyAcyclic);err != nil {
		fmt.Printf("get property acyclic error:%v\n", err)
		return
	}
	fmt.Printf("acyclic:%v\n", p.Value)
}

order:6
size:5
connected:true
unidirectional connected:false
acyclic:true
Workflow

Graphlib also provides an ExecGraph object that represents a goroutine (Job) execution process arranged in a directed acyclic graph logic, conceptually similar to any other workflow system, such as argo-workflows.

Users can add tasks to the ExecGraph object and set dependencies between tasks. Users can manage the entire workflow declaration cycle through the ExecGraph interface method.

The following example shows how to create, run, and wait for ExecGraph:

job1---->job2--.
                \
                 \
                  v
job3---->job4--->job5

import(
	"fmt"
    
	"github.com/flxj/graphlib"
)

func main() {
	g,err:= graphlib.NewExecGraph[int,graphlib.Job]("exec")
	if err!=nil{
		fmt.Printf("[ERR] create exec graph error: %v\n",err)
		return 
	}
    var (
		v1 int
		v2 int 
		v3 int 
	)
	// input:  v1 <- x, v2 <- y
	// output: v3 <- 2*(x+100) + 3*x-10

	job1:=func() error {
		v1 += 100
		return nil 
	}
	job2:=func() error {
		v1 = 2*v1 
		return nil 
	}
	job3:=func() error {
		v2 = 3*v2
		return nil 
	}
	job4:=func() error {
		v2 = v2-10
		return nil 
	}
	job5:=func() error {
		v3 = v1+v2
		return nil
	}

	jobs:=map[int]Job{
		1:job1,
		2:job2,
		3:job3,
		4:job4,
		5:job5,
	}
	for k,j:=range jobs {
		if err:=g.AddJob(k,j);err!=nil{
			fmt.Printf("[ERR] add job error: %v\n",err)
			return 
		}
	}

	deps:=[][]int{
		{1,2},
		{3,4},
		{2,5},
		{4,5},
	}
	for _,d:=range deps {
		if err:=g.AddDependency(d[0],d[1]);err!=nil{
			fmt.Printf("[ERR] add dep error: %v\n",err)
			return 
		}
	}

	v1 = 100
	v2 = 200 
	var val = 2*(v1+100) + 3*v2-10

	if err:=g.Start();err!=nil{
		fmt.Printf("[ERR] start graph error: %v\n",err)
		return 
	}

	if err:=g.Wait();err!=nil{
		fmt.Printf("[ERR] wait graph error: %v\n",err)
		return 
	}

	if v3 != val {
		fmt.Printf("exec err: expect %d, actual get %d\n",val,v3)
	}else{
		fmt.Println("success")
	}
}

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func BFS 

func BFS[K comparable, V any, W number](g Graph[K, V, W], start K, visitor func(v Vertex[K, V]) error) error

Start breadth first search from the specified source vertex, where g can be a directed or undirected graph.

func BFSDigraph 

func BFSDigraph[K comparable, V any, W number](dg Digraph[K, V, W], start K, in bool, visitor func(v Vertex[K, V]) error) error

Perform breadth first search in a directed graph, and specify the search direction using the in parameter: if in is set to true, search from source in the order of the incident vertices of the current vertex.

func BipartiteMaxMatching added in v0.2.0 

func BipartiteMaxMatching[K comparable, V any, W number](g Bipartite[K, V, W]) ([]K, error)

Calculate the maximum matching of bipartite graph.

func BipartitePerfectMatching added in v0.2.0 

func BipartitePerfectMatching[K comparable, V any, W number](g Bipartite[K, V, W]) ([]K, error)

func Connected 

func Connected[K comparable, V any, W number](g Graph[K, V, W], start, end K) (bool, error)

Determine whether the start and end vertices in graph g are connected. If it is a directed graph, determine if there is a directed path from start to end.

func Contains 

func Contains[K comparable, V any, W number](g1 Graph[K, V, W], g2 Graph[K, V, W]) (bool, error)

Does g1 include g2 as a subgraph.

func CountCycles added in v0.2.1 

func CountCycles[K comparable, V any, W number](g Graph[K, V, W], length int) (int, error)

func DFS 

func DFS[K comparable, V any, W number](g Graph[K, V, W], start K, visitor func(v Vertex[K, V]) error) error

Start depth first search from the specified source vertex, where g can be a directed or undirected graph.

func DFSDigraph 

func DFSDigraph[K comparable, V any, W number](dg Digraph[K, V, W], start K, in bool, visitor func(v Vertex[K, V]) error) error

Perform depth first search in a directed graph, and specify the search direction using the in parameter: if in is set to true, search from source in the order of the incident vertices of the current vertex.

func EdgeColouring added in v0.2.1 

func EdgeColouring[K comparable, V any, W number](g Graph[K, V, W], colours int) (map[K]int, error)

Graph edge coloring, returning a feasible coloring scheme.

func IsAlreadyExists 

func IsAlreadyExists(err error) bool

func IsBipartite added in v0.2.0 

func IsBipartite[K comparable, V any, W number](g Graph[K, V, W]) (bool, error)

Determine whether the given graph is a bipartite graph.

func IsBridge 

func IsBridge[K comparable, V any, W number](g Graph[K, V, W], edge K) (bool, error)

func IsCutvertex 

func IsCutvertex[K comparable, V any, W number](g Graph[K, V, W], vertex K) (bool, error)

func IsNotExists 

func IsNotExists(err error) bool

func MarshalGraphToJSON 

func MarshalGraphToJSON[K comparable, V any, W number](g Graph[K, V, W]) ([]byte, error)

Serialize Graph in JSON format.

func MarshalGraphToYaml 

func MarshalGraphToYaml[K comparable, V any, W number](g Graph[K, V, W]) ([]byte, error)

Serialize Graph in yaml format.

func MaxFlow added in v0.2.0 

func MaxFlow[K comparable, V any, W number](g Graph[K, V, W], source, sink K) (W, error)

Calculate the maximum flow from the source vertex to the sink vertex.

func MaxMatching 

func MaxMatching[K comparable, V any, W number](g Graph[K, V, W]) ([]K, error)

Calculate the maximum matching of any graph and return the set of edges.

func MaxWeightMatching added in v0.2.0 

func MaxWeightMatching[K comparable, V any, W number](g Graph[K, V, W]) ([]K, error)

func MinWeightSpanningForest 

func MinWeightSpanningForest[K comparable, V any, W number](g Graph[K, V, W]) ([][]K, [][]Edge[K, W], []W, error)

Generate the minimum spanning forest of a weighted graph, which generates a corresponding minimum spanning tree for each connected component, returns the set of vertices and edges for each tree, as well as the sum of tree weights.

func PerfectMatching 

func PerfectMatching[K comparable, V any, W number](g Graph[K, V, W]) ([]K, error)

Calculate the perfect matching of any graph, if it exists, return the set of edges, otherwise return non-existent.

func StronglyConnectedComponent 

func StronglyConnectedComponent[K comparable, V any, W number](g Digraph[K, V, W]) ([][]K, error)

Calculate the strongly connected components of a directed graph and return the set of vertices for each strongly connected component.

func VertexColouring added in v0.2.1 

func VertexColouring[K comparable, V any, W number](g Graph[K, V, W], colours int) (map[K]int, error)

Graph vertex coloring, returning a feasible coloring scheme.

Types

type AdjacencyMatrix 

type AdjacencyMatrix[K comparable] struct {
	// contains filtered or unexported fields
}

func NewAdjacencytMatrix 

func NewAdjacencytMatrix[K comparable, V any, W number](g Graph[K, V, W]) (*AdjacencyMatrix[K], error)

Create adjacency matrix for graph.

func (*AdjacencyMatrix[K]) Columns 

func (m *AdjacencyMatrix[K]) Columns() []K

func (*AdjacencyMatrix[K]) Matrix 

func (m *AdjacencyMatrix[K]) Matrix() [][]int

type Bipartite 

type Bipartite[K comparable, V any, W number] struct {
	Graph[K, V, W]
	// contains filtered or unexported fields
}

func NewBipartite 

func NewBipartite[K comparable, V any, W number](digraph bool, name string) (*Bipartite[K, V, W], error)

func (*Bipartite[K, V, W]) AddEdge 

func (bg *Bipartite[K, V, W]) AddEdge(edge Edge[K, W]) error

func (*Bipartite[K, V, W]) AddVertex 

func (bg *Bipartite[K, V, W]) AddVertex(v Vertex[K, V]) error

func (*Bipartite[K, V, W]) AddVertexTo 

func (bg *Bipartite[K, V, W]) AddVertexTo(v Vertex[K, V], partA bool) error

func (*Bipartite[K, V, W]) AllEdges 

func (bg *Bipartite[K, V, W]) AllEdges() ([]Edge[K, W], error)

func (*Bipartite[K, V, W]) AllVertexes 

func (bg *Bipartite[K, V, W]) AllVertexes() ([]Vertex[K, V], error)

func (*Bipartite[K, V, W]) Clone 

func (bg *Bipartite[K, V, W]) Clone() (Graph[K, V, W], error)

func (*Bipartite[K, V, W]) Degree 

func (bg *Bipartite[K, V, W]) Degree(key K) (int, error)

func (*Bipartite[K, V, W]) DeleteEdgeLabel 

func (bg *Bipartite[K, V, W]) DeleteEdgeLabel(endpoint1, endpoint2 K, labelKey string) error

func (*Bipartite[K, V, W]) DeleteEdgeLabelByKey 

func (bg *Bipartite[K, V, W]) DeleteEdgeLabelByKey(key K, labelKey string) error

func (*Bipartite[K, V, W]) DeleteVertexLabel 

func (bg *Bipartite[K, V, W]) DeleteVertexLabel(key K, labelKey string) error

func (*Bipartite[K, V, W]) DetectCycle 

func (bg *Bipartite[K, V, W]) DetectCycle() ([][]K, error)

func (*Bipartite[K, V, W]) GetEdge 

func (bg *Bipartite[K, V, W]) GetEdge(v1, v2 K) ([]Edge[K, W], error)

func (*Bipartite[K, V, W]) GetEdgeByKey 

func (bg *Bipartite[K, V, W]) GetEdgeByKey(key K) (Edge[K, W], error)

func (*Bipartite[K, V, W]) GetEdgesByLabel 

func (bg *Bipartite[K, V, W]) GetEdgesByLabel(labels map[string]string) ([]Edge[K, W], error)

func (*Bipartite[K, V, W]) GetVertex 

func (bg *Bipartite[K, V, W]) GetVertex(key K) (Vertex[K, V], error)

func (*Bipartite[K, V, W]) GetVertexesByLabel 

func (bg *Bipartite[K, V, W]) GetVertexesByLabel(labels map[string]string) ([]Vertex[K, V], error)

func (*Bipartite[K, V, W]) InDegree 

func (bg *Bipartite[K, V, W]) InDegree(vertex K) (int, error)

func (*Bipartite[K, V, W]) InEdges 

func (bg *Bipartite[K, V, W]) InEdges(vertex K) ([]Edge[K, W], error)

func (*Bipartite[K, V, W]) InNeighbours 

func (bg *Bipartite[K, V, W]) InNeighbours(vertex K) ([]Vertex[K, V], error)

func (*Bipartite[K, V, W]) IncidentEdges added in v0.2.1 

func (bg *Bipartite[K, V, W]) IncidentEdges(vertex K) ([]Edge[K, W], error)

func (*Bipartite[K, V, W]) IsDigraph 

func (bg *Bipartite[K, V, W]) IsDigraph() bool

func (*Bipartite[K, V, W]) Name 

func (bg *Bipartite[K, V, W]) Name() string

func (*Bipartite[K, V, W]) NeighbourEdges added in v0.2.1 

func (bg *Bipartite[K, V, W]) NeighbourEdges(endpoint1, endpoint2 K) ([]Edge[K, W], error)

func (*Bipartite[K, V, W]) NeighbourEdgesByKey added in v0.2.1 

func (bg *Bipartite[K, V, W]) NeighbourEdgesByKey(edge K) ([]Edge[K, W], error)

func (*Bipartite[K, V, W]) Neighbours 

func (bg *Bipartite[K, V, W]) Neighbours(v K) ([]Vertex[K, V], error)

func (*Bipartite[K, V, W]) Order 

func (bg *Bipartite[K, V, W]) Order() int

func (*Bipartite[K, V, W]) OutDegree 

func (bg *Bipartite[K, V, W]) OutDegree(vertex K) (int, error)

func (*Bipartite[K, V, W]) OutEdges 

func (bg *Bipartite[K, V, W]) OutEdges(vertex K) ([]Edge[K, W], error)

func (*Bipartite[K, V, W]) OutNeighbours 

func (bg *Bipartite[K, V, W]) OutNeighbours(vertex K) ([]Vertex[K, V], error)

func (*Bipartite[K, V, W]) Part 

func (bg *Bipartite[K, V, W]) Part(partA bool) ([]Vertex[K, V], error)

func (*Bipartite[K, V, W]) Property 

func (bg *Bipartite[K, V, W]) Property(p PropertyName) (GraphProperty[any], error)

func (*Bipartite[K, V, W]) RandomEdge added in v0.2.1 

func (bg *Bipartite[K, V, W]) RandomEdge() (Edge[K, W], error)

func (*Bipartite[K, V, W]) RandomVertex added in v0.2.1 

func (bg *Bipartite[K, V, W]) RandomVertex() (Vertex[K, V], error)

func (*Bipartite[K, V, W]) Recerse 

func (bg *Bipartite[K, V, W]) Recerse() error

func (*Bipartite[K, V, W]) RemoveEdge 

func (bg *Bipartite[K, V, W]) RemoveEdge(v1, v2 K) error

func (*Bipartite[K, V, W]) RemoveEdgeByKey 

func (bg *Bipartite[K, V, W]) RemoveEdgeByKey(key K) error

func (*Bipartite[K, V, W]) RemoveVertex 

func (bg *Bipartite[K, V, W]) RemoveVertex(key K) error

func (*Bipartite[K, V, W]) SetEdgeLabel 

func (bg *Bipartite[K, V, W]) SetEdgeLabel(endpoint1, endpoint2 K, labelKey, labelVal string) error

func (*Bipartite[K, V, W]) SetEdgeLabelByKey 

func (bg *Bipartite[K, V, W]) SetEdgeLabelByKey(key K, labelKey, labelVal string) error

func (*Bipartite[K, V, W]) SetEdgeValue 

func (bg *Bipartite[K, V, W]) SetEdgeValue(endpoint1, endpoint2 K, value any) error

func (*Bipartite[K, V, W]) SetEdgeValueByKey 

func (bg *Bipartite[K, V, W]) SetEdgeValueByKey(key K, value any) error

func (*Bipartite[K, V, W]) SetName 

func (bg *Bipartite[K, V, W]) SetName(name string)

func (*Bipartite[K, V, W]) SetVertexLabel 

func (bg *Bipartite[K, V, W]) SetVertexLabel(key K, labelKey, labelVal string) error

func (*Bipartite[K, V, W]) SetVertexValue 

func (bg *Bipartite[K, V, W]) SetVertexValue(key K, value V) error

func (*Bipartite[K, V, W]) Sinks 

func (bg *Bipartite[K, V, W]) Sinks() ([]Vertex[K, V], error)

func (*Bipartite[K, V, W]) Size 

func (bg *Bipartite[K, V, W]) Size() int

func (*Bipartite[K, V, W]) Sources 

func (bg *Bipartite[K, V, W]) Sources() ([]Vertex[K, V], error)

type ContextJob 

type ContextJob func(context.Context) error

ContextJob represents a runnable function object with a context parameter, which differs from Job in that when running ContextJob,the ExecGraph execution engine automatically generates a context parameter for it and cancels the context when the user performs a Stop operation.

type DegreeMatrix 

type DegreeMatrix[K comparable] struct {
	// contains filtered or unexported fields
}

func NewDegreeMatrix 

func NewDegreeMatrix[K comparable, V any, W number](g Graph[K, V, W]) (*DegreeMatrix[K], error)

func (*DegreeMatrix[K]) Columns 

func (m *DegreeMatrix[K]) Columns() []K

func (*DegreeMatrix[K]) Weight 

func (m *DegreeMatrix[K]) Weight() [][]int

type Digraph 

type Digraph[K comparable, V any, W number] interface {
	Graph[K, V, W]
	//
	// indegree of vertex v.
	InDegree(v K) (int, error)
	//
	// outdegree of vertex v.
	OutDegree(v K) (int, error)
	//
	// The set composed of head vertexes of all v's inedges.
	InNeighbours(v K) ([]Vertex[K, V], error)
	//
	// The set composed of tail vertexes of all v's outedges.
	OutNeighbours(v K) ([]Vertex[K, V], error)
	//
	// All arcs with v as the tail vertex.
	// For example [a->v, b->v,...,x->v].
	InEdges(v K) ([]Edge[K, W], error)
	//
	// All arcs with v as the head vertex.
	// For example [v->a, v->b,...,v->x].
	OutEdges(v K) ([]Edge[K, W], error)
	//
	// All vertices with an in degree of 0.
	Sources() ([]Vertex[K, V], error)
	//
	// All vertices with degree 0.
	Sinks() ([]Vertex[K, V], error)
	//
	DetectCycle() ([][]K, error)
	//
	// Reverse all edges in a directed graph.
	Reverse() error
}

This interface represents a directed graph.

The concept of directed graphs can be referenced: https://mathworld.wolfram.com/DirectedGraph.html

func NewDigraph 

func NewDigraph[K comparable, V any, W number](name string) (Digraph[K, V, W], error)

Create a new directed graph.

func NewDigraphFromFile 

func NewDigraphFromFile[K comparable, V any, W number](path string) (Digraph[K, V, W], error)

func UnmarshalDigraph 

func UnmarshalDigraph[K comparable, V any, W number](s []byte) (Digraph[K, V, W], error)

type Edge 

type Edge[K comparable, W number] struct {
	// The unique identifier of this edge.
	// use a key to distinguish edge,
	// because maybe exists multiedge in graph
	Key K `json:"key" yaml:"key"`
	// One endpoint of an edge.
	Head K `json:"head" yaml:"head"`
	// The other endpoint of an edge.
	// For a directed graph, the direction of the edge is head ->tail.
	Tail K `json:"tail" yaml:"tail"`
	// Edge weight.
	Weight W `json:"weight" yaml:"weight"`
	// Edge data.
	Value any `json:"value" yaml:"value"`
	// Edge labels.
	Labels map[string]string `json:"labels" yaml:"labels"`
}

func MinWeightSpanningTree 

func MinWeightSpanningTree[K comparable, V any, W number](g Graph[K, V, W]) ([]Edge[K, W], W, error)

Generate the minimum spanning tree of a weighted connected graph, return the set of edges of the tree, and the sum of tree weights. If the graph is non connected, an error will be returned.

func (*Edge[K, W]) Clone 

func (e *Edge[K, W]) Clone() *Edge[K, W]

type ExecGraph 

type ExecGraph[K comparable, J job] interface {
	//
	// The Start method will attempt to run ExecGraph. If it is currently
	// in a Waiting, Stopped, or Failed state, the entire Graph will be run
	// from scratch.If it is in the Paused state, it will continue running
	// from the pause point.
	//
	// Until the status of the Graph changes to Success or Failed, it indicates
	// that the Graph has finished running.
	//
	// Running a Graph that is already in the Running state will return an
	// error indicating that it is already running.
	//
	// Currently, all Start calls to the Success state graph will be ignored.
	// If you want to run it again, you need to first call the Reset method
	// to reset the Graph to the Waiting state.
	Start() error
	//
	// The Stop method will attempt to terminate the current Graph run
	// (Cancel the running job and no longer run a new job).
	//
	// If calling the Graph method on the Success state, it will return an error.
	Stop() error
	//
	// Wait is used to wait for the Graph to finish running and will return
	// the latest error message.
	//
	// The gorouting calling this method will block until there are no
	// runnable jobs in the Graph.
	Wait() error
	//
	// The Reset method will reset the Graph to its initial state.
	// Calling this method on a Graph in Running state
	// will first stop the Graph and then reset it.
	Reset() error
	//
	// The Pause method will pause the execution of the Graph.
	//
	// Note that if there are jobs that happen to be running when calling
	// Pause, meaning they start before the current pause point, then these
	// jobs will not be canceled.
	Pause() error
	//
	// The Status method is used to view the global status of the current Graph.
	Status() State
	//
	// The Job method returns the basic information of the job corresponding
	// to the key value,including the current status, error information, etc.
	//
	// If the job does not exist, return NotExists error.
	Job(key K) (JobInfo[K], error)
	//
	// Get current all jobs info in the graph.
	AllJobs() []JobInfo[K]
	//
	// Add a new job to the Graph, and if the same key value already exists,
	// update the Job.
	//
	// Note that dynamic modification of the running Graph structure is
	// currently not allowed, so this method can only be called on graphs
	// in the Waiting state.
	AddJob(key K, job J) error
	//
	// AddTimeoutJob adds a new job to the Graph and sets the timeout for
	// the job to run.
	//
	// If the same key value already exists, the Job will be updated.
	//
	// Note that dynamic modification of the running Graph structure is
	// currently not allowed, so this method can only be called on graphs
	// in the Waiting state.
	AddTimeoutJob(key K, job J, timeout time.Duration) error
	//
	// AddRetryJob adds a new job to the Graph and sets the number of retries
	// for the job to run (n<=0 indicates no retry).
	//
	// If the same key value already exists, the Job will be updated.
	//
	// Note that dynamic modification of the running Graph structure is
	// currently not allowed,so this method can only be called on graphs
	// in the Waiting state.
	AddRetryJob(key K, job J, retry int) error
	//
	// RemoveJob removes a Job from the current Graph And remove the
	// relevant dependencies.
	//
	// If the job does not exist, return a NotExists error.
	//
	// Note that currently only calling this method on Graph in Waiting
	// state is supported.
	RemoveJob(key K) error
	//
	// AddDependency adds a dependency relationship between jobs in the current
	// Graph, which is unidirectional:Source job ->target job
	// indicates that source is the predecessor task of the target.
	//
	// Note that currently only calling this method on Graph in Waiting
	// state is supported.
	AddDependency(source, target K) error
	//
	// RemoveDependency removes dependencies between tasks from the current Graph.
	//
	// Note that currently only calling this method on Graph in Waiting
	// state is supported.
	RemoveDependency(source, target K) error
	//
	// Set the maximum number of concurrent job runs.
	// Note that this setting is currently not supported,
	// meaning there is no limit on the concurrency of jobs.
	SetMaxConcurrencyJob(n int)
	//
	// StoppJob stops a running job.
	//
	// Note that stopping the job may have an impact on its subsequent operations.
	//
	// If ignoreErr is set to false, the stopped job is considered a failure
	// (the reason for the failure is due to the user's active cancellation),
	// which will result in the final graph state being Failed;
	//
	// On the other hand, if ignoreErr is set to true, the job is considered
	// to have ended successfully.
	StopJob(key K, ignoreErr bool) error
	//
	// RunJob runs a specific job separately.
	// Note that this feature is currently not supported.
	RunJob(key K) error
	//
	// Detecting possible job ring dependencies in the Graph.
	DetectCycle() ([][]K, error)
}

ExecGraph represents a workflow object for a task arranged in DAG order.

func NewExecGraph 

func NewExecGraph[K comparable, J job](name string) (ExecGraph[K, J], error)

Create an empty ExecGraph.

func NewExecGraphFromDAG 

func NewExecGraphFromDAG[K comparable, V any, W number, J job](g Digraph[K, V, W]) (ExecGraph[K, J], error)

Create an ExecGraph based on an existing DAG object.

func NewExecGraphFromFile 

func NewExecGraphFromFile[K comparable, V any, W number, J job](path string) (ExecGraph[K, J], error)

Load a DAG from text data and create an ExecGraph based on it.

type Graph 

type Graph[K comparable, V any, W number] interface {
	//
	// The name of current graph object.
	Name() string
	//
	// Change the name of graph.
	SetName(name string)
	//
	// The number of vertexes in the graph.
	Order() int
	//
	// The number of edges in the graph.
	Size() int
	//
	// Is it a directed graph.
	IsDigraph() bool
	//
	// Query the properties of the current graph.
	// The current default Graph implementation in Graphlib provides
	// calculations for the following properties
	//
	// PropertyGraph: Is it a directed graph
	// PropertyAcyclic: Is it an acyclic graph
	//
	// PropertySimple: Is it a simple graph?
	// For the definition of a simple graph,
	// please refer to https://mathworld.wolfram.com/SimpleGraph.html
	//
	// PropertyRegular: Is it a regular graph?
	// For the definition of a regular graph,
	// please refer to https://mathworld.wolfram.com/RegularGraph.html
	//
	// PropertyConnected: Is it a connected graph?
	// For the definition of connectivity,
	// please refer to https://mathworld.wolfram.com/ConnectedGraph.html
	//
	// PropertyForest: Is it a forest?
	// For the definition of forest,
	// please refer to https://mathworld.wolfram.com/Forest.html
	//
	// PropertyCompleted: Is it a complete graph?
	// For the definition of a complete graph,
	// please refer to https://mathworld.wolfram.com/CompleteGraph.html
	//
	// PropertyTree: Is it a tree?
	// For the definition of a tree,
	// please refer to https://mathworld.wolfram.com/Tree.html
	//
	// PropertyLoop: Does it include a loop.
	//
	// PropertyNegativeWeight: Does it contain negative weight edges
	//
	// PropertyGraphName: Graph name
	//
	// PropertyOrder: The number of vertices in the graph
	//
	// PropertySize: The number of edges in a graph
	//
	// PropertyMaxDegree: Maximum Degree
	//
	// PropertyMinDegree: Minimum Read
	//
	// PropertyAvgDegree: Average degree (float64)
	Property(p PropertyName) (GraphProperty[any], error)
	//
	// The unordered set of all vertices in a graph.
	AllVertexes() ([]Vertex[K, V], error)
	//
	// The unordered set of all edges in the graph.
	AllEdges() ([]Edge[K, W], error)
	//
	// Add vertices to the graph.
	AddVertex(vertex Vertex[K, V]) error
	//
	// Delete a vertex, and all edges corresponding to that vertex
	// will also be deleted. If the vertex does not exist, return an error.
	RemoveVertex(key K) error
	//
	// Add new edge, if the corresponding vertex of the
	// edge does not exist, return an error.
	AddEdge(edge Edge[K, W]) error
	//
	// Delete specified edge.
	RemoveEdgeByKey(key K) error
	//
	// Delete edges with endpoints ednpoint1 and endpoint2.
	// If it is a directed graph, delete all arcs in the 'endpoint1->endpoint2'
	// and 'endpoint2->endpoint1' directions simultaneously.
	RemoveEdge(endpoint1, endpoint2 K) error
	//
	// Calculate the degree of vertices.
	// If it is a directed graph, calculate the sum of in degree and out degree.
	// If the vertex does not exist, an error is returned.
	Degree(vertex K) (int, error)
	//
	// Query the adjacent vertices of a specified vertex.
	Neighbours(vertex K) ([]Vertex[K, V], error)
	//
	// Query specified vertex.
	GetVertex(key K) (Vertex[K, V], error)
	//
	// Query all edges with endpoints 1 and 2 as their respective endpoints.
	GetEdge(endpoint1, endpoint2 K) ([]Edge[K, W], error)
	//
	// Query specified edge.
	GetEdgeByKey(key K) (Edge[K, W], error)
	//
	// Filter vertices based on label information,
	// and eligible vertices need to include all label items in
	// the label parameter simultaneously.
	GetVertexesByLabel(labels map[string]string) ([]Vertex[K, V], error)
	//
	// Filter edges based on label information,
	// and eligible edges need to include all label items
	// in the label parameter simultaneously.
	GetEdgesByLabel(labels map[string]string) ([]Edge[K, W], error)
	//
	// Update vertex data.
	SetVertexValue(key K, value V) error
	//
	// Update vertex label.
	SetVertexLabel(key K, labelKey, labelVal string) error
	//
	// Remove vertex label.
	DeleteVertexLabel(key K, labelKey string) error
	//
	// Update edge data.
	SetEdgeValueByKey(key K, value any) error
	//
	// Update dege label.
	SetEdgeLabelByKey(key K, labelKey, labelVal string) error
	//
	// Remove edge label.
	DeleteEdgeLabelByKey(key K, labelKey string) error
	//
	// Update edge data. If there are multiple edges associated with
	// endpoints1 and endpoint2 simultaneously,
	// the data of these edges will be updated simultaneously.
	SetEdgeValue(endpoint1, endpoint2 K, value any) error
	//
	// Update edge label. If there are multiple edges associated with
	// endpoints1 and endpoint2 simultaneously,
	// the label of these edges will be updated simultaneously.
	SetEdgeLabel(endpoint1, endpoint2 K, labelKey, labelVal string) error
	//
	// Delete edge label. If there are multiple edges associated with
	// endpoints1 and endpoint2 simultaneously,
	// the label of these edges will be updated simultaneously.
	DeleteEdgeLabel(endpoint1, endpoint2 K, labelKey string) error
	//
	// Copy the current graph.
	Clone() (Graph[K, V, W], error)
	//
	// Randomly select a vertex from the graph.
	RandomVertex() (Vertex[K, V], error)
	//
	// Randomly select a edge from the graph
	RandomEdge() (Edge[K, W], error)
	//
	// Query the adjacent edges of a specified edge.
	NeighbourEdgesByKey(edge K) ([]Edge[K, W], error)
	//
	// Query the adjacent edges of a specified edge endpoint1-endpoint2 or endpoint2-endpoint11.
	NeighbourEdges(endpoint1, endpoint2 K) ([]Edge[K, W], error)
	//
	// Query all edges associated with a specified vertex.
	IncidentEdges(vertex K) ([]Edge[K, W], error)
}

Graph [K, V, W] represents the graph object, K represents the identification type of vertices and edges, V represents the data type of vertices, and W represents the weight data type of edges.

In a mathematician's terminology, a graph is a collection of points and lines connecting some (possibly empty) subset of them. The points of a graph are most commonly known as graph vertices, but may also be called "nodes" or simply "points." Similarly, the lines connecting the vertices of a graph are most commonly known as graph edges, but may also be called "arcs" or "lines."

The concept of graph can be referenced: https://mathworld.wolfram.com/Graph.html

func CartesianProduct 

func CartesianProduct[K comparable, V any, W number](g1, g2 Graph[K, V, W]) (Graph[K, V, W], error)

func ConstructGraph 

func ConstructGraph[K comparable, V any, W number](digraph bool, name string, vertexes []Vertex[K, V], edges []Edge[K, W]) (Graph[K, V, W], error)

Create a graph using vertex and edge sets.

func Contract 

func Contract[K comparable, V any, W number](g Graph[K, V, W], v1, v2 K, newVertex K) (Graph[K, V, W], error)

page 55

func Identify 

func Identify[K comparable, V any, W number](g Graph[K, V, W], v1, v2 K, newVertex K) (Graph[K, V, W], error)

page 55

func InducedSubgraph 

func InducedSubgraph[K comparable, V any, W number](g Graph[K, V, W], vertexes []K) (Graph[K, V, W], error)

Generate an induced subgraph of g, where the new graph will not contain vertices in vertices.

func Intersection 

func Intersection[K comparable, V any, W number](g1, g2 Graph[K, V, W]) (Graph[K, V, W], error)

Calculate the union of two graphs.

func NewGraph 

func NewGraph[K comparable, V any, W number](digraph bool, name string) (Graph[K, V, W], error)

Create a new graph.

func NewGraphFromFile 

func NewGraphFromFile[K comparable, V any, W number](path string) (Graph[K, V, W], error)

Load graph from json or yaml file.

func NewUnDigraph 

func NewUnDigraph[K comparable, V any, W number](name string) (Graph[K, V, W], error)

Create a new undirected graph

func SpanningSubgraph 

func SpanningSubgraph[K comparable, V any, W number](g Graph[K, V, W], edges [][]K) (Graph[K, V, W], error)

Generate a spanning subgraph of g, and the new graph will not include edges in the edges list. The format of the edges list is [] [] K {head1, tail1} {headN, tailN}}.

func SpanningSupergraph 

func SpanningSupergraph[K comparable, V any, W number](g Graph[K, V, W], edges []*Edge[K, W]) (Graph[K, V, W], error)

Generate a spanning supergraph of g, and add edges to the edges list in the new graph.

func Split 

func Split[K comparable, V any, W number](g Graph[K, V, W], vertex K, v1, v2, edge K) (Graph[K, V, W], error)

page 55

func Subdivide 

func Subdivide[K comparable, V any, W number](g Graph[K, V, W], edge K, newVertex K) (Graph[K, V, W], error)

page 55

func Union 

func Union[K comparable, V any, W number](g1, g2 Graph[K, V, W]) (Graph[K, V, W], error)

Calculate the intersection of two graphs.

func UnmarshalGraph 

func UnmarshalGraph[K comparable, V any, W number](s []byte) (Graph[K, V, W], error)

type GraphInfo 

type GraphInfo[K comparable, V any, W number] struct {
	Name     string         `json:"name" yaml:"name"`
	Digraph  bool           `json:"digraph" yaml:"digraph"`
	Vertexes []Vertex[K, V] `json:"vertexes" yaml:"vertexes"`
	Edges    []Edge[K, W]   `json:"edges" yaml:"edges"`
}

GraphInfo represents the basic information of a graph, used for serialization of graph objects.

type GraphProperty 

type GraphProperty[T any] struct {
	Name  PropertyName
	Value T
}

type Job 

type Job func() error

Job represents a runnable function object, which in graphlib is an abstraction of an independent task.

type JobInfo 

type JobInfo[K comparable] struct {
	// The unique identifier of the job.
	Key K
	// The error message returned by running the job.
	Error error
	// The current status of the job.
	Status State
	// Start time.
	StartAt time.Time
	// End time.
	EndAt time.Time
}

JobInfo record the job's status of the ExecGraph node.

type Path 

type Path[K comparable, W number] struct {
	Source K
	Target K
	Edges  []K
	Weight W
}

Path represents a path on the graph, starting from Source and ending at Target. It contains edges (the key for recording edges), and the weighted sum of path lengths is Weight.

func AllShortestPaths 

func AllShortestPaths[K comparable, V any, W number](g Graph[K, V, W]) ([]Path[K, W], error)

Solve the shortest path between all vertex pairs in the graph If a pair of vertices are unreachable between them, the corresponding shortest path value is MaxDistance.

func ShortestPath 

func ShortestPath[K comparable, V any, W number](g Graph[K, V, W], source K, target K) (Path[K, W], error)

Calculate the shortest path from the source vertex to the target vertex in the graph. If the source or target vertex does not exist, an error will be reported. g can be an undirected graph or a directed graph, and negative weights are allowed (but if negative loops are detected during the calculation process, an error will be returned). If the source and target are not connected, the shortest path does not exist, and the corresponding length is MaxDistance.

func ShortestPaths 

func ShortestPaths[K comparable, V any, W number](g Graph[K, V, W], source K) ([]Path[K, W], error)

Calculate the shortest path from the source vertex to all other vertices in the graph, where g can be an undirected or directed graph, with negative weights allowed (however, if negative loops are detected during the calculation process, an error will be returned)。

type PropertyName 

type PropertyName int
const (
	PropertyDigraph PropertyName = iota
	PropertyAcyclic
	PropertySimple
	PropertyRegular
	PropertyConnected
	PropertyForest
	PropertyLoop
	PropertyCompleted
	PropertyTree
	PropertyNegativeWeight
	PropertyUnilateralConnected
	PropertyGraphName
	PropertyOrder
	PropertySize
	PropertyMaxDegree
	PropertyMinDegree
	PropertyAvgDegree
)

type State 

type State string
const (
	// Waiting represents the initial state of a job or
	// ExecGraph, in which the user can adjust the ExecGraph
	// structure to update the job.
	Waiting State = "waiting"
	// Running status indicates that Job or ExecGraph is running
	Running State = "running"
	// If the job runs without returning an error, it will
	// be in the Success state.After all jobs in the
	// ExecGraph run successfully, the ExecGraph will also
	// be set to the Success state
	Success State = "success"
	// Stopped status indicates that Job or ExecGraph
	// has been actively terminated by the user.
	Stopped State = "stopped"
	// Failed indicates that the job encountered an error
	// while running.If any job in ExecGraph fails to run
	// at the same time, the final status of ExecGraph will
	// also be set to Failed.
	Failed State = "failed"
	// Paused represents the state of ExecGraph
	// after being actively paused by the user.
	Paused State = "paused"

	//
	DefaultMaxConcurrencyJob = 1000000
)

type Vertex 

type Vertex[K comparable, V any] struct {
	// The unique identifier of this vertex.
	Key K `json:"key" yaml:"key"`
	// The data object of this vertex .
	Value V `json:"value" yaml:"value"`
	// The label of this vertex.
	Labels map[string]string `json:"labels" yaml:"labels"`
}

func TopologicalSort 

func TopologicalSort[K comparable, V any, W number](g Digraph[K, V, W]) ([]Vertex[K, V], error)

Perform topological sorting on a directed graph and return a sequence of vertices. If there is a cycle in the graph, return an error.

func (*Vertex[K, V]) Clone 

func (v *Vertex[K, V]) Clone() *Vertex[K, V]

type WeightMatrix 

type WeightMatrix[K comparable, W number] struct {
	// contains filtered or unexported fields
}

func NewWeightMatrix 

func NewWeightMatrix[K comparable, V any, W number](g Graph[K, V, W]) (*WeightMatrix[K, W], error)

Create weight matrix for graph.

func (*WeightMatrix[K, W]) Columns 

func (m *WeightMatrix[K, W]) Columns() []K

func (*WeightMatrix[K, W]) Distance 

func (m *WeightMatrix[K, W]) Distance(infinite float64) [][]float64

func (*WeightMatrix[K, W]) Weight 

func (m *WeightMatrix[K, W]) Weight(none W) [][]W

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.