algorithms

package
v1.7.2 Latest Latest
Warning

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

 Go to latest Published: Aug 7, 2022 License: MIT Imports: 10 Imported by: 1

Documentation

Overview

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

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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 added in v1.6.1 

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 added in v1.6.6 

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 added in v1.6.6 

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 added in v1.6.6 

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 added in v1.6.6 

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 added in v1.6.1 

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 added in v1.6.1 

func (c *Counters) AddBacktrack(level int)

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

func (*Counters) CopyRef added in v1.6.1 

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

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

func (*Counters) Init added in v1.6.1 

func (c *Counters) Init()

Init is used to set up the Counters struct

func (*Counters) String added in v1.6.1 

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 added in v1.6.6 

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 added in v1.6.15 

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 added in v1.6.15 

func (b JCostBalSepLocal) FindDecomp() lib.Decomp

FindDecomp finds a decomp

func (JCostBalSepLocal) FindDecompGraph added in v1.6.15 

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

FindDecompGraph finds a decomp, for an explicit graph

func (JCostBalSepLocal) Name added in v1.6.15 

func (b JCostBalSepLocal) Name() string

Name returns the name of the algorithm

func (*JCostBalSepLocal) SetGenerator added in v1.6.15 

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

SetGenerator defines the type of Search to use

func (*JCostBalSepLocal) SetWidth added in v1.6.15 

func (b *JCostBalSepLocal) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm

type SplitDecomp added in v1.6.4 

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 added in v1.6.4 

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

FindDecomp finds a decomp

func (*SplitDecomp) FindDecompGraph added in v1.6.4 

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

FindDecompGraph finds a decomp, for an explicit lib.Graph

func (*SplitDecomp) Name added in v1.6.4 

func (d *SplitDecomp) Name() string

Name returns the name of the algorithm

func (*SplitDecomp) SetWidth added in v1.6.4 

func (d *SplitDecomp) SetWidth(K int)

SetWidth sets the current width parameter of the algorithm

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.