Library Reference
Lower Bound Algorithms
CliqueTrees.LowerBoundAlgorithm
— TypeLowerBoundAlgorithm
An algorithm for computing a lower bound to the treewidth of a graph. The options are
type | name | time | space |
---|---|---|---|
MMW | minor-min-width |
CliqueTrees.MMW
— TypeMMW{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.
CliqueTrees.lowerbound
— Functionlowerbound([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
— ConstantDEFAULT_LOWER_BOUND_ALGORITHM = MMW()
Dissection Algorithms
CliqueTrees.DissectionAlgorithm
— TypeDissectionAlgorithm
A vertex separator algorithm.
CliqueTrees.METISND
— TypeMETISND <: 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 dissectionseed
: 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
— TypeKaHyParND{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
orReverse
).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
— ConstantDEFAULT_DISSECTION_ALGORITHM = METISND()
The default dissection algorithm.
Elimination Algorithms
CliqueTrees.EliminationAlgorithm
— TypeEliminationAlgorithm
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.
CliqueTrees.PermutationOrAlgorithm
— TypePermutationOrAlgorithm = Union{
AbstractVector,
Tuple{AbstractVector, AbstractVector},
EliminationAlgorithm,
}
Either a permutation or an algorithm.
CliqueTrees.DEFAULT_ELIMINATION_ALGORITHM
— ConstantDEFAULT_ELIMINATION_ALGORITHM = MMD()
The default algorithm.
CliqueTrees.BFS
— TypeBFS <: 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
— TypeMCS <: 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
— TypeLexBFS <: 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
— TypeRCMMD{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
— TypeRCMGL{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
— TypeRCM = RCMGL
The default variant of the reverse Cuthill-Mckee algorithm.
CliqueTrees.LexM
— TypeLexM <: 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
— TypeMCSM <: 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
— TypeAMD <: 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 parameteraggressive
: 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
— TypeSymAMD <: 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 parameterdense_column
: dense column parameteraggressive
: 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
— TypeAMF <: 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
— TypeMF <: 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
— TypeMMD <: 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
— TypeMETIS <: 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 coarseningrtype
: algorithm used for refinementnseps
: number of different separators computed at each level of nested dissectionniter
: number of iterations for refinement algorithm at each stage of the uncoarsening processseed
: random seedcompress
: whether to combine vertices with identical adjacency listsccorder
: whether to order connected components separatelypfactor
: minimum degree of vertices that will be ordered lastufactor
: 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
— TypeND{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.
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
alg
: elimination algorithmdis
: separation algorithmwidth
: minimum widthlevel
: maximum levelimbalance
: separator imbalance
CliqueTrees.Spectral
— TypeSpectral <: 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
— TypeFlowCutter <: 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 timeseed
: random seed
References
- Strasser, Ben. "Computing tree decompositions with flowcutter: PACE 2017 submission." arXiv preprint arXiv:1709.08949 (2017).
CliqueTrees.BT
— TypeBT <: 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
— TypeSAT{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
— TypeMinimalChordal{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
— TypeCompositeRotations{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
: cliquealg
: 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
— TypeSafeRules{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 algorithmlb
: 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
— TypeSafeSeparators{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.
The algorithm min
must compute a minimimal ordering. This property is guaranteed by the following algorithms:
Parameters
alg
: elimination algorithmmin
: 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
— TypeConnectedComponents{A} <: EliminationAlgorithm
ConnectedComponents(alg::PermutationOrAlgorithm)
ConnectedComponents()
Apply an elimination algorithm to each connected component of a graph.
Parameters
alg
: elimination algorithm
CliqueTrees.permutation
— Functionpermutation([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
— Functionmcs(graph[, clique])
Perform a maximum cardinality search, optionally specifying a clique to be ordered last. Returns the inverse permutation.
Supernodes
CliqueTrees.SupernodeType
— TypeSupernodeType
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
— ConstantDEFAULT_SUPERNODE_TYPE = Maximal()
The default supernode partition.
CliqueTrees.Nodal
— TypeNodal <: SupernodeType
A nodal supernode partition.
CliqueTrees.Maximal
— TypeMaximal <: SupernodeType
A maximal supernode partition.
CliqueTrees.Fundamental
— TypeFundamental <: SupernodeType
A fundamental supernode partition.
Linked Lists
CliqueTrees.SinglyLinkedList
— TypeSinglyLinkedList{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
— TypeAbstractTree{V} = Union{Tree{V}, SupernodeTree{V}, CliqueTree{V}}
A rooted forest. This type implements the indexed tree interface.
CliqueTrees.rootindices
— Functionrootindices(tree::AbstractTree)
Get the roots of a rooted forest.
CliqueTrees.firstchildindex
— Functionfirstchildindex(tree::AbstractTree, i::Integer)
Get the first child of node i
. Returns nothing
if i
is a leaf.
CliqueTrees.ancestorindices
— Functionancestorindices(tree::AbstractTree, i::Integer)
Get the proper ancestors of node i
.
Trees
CliqueTrees.Tree
— TypeTree{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
— Functioneliminationtree([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
— TypeSupernodeTree{V} <: AbstractVector{UnitRange{V}}
A supernodal elimination tree with vertices of type V
. This type implements the indexed tree interface.
CliqueTrees.supernodetree
— Functionsupernodetree(graph;
alg::PermutationOrAlgorithm=DEFAULT_ELIMINATION_ALGORITHM,
snd::SupernodeType=DEFAULT_SUPERNODE_TYPE)
Construct a supernodal elimination tree.
Clique Trees
CliqueTrees.Clique
— TypeClique{V, E} <: AbstractVector{V}
A clique of a clique tree.
CliqueTrees.CliqueTree
— TypeCliqueTree{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
— Functioncliquetree([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
— Functiontreewidth([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
— Functionseparator(clique::Clique)
Get the separator of a clique.
separator(tree::CliqueTree, i::Integer)
Get the separator at node i
.
CliqueTrees.residual
— Functionresidual(clique::Clique)
Get the residual of a clique.
residual(tree::CliqueTree, i::Integer)
Get the residual at node i
.
Filled Graphs
CliqueTrees.FilledGraph
— TypeFilledGraph{V, E} <: AbstractGraph{V}
A filled graph.
CliqueTrees.ischordal
— Functionischordal(graph)
Determine whether a simple graph is chordal.
CliqueTrees.isperfect
— Functionisperfect(graph, order::AbstractVector[, index::AbstractVector])
Determine whether an fill-reducing permutation is perfect.