Library Reference

Lower Bound Algorithms

CliqueTrees.LowerBoundAlgorithm — Type

LowerBoundAlgorithm

An algorithm for computing a lower bound to the treewidth of a graph. The options are

type	name	time	space
`MMW`	minor-min-width		O(m + n)

CliqueTrees.MMW — Type

MMW{S} <: LowerBoundAlgorithm

MMW{S}()

The minor-min-width heuristic.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = MMW{1}()
MMW{1}

julia> lowerbound(graph; alg)
2

Parameters

S: strategy
- 1: min-d (fast)
- 2: max-d (fast)
- 3: least-c (slow)

References

Gogate, Vibhav, and Rina Dechter. "A complete anytime algorithm for treewidth." Proceedings of the 20th conference on Uncertainty in artificial intelligence. 2004.
Bodlaender, Hans, Thomas Wolle, and Arie Koster. "Contraction and treewidth lower bounds." Journal of Graph Algorithms and Applications 10.1 (2006): 5-49.

CliqueTrees.lowerbound — Function

lowerbound([weights, ]graph;
    alg::WidthOrAlgorithm=DEFAULT_LOWER_BOUND_ALGORITHM)

Compute a lower bound to the treewidth of a graph.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> lowerbound(graph)
2

CliqueTrees.DEFAULT_LOWER_BOUND_ALGORITHM — Constant

DEFAULT_LOWER_BOUND_ALGORITHM = MMW()

Dissection Algorithms

CliqueTrees.DissectionAlgorithm — Type

DissectionAlgorithm

A vertex separator algorithm.

CliqueTrees.METISND — Type

METISND <: DissectionAlgorithm

METISND(; nseps=-1, seed=-1)

Compute a vertex separator using the graph partitioning library METIS.

Parameters

nseps: number of different separators computed at each level of nested dissection
seed: random seed

References

Karypis, George, and Vipin Kumar. "A fast and high quality multilevel scheme for partitioning irregular graphs." SIAM Journal on Scientific Computing 20.1 (1998): 359-392.

CliqueTrees.KaHyParND — Type

KaHyParND{O} <: DissectionAlgorithm

KaHyParND(order; beta=1.0)

Compute a vertex separator using the hypergraph partitioning library KaHyPar. A β-quasi-clique cover is constructed using a greedy algorithm controlled by the parameters order and beta.

Parameters

order: tie breaking strategy (Forward or Reverse).
beta: quasi-clique parameter

References

Çatalyürek, Ümit V., Cevdet Aykanat, and Enver Kayaaslan. "Hypergraph partitioning-based fill-reducing ordering for symmetric matrices." SIAM Journal on Scientific Computing 33.4 (2011): 1996-2023.
Kaya, Oguz, et al. "Fill-in reduction in sparse matrix factorizations using hypergraphs".

CliqueTrees.DEFAULT_DISSECTION_ALGORITHM — Constant

DEFAULT_DISSECTION_ALGORITHM = METISND()

The default dissection algorithm.

Elimination Algorithms

CliqueTrees.EliminationAlgorithm — Type

EliminationAlgorithm

A graph elimination algorithm computes a total ordering of the vertices of a graph. The algorithms implemented in CliqueTrees.jl can be divided into five categories.

triangulation recognition algorithms
bandwidth reduction algorithms
greedy algorithms
nested dissection algorithms
exact treewidth algorithms

Triangulation Recognition Algorithms

type	name	time	space	package
`MCS`	maximum cardinality search	O(m + n)	O(n)
`LexBFS`	lexicographic breadth-first search	O(m + n)	O(m + n)
`MCSM`	maximum cardinality search (minimal)	O(mn)	O(n)
`LexM`	lexicographic breadth-first search (minimal)	O(mn)	O(n)

These algorithms will compute perfect orderings when applied to chordal graphs.

Bandwidth and Envelope Minimization Algorithms

type	name	time	space	package
`RCMMD`	reverse Cuthill-Mckee (minimum degree)	O(m + n)	O(m + n)
`RCMGL`	reverse Cuthill-Mckee (George-Liu)	O(m + n)	O(m + n)

These algorithms try to minimize the bandwidth and envelope of the ordered graph.

Local Algorithms

type	name	time	space	package
`MMD`	multiple minimum degree	O(mn²)	O(m + n)
`MF`	minimum fill	O(mn²)
`AMD`	approximate minimum degree	O(mn)	O(m + n)	AMD.jl
`SymAMD`	column approximate minimum degree	O(mn)	O(m + n)	AMD.jl
`AMF`	approximate minimum fill	O(mn)	O(m + n)

These algorithms simulate the graph elimination process, greedily eliminating vertices that minimize a cost function. They are faster then the nested dissection algorithms, but have worse results.

Global Algorithms

type	name	time	space	package
`METIS`	nested dissection			Metis.jl
`ND`	nested dissection

These algorithms recursively partition a graph, then call a local algorithm on the leaves. These are slower than the local algorithms, but have better results.

Exact Treewidth Algorithms

type	name	time	space	package
`BT`	Bouchitte-Todinca			TreeWidthSolver.jl
`SAT`	SAT encoding

The orderings computed by these algorithms induce minimum-width tree decompositions.

Warning

This is an NP-hard problem.

CliqueTrees.PermutationOrAlgorithm — Type

PermutationOrAlgorithm = Union{
AbstractVector,
Tuple{AbstractVector, AbstractVector},
EliminationAlgorithm,

}

Either a permutation or an algorithm.

CliqueTrees.DEFAULT_ELIMINATION_ALGORITHM — Constant

DEFAULT_ELIMINATION_ALGORITHM = MMD()

The default algorithm.

CliqueTrees.BFS — Type

BFS <: EliminationAlgorithm

BFS()

The breadth-first search algorithm.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = BFS()
BFS

julia> treewidth(graph; alg)
2

CliqueTrees.MCS — Type

MCS <: EliminationAlgorithm

MCS()

The maximum cardinality search algorithm.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = MCS()
MCS

julia> treewidth(graph; alg)
3

References

Tarjan, Robert E., and Mihalis Yannakakis. "Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs." SIAM Journal on Computing 13.3 (1984): 566-579.

CliqueTrees.LexBFS — Type

LexBFS <: EliminationAlgorithm

LexBFS()

The lexicographic breadth-first-search algorithm.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = LexBFS()
LexBFS

julia> treewidth(graph; alg)
2

References

Rose, Donald J., R. Endre Tarjan, and George S. Lueker. "Algorithmic aspects of vertex elimination on graphs." SIAM Journal on Computing 5.2 (1976): 266-283.

CliqueTrees.RCMMD — Type

RCMMD{A} <: EliminationAlgorithm

RCMMD(alg::Algorithm)

RCMMD()

The reverse Cuthill-McKee algorithm. An initial vertex is selected using the minimum degree heuristic.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = RCMMD(QuickSort)
RCMMD:
    Base.Sort.QuickSortAlg()

julia> treewidth(graph; alg)
3

Parameters

alg: sorting algorithm

References

Cuthill, Elizabeth, and James McKee. "Reducing the bandwidth of sparse symmetric matrices." Proceedings of the 1969 24th National Conference. 1969.

CliqueTrees.RCMGL — Type

RCMGL{A} <: EliminationAlgorithm

RCMGL(alg::Algorithm)

RCMGL()

The reverse Cuthill-McKee algorithm. An initial vertex is selected using George and Liu's variant of the GPS algorithm.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = RCMGL(QuickSort)
RCMGL:
    Base.Sort.QuickSortAlg()

julia> treewidth(graph; alg)
3

Parameters

alg: sorting algorithm

References

Cuthill, Elizabeth, and James McKee. "Reducing the bandwidth of sparse symmetric matrices." Proceedings of the 1969 24th National Conference. 1969.
George, Alan, and Joseph WH Liu. "An implementation of a pseudoperipheral node finder." ACM Transactions on Mathematical Software (TOMS) 5.3 (1979): 284-295.

CliqueTrees.RCM — Type

RCM = RCMGL

The default variant of the reverse Cuthill-Mckee algorithm.

CliqueTrees.LexM — Type

LexM <: EliminationAlgorithm

LexM()

A minimal variant of the lexicographic breadth-first-search algorithm.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = LexM()
LexM

julia> treewidth(graph; alg)
2

References

Rose, Donald J., R. Endre Tarjan, and George S. Lueker. "Algorithmic aspects of vertex elimination on graphs." SIAM Journal on Computing 5.2 (1976): 266-283.

CliqueTrees.MCSM — Type

MCSM <: EliminationAlgorithm

MCSM()

A minimal variant of the maximal cardinality search algorithm.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = MCSM()
MCSM

julia> treewidth(graph; alg)
2

References

Berry, Anne, et al. "Maximum cardinality search for computing minimal triangulations of graphs." Algorithmica 39 (2004): 287-298.

CliqueTrees.AMD — Type

AMD <: EliminationAlgorithm

AMD(; dense=10.0, aggressive=1.0)

The approximate minimum degree algorithm.

julia> using CliqueTrees

julia> import AMD as AMDLib

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = AMD(; dense=5.0, aggressive=2.0)
AMD:
    dense: 5.0
    aggressive: 2.0

julia> treewidth(graph; alg)
2

Parameters

dense: dense row parameter
aggressive: aggressive absorption

References

Amestoy, Patrick R., Timothy A. Davis, and Iain S. Duff. "An approximate minimum degree ordering algorithm." SIAM Journal on Matrix Analysis and Applications 17.4 (1996): 886-905.

CliqueTrees.SymAMD — Type

SymAMD <: EliminationAlgorithm

SymAMD(; dense_row=10.0, dense_col=10.0, aggressive=1.0)

The column approximate minimum degree algorithm.

julia> using CliqueTrees

julia> import AMD as AMDLib

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = SymAMD(; dense_row=5.0, dense_col=5.0, aggressive=2.0)
SymAMD:
    dense_row: 5.0
    dense_col: 5.0
    aggressive: 2.0


julia> treewidth(graph, alg)
2

Parameters

dense_row: dense row parameter
dense_column: dense column parameter
aggressive: aggressive absorption

References

Davis, Timothy A., et al. "A column approximate minimum degree ordering algorithm." ACM Transactions on Mathematical Software (TOMS) 30.3 (2004): 353-376.

CliqueTrees.AMF — Type

AMF <: EliminationAlgorithm

AMF()

The approximate minimum fill algorithm.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = AMF(; speed=2)
AMF

julia> treewidth(graph; alg)
2

References

Rothberg, Edward, and Stanley C. Eisenstat. "Node selection strategies for bottom-up sparse matrix ordering." SIAM Journal on Matrix Analysis and Applications 19.3 (1998): 682-695.

CliqueTrees.MF — Type

MF <: EliminationAlgorithm

MF()

The greedy minimum fill algorithm.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = MF
MF

julia> treewidth(graph; alg)
2

References

Tinney, William F., and John W. Walker. "Direct solutions of sparse network equations by optimally ordered triangular factorization." Proceedings of the IEEE 55.11 (1967): 1801-1809.

CliqueTrees.MMD — Type

MMD <: EliminationAlgorithm

MMD(; delta=0)

The multiple minimum degree algorithm.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = MMD(; delta=1)
MMD:
    delta: 1

julia> treewidth(graph; alg)
2

Parameters

delta: tolerance for multiple elimination

References

Liu, Joseph WH. "Modification of the minimum-degree algorithm by multiple elimination." ACM Transactions on Mathematical Software (TOMS) 11.2 (1985): 141-153.

CliqueTrees.METIS — Type

METIS <: EliminationAlgorithm

METIS(; ctype=-1, rtype=-1, nseps=-1, niter=-1, seed=-1,
        compress=-1, ccorder=-1, pfactor=-1, ufactor=-1)

The multilevel nested dissection algorithm implemented in METIS.

julia> using CliqueTrees, Metis

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = METIS(ctype=Metis.METIS_CTYPE_RM)
METIS:
    ctype: 0
    rtype: -1
    nseps: -1
    niter: -1
    seed: -1
    compress: -1
    ccorder: -1
    pfactor: -1
    ufactor: -1


julia> treewidth(graph; alg)
3

Parameters

ctype: matching scheme to be used during coarsening
rtype: algorithm used for refinement
nseps: number of different separators computed at each level of nested dissection
niter: number of iterations for refinement algorithm at each stage of the uncoarsening process
seed: random seed
compress: whether to combine vertices with identical adjacency lists
ccorder: whether to order connected components separately
pfactor: minimum degree of vertices that will be ordered last
ufactor: maximum allowed load imbalance partitions

References

Karypis, George, and Vipin Kumar. "A fast and high quality multilevel scheme for partitioning irregular graphs." SIAM Journal on Scientific Computing 20.1 (1998): 359-392.

CliqueTrees.ND — Type

ND{S, A, D} <: EliminationAlgorithm

ND{S}(alg::EliminationAlgorithm, dis::DissectionAlgorithm;
    width = 120,
    level = 6,
    imbalance = 130,
)

The nested dissection algorithm. The algorithm dis is used to compute vertex separators, and the algorithm alg is called on the of the separator tree. The type parameter S controls the behavior of the algorithm: if S is equal to 1 or 2, then alg is additionally called on the branches of the separator tree. At each branch, the ordering computed by alg is compared to the ordering computed by the nested dissection algorithm, and the worse of the two is discarded.

1: minimize width (slow)
2: minimize fill (slow)
3: no strategy (fast)

CliqueTrees currently has two vertex separator algorithms, both of which require loading an external package.

type	name	package
`METISND`	multilevel vertex separation	Metis.jl
`KaHyParND`	multilevel hypergraph partitioning	KayHyPar.jl

The algorithm KaHyParND computes a vertex separator indirectly, by partitioning a quasi-clique-cover of the original graph. The parameters width and level control the recursion depth of the algorithm, and the parameter imbalance controls the maximum imbalance of the vertex separator.

julia> using CliqueTrees, Metis

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = ND{1}(MF(), METISND())
ND{1, MF, METISND}:
    MF
    METISND:
        nseps: -1
        seed: -1
    width: 120
    level: 6
    imbalance: 130

julia> treewidth(graph; alg)
2

Parameters

S: strategy
- 1: minimize width (slow)
- 2: minimize fill (slow)
- 3: no strategy (fast)
alg: elimination algorithm
dis: separation algorithm
width: minimum width
level: maximum level
imbalance: separator imbalance

CliqueTrees.Spectral — Type

Spectral <: EliminationAlgorithm

Spectral(; tol=0.0)

The spectral ordering algorithm only works on connected graphs. In order to use it, import the package Laplacians.

julia> using CliqueTrees, Laplacians

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = Spectral(; tol=0.001)
Spectral:
    tol: 0.001

julia> treewidth(graph; alg)
4

Parameters

tol: tolerance for convergence

References

Barnard, Stephen T., Alex Pothen, and Horst D. Simon. "A spectral algorithm for envelope reduction of sparse matrices." Proceedings of the 1993 ACM/IEEE Conference on Supercomputing. 1993.

CliqueTrees.FlowCutter — Type

FlowCutter <: EliminationAlgorithm

FlowCutter(; time=5, seed=0)

The FlowCutter algorithm.

julia> using CliqueTrees, FlowCutterPACE17_jll

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = FlowCutter(; time=2, seed=1)
FlowCutter:
    time: 2
    seed: 1

julia> treewidth(graph; alg)
2

Parameters

time: run time
seed: random seed

References

Strasser, Ben. "Computing tree decompositions with flowcutter: PACE 2017 submission." arXiv preprint arXiv:1709.08949 (2017).

CliqueTrees.BT — Type

BT <: EliminationAlgorithm

BT()

The Bouchitte-Todinca algorithm.

julia> using CliqueTrees, TreeWidthSolver

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = BT()
BT

julia> treewidth(graph; alg)
2

References

Korhonen, Tuukka, Jeremias Berg, and Matti Järvisalo. "Solving Graph Problems via Potential Maximal Cliques: An Experimental Evaluation of the Bouchitté-Todinca Algorithm." Journal of Experimental Algorithmics (JEA) 24 (2019): 1-19.

CliqueTrees.SAT — Type

SAT{H, A} <: EliminationAlgorithm

SAT{H}(alg::PermutationOrAlgorithm)

SAT{H}()

Compute a minimum-treewidth permutation using a SAT solver.

julia> using CliqueTrees, libpicosat_jll, PicoSAT_jll, CryptoMiniSat_jll, Lingeling_jll

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = SAT{libpicosat_jll}(MF()) # picosat
SAT{libpicosat_jll, MF}:
    MF

julia> alg = SAT{PicoSAT_jll}(MF()) # picosat
SAT{PicoSAT_jll, MF}:
    MF

julia> alg = SAT{CryptoMiniSat_jll}(MF()) # cryptominisat
SAT{CryptoMiniSat_jll, MF}:
    MF

julia> alg = SAT{Lingeling_jll}(MMW(), MF()) # lingeling
SAT{Lingeling_jll, MF}:
    MF

julia> treewidth(graph; alg)
2

Parameters

alg: elimination algorithm

References

Samer, Marko, and Helmut Veith. "Encoding treewidth into SAT." Theory and Applications of Satisfiability Testing-SAT 2009: 12th International Conference, SAT 2009, Swansea, UK, June 30-July 3, 2009. Proceedings 12. Springer Berlin Heidelberg, 2009.
Berg, Jeremias, and Matti Järvisalo. "SAT-based approaches to treewidth computation: An evaluation." 2014 IEEE 26th international conference on tools with artificial intelligence. IEEE, 2014.
Bannach, Max, Sebastian Berndt, and Thorsten Ehlers. "Jdrasil: A modular library for computing tree decompositions." 16th International Symposium on Experimental Algorithms (SEA 2017). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017.

CliqueTrees.MinimalChordal — Type

MinimalChordal{A} <: EliminationAlgorithm

MinimalChordal(alg::PermutationOrAlgorithm)

MinimalChordal()

Evaluate an elimination algorithm, and them improve its output using the MinimalChordal algorithm. The result is guaranteed to be minimal.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg1 = MCS()
MCS

julia> alg2 = MinimalChordal(MCS())
MinimalChordal{MCS}:
    MCS

julia> label1, tree1 = cliquetree(graph; alg=alg1);

julia> label2, tree2 = cliquetree(graph; alg=alg2);

julia> FilledGraph(tree1) # more edges
{8, 12} FilledGraph{Int64, Int64}

julia> FilledGraph(tree2) # fewer edges
{8, 11} FilledGraph{Int64, Int64}

Parameters

alg: elimination algorithm

References

Blair, Jean RS, Pinar Heggernes, and Jan Arne Telle. "A practical algorithm for making filled graphs minimal." Theoretical Computer Science 250.1-2 (2001): 125-141.

CliqueTrees.CompositeRotations — Type

CompositeRotations{C, A} <: EliminationAlgorithm

CompositeRotations(clique::AbstractVector, alg::EliminationAlgorithm)

CompositeRotations(clique::AbstractVector)

Evaluate an eliminaton algorithm, ensuring that the given clique is at the end of the ordering.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg = CompositeRotations([2], MCS())
CompositeRotations{Vector{Int64}, MCS}:
    clique: [2]
    MCS

julia> order, index = permutation(graph; alg);

julia> order # 2 is the last vertex in the ordering
8-element Vector{Int64}:
 4
 5
 7
 8
 3
 6
 1
 2

Parameters

clique: clique
alg: elimination algorithm

References

Liu, Joseph WH. "Equivalent sparse matrix reordering by elimination tree rotations." Siam Journal on Scientific and Statistical Computing 9.3 (1988): 424-444.

CliqueTrees.SafeRules — Type

SafeRules{A, L, U} <: EliminationAlgorithm

SafeRules(alg::EliminationAlgorithm, lb::WidthOrAlgorithm, ub::EliminationAlgororithm)

SafeRules()

Preprocess a graph using safe reduction rules. The algorithm lb is used to compute a lower bound to the treewidth; better lower bounds allow the algorithm to perform more reductions.

julia> using CliqueTrees, TreeWidthSolver

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> alg1 = BT()
BT

julia> alg2 = SafeRules(BT(), MMW(), MF())
SafeRules{BT, MMW, MF}:
    BT
    MMW
    MF

julia> @time treewidth(graph; alg=alg1) # slow
  0.000177 seconds (1.41 k allocations: 90.031 KiB)
2

julia> @time treewidth(graph; alg=alg2) # fast
  0.000044 seconds (282 allocations: 15.969 KiB)
2

Parameters

alg: elimination algorithm
lb: lower bound algorithm (used to lower bound the treiwidth)
ub: elimination algorithm (used to upper bound the treewidth)

References

Bodlaender, Hans L., et al. "Pre-processing for triangulation of probabilistic networks." (2001).
Bodlaender, Hans L., Arie M.C.A. Koster, and Frank van den Eijkhof. "Preprocessing rules for triangulation of probabilistic networks." Computational Intelligence 21.3 (2005): 286-305.
van den Eijkhof, Frank, Hans L. Bodlaender, and Arie M.C.A. Koster. "Safe reduction rules for weighted treewidth." Algorithmica 47 (2007): 139-158.

CliqueTrees.SafeSeparators — Type

SafeSeparators{M, A} <: EliminationAlgorithm

SafeSeparators(alg::EliminationAlgorithm, min::PermutationOrAlgorithm)

SafeSeparators(alg::EliminationAlgorithm)

SafeSeparators()

Apple an elimination algorithm to the atoms of an almost-clique separator decomposition. The algorithm min is used to compute the decomposition.

Warning

The algorithm min must compute a minimimal ordering. This property is guaranteed by the following algorithms:

MCSM
LexM
MinimalChordal

Parameters

alg: elimination algorithm
min: minimal elimination algorithm

References

Bodlaender, Hans L., and Arie MCA Koster. "Safe separators for treewidth." Discrete Mathematics 306.3 (2006): 337-350.
Tamaki, Hisao. "A heuristic for listing almost-clique minimal separators of a graph." arXiv preprint arXiv:2108.07551 (2021).

CliqueTrees.ConnectedComponents — Type

ConnectedComponents{A} <: EliminationAlgorithm

ConnectedComponents(alg::PermutationOrAlgorithm)

ConnectedComponents()

Apply an elimination algorithm to each connected component of a graph.

Parameters

alg: elimination algorithm

CliqueTrees.permutation — Function

permutation([weights, ]graph;
    alg::PermutationOrAlgorithm=DEFAULT_ELIMINATION_ALGORITHM)

Construct a fill-reducing permutation of the vertices of a simple graph.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> order, index = permutation(graph);

julia> order
8-element Vector{Int64}:
 4
 1
 2
 8
 5
 3
 6
 7

julia> index == invperm(order)
true

CliqueTrees.mcs — Function

mcs(graph[, clique])

Perform a maximum cardinality search, optionally specifying a clique to be ordered last. Returns the inverse permutation.

Supernodes

CliqueTrees.SupernodeType — Type

SupernodeType

A type of supernode partition. The options are

type	name
`Nodal`	nodal supernode partition
`Maximal`	maximal supernode partition
`Fundamental`	fundamental supernode partition

CliqueTrees.DEFAULT_SUPERNODE_TYPE — Constant

DEFAULT_SUPERNODE_TYPE = Maximal()

The default supernode partition.

CliqueTrees.Nodal — Type

Nodal <: SupernodeType

A nodal supernode partition.

CliqueTrees.Maximal — Type

Maximal <: SupernodeType

A maximal supernode partition.

CliqueTrees.Fundamental — Type

Fundamental <: SupernodeType

A fundamental supernode partition.

Linked Lists

CliqueTrees.SinglyLinkedList — Type

SinglyLinkedList{I, Head, Next} <: AbstractLinkedList{I}

SinglyLinkedList{I}(n::Integer)

A singly linked list of distinct natural numbers. This type supports the iteration interface.

julia> using CliqueTrees

julia> list = SinglyLinkedList{Int}(10)
SinglyLinkedList{Int64, Array{Int64, 0}, Vector{Int64}}:

julia> pushfirst!(list, 4, 5, 6, 7, 8, 9)
SinglyLinkedList{Int64, Array{Int64, 0}, Vector{Int64}}:
 4
 5
 6
 7
 8
 ⋮

julia> collect(list)
6-element Vector{Int64}:
 4
 5
 6
 7
 8
 9

Trees

CliqueTrees.AbstractTree — Type

AbstractTree{V} = Union{Tree{V}, SupernodeTree{V}, CliqueTree{V}}

A rooted forest. This type implements the indexed tree interface.

CliqueTrees.rootindices — Function

rootindices(tree::AbstractTree)

Get the roots of a rooted forest.

CliqueTrees.firstchildindex — Function

firstchildindex(tree::AbstractTree, i::Integer)

Get the first child of node i. Returns nothing if i is a leaf.

CliqueTrees.ancestorindices — Function

ancestorindices(tree::AbstractTree, i::Integer)

Get the proper ancestors of node i.

Trees

CliqueTrees.Tree — Type

Tree{V} <: AbstractUnitRange{V}

Tree(tree::AbstractTree)

Tree{V}(tree::AbstractTree) where V

A rooted forest with vertices of type V. This type implements the indexed tree interface.

CliqueTrees.eliminationtree — Function

eliminationtree([weights, ]graph;
    alg::PermutationOrAlgorithm=DEFAULT_ELIMINATION_ALGORITHM)

Construct a tree-depth decomposition of a simple graph.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> label, tree = eliminationtree(graph);

julia> tree
8-element Tree{Int64, Vector{Int64}, Array{Int64, 0}, Vector{Int64}, Vector{Int64}}:
 8
 └─ 7
    ├─ 5
    └─ 6
       ├─ 1
       ├─ 3
       │  └─ 2
       └─ 4

Supernode Trees

CliqueTrees.SupernodeTree — Type

SupernodeTree{V} <: AbstractVector{UnitRange{V}}

A supernodal elimination tree with vertices of type V. This type implements the indexed tree interface.

CliqueTrees.supernodetree — Function

supernodetree(graph;
    alg::PermutationOrAlgorithm=DEFAULT_ELIMINATION_ALGORITHM,
    snd::SupernodeType=DEFAULT_SUPERNODE_TYPE)

Construct a supernodal elimination tree.

Clique Trees

CliqueTrees.Clique — Type

Clique{V, E} <: AbstractVector{V}

A clique of a clique tree.

CliqueTrees.CliqueTree — Type

CliqueTree{V, E} <: AbstractVector{Clique{V, E}}

A clique tree with vertices of type V and edges of type E. This type implements the indexed tree interface.

CliqueTrees.cliquetree — Function

cliquetree([weights, ]graph;
    alg::PermutationOrAlgorithm=DEFAULT_ELIMINATION_ALGORITHM,
    snd::SupernodeType=DEFAULT_SUPERNODE_TYPE)

Construct a tree decomposition of a simple graph. The vertices of the graph are first ordered by a fill-reducing permutation computed by the algorithm alg. The size of the resulting decomposition is determined by the supernode partition snd.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> label, tree = cliquetree(graph);

julia> tree
6-element CliqueTree{Int64, Int64}:
 [6, 7, 8]
 └─ [5, 7, 8]
    ├─ [1, 5]
    ├─ [3, 5, 7]
    │  └─ [2, 3]
    └─ [4, 5, 8]

CliqueTrees.treewidth — Function

treewidth([weights, ]tree::CliqueTree)

Compute the width of a clique tree.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> label, tree = cliquetree(graph);

julia> treewidth(tree)
2

treewidth([weights, ]graph;
    alg::PermutationOrAlgorithm=DEFAULT_ELIMINATION_ALGORITHM)

Compute the width induced by an elimination algorithm.

julia> using CliqueTrees, TreeWidthSolver

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> treewidth(graph; alg=MCS())
3

julia> treewidth(graph; alg=BT()) # exact treewidth
2

CliqueTrees.separator — Function

separator(clique::Clique)

Get the separator of a clique.

separator(tree::CliqueTree, i::Integer)

Get the separator at node i.

CliqueTrees.residual — Function

residual(clique::Clique)

Get the residual of a clique.

residual(tree::CliqueTree, i::Integer)

Get the residual at node i.

Filled Graphs

CliqueTrees.FilledGraph — Type

FilledGraph{V, E} <: AbstractGraph{V}

A filled graph.

CliqueTrees.ischordal — Function

ischordal(graph)

Determine whether a simple graph is chordal.

CliqueTrees.isperfect — Function

isperfect(graph, order::AbstractVector[, index::AbstractVector])

Determine whether an fill-reducing permutation is perfect.