algorithms

Documentation

Index

• type Category
• type PseudoSteiner
  • func NewPseudoSteiner[K comparable](graph gograph.Graph[K], opts ...PseudoSteinerOption[K]) (*PseudoSteiner[K], error)
  • func (q *PseudoSteiner[K]) Run(terminals []K) (gograph.Graph[K], error)
• type PseudoSteinerOption
  • func WithMaxEffort[K comparable](maxEffort float64) PseudoSteinerOption[K]
• type Sap
  • func NewSapAlgorithm(graph gograph.Graph[string], opts ...SapOption) (*Sap, error)
  • func (s *Sap) Run() (*SapResult, error)
• type SapOption
  • func WithLeaves(leaves int) SapOption
  • func WithRoots(roots int) SapOption
  • func WithTrunks(trunks int) SapOption
• type SapResult

Types

type Category

type Category string

const (
	CategoryNone  Category = "none"
	CategoryRoot  Category = "root"
	CategoryTrunk Category = "trunk"
	CategoryLeaf  Category = "leaf"
)

type PseudoSteiner

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

PseudoSteiner is a struct that represents a pseudo-steiner algorithm.

func NewPseudoSteiner

func NewPseudoSteiner[K comparable](graph gograph.Graph[K], opts ...PseudoSteinerOption[K]) (*PseudoSteiner[K], error)

NewPseudoSteiner creates a new PseudoSteiner instance.

It takes linear or amortized O(V + E) time to prepare the pseudo-steiner structure.

func (*PseudoSteiner[K]) Run

func (q *PseudoSteiner[K]) Run(terminals []K) (gograph.Graph[K], error)

Run runs the pseudo-steiner algorithm on the given terminals and returns the resulting graph.

Go figure what the complexity is. But don't call this with a large number of terminals.

type PseudoSteinerOption

type PseudoSteinerOption[K comparable] func(*PseudoSteiner[K])

func WithMaxEffort

func WithMaxEffort[K comparable](maxEffort float64) PseudoSteinerOption[K]

WithMaxEffort sets the maximum effort for the pseudo-steier algorithm.

type Sap

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

func NewSapAlgorithm

func NewSapAlgorithm(graph gograph.Graph[string], opts ...SapOption) (*Sap, error)

func (*Sap) Run

func (s *Sap) Run() (*SapResult, error)

type SapOption

type SapOption func(*Sap)

func WithLeaves

func WithLeaves(leaves int) SapOption

func WithRoots

func WithRoots(roots int) SapOption

func WithTrunks

func WithTrunks(trunks int) SapOption

type SapResult

type SapResult struct {
	Categories map[string]Category
	Rootness   map[string]float64
	Trunkness  map[string]float64
	Leafness   map[string]float64
}