lib

package
v1.6.3 Latest Latest
Warning

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

 Go to latest Published: Apr 8, 2021 License: MIT Imports: 22 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

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

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

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 {
	// contains filtered or unexported fields
}

A CombinationIterator generates combinations iteratively.

func SplitCombin 

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

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

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

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 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 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) 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 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) 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 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 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) ([]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) 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 Node 

type Node struct {
	Bag      []int
	Cover    Edges
	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) 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 ParentCheck 

type ParentCheck struct {
	Conn  []int
	Child []int
}

ParentCheck looks a separator that could function as the direct ancestor (or "parent") of some child node in the GHD, where the connecting vertices "Conn" are explicitly provided

func (ParentCheck) Check 

func (p ParentCheck) Check(H *Graph, sep *Edges, balFactor int) bool

Check performs the needed computation to ensure whether sep is a good parent

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) bool
}

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

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

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

func (*Search) FindNext 

func (s *Search) 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

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

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.