graphman

package module
Version: v1.6.0 Latest Latest
Warning

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

Go to latest
Published: Dec 31, 2019 License: Apache-2.0 Imports: 7 Imported by: 5

README

graphman

graph manipulation library in golang

CircleCI GoDoc License GitHub release Go Report Card CodeFactor Docker Metrics Made by Manfred Touron

Library

graphman is a golang library that manipulates graphs, take a look at godoc and examples to get a quick understanding of what it can be used for.

Binaries

Pertify

Install with: go get -u moul.io/graphman/cmd/pertify

Documentation

Index

Examples

Constants

View Source
const (
	Day  = 24 * time.Hour
	Week = 7 * Day
)

Variables

This section is empty.

Functions

This section is empty.

Types

type Attrs

type Attrs map[string]interface{}

func (Attrs) Clone

func (a Attrs) Clone() Attrs

func (*Attrs) Del

func (a *Attrs) Del(key string)

func (Attrs) GetColor

func (a Attrs) GetColor() string

func (Attrs) GetComment

func (a Attrs) GetComment() string

func (Attrs) GetPert

func (a Attrs) GetPert() *PertAttrs

func (Attrs) GetTitle

func (a Attrs) GetTitle() string

func (Attrs) Has

func (a Attrs) Has(key string) bool

func (Attrs) IsEmpty

func (a Attrs) IsEmpty() bool

func (*Attrs) Merge

func (a *Attrs) Merge(b Attrs)

func (Attrs) SetColor

func (a Attrs) SetColor(color string) Attrs

func (Attrs) SetComment

func (a Attrs) SetComment(comment string) Attrs

func (Attrs) SetPertAction added in v1.3.0

func (a Attrs) SetPertAction() Attrs

func (Attrs) SetPertEstimates

func (a Attrs) SetPertEstimates(opt, real, pess float64) Attrs

func (Attrs) SetPertNonStandardGraph added in v1.3.0

func (a Attrs) SetPertNonStandardGraph() Attrs

func (Attrs) SetPertState added in v1.3.0

func (a Attrs) SetPertState() Attrs

func (Attrs) SetPertUndefinedDependency added in v1.4.0

func (a Attrs) SetPertUndefinedDependency() Attrs

func (Attrs) SetPertUntitled added in v1.3.0

func (a Attrs) SetPertUntitled() Attrs

func (Attrs) SetPertZeroTimeActivity

func (a Attrs) SetPertZeroTimeActivity() Attrs

func (Attrs) SetTitle

func (a Attrs) SetTitle(title string) Attrs

func (Attrs) String

func (a Attrs) String() string

type Edge

type Edge struct {
	Attrs
	// contains filtered or unexported fields
}
Example
graph := New()
graph.AddVertex("A")
graph.AddVertex("B")
graph.AddVertex("C", Attrs{"D": "E"})
fmt.Println(graph.AddEdge("A", "B"))
fmt.Println(graph.AddEdge("A", "C"))
fmt.Println(graph.Edges())
Output:

(A,B)
(A,C)
{(A,B),(A,C)}

func (Edge) Dst

func (e Edge) Dst() *Vertex

func (*Edge) HasVertex

func (e *Edge) HasVertex(id string) bool

func (*Edge) OtherVertex

func (e *Edge) OtherVertex(id string) *Vertex

func (Edge) Src

func (e Edge) Src() *Vertex

func (*Edge) String

func (e *Edge) String() string

func (*Edge) Vertices

func (e *Edge) Vertices() Vertices

type EdgeCostFN

type EdgeCostFN func(e *Edge) int64

type Edges

type Edges []*Edge

func (Edges) AllCombinations added in v1.1.0

func (e Edges) AllCombinations() EdgesCombinations

AllCombinations returns the different combinations of Edges in a group of Edges

Adapted from https://github.com/mxschmitt/golang-combinations

func (Edges) Equals added in v1.1.0

func (e Edges) Equals(other Edges) bool

func (Edges) String

func (e Edges) String() string

type EdgesCombinations added in v1.1.0

type EdgesCombinations []Edges

func (EdgesCombinations) LongestToShortest added in v1.1.0

func (ec EdgesCombinations) LongestToShortest() EdgesCombinations

type Graph

type Graph struct {
	Attrs
	// contains filtered or unexported fields
}
Example (Big)
graph := New()
amount := 100

for i := 0; i <= amount; i++ {
	graph.AddVertex(fmt.Sprintf("%d", i))
}

for i := 0; i <= amount-1; i++ {
	graph.AddEdge(
		fmt.Sprintf("%d", i),
		fmt.Sprintf("%d", i+1),
	)
}

fmt.Println(graph)
path, dist := graph.FindShortestPath("0", "100")
fmt.Println("0-100:", path, dist)
Output:

{(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10),(10,11),(11,12),(12,13),(13,14),(14,15),(15,16),(16,17),(17,18),(18,19),(19,20),(20,21),(21,22),(22,23),(23,24),(24,25),(25,26),(26,27),(27,28),(28,29),(29,30),(30,31),(31,32),(32,33),(33,34),(34,35),(35,36),(36,37),(37,38),(38,39),(39,40),(40,41),(41,42),(42,43),(43,44),(44,45),(45,46),(46,47),(47,48),(48,49),(49,50),(50,51),(51,52),(52,53),(53,54),(54,55),(55,56),(56,57),(57,58),(58,59),(59,60),(60,61),(61,62),(62,63),(63,64),(64,65),(65,66),(66,67),(67,68),(68,69),(69,70),(70,71),(71,72),(72,73),(73,74),(74,75),(75,76),(76,77),(77,78),(78,79),(79,80),(80,81),(81,82),(82,83),(83,84),(84,85),(85,86),(86,87),(87,88),(88,89),(89,90),(90,91),(91,92),(92,93),(93,94),(94,95),(95,96),(96,97),(97,98),(98,99),(99,100)}
0-100: (0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100) 100
Example (Complex)
graph := New()
graph.AddVertex("A", Attrs{"hello": "world"}) // create a vertex with attributes
graph.AddVertex("B")                          // create an empty vertex
graph.AddVertex("temp")                       // create a vertex that we will delete later
graph.AddVertex("isolated")                   // create a vertex that won't have any edge
graph.AddEdge("A", "B")                       // connect existing vertices A and B
graph.AddEdge("B", "C")                       // connect existing vertex A with newly created vertex C
graph.RemoveVertex("temp")
fmt.Println(graph)
Output:

{(A,B),(B,C),isolated}
Example (Components)
graph := New()
// component 1: loop
graph.AddEdge("A", "B")
graph.AddEdge("B", "C")
graph.AddEdge("C", "D")
graph.AddEdge("D", "A")

// component 2: standard
graph.AddEdge("L", "M")
graph.AddEdge("M", "N")
graph.AddEdge("M", "O")
graph.AddEdge("M", "P")
graph.AddEdge("N", "Q")
graph.AddEdge("O", "Q")
graph.AddEdge("P", "Q")
graph.AddEdge("Q", "R")

// component 3: self loop
graph.AddEdge("Z", "Z")

// component 4: reverse (sorted string)
graph.AddEdge("Y", "X")
graph.AddEdge("X", "W")
graph.AddEdge("W", "V")
graph.AddEdge("V", "U")

for _, couple := range [][2]string{
	{"A", "D"}, // using the loop from component 1
	{"B", "A"}, // same
	{"A", "L"}, // two components
	{"L", "R"}, // through all the component 2
	{"Z", "Z"}, // self loop
	{"Y", "U"}, // reverse sorted string
} {
	fmt.Printf("couple %s-%s:\n", couple[0], couple[1])
	for _, path := range graph.FindAllPaths(couple[0], couple[1]) {
		fmt.Println("-", path)
	}
	path, dist := graph.FindShortestPath(couple[0], couple[1])
	fmt.Println("shortest:", path, dist)
	fmt.Println()
}
Output:

couple A-D:
- (A,B,C,D)
shortest: (A,B,C,D) 3

couple B-A:
- (B,C,D,A)
shortest: (B,C,D,A) 3

couple A-L:
shortest: [INVALID] -1

couple L-R:
- (L,M,N,Q,R)
- (L,M,O,Q,R)
- (L,M,P,Q,R)
shortest: (L,M,N,Q,R) 4

couple Z-Z:
- (Z,Z)
shortest: () 0

couple Y-U:
- (Y,X,W,V,U)
shortest: (Y,X,W,V,U) 4
Example (Simple)
graph := New()
graph.AddVertex("A")
graph.AddVertex("B")
graph.AddVertex("C")
graph.AddVertex("D")
graph.AddVertex("E")
graph.AddVertex("F")
graph.AddEdge("A", "B")
graph.AddEdge("B", "C")
graph.AddEdge("E", "F")
fmt.Println(graph)
Output:

{(A,B),(B,C),(E,F),D}

func FromPertConfig

func FromPertConfig(config PertConfig) *Graph
Example
yamlConfig := `
actions:
  - id: "1"
    title: "Prepare foundation"
    estimate: [4, 6, 10]
  - id: "2"
    title: "Make & position door frames"
    estimate: [2, 4, 7]
  - id: "3"
    title: "Lay drains & floor base"
    estimate: [7, 9, 12]
  - id: "4"
    title: "Install service & settings"
    estimate: [2, 4, 5]
    depends_on: ["5"]
  - id: "5"
    title: "Erect walls"
    estimate: [7, 10, 15]
    depends_on: ["1", "2"]
  - id: "6"
    title: "Plaster ceilings"
    estimate: [1, 2, 4]
    depends_on: ["4", "7"]
  - id: "7"
    title: "Erect roof"
    estimate: [4, 6, 8]
    depends_on: ["5"]
  - id: "8"
    title: "Install door & windows"
    estimate: [7, 9, 11]
    depends_on: ["7"]
  - id: "9"
    title: "Fit gutters & pipes"
    estimate: [1, 2, 3]
    depends_on: ["3", "6"]
  - id: "10"
    title: "Paint outside"
    estimate: [1, 2, 3]
    depends_on: ["8", "9"]
opts:
  standard-pert: true
`
var config PertConfig
if err := yaml.Unmarshal([]byte(yamlConfig), &config); err != nil {
	panic(err)
}

graph := FromPertConfig(config)
fmt.Println(graph)
Output:

{(Start,post_1)[[pert:To=4,Tm=6,Tp=10,Te=6.33,σe=1,Ve=1,title:Prepare foundation]],(Start,post_2)[[pert:To=2,Tm=4,Tp=7,Te=4.17,σe=0.83,Ve=0.69,title:Make & position door frames]],(Start,post_3)[[pert:To=7,Tm=9,Tp=12,Te=9.17,σe=0.83,Ve=0.69,title:Lay drains & floor base]],(post_5,pre_4)[[pert:To=2,Tm=4,Tp=5,Te=3.83,σe=0.5,Ve=0.25,title:Install service & settings]],(pre_5,post_5)[[pert:To=7,Tm=10,Tp=15,Te=10.33,σe=1.33,Ve=1.78,title:Erect walls]],(post_1,pre_5)[[]],(post_2,pre_5)[[]],(pre_6,post_6)[[pert:To=1,Tm=2,Tp=4,Te=2.17,σe=0.5,Ve=0.25,title:Plaster ceilings]],(post_4,pre_6)[[]],(post_7,pre_6)[[]],(post_5,pre_7)[[pert:To=4,Tm=6,Tp=8,Te=6,σe=0.67,Ve=0.44,title:Erect roof]],(post_7,pre_8)[[pert:To=7,Tm=9,Tp=11,Te=9,σe=0.67,Ve=0.44,title:Install door & windows]],(pre_9,post_9)[[pert:To=1,Tm=2,Tp=3,Te=2,σe=0.33,Ve=0.11,title:Fit gutters & pipes]],(post_3,pre_9)[[]],(post_6,pre_9)[[]],(pre_10,post_10)[[pert:To=1,Tm=2,Tp=3,Te=2,σe=0.33,Ve=0.11,title:Paint outside]],(post_8,pre_10)[[]],(post_9,pre_10)[[]],(pre_4,Finish)[[]],(pre_7,Finish)[[]],(pre_8,Finish)[[]],(post_10,Finish)[[]]}

func New

func New(attrs ...Attrs) *Graph

func (*Graph) AddEdge

func (g *Graph) AddEdge(srcID, dstID string, attrs ...Attrs) *Edge

func (*Graph) AddVertex

func (g *Graph) AddVertex(id string, attrs ...Attrs) *Vertex

func (Graph) ConnectedSubgraphFromVertex

func (g Graph) ConnectedSubgraphFromVertex(start *Vertex) *Graph

func (Graph) ConnectedSubgraphs

func (g Graph) ConnectedSubgraphs() Graphs
Example
graph := New()
// component 1
graph.AddEdge("A", "B")
graph.AddEdge("B", "C")
graph.AddEdge("C", "D")
graph.AddEdge("D", "A")
// component 2
graph.AddEdge("E", "E")
// component 3
graph.AddEdge("F", "G")
graph.AddEdge("G", "H")
graph.AddEdge("G", "I")
graph.AddEdge("H", "J")
graph.AddEdge("I", "J")
graph.AddEdge("J", "K")

for _, subgraph := range graph.ConnectedSubgraphs() {
	fmt.Println(subgraph, subgraph.vertices)
}
Output:

{(D,A),(A,B),(B,C),(C,D)} {A,B,C,D}
{(E,E)} {E}
{(F,G),(G,H),(G,I),(H,J),(I,J),(J,K)} {F,G,H,J,K,I}

func (Graph) Edges

func (g Graph) Edges() Edges

func (Graph) FindAllPaths

func (g Graph) FindAllPaths(srcID, dstID string) Paths
Example
graph := New()
graph.AddEdge("G", "H")
graph.AddEdge("A", "B")
graph.AddEdge("A", "B")
graph.AddEdge("F", "H")
graph.AddEdge("A", "C")
graph.AddEdge("B", "E")
graph.AddEdge("B", "G")
graph.AddEdge("C", "F")
graph.AddEdge("D", "H")
graph.AddEdge("A", "D")
graph.AddEdge("E", "G")
graph.AddEdge("E", "H")
graph.AddEdge("F", "G")

for _, path := range graph.FindAllPaths("A", "H") {
	fmt.Println(path)
}

fmt.Println()
path, dist := graph.FindShortestPath("A", "H")
fmt.Printf("shortest (distance=%d): %s\n", dist, path)
Output:

(A,B,E,G,H)
(A,B,E,G,H)
(A,B,E,H)
(A,B,E,H)
(A,B,G,H)
(A,B,G,H)
(A,C,F,G,H)
(A,C,F,H)
(A,D,H)

shortest (distance=2): (A,D,H)

func (Graph) FindShortestPath

func (g Graph) FindShortestPath(srcID, dstID string) (Path, int64)

func (Graph) FindShortestPathFN

func (g Graph) FindShortestPathFN(srcID, dstID string, fn EdgeCostFN) (Path, int64)

func (Graph) GetVertex

func (g Graph) GetVertex(id string) *Vertex

func (*Graph) Human added in v1.6.0

func (g *Graph) Human() string

Human returns a diff-friendly and human-readable representation of the vertices and edges

Example
graph := New()
graph.AddEdge("G", "H")
graph.AddEdge("A", "B")
graph.AddEdge("A", "B")
graph.AddEdge("F", "H")
graph.AddEdge("A", "C")
graph.AddEdge("B", "E")
graph.AddEdge("B", "G")
graph.AddEdge("C", "F")
graph.AddEdge("D", "H")
graph.AddEdge("A", "D")
graph.AddEdge("E", "G")
graph.AddEdge("E", "H")
graph.AddEdge("F", "G")
graph.AddVertex("I")
graph.AddVertex("J")
graph.AddVertex("K")
fmt.Println(graph.Human())
Output:

* A
  * (A,B)
  * (A,B)
  * (A,C)
  * (A,D)
* B
  * (A,B)
  * (A,B)
  * (B,E)
  * (B,G)
* C
  * (A,C)
  * (C,F)
* D
  * (A,D)
  * (D,H)
* E
  * (B,E)
  * (E,G)
  * (E,H)
* F
  * (C,F)
  * (F,H)
  * (F,G)
* G
  * (B,G)
  * (E,G)
  * (F,G)
  * (G,H)
* H
  * (G,H)
  * (F,H)
  * (D,H)
  * (E,H)
* I
* J
* K

func (Graph) IsolatedVertices

func (g Graph) IsolatedVertices() Vertices

func (*Graph) RemoveEdge

func (g *Graph) RemoveEdge(src, dst string) bool

func (*Graph) RemoveVertex

func (g *Graph) RemoveVertex(id string) bool

func (Graph) SinkVertices

func (g Graph) SinkVertices() Vertices

func (Graph) SourceVertices

func (g Graph) SourceVertices() Vertices

func (*Graph) String

func (g *Graph) String() string

func (Graph) Vertices

func (g Graph) Vertices() Vertices

type Graphs

type Graphs []*Graph

type Path

type Path Edges
Example
graph := New()

eab := graph.AddEdge("A", "B")
ebc := graph.AddEdge("B", "C")
ecd := graph.AddEdge("C", "D", Attrs{"hello": "world"})

path := Path{eab, ebc, ecd}
fmt.Println(path)
Output:

(A,B,C,D)

func (Path) Edges

func (p Path) Edges() Edges

func (Path) FirstEdge

func (p Path) FirstEdge() *Edge

func (Path) FirstVertex

func (p Path) FirstVertex() *Vertex

func (Path) HasVertex

func (p Path) HasVertex(id string) bool

func (Path) IsValid

func (p Path) IsValid() bool

func (Path) LastEdge

func (p Path) LastEdge() *Edge

func (Path) LastVertex

func (p Path) LastVertex() *Vertex

func (Path) String

func (p Path) String() string

func (Path) Vertices

func (p Path) Vertices() Vertices

type Paths

type Paths []*Path

func (Paths) Len

func (p Paths) Len() int

func (Paths) Less

func (p Paths) Less(i, j int) bool

func (Paths) String

func (p Paths) String() string

func (Paths) Swap

func (p Paths) Swap(i, j int)

type PertAction

type PertAction struct {
	ID        string    `yaml:"id"`
	Title     string    `yaml:"title"`
	Estimate  []float64 `yaml:"estimate"`
	DependsOn []string  `yaml:"depends_on"`
}

type PertAttrs

type PertAttrs struct {
	Pessimistic, Realistic, Optimistic float64
	IsZeroTimeActivity                 bool // a.k.a DummyActivity
	IsUntitled                         bool
	IsAction, IsState                  bool
	IsNonStandardGraph                 bool
	IsStart, IsFinish                  bool
	IsUndefinedDependency              bool
}

func (PertAttrs) AverageEstimate

func (pa PertAttrs) AverageEstimate() float64

func (PertAttrs) StandardDeviation

func (pa PertAttrs) StandardDeviation() float64

func (PertAttrs) String

func (pa PertAttrs) String() string

func (PertAttrs) Variance

func (pa PertAttrs) Variance() float64

func (PertAttrs) WeightedEstimate

func (pa PertAttrs) WeightedEstimate() float64

type PertConfig

type PertConfig struct {
	Actions []PertAction `yaml:"actions"`
	States  []PertState  `yaml:"states"`
	Opts    struct {
		NoSimplify   bool `yaml:"no-simplify"`
		StandardPert bool `yaml:"standard-pert"`
	} `yaml:"opts"`
}

type PertResult

type PertResult struct {
	CriticalPathVariance          float64
	CriticalPathStandardDeviation float64
	CriticalPath                  Path
}
Example (WithValue)
graph := New()
graph.AddEdge("1", "2", Attrs{}.SetPertEstimates(3, 6, 15))
graph.AddEdge("1", "3", Attrs{}.SetPertEstimates(2, 5, 14))
graph.AddEdge("1", "4", Attrs{}.SetPertEstimates(6, 12, 30))
graph.AddEdge("2", "5", Attrs{}.SetPertEstimates(2, 5, 8))
graph.AddEdge("2", "6", Attrs{}.SetPertEstimates(5, 11, 17))
graph.AddEdge("3", "6", Attrs{}.SetPertEstimates(3, 6, 15))
graph.AddEdge("4", "7", Attrs{}.SetPertEstimates(3, 9, 27))
graph.AddEdge("5", "7", Attrs{}.SetPertEstimates(1, 4, 7))
graph.AddEdge("6", "7", Attrs{}.SetPertEstimates(4, 19, 28))

fmt.Println("graph before computing:")
for _, e := range graph.Edges() {
	fmt.Println("*", e)
}
fmt.Println()

result := ComputePert(graph)
fmt.Println("graph after computing:")
for _, e := range graph.Edges() {
	fmt.Println("*", e)
}
fmt.Println("result:", result)
Output:

graph before computing:
* (1,2)[[pert:To=3,Tm=6,Tp=15,Te=7,σe=2,Ve=4]]
* (1,3)[[pert:To=2,Tm=5,Tp=14,Te=6,σe=2,Ve=4]]
* (1,4)[[pert:To=6,Tm=12,Tp=30,Te=14,σe=4,Ve=16]]
* (2,5)[[pert:To=2,Tm=5,Tp=8,Te=5,σe=1,Ve=1]]
* (2,6)[[pert:To=5,Tm=11,Tp=17,Te=11,σe=2,Ve=4]]
* (3,6)[[pert:To=3,Tm=6,Tp=15,Te=7,σe=2,Ve=4]]
* (4,7)[[pert:To=3,Tm=9,Tp=27,Te=11,σe=4,Ve=16]]
* (5,7)[[pert:To=1,Tm=4,Tp=7,Te=4,σe=1,Ve=1]]
* (6,7)[[pert:To=4,Tm=19,Tp=28,Te=18,σe=4,Ve=16]]

graph after computing:
* (1,2)[[pert:To=3,Tm=6,Tp=15,Te=7,σe=2,Ve=4]]
* (1,3)[[pert:To=2,Tm=5,Tp=14,Te=6,σe=2,Ve=4]]
* (1,4)[[pert:To=6,Tm=12,Tp=30,Te=14,σe=4,Ve=16]]
* (2,5)[[pert:To=2,Tm=5,Tp=8,Te=5,σe=1,Ve=1]]
* (2,6)[[pert:To=5,Tm=11,Tp=17,Te=11,σe=2,Ve=4]]
* (3,6)[[pert:To=3,Tm=6,Tp=15,Te=7,σe=2,Ve=4]]
* (4,7)[[pert:To=3,Tm=9,Tp=27,Te=11,σe=4,Ve=16]]
* (5,7)[[pert:To=1,Tm=4,Tp=7,Te=4,σe=1,Ve=1]]
* (6,7)[[pert:To=4,Tm=19,Tp=28,Te=18,σe=4,Ve=16]]
result: Tσe=8.12,TVe=66
Example (WithoutValue)
graph := New()
graph.AddEdge("1", "2")
graph.AddEdge("1", "3")
graph.AddEdge("1", "4")
graph.AddEdge("2", "5")
graph.AddEdge("2", "6")
graph.AddEdge("3", "6")
graph.AddEdge("4", "7")
graph.AddEdge("5", "7")
graph.AddEdge("6", "7")

fmt.Println("graph before computing:")
for _, e := range graph.Edges() {
	fmt.Println("*", e)
}
fmt.Println()

result := ComputePert(graph)
fmt.Println("graph after computing:")
for _, e := range graph.Edges() {
	fmt.Println("*", e)
}
fmt.Println("result:", result)
Output:

graph before computing:
* (1,2)
* (1,3)
* (1,4)
* (2,5)
* (2,6)
* (3,6)
* (4,7)
* (5,7)
* (6,7)

graph after computing:
* (1,2)[[pert:To=1,Tm=1,Tp=1,Te=1,σe=0,Ve=0]]
* (1,3)[[pert:To=1,Tm=1,Tp=1,Te=1,σe=0,Ve=0]]
* (1,4)[[pert:To=1,Tm=1,Tp=1,Te=1,σe=0,Ve=0]]
* (2,5)[[pert:To=1,Tm=1,Tp=1,Te=1,σe=0,Ve=0]]
* (2,6)[[pert:To=1,Tm=1,Tp=1,Te=1,σe=0,Ve=0]]
* (3,6)[[pert:To=1,Tm=1,Tp=1,Te=1,σe=0,Ve=0]]
* (4,7)[[pert:To=1,Tm=1,Tp=1,Te=1,σe=0,Ve=0]]
* (5,7)[[pert:To=1,Tm=1,Tp=1,Te=1,σe=0,Ve=0]]
* (6,7)[[pert:To=1,Tm=1,Tp=1,Te=1,σe=0,Ve=0]]
result: Tσe=0,TVe=0

func ComputePert

func ComputePert(g *Graph) PertResult

func (PertResult) String

func (pr PertResult) String() string

type PertState

type PertState struct {
	ID        string   `yaml:"id"`
	Title     string   `yaml:"title"`
	DependsOn []string `yaml:"depends_on"`
}

type Vertex

type Vertex struct {
	Attrs
	// contains filtered or unexported fields
}
Example (Helpers)
graph := New()
graph.AddVertex("bob")
graph.AddVertex("eve")
graph.AddVertex("joy")
graph.AddVertex("sam")
graph.AddVertex("han")      // solo
graph.AddEdge("bob", "eve") // bob is the predecessor of eve
graph.AddEdge("bob", "bob") // bob is linked to itself
graph.AddEdge("eve", "joy") // eve is the predecessor of joy
graph.AddEdge("joy", "eve") // and also its successor
graph.AddEdge("sam", "bob") // sam is the predecessor of bob

for _, vertex := range graph.Vertices() {
	fmt.Println(vertex.ID())
	fmt.Println("  isolated:             ", vertex.IsIsolated())
	fmt.Println("  neighbors:            ", vertex.Neighbors())
	fmt.Println("  predecessor vertices: ", vertex.PredecessorVertices())
	fmt.Println("  predecessor edges:    ", vertex.PredecessorEdges())
	fmt.Println("  successor vertices:   ", vertex.SuccessorVertices())
	fmt.Println("  successor edges:      ", vertex.SuccessorEdges())
	fmt.Println("  edges:                ", vertex.Edges())
}
Output:

bob
  isolated:              false
  neighbors:             {bob,eve,sam}
  predecessor vertices:  {bob,sam}
  predecessor edges:     {(bob,bob),(sam,bob)}
  successor vertices:    {bob,eve}
  successor edges:       {(bob,eve),(bob,bob)}
  edges:                 {(bob,bob),(sam,bob),(bob,eve),(bob,bob)}
eve
  isolated:              false
  neighbors:             {bob,joy}
  predecessor vertices:  {bob,joy}
  predecessor edges:     {(bob,eve),(joy,eve)}
  successor vertices:    {joy}
  successor edges:       {(eve,joy)}
  edges:                 {(bob,eve),(joy,eve),(eve,joy)}
han
  isolated:              true
  neighbors:             {}
  predecessor vertices:  {}
  predecessor edges:     {}
  successor vertices:    {}
  successor edges:       {}
  edges:                 {}
joy
  isolated:              false
  neighbors:             {eve}
  predecessor vertices:  {eve}
  predecessor edges:     {(eve,joy)}
  successor vertices:    {eve}
  successor edges:       {(joy,eve)}
  edges:                 {(eve,joy),(joy,eve)}
sam
  isolated:              false
  neighbors:             {bob}
  predecessor vertices:  {}
  predecessor edges:     {}
  successor vertices:    {bob}
  successor edges:       {(sam,bob)}
  edges:                 {(sam,bob)}
Example (Simple)
graph := New()
v := graph.AddVertex("A")
fmt.Println(v)
fmt.Println(v.ID())
Output:

A
A
Example (WithAttrs)
graph := New()
v := graph.AddVertex("A", Attrs{
	"ccc": "ddd",
	"eee": []string{"fff", "ggg"},
	"hhh": 42,
})
fmt.Println(v)
fmt.Println(v.ID())
Output:

A[[ccc:ddd,eee:[fff ggg],hhh:42]]
A

func (Vertex) Degree

func (v Vertex) Degree() int

func (Vertex) Edges

func (v Vertex) Edges() Edges

func (Vertex) ID

func (v Vertex) ID() string

func (Vertex) InDegree

func (v Vertex) InDegree() int

func (Vertex) IsIsolated

func (v Vertex) IsIsolated() bool

func (Vertex) IsSink

func (v Vertex) IsSink() bool

func (Vertex) IsSource

func (v Vertex) IsSource() bool

func (Vertex) Neighbors

func (v Vertex) Neighbors() Vertices

func (Vertex) OutDegree

func (v Vertex) OutDegree() int

func (Vertex) PredecessorEdges

func (v Vertex) PredecessorEdges() Edges

func (Vertex) PredecessorVertices

func (v Vertex) PredecessorVertices() Vertices

func (Vertex) String

func (v Vertex) String() string

func (Vertex) SuccessorEdges

func (v Vertex) SuccessorEdges() Edges

func (Vertex) SuccessorVertices

func (v Vertex) SuccessorVertices() Vertices

func (*Vertex) WalkAdjacentVertices

func (v *Vertex) WalkAdjacentVertices(fn VerticesWalkFunc) error

func (*Vertex) WalkPredecessorVertices

func (v *Vertex) WalkPredecessorVertices(fn VerticesWalkFunc) error

func (*Vertex) WalkSuccessorVertices

func (v *Vertex) WalkSuccessorVertices(fn VerticesWalkFunc) error

type Vertices

type Vertices []*Vertex
Example
graph := New()
a := graph.AddVertex("A")
b := graph.AddVertex("B")
c := graph.AddVertex("C")
d := graph.AddVertex("D")
vertices := &Vertices{a, b, c, d}
fmt.Println(vertices)
Output:

{A,B,C,D}

func (Vertices) Equals added in v1.1.0

func (v Vertices) Equals(other Vertices) bool

func (Vertices) Len

func (v Vertices) Len() int

func (Vertices) Less

func (v Vertices) Less(i, j int) bool

func (Vertices) String

func (v Vertices) String() string

func (Vertices) Swap

func (v Vertices) Swap(i, j int)

func (Vertices) Unique

func (v Vertices) Unique() Vertices

type VerticesWalkFunc

type VerticesWalkFunc func(current, previous *Vertex, depth int) error

Directories

Path Synopsis
lambda module
viz module

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL