algorithms

Documentation

Index

• type Algorithm
• type BalSepGlobal
  • func (b BalSepGlobal) FindDecomp() lib.Decomp
  • func (b BalSepGlobal) FindDecompGraph(G lib.Graph) lib.Decomp
  • func (b BalSepGlobal) Name() string
  • func (b *BalSepGlobal) SetWidth(K int)
• type BalSepHybrid
  • func (b BalSepHybrid) FindDecomp() lib.Decomp
  • func (b BalSepHybrid) FindDecompGraph(G lib.Graph) lib.Decomp
  • func (b BalSepHybrid) Name() string
  • func (b *BalSepHybrid) SetWidth(K int)
• type BalSepHybridSeq
  • func (s BalSepHybridSeq) FindDecomp() lib.Decomp
  • func (s BalSepHybridSeq) FindDecompGraph(G lib.Graph) lib.Decomp
  • func (s BalSepHybridSeq) Name() string
  • func (s *BalSepHybridSeq) SetWidth(K int)
• type BalSepLocal
  • func (b BalSepLocal) FindDecomp() lib.Decomp
  • func (b BalSepLocal) FindDecompGraph(G lib.Graph) lib.Decomp
  • func (b BalSepLocal) Name() string
  • func (b *BalSepLocal) SetWidth(K int)
• type DetKDecomp
  • func (d *DetKDecomp) FindDecomp() lib.Decomp
  • func (d *DetKDecomp) FindDecompGraph(G lib.Graph) lib.Decomp
  • func (d *DetKDecomp) Name() string
  • func (d *DetKDecomp) SetWidth(K int)
• type HybridPredicate
• type LogKDecomp
  • func (l *LogKDecomp) FindDecomp() lib.Decomp
  • func (l *LogKDecomp) FindDecompGraph(Graph lib.Graph) lib.Decomp
  • func (l *LogKDecomp) Name() string
  • func (l *LogKDecomp) SetWidth(K int)
• type LogKHybrid
  • func (l *LogKHybrid) ETimesKDivAvgEdgePred(H lib.Graph, K int) bool
  • func (l *LogKHybrid) FindDecomp() lib.Decomp
  • func (l *LogKHybrid) FindDecompGraph(Graph lib.Graph) lib.Decomp
  • func (l *LogKHybrid) Name() string
  • func (l *LogKHybrid) NumberEdgesPred(H lib.Graph, K int) bool
  • func (l *LogKHybrid) OneRoundPred(H lib.Graph, K int) bool
  • func (l *LogKHybrid) SetWidth(K int)
  • func (l *LogKHybrid) SumEdgesPred(H lib.Graph, K int) bool

Types

type Algorithm

type Algorithm interface {
	// A Name is useful to identify the individual algorithms in the result
	Name() string
	FindDecomp() lib.Decomp
	FindDecompGraph(G lib.Graph) lib.Decomp
	SetWidth(K int)
}

Algorithm serves as the common interfacea of all hypergraph decomposition algorithms

type BalSepGlobal

type BalSepGlobal struct {
	K         int
	Graph     lib.Graph
	BalFactor int
}

BalSepGlobal implements the global Balanced Separator algorithm. This requires all subedges to be added explicitly to the input lib.Graph.

func (BalSepGlobal) FindDecomp

func (b BalSepGlobal) FindDecomp() lib.Decomp

FindDecomp finds a decomp

func (BalSepGlobal) FindDecompGraph

func (b BalSepGlobal) FindDecompGraph(G lib.Graph) lib.Decomp

FindDecompGraph finds a decomp, for an explicit lib.Graph

func (BalSepGlobal) Name

func (b BalSepGlobal) Name() string

Name returns the name of the algorithm

func (*BalSepGlobal) SetWidth

func (b *BalSepGlobal) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm

type BalSepHybrid

type BalSepHybrid struct {
	K         int
	Graph     lib.Graph
	BalFactor int
	Depth     int // how many rounds of balSep are used
}

BalSepHybrid implements a hybridised algorithm, using BalSep Local and DetKDecomp in tandem

func (BalSepHybrid) FindDecomp

func (b BalSepHybrid) FindDecomp() lib.Decomp

FindDecomp finds a decomp

func (BalSepHybrid) FindDecompGraph

func (b BalSepHybrid) FindDecompGraph(G lib.Graph) lib.Decomp

FindDecompGraph finds a decomp, for an explicit graph

func (BalSepHybrid) Name

func (b BalSepHybrid) Name() string

Name returns the name of the algorithm

func (*BalSepHybrid) SetWidth

func (b *BalSepHybrid) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm

type BalSepHybridSeq

type BalSepHybridSeq struct {
	K         int
	Graph     lib.Graph
	BalFactor int
	Depth     int // how many rounds of balSep are used
}

BalSepHybridSeq is a purely sequential version of BalSepHybrid

func (BalSepHybridSeq) FindDecomp

func (s BalSepHybridSeq) FindDecomp() lib.Decomp

FindDecomp finds a decomp

func (BalSepHybridSeq) FindDecompGraph

func (s BalSepHybridSeq) FindDecompGraph(G lib.Graph) lib.Decomp

FindDecompGraph finds a decomp, for an explicit graph

func (BalSepHybridSeq) Name

func (s BalSepHybridSeq) Name() string

Name returns the name of the algorithm

func (*BalSepHybridSeq) SetWidth

func (s *BalSepHybridSeq) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm

type BalSepLocal

type BalSepLocal struct {
	K         int
	Graph     lib.Graph
	BalFactor int
}

BalSepLocal implements the local Balanced Separator algorithm for computing GHDs. This will look for subedges locally, i.e. create them for each subgraph as needed.

func (BalSepLocal) FindDecomp

func (b BalSepLocal) FindDecomp() lib.Decomp

FindDecomp finds a decomp

func (BalSepLocal) FindDecompGraph

func (b BalSepLocal) FindDecompGraph(G lib.Graph) lib.Decomp

FindDecompGraph finds a decomp, for an explicit graph

func (BalSepLocal) Name

func (b BalSepLocal) Name() string

Name returns the name of the algorithm

func (*BalSepLocal) SetWidth

func (b *BalSepLocal) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm

type DetKDecomp

type DetKDecomp struct {
	K         int
	Graph     lib.Graph
	BalFactor int
	SubEdge   bool
	// contains filtered or unexported fields
}

DetKDecomp computes for a graph and some width K a HD of width K if it exists

func (*DetKDecomp) FindDecomp

func (d *DetKDecomp) FindDecomp() lib.Decomp

FindDecomp finds a decomp

func (*DetKDecomp) FindDecompGraph

func (d *DetKDecomp) FindDecompGraph(G lib.Graph) lib.Decomp

FindDecompGraph finds a decomp, for an explicit graph

func (*DetKDecomp) Name

func (d *DetKDecomp) Name() string

Name returns the name of the algorithm

func (*DetKDecomp) SetWidth

func (d *DetKDecomp) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm

type HybridPredicate

type HybridPredicate = func(H lib.Graph, K int) bool

HybridPredicate is used to determine when to switch from LogKDecomp to using DetKDecomp

type LogKDecomp

type LogKDecomp struct {
	Graph lib.Graph
	K     int

	BalFactor int
	// contains filtered or unexported fields
}

LogKDecomp implements a parallel log-depth HD algorithm

func (*LogKDecomp) FindDecomp

func (l *LogKDecomp) FindDecomp() lib.Decomp

FindDecomp finds a decomp

func (*LogKDecomp) FindDecompGraph

func (l *LogKDecomp) FindDecompGraph(Graph lib.Graph) lib.Decomp

FindDecompGraph finds a decomp, for an explicit graph

func (*LogKDecomp) Name

func (l *LogKDecomp) Name() string

Name returns the name of the algorithm

func (*LogKDecomp) SetWidth

func (l *LogKDecomp) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm

type LogKHybrid

type LogKHybrid struct {
	Graph lib.Graph
	K     int

	BalFactor int
	Predicate HybridPredicate // used to determine when to switch to DetK
	Size      int
	// contains filtered or unexported fields
}

LogKHybrid implements a hybridised algorithm, using LogKDecomp and DetKDecomp in tandem

func (*LogKHybrid) ETimesKDivAvgEdgePred

func (l *LogKHybrid) ETimesKDivAvgEdgePred(H lib.Graph, K int) bool

ETimesKDivAvgEdgePred checks a complex formula over the subgraph and used K

func (*LogKHybrid) FindDecomp

func (l *LogKHybrid) FindDecomp() lib.Decomp

FindDecomp finds a decomp

func (*LogKHybrid) FindDecompGraph

func (l *LogKHybrid) FindDecompGraph(Graph lib.Graph) lib.Decomp

FindDecompGraph finds a decomp, for an explicit graph

func (*LogKHybrid) Name

func (l *LogKHybrid) Name() string

Name returns the name of the algorithm

func (*LogKHybrid) NumberEdgesPred

func (l *LogKHybrid) NumberEdgesPred(H lib.Graph, K int) bool

NumberEdgesPred checks the number of edges of the subgraph

func (*LogKHybrid) OneRoundPred

func (l *LogKHybrid) OneRoundPred(H lib.Graph, K int) bool

OneRoundPred will match the behaviour of BalDetK, with Depth 1

func (*LogKHybrid) SetWidth

func (l *LogKHybrid) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm

func (*LogKHybrid) SumEdgesPred

func (l *LogKHybrid) SumEdgesPred(H lib.Graph, K int) bool

SumEdgesPred checks the sum over all edges of the subgraph