graphs

README

Graph

A simple graph library written in Go.

Graphs are represented by an adjacency list combined with ports for each node. Paths can be found by using recursive depth first search.

Caution when using references

When using reference types as type parameter, always use the same pointer to reference the same logical object! As the type is being used as key in a map and compared for equality, this is very important.

Usage

Consider the following simple graph:

Define the nodes

one := graphs.NewNode[int, string](1)
two := graphs.NewNode[int, string](2)
three := graphs.NewNode[int, string](3)
four := graphs.NewNode[int, string](4)
five := graphs.NewNode[int, string](5)
six := graphs.NewNode[int, string](6)

Define inner port connections

one.ConnectBi("a", "b")
two.ConnectBi("a", "b")
two.ConnectBi("a", "c")
three.ConnectBi("a", "b")
four.ConnectBi("a", "b")
five.ConnectBi("a", "b")
five.ConnectBi("a", "c")
six.ConnectBi("a", "b")

Initialize the graph

graph := graphs.NewGraph[int, string]()
graphs.AddNode(one)
graphs.AddNode(two)
graphs.AddNode(three)
graphs.AddNode(four)
graphs.AddNode(five)
graphs.AddNode(six)

Define outer node connections

graphs.ConnectRefBi(1, "b", 2, "a")
graphs.ConnectRefBi(2, "b", 3, "a")
graphs.ConnectRefBi(2, "c", 4, "a")
graphs.ConnectRefBi(3, "b", 5, "b")
graphs.ConnectRefBi(4, "b", 5, "c")
graphs.ConnectRefBi(5, "a", 6, "a")

Find all paths

paths := graphs.FindRef(1, "b", 4, "b")

Documentation

Index

• type Connection
  • func NewConnection[O, P comparable](fromNode *Node[O, P], fromPort P, toNode *Node[O, P], toPort P) *Connection[O, P]
  • func (connection *Connection[O, P]) EqualNodes() bool
  • func (connection *Connection[O, P]) IsSelf() bool
  • func (connection *Connection[O, P]) String() string
• type Graph
  • func NewGraph[O, P comparable]() *Graph[O, P]
  • func (graph *Graph[O, P]) AddConnection(connection *Connection[O, P]) error
  • func (graph *Graph[O, P]) AddNode(node *Node[O, P])
  • func (graph *Graph[O, P]) Connect(fromNode *Node[O, P], fromPort P, toNode *Node[O, P], toPort P) error
  • func (graph *Graph[O, P]) ConnectBi(fromNode *Node[O, P], fromPort P, toNode *Node[O, P], toPort P) error
  • func (graph *Graph[O, P]) ConnectRef(fromRef O, fromPort P, toRef O, toPort P) error
  • func (graph *Graph[O, P]) ConnectRefBi(fromRef O, fromPort P, toRef O, toPort P) error
  • func (graph *Graph[O, P]) Find(fromNode *Node[O, P], fromPort P, toNode *Node[O, P], toPort P) [][]*PathSegment[O, P]
  • func (graph *Graph[O, P]) FindConnection(node *Node[O, P], port P) (*Connection[O, P], bool)
  • func (graph *Graph[O, P]) FindRef(fromRef O, fromPort P, toRef O, toPort P) ([][]*PathSegment[O, P], error)
• type Node
  • func NewNode[O, P comparable](id O) *Node[O, P]
  • func (node *Node[O, P]) Connect(from, to P)
  • func (node *Node[O, P]) ConnectBi(from, to P)
  • func (node *Node[O, P]) Equals(o *Node[O, P]) bool
  • func (node *Node[O, P]) Id() O
  • func (node *Node[O, P]) Next(port P) []P
  • func (node *Node[O, P]) String() string
• type PathSegment
  • func (seg *PathSegment[O, P]) String() string
• type Triple

Types

type Connection

type Connection[O, P comparable] struct {
	FromNode *Node[O, P]
	FromPort P
	ToNode   *Node[O, P]
	ToPort   P
}

func NewConnection

func NewConnection[O, P comparable](fromNode *Node[O, P], fromPort P, toNode *Node[O, P], toPort P) *Connection[O, P]

func (*Connection[O, P]) EqualNodes

func (connection *Connection[O, P]) EqualNodes() bool

func (*Connection[O, P]) IsSelf

func (connection *Connection[O, P]) IsSelf() bool

func (*Connection[O, P]) String

func (connection *Connection[O, P]) String() string

type Graph

type Graph[O, P comparable] struct {
	// contains filtered or unexported fields
}

func NewGraph

func NewGraph[O, P comparable]() *Graph[O, P]

func (*Graph[O, P]) AddConnection

func (graph *Graph[O, P]) AddConnection(connection *Connection[O, P]) error

func (*Graph[O, P]) AddNode

func (graph *Graph[O, P]) AddNode(node *Node[O, P])

func (*Graph[O, P]) Connect

func (graph *Graph[O, P]) Connect(fromNode *Node[O, P], fromPort P, toNode *Node[O, P], toPort P) error

func (*Graph[O, P]) ConnectBi

func (graph *Graph[O, P]) ConnectBi(fromNode *Node[O, P], fromPort P, toNode *Node[O, P], toPort P) error

func (*Graph[O, P]) ConnectRef

func (graph *Graph[O, P]) ConnectRef(fromRef O, fromPort P, toRef O, toPort P) error

func (*Graph[O, P]) ConnectRefBi

func (graph *Graph[O, P]) ConnectRefBi(fromRef O, fromPort P, toRef O, toPort P) error

func (*Graph[O, P]) Find

func (graph *Graph[O, P]) Find(fromNode *Node[O, P], fromPort P, toNode *Node[O, P], toPort P) [][]*PathSegment[O, P]

func (*Graph[O, P]) FindConnection

func (graph *Graph[O, P]) FindConnection(node *Node[O, P], port P) (*Connection[O, P], bool)

func (*Graph[O, P]) FindRef

func (graph *Graph[O, P]) FindRef(fromRef O, fromPort P, toRef O, toPort P) ([][]*PathSegment[O, P], error)

type Node

type Node[O, P comparable] struct {
	// contains filtered or unexported fields
}

func NewNode

func NewNode[O, P comparable](id O) *Node[O, P]

func (*Node[O, P]) Connect

func (node *Node[O, P]) Connect(from, to P)

func (*Node[O, P]) ConnectBi

func (node *Node[O, P]) ConnectBi(from, to P)

func (*Node[O, P]) Equals

func (node *Node[O, P]) Equals(o *Node[O, P]) bool

func (*Node[O, P]) Id

func (node *Node[O, P]) Id() O

func (*Node[O, P]) Next

func (node *Node[O, P]) Next(port P) []P

func (*Node[O, P]) String

func (node *Node[O, P]) String() string

type PathSegment

type PathSegment[O, P comparable] Triple[optional.Option[P], *Node[O, P], optional.Option[P]]

func (*PathSegment[O, P]) String

func (seg *PathSegment[O, P]) String() string

type Triple

type Triple[L, M, R any] struct {
	Left   L
	Middle M
	Right  R
}