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

Compute a vertex separator using METIS_computeVertexSeparator.

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(; speed=1)

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:
    speed: 2

julia> treewidth(graph; alg)
2

Parameters

  • speed: fill approximation strategy (1, 2, or, 3)

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; limit=200, level=6)

The nested dissection algorithm.

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(); limit=0, level=2)
ND{1, MF, METISND}:
    MF
    METISND:
        seed: -1
        ufactor: -1
    limit: 0
    level: 2

julia> treewidth(graph; alg)
2

Parameters

  • alg: elimination algorithm
  • dis: dissection algorithm
  • limit: smallest subgraph
  • level: search depth
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