Library Reference

Lower Bound Algorithms

CliqueTrees.MMWType
MMW{S} <: LowerBoundAlgorithm

MMW{1}() # min-d heuristic

MMW{2}() # max-d heuristic

MMW{3}() # least-c heuristic

MMW()

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

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.
source
CliqueTrees.lowerboundFunction
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
source

Dissection Algorithms

CliqueTrees.METISNDType
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.
source
CliqueTrees.KaHyParNDType
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".
source

Elimination Algorithms

CliqueTrees.EliminationAlgorithmType
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

typenametimespacepackage
MCSmaximum cardinality searchO(m + n)O(n)
LexBFSlexicographic breadth-first searchO(m + n)O(m + n)
MCSMmaximum cardinality search (minimal)O(mn)O(n)
LexMlexicographic breadth-first search (minimal)O(mn)O(n)

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

Bandwidth and Envelope Minimization Algorithms

typenametimespacepackage
RCMMDreverse Cuthill-Mckee (minimum degree)O(m + n)O(m + n)
RCMGLreverse 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

typenametimespacepackage
MMDmultiple minimum degreeO(mn²)O(m + n)
MFminimum fillO(mn²)
AMDapproximate minimum degreeO(mn)O(m + n)AMD.jl
SymAMDcolumn approximate minimum degreeO(mn)O(m + n)AMD.jl
AMFapproximate minimum fillO(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

typenametimespacepackage
METISnested dissectionMetis.jl
NDnested 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

typenametimespacepackage
BTBouchitte-TodincaTreeWidthSolver.jl
SATSAT encoding

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

Warning

This is an NP-hard problem.

source
CliqueTrees.BFSType
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
source
CliqueTrees.MCSType
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.
source
CliqueTrees.LexBFSType
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.
source
CliqueTrees.RCMMDType
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.
source
CliqueTrees.RCMGLType
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.
source
CliqueTrees.LexMType
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.
source
CliqueTrees.MCSMType
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.
source
CliqueTrees.AMDType
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.
source
CliqueTrees.SymAMDType
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.
source
CliqueTrees.AMFType
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.
source
CliqueTrees.MFType
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.
source
CliqueTrees.MMDType
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.
source
CliqueTrees.METISType
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.
source
CliqueTrees.NDType
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: optimize for width (slow)
  • 2: optimize for fill (slow)
  • 3: no optimization (fast)

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

typenamepackage
METISNDmultilevel vertex separationMetis.jl
KaHyParNDmultilevel hypergraph partitioningKayHyPar.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

  • alg: elimination algorithm
  • dis: separation algorithm
  • width: minimum width
  • level: maximum level
  • imbalance: separator imbalance
source
CliqueTrees.SpectralType
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.
source
CliqueTrees.FlowCutterType
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).
source
CliqueTrees.BTType
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.
source
CliqueTrees.SATType
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.
source
CliqueTrees.MinimalChordalType
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.
source
CliqueTrees.CompositeRotationsType
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.
source
CliqueTrees.SafeRulesType
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.
source
CliqueTrees.SafeSeparatorsType
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:

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).
source
CliqueTrees.ConnectedComponentsType
ConnectedComponents{A} <: EliminationAlgorithm

ConnectedComponents(alg::PermutationOrAlgorithm)

ConnectedComponents()

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

Parameters

  • alg: elimination algorithm
source
CliqueTrees.permutationFunction
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
source
CliqueTrees.mcsFunction
mcs(graph[, clique])

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

source

Supernodes

Linked Lists

CliqueTrees.SinglyLinkedListType
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
source

Trees

Trees

CliqueTrees.eliminationtreeFunction
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
source

Supernode Trees

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

Construct a supernodal elimination tree.

source

Clique Trees

CliqueTrees.cliquetreeFunction
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]
source
CliqueTrees.treewidthFunction
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
source
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
source
CliqueTrees.separatorFunction
separator(clique::Clique)

Get the separator of a clique.

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

Get the separator at node i.

source
CliqueTrees.residualFunction
residual(clique::Clique)

Get the residual of a clique.

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

Get the residual at node i.

source

Filled Graphs

CliqueTrees.isperfectFunction
isperfect(graph, order::AbstractVector[, index::AbstractVector])

Determine whether an fill-reducing permutation is perfect.

source