lib

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: 24 Imported by: 7

Documentation

Overview

Package lib provides various functions, data structures and methods to aid in the design of algorithms to compute structural decomposition methods.

Index

Constants

This section is empty.

Variables

View Source 
var Empty struct{}

Empty used for maps of type struct{}

Functions

func Diff 

func Diff(a, b []int) []int

Diff computes the set difference between two slices a b

func GetGraph 

func GetGraph(s string) (Graph, ParseGraph)

GetGraph parses a string in HyperBench format into a graph

func GetPercentagesSlice added in v1.6.1 

func GetPercentagesSlice(cs []*CombinationIterator) (int, int)

GetPercentagesSlice calculates a total percentage from a slice of CombinationIterators

func IntHash 

func IntHash(vertices []int) uint32

IntHash computes a hash for slices of integers

func Inter 

func Inter(as, bs []int) []int

Inter is the set intersection between slices as and bs

func PrintVertices 

func PrintVertices(vertices []int) string

PrintVertices will pretty print an int slice using the encodings in the m map

func RemoveDuplicates 

func RemoveDuplicates(elements []int) []int

RemoveDuplicates is using an algorithm from "SliceTricks" https://github.com/golang/go/wiki/SliceTricks

func Subset 

func Subset(as []int, bs []int) bool

Subset returns true if as subset of bs, false otherwise

func TransparentEncoding added in v1.7.2 

func TransparentEncoding()

TransparentEncoding will overwrite the encoding map in order to print out the exact underlying integer encoding. Needs to be called after GetGraph to be effective.

func WriteDecomp added in v1.7.0 

func WriteDecomp(input Decomp) []byte

Types

type AlgorithmH 

type AlgorithmH interface {
	Name() string
	FindDecomp() Decomp
	FindDecompGraph(G Graph) Decomp
	SetWidth(K int)
}

AlgorithmH is strict generalisation on the Algorithm interface.

type BalancedCheck 

type BalancedCheck struct{}

BalancedCheck looks for Balanced Separators

func (BalancedCheck) Check 

func (b BalancedCheck) Check(H *Graph, sep *Edges, balFactor int, Vertices map[int]*disjoint.Element) bool

Check performs the needed computation to ensure whether sep is a Balanced Separator

func (BalancedCheck) CheckOut added in v1.6.15 

func (b BalancedCheck) CheckOut(H *Graph, sep *Edges, balFactor int, Vertices map[int]*disjoint.Element) (bool, []Graph, []Edge)

CheckOut does the same as Check, except it also passes on the components found, if output is true

type Cache 

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

Cache implements a caching mechanism for generic hypergraph decomposition algorithms

func (*Cache) AddNegative 

func (c *Cache) AddNegative(sep Edges, comp Graph)

AddNegative adds a separator sep and subgraph comp as a known failure case

func (*Cache) AddPositive 

func (c *Cache) AddPositive(sep Edges, comp Graph)

AddPositive adds a separator sep and subgraph comp as a known successor case TODO: not really used and tested

func (*Cache) CheckNegative 

func (c *Cache) CheckNegative(sep Edges, comps []Graph) bool

CheckNegative checks for a separator sep and a subgraph whether it is a known failure case

func (*Cache) CheckPositive 

func (c *Cache) CheckPositive(sep Edges, comps []Graph) bool

CheckPositive checks for a separator sep and a subgraph whether it is a known successor case TODO: not really used and tested

func (*Cache) CopyRef 

func (c *Cache) CopyRef(other *Cache)

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

func (*Cache) Init 

func (c *Cache) Init()

Init needs to be called to initialise the cache

func (*Cache) Len 

func (c *Cache) Len() int

Len returns the number of bindings in the cache

func (*Cache) Reset added in v1.5.7 

func (c *Cache) Reset()

Reset will throw out all saved cache entries

type CombinationIterator 

type CombinationIterator struct {
	N           int
	K           int
	OldK        int // needed to compute current progress
	Combination []int
	Empty       bool
	StepSize    int
	Extended    bool
	Confirmed   bool
	BalSep      bool // cache the result of balSep check
}

A CombinationIterator generates combinations iteratively.

func (*CombinationIterator) CheckFound added in v1.6.6 

func (c *CombinationIterator) CheckFound() bool

CheckFound returns the current value of the cached result

func (*CombinationIterator) Confirm added in v1.6.6 

func (c *CombinationIterator) Confirm()

Confirm is used to double check the last element has been used. Useful only for concurrent searching

func (*CombinationIterator) Found added in v1.6.6 

func (c *CombinationIterator) Found()

Found is used by the search to cache the previous check result

func (*CombinationIterator) GetNext added in v1.6.6 

func (c *CombinationIterator) GetNext() []int

GetNext returns the currently selected combination

func (CombinationIterator) GetPercentage 

func (c CombinationIterator) GetPercentage() float32

GetPercentage returns the current progress as a percentage, with 100% representing that all combinations have been visited

func (*CombinationIterator) HasNext added in v1.6.6 

func (c *CombinationIterator) HasNext() bool

HasNext checks if the iterator still has new elements and advances the iterator if so

type Cover 

type Cover struct {
	InComp []bool //indicates for each Edge if its in comp. or not

	Subset []int //The current selection

	HasNext bool
	// contains filtered or unexported fields
}

Cover is used to quickly iterate over all valid hypergraph covers for a subset of vertices

func NewCover 

func NewCover(K int, vertices []int, bound Edges, compVertices []int) Cover

NewCover acts as a constructor for Cover

func (*Cover) NextSubset 

func (c *Cover) NextSubset() int

NextSubset returns number of selected edges, or -1 if no alternative possible

type DSD added in v1.6.11 

type DSD struct {
	Graph       *Graph
	SepVertices map[int]bool //cached vertices of the seperator
	Vertices    map[int]*disjoint.Element
	Comps       map[*disjoint.Element][]Edge
	CompsSp     map[*disjoint.Element][]Edges
}
A DSD (short for Disjoint-Set-Datastructure) collects the information on the connected components of a graph

relative to seperator

func (*DSD) AddSepVertices added in v1.6.12 

func (d *DSD) AddSepVertices(e Edge)

AddSepVertices adds new map bindings to SepVertices

func (*DSD) Update added in v1.6.11 

func (d *DSD) Update(e Edge)

type Decomp 

type Decomp struct {
	Graph         Graph
	Root          Node
	SkipRerooting bool //needed for BalDetK
}

A Decomp (short for Decomposition) consists of a labelled tree which subdivides a graph in a certain way

func GetDecomp added in v1.7.0 

func GetDecomp(input []byte, graph Graph, encoding map[string]int) Decomp

func GetDecompGML 

func GetDecompGML(input string, graph Graph, encoding map[string]int) Decomp

GetDecompGML can parse an input string in GML format to produce a decomp

func (Decomp) CheckWidth 

func (d Decomp) CheckWidth() int

CheckWidth returns the size of the largest bag of any node in a decomp

func (Decomp) Correct 

func (d Decomp) Correct(g Graph) bool

Correct checks if a decomp full fills the properties of a GHD when given a hypergraph g as input. It also checks for the special condition of HDs, though it merely prints a warning if it is not satisfied, the output is not affected by this additional check.

func (Decomp) IntoJson added in v1.7.0 

func (d Decomp) IntoJson() DecompJson

func (*Decomp) RestoreSubedges 

func (d *Decomp) RestoreSubedges()

RestoreSubedges replaces any ad-hoc subedge with actual edges occurring in the graph

func (Decomp) String 

func (d Decomp) String() string

func (Decomp) ToGML 

func (d Decomp) ToGML() string

ToGML exports the decomp as a string, in GML format

type DecompJson added in v1.7.0 

type DecompJson struct {
	Root NodeJson
}

func (DecompJson) IntoDecomp added in v1.7.0 

func (d DecompJson) IntoDecomp(graph Graph, encoding map[string]int) Decomp

type Edge 

type Edge struct {
	Name     int
	Vertices []int // use integers for vertices
}

An Edge (used here for hyperedge) consists of a collection of vertices and a name

func (Edge) FullString 

func (e Edge) FullString() string

FullString always prints the list of vertices of an edge, even if the edge is named

func (Edge) FullStringInt added in v1.5.7 

func (e Edge) FullStringInt() string

FullStringInt always prints the list of vertices of an edge, even if the edge is named

func (Edge) Hash 

func (e Edge) Hash() uint64

Hash computes a (non-cryptographic) hash. This hash is the same for all permutations of this edge

func (Edge) String 

func (e Edge) String() string

type Edges 

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

Edges struct is a slice of Edge, defined for the use of the sort interface, as well as various other optimisations which are only possible on the slice level

func CutEdges 

func CutEdges(edges Edges, vertices []int) Edges

CutEdges filters an Edges slice for a given set of vertices. Edges are transformed to their intersection against the vertex set, producing the induced subgraph

func FilterVertices 

func FilterVertices(edges Edges, vertices []int) Edges

FilterVertices filters an Edges slice for a given set of vertices. Edges are only removed, if they have an empty intersection with the vertex set.

func FilterVerticesStrict 

func FilterVerticesStrict(edges Edges, vertices []int) Edges

FilterVerticesStrict filters an Edges slice for a given set of vertices. Edges are removed if they are not full subsets of the vertex set

func GetDegreeOrder 

func GetDegreeOrder(edges Edges) Edges

GetDegreeOrder orders the edges based on the sum of the vertex degrees

func GetEdgeDegreeOrder 

func GetEdgeDegreeOrder(edges Edges) Edges

GetEdgeDegreeOrder orders the edges based on the sum of the edge degrees

func GetMSCOrder 

func GetMSCOrder(edges Edges) Edges

GetMSCOrder produces the Maximal Cardinality Search Ordering. Implementation is based det-k-decomp of Samer and Gottlob '09

func GetMaxSepOrder 

func GetMaxSepOrder(edges Edges) Edges

GetMaxSepOrder orders the edges by how much they increase shortest paths within the hypergraph, using basic Floyd-Warschall (using the primal graph)

func GetSubset 

func GetSubset(edges Edges, s []int) Edges

GetSubset produces a selection of edges from slice of integers s used as indices. This is used to select new potential separators. Note that special edges are ignored here, since they should never be considered when choosing a separator

func NewEdges 

func NewEdges(slice []Edge) Edges

NewEdges is a constructor for Edges

func (*Edges) Diff 

func (e *Edges) Diff(other Edges) Edges

Diff computes the set difference of edges based on names

func (Edges) FullString 

func (e Edges) FullString() string

FullString always prints the list of vertices of an edge, even if named

func (*Edges) GobDecode added in v1.6.7 

func (e *Edges) GobDecode(b []byte) error

func (Edges) GobEncode added in v1.6.7 

func (e Edges) GobEncode() ([]byte, error)

func (*Edges) Hash 

func (e *Edges) Hash() uint64

Hash computes a (non-cryptographic) hash. This hash is the same for all permutations of edges

func (Edges) Len 

func (e Edges) Len() int

Len returns the length of the internal slice

func (Edges) Less 

func (e Edges) Less(i, j int) bool

lexicographic order on each edge

func (*Edges) RemoveDuplicates 

func (e *Edges) RemoveDuplicates()

RemoveDuplicates removes duplicate edges from an Edges struct

func (Edges) Slice 

func (e Edges) Slice() []Edge

Slice returns the internal slice of an Edges struct

func (Edges) String 

func (e Edges) String() string

func (Edges) Swap 

func (e Edges) Swap(i, j int)

Swap as used for the sort interface

func (*Edges) Vertices 

func (e *Edges) Vertices() []int

Vertices produces the union of all vertices from a slice of Edge

type EdgesCostMap added in v1.6.15 

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

An EdgesCostMap associates costs to combinations of edges

func (*EdgesCostMap) Cost added in v1.6.15 

func (m *EdgesCostMap) Cost(edgeComb []int) float64

Cost of an edge combination

func (*EdgesCostMap) Init added in v1.6.15 

func (m *EdgesCostMap) Init()

Init an EdgeCostMap with the edges on which it will work

func (*EdgesCostMap) Put added in v1.6.15 

func (m *EdgesCostMap) Put(edgeComb []int, c float64)

Put the cost of an edge combination into the map

func (EdgesCostMap) Records added in v1.6.15 

func (m EdgesCostMap) Records() ([]uint64, []float64)

Records in this EdgesCostMap

type GYÖReduct 

type GYÖReduct interface {
	// contains filtered or unexported methods
}

A GYÖReduct (that's short for GYÖ (Graham - Yu - Özsoyoğlu) Reduction ) consists of a list of operations that simplify a graph by 1) removing isolated vertices or 2) removing edges fully contained in other edges (and applying these two operations iteratively, until convergence)

type Generator added in v1.6.6 

type Generator interface {
	HasNext() bool    // check if generator still has new elements
	GetNext() []int   // the slice of int represents some choice of edges, with an underlying order
	Confirm()         // confirm that the current selection has been checked *and* sent to central goroutine
	Found()           // used to cache the check result
	CheckFound() bool // used by search to see if previous run already performed the check
}

A Generator is black-box view for any kind of generation of items to look at in linear order, and it provides some helpful methods for the search

func SplitCombin 

func SplitCombin(n int, k int, split int, unextended bool) []Generator

SplitCombin generates multiple iterators, splitting the search space into multiple "splits"

type Graph 

type Graph struct {
	Edges   Edges
	Special []Edges
	// contains filtered or unexported fields
}

A Graph is a collection of (special) edges

func GetGraphPACE 

func GetGraphPACE(s string) Graph

GetGraphPACE parses a string in PACE 2019 format into a graph

func (Graph) ComputeSubEdges 

func (g Graph) ComputeSubEdges(K int) Graph

ComputeSubEdges computes all relevant subedges to produce a GHD of width K

func (Graph) GYÖReduct 

func (g Graph) GYÖReduct() (Graph, []GYÖReduct)

GYÖReduct performs the GYÖ reduction on the graph

func (Graph) GetBIP 

func (g Graph) GetBIP() int

GetBIP computes the BIP number of the graph

func (Graph) GetComponents 

func (g Graph) GetComponents(sep Edges, vertices map[int]*disjoint.Element) ([]Graph, map[int]int, []Edge)

GetComponents uses Disjoint Set data structure to compute connected components

func (Graph) GetSubset 

func (g Graph) GetSubset(s []int) Edges

GetSubset is as above, but the first parameter is omitted when used as the method call of a graph

func (*Graph) Hash 

func (g *Graph) Hash() uint64

Hash computes a (non-cryptographic) hash. This hash is the same for all permutations of edges

func (Graph) Len 

func (g Graph) Len() int

Len returns the number of edges and special edges of the graph

func (*Graph) MakeEdgesDistinct added in v1.6.12 

func (g *Graph) MakeEdgesDistinct() []int

func (Graph) String 

func (g Graph) String() string

func (Graph) ToHyberBenchFormat added in v1.5.7 

func (g Graph) ToHyberBenchFormat() string

ToHyberBenchFormat transforms the graph structure to a string in HyperBench Format. This is only relevant for generated instances with no existing string representation. Using this with a parsed graph is not the target use case, only used for internal testing

func (Graph) ToPACE 

func (g Graph) ToPACE() string

ToPACE exports the graph as a string, in the PACE 2019 format

func (Graph) TypeCollapse 

func (g Graph) TypeCollapse() (Graph, map[int][]int, int)

TypeCollapse performs type collapse on the graph, the mapping that's also output can be used to restore the original hypergraph.

Possible optimization: When computing the distances, use the matrix to speed up type detection

func (*Graph) Vertices 

func (g *Graph) Vertices() []int

Vertices produces the union of all vertices from all edges of the graph

type Hingetree 

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

A Hingetree is a tree with each node representing a subgraph and its respective decomposition and connected by exactly one edge, which is the sole intersection between the two graphs of its connecting nodes

func GetHingeTree 

func GetHingeTree(g Graph) Hingetree

GetHingeTree produces a hingetree for a given graph

func (Hingetree) DecompHinge 

func (h Hingetree) DecompHinge(alg AlgorithmH, g Graph) Decomp

DecompHinge computes a decomposition of the original input graph, using the hingetree to speed up the computation

func (Hingetree) GetLargestGraph 

func (h Hingetree) GetLargestGraph() Graph

GetLargestGraph returns the largest graph within the hinge tree

func (Hingetree) String 

func (h Hingetree) String() string

type JoinHeap added in v1.6.15 

type JoinHeap []*Separator

func (JoinHeap) Len added in v1.6.15 

func (jh JoinHeap) Len() int

func (JoinHeap) Less added in v1.6.15 

func (jh JoinHeap) Less(i, j int) bool

func (*JoinHeap) Pop added in v1.6.15 

func (jh *JoinHeap) Pop() interface{}

func (*JoinHeap) Push added in v1.6.15 

func (jh *JoinHeap) Push(x interface{})

func (JoinHeap) Swap added in v1.6.15 

func (jh JoinHeap) Swap(i, j int)

type Node 

type Node struct {
	Bag      []int
	Cover    Edges
	Cost     float64
	Children []Node
	// contains filtered or unexported fields
}

A Node is the root of a labelled tree, where the labels are the bag and the (edge) cover

func (*Node) CombineNodes 

func (n *Node) CombineNodes(subtree Node, connecting Edges) *Node

CombineNodes attaches subtree to n, via the connecting special edge

func (Node) IntoJson added in v1.7.0 

func (n Node) IntoJson() NodeJson

func (*Node) RemoveVertices added in v1.6.12 

func (n *Node) RemoveVertices(vertices []int)

func (Node) Reroot 

func (n Node) Reroot(child Node) Node

Reroot produces a new, isomorphic subtree, rerooting G at child

func (Node) RerootEdge 

func (n Node) RerootEdge(edge []int) Node

RerootEdge reroots G at node covering edge, producing an isomorphic graph

func (Node) RestoreGYÖ 

func (n Node) RestoreGYÖ(reducts []GYÖReduct) (Node, bool)

RestoreGYÖ can restore any performed reductions on the graph, given a slice of reducts

func (Node) RestoreTypes 

func (n Node) RestoreTypes(restoreMap map[int][]int) (Node, bool)

RestoreTypes can restore any performed Type reductions given a mapping of the reductions

func (Node) String 

func (n Node) String() string

func (*Node) Vertices 

func (n *Node) Vertices() []int

Vertices recursively collects all vertices from the bag of this node, and the bags of all its children

type NodeJson added in v1.7.0 

type NodeJson struct {
	Bag      []string
	Cover    []string
	Children []NodeJson
}

func (NodeJson) IntoNode added in v1.7.0 

func (n NodeJson) IntoNode(graph Graph, encoding map[string]int) Node

type ParallelSearch added in v1.6.6 

type ParallelSearch struct {
	H               *Graph
	Edges           *Edges
	BalFactor       int
	Result          []int
	Generators      []Generator
	ExhaustedSearch bool
}

func (*ParallelSearch) FindNext added in v1.6.6 

func (s *ParallelSearch) FindNext(pred Predicate)

FindNext starts the search and stops if some separator which satisfies the predicate is found, or if the entire search space has been exhausted

func (*ParallelSearch) GetResult added in v1.6.6 

func (s *ParallelSearch) GetResult() []int

GetResult returns the last found result

func (*ParallelSearch) SearchEnded added in v1.6.6 

func (s *ParallelSearch) SearchEnded() bool

SearchEnded returns true if search is completed

type ParallelSearchGen added in v1.6.6 

type ParallelSearchGen struct{}

func (ParallelSearchGen) GetSearch added in v1.6.6 

func (p ParallelSearchGen) GetSearch(H *Graph, Edges *Edges, BalFactor int, Gens []Generator) Search

type ParseGraph 

type ParseGraph struct {
	Edges    []parseEdge `( @@ ","?)* (".")?`
	Encoding map[string]int
}

ParseGraph contains data used to parse a graph, potentially useful for testing

func (*ParseGraph) GetEdge 

func (p *ParseGraph) GetEdge(input string) Edge

GetEdge can be used parse additional hyperedges. Useful for testing purposes

type Predicate 

type Predicate interface {
	Check(H *Graph, sep *Edges, balancedFactor int, Vertices map[int]*disjoint.Element) bool
}

A Predicate checks if for some subgraph and a separator, some condition holds 

type Search interface {
	FindNext(pred Predicate)
	SearchEnded() bool // return true if every element has been returned once
	GetResult() []int  // get the last found result
}

A Search implements a parallel search for separators fulfilling some given predicate

type SearchGenerator added in v1.6.6 

type SearchGenerator interface {
	GetSearch(H *Graph, Edges *Edges, BalFactor int, Generators []Generator) Search
}

A SearchGenerator sets up a Search interface

type SepSub 

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

SepSub is used to iterate over all subedge variants of a separator

func GetSepSub 

func GetSepSub(edges Edges, sep Edges, k int) *SepSub

GetSepSub is a constructor for SepSub

func (SepSub) GetCurrent 

func (sep SepSub) GetCurrent() Edges

GetCurrent is used to extract the current subedge variant

func (*SepSub) HasNext 

func (sep *SepSub) HasNext() bool

HasNext checks if SepSub has more subedge variants to produce

type Separator added in v1.6.15 

type Separator struct {
	Found    []int
	EdgeComb []int
	Cost     float64
}

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.