algorithms

Documentation

Overview

Package algorithms implements various algorithms to compute Generalized Hypertree Decompositions as well as the more restricted set of Hypertree Decompositions.

Index

• type Algorithm
• type AlgorithmDebug
• 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) SetGenerator(Gen lib.SearchGenerator)
  • 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) SetGenerator(Gen lib.SearchGenerator)
  • 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 (b *BalSepHybridSeq) SetGenerator(Gen lib.SearchGenerator)
  • 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) SetGenerator(Gen lib.SearchGenerator)
  • func (b *BalSepLocal) SetWidth(K int)
• type Counters
  • func (c *Counters) AddBacktrack(level int)
  • func (c *Counters) CopyRef(other *Counters)
  • func (c *Counters) Init()
  • func (c *Counters) String() string
• 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) SetGenerator(Gen lib.SearchGenerator)
  • func (d *DetKDecomp) SetWidth(K int)
• type JCostBalSepLocal
  • func (b JCostBalSepLocal) FindDecomp() lib.Decomp
  • func (b JCostBalSepLocal) FindDecompGraph(G lib.Graph) lib.Decomp
  • func (b JCostBalSepLocal) Name() string
  • func (b *JCostBalSepLocal) SetGenerator(Gen lib.SearchGenerator)
  • func (b *JCostBalSepLocal) SetWidth(K int)
• type SplitDecomp
  • func (d *SplitDecomp) FindDecomp() lib.Decomp
  • func (d *SplitDecomp) FindDecompGraph(G lib.Graph) lib.Decomp
  • func (d *SplitDecomp) Name() string
  • func (d *SplitDecomp) SetWidth(K int)

Types

type Algorithm

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

Algorithm serves as the common interface of all hypergraph decomposition algorithms

type AlgorithmDebug

type AlgorithmDebug interface {
	GetCounters() Counters // GetCounters returns the counters collected during a run
}

An AlgorithmDebug exports internal counters to see how far the computation has progressed. To be extracted in case of a timeout.

type BalSepGlobal

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

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) SetGenerator

func (b *BalSepGlobal) SetGenerator(Gen lib.SearchGenerator)

SetGenerator defines the type of Search to use

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
	Generator lib.SearchGenerator
}

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) SetGenerator

func (b *BalSepHybrid) SetGenerator(Gen lib.SearchGenerator)

SetGenerator defines the type of Search to use

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
	Generator lib.SearchGenerator
}

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) SetGenerator

func (b *BalSepHybridSeq) SetGenerator(Gen lib.SearchGenerator)

SetGenerator defines the type of Search to use

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
	Generator lib.SearchGenerator
}

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) SetGenerator

func (b *BalSepLocal) SetGenerator(Gen lib.SearchGenerator)

SetGenerator defines the type of Search to use

func (*BalSepLocal) SetWidth

func (b *BalSepLocal) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm

type Counters

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

Counters allow to track how often an algorithm had to backtrack, and at which level, and the toplevel completion as a percentage value between [0,1)

func (*Counters) AddBacktrack

func (c *Counters) AddBacktrack(level int)

AddBacktrack enables a thread-safe way to add new backtracks to the counter

func (*Counters) CopyRef

func (c *Counters) CopyRef(other *Counters)

CopyRef allows for safe copying of a cache by reference, not value

func (*Counters) Init

func (c *Counters) Init()

Init is used to set up the Counters struct

func (*Counters) String

func (c *Counters) String() string

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) SetGenerator

func (d *DetKDecomp) SetGenerator(Gen lib.SearchGenerator)

SetGenerator defines the type of Search to use

func (*DetKDecomp) SetWidth

func (d *DetKDecomp) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm

type JCostBalSepLocal

type JCostBalSepLocal struct {
	K         int
	Graph     lib.Graph
	BalFactor int
	Generator lib.SearchGenerator
	JCosts    lib.EdgesCostMap
}

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 (JCostBalSepLocal) FindDecomp

func (b JCostBalSepLocal) FindDecomp() lib.Decomp

FindDecomp finds a decomp

func (JCostBalSepLocal) FindDecompGraph

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

FindDecompGraph finds a decomp, for an explicit graph

func (JCostBalSepLocal) Name

func (b JCostBalSepLocal) Name() string

Name returns the name of the algorithm

func (*JCostBalSepLocal) SetGenerator

func (b *JCostBalSepLocal) SetGenerator(Gen lib.SearchGenerator)

SetGenerator defines the type of Search to use

func (*JCostBalSepLocal) SetWidth

func (b *JCostBalSepLocal) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm

type SplitDecomp

type SplitDecomp struct {
	K     int
	Graph lib.Graph
}

SplitDecomp is a special algorihm that only tries to find a decomposition by splitting the hypergraph in two. This is only useful as a first step for the approximation method for finding decomposition.

func (*SplitDecomp) FindDecomp

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

FindDecomp finds a decomp

func (*SplitDecomp) FindDecompGraph

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

FindDecompGraph finds a decomp, for an explicit lib.Graph

func (*SplitDecomp) Name

func (d *SplitDecomp) Name() string

Name returns the name of the algorithm

func (*SplitDecomp) SetWidth

func (d *SplitDecomp) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm