CliqueTrees.jl

CliqueTrees.jl implements clique trees in Julia. You can use it to construct tree decompositions and chordal completions of graphs.

Getting Help

If you have a question about the library, feel free to open an issue or leave a message in the cliquetrees.jl Zulip channel.

Projects using CliqueTrees

• BandedMatrices.jl
• BayesNets.jl
• CausalInference.jl
• EinExprs.jl
• IncrementalInference.jl
• OMEinsumContractionOrders.jl
• Scruff.jl
• SparseMatrixColorings.jl
• SumOfSquares.jl
• TSSOS.jl

Installation

To install CliqueTrees.jl, enter the Pkg REPL by typing ] and run the following command.

julia-repl pkg> add CliqueTrees

Basic Usage

Tree Decompositions

The function cliquetree computes tree decompositions.

```julia-repl julia> using CliqueTrees, LinearAlgebra, SparseArrays

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] ```

The clique tree tree is a tree decomposition of the permuted graph graph[label, label]. A clique tree is a vector of cliques, so you can retrieve the clique at node 4 by typing tree[4].

julia-repl julia> tree[4] 3-element Clique{Int64, Int64}: 4 5 8

[!WARNING] The numbers in each clique are vertices of the permuted graph graph[label, label]. You can see the vertices of the original graph by typing julia-repl julia> label[tree[4]] 3-element Vector{Int64}: 8 3 7 Notice that the clique is no longer sorted.

The width of a clique tree is computed by the function treewidth.

julia-repl julia> treewidth(tree) 2

Chordal Completions

Clique trees can be used to construct chordal completions.

```julia-repl julia> filledgraph = FilledGraph(tree) {8, 11} FilledGraph{Int64, Int64}

julia> sparse(filledgraph) 8×8 SparseMatrixCSC{Bool, Int64} with 11 stored entries: ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1 ⋅ 1 1 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1 ⋅ 1 1 ⋅ ⋅ ⋅ ⋅ ⋅ 1 1 1 1 ⋅ ```

The graph filledgraph is ordered: its edges are directed from lower to higher vertices. The underlying undirected graph is a chordal completion of the permuted graph graph[label, label].

```julia-repl julia> chordalgraph = Symmetric(sparse(filledgraph), :L) 8×8 Symmetric{Bool, SparseMatrixCSC{Bool, Int64}}: ⋅ ⋅ ⋅ ⋅ 1 ⋅ ⋅ ⋅ ⋅ ⋅ 1 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1 ⋅ ⋅ 1 ⋅ 1 ⋅ ⋅ ⋅ ⋅ ⋅ 1 ⋅ ⋅ 1 1 ⋅ 1 1 ⋅ ⋅ 1 1 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1 1 ⋅ ⋅ 1 ⋅ 1 1 ⋅ 1 ⋅ ⋅ ⋅ 1 1 1 1 ⋅

julia> ischordal(graph) false

julia> ischordal(chordalgraph) true

julia> all(graph[label, label] .<= chordalgraph) true ```

Cholesky Factorization

The function cholesky computes Cholesky factorizations of sparse positive-definite matrices.

```julia-repl julia> import CliqueTrees

julia> matrix = [ 3 1 0 0 0 0 0 0 1 3 1 0 0 2 0 0 0 1 3 1 0 1 2 1 0 0 1 3 0 0 0 0 0 0 0 0 3 1 1 0 0 2 1 0 1 3 0 0 0 0 2 0 1 0 3 1 0 0 1 0 0 0 1 3 ];

julia> cholfact = CliqueTrees.cholesky(matrix) CholFact{Float64, Int64}: nnz: 19 success: true ```

You can solve linear systems of equations with the operators / and \.

```julia-repl julia> rhs = rand(8, 2);

julia> sol = cholfact \ rhs # sol = inv(matrix) * rhs 8×2 Matrix{Float64}: -0.202009 -0.164852 0.661177 0.665989 0.173183 -0.126911 0.110932 0.0915613 0.375653 0.187998 -0.556495 -0.378656 -0.0751984 0.0536805 0.0793129 0.127395 ```

Graphs

Users can input graphs as adjacency matrices. Additionally, CliqueTrees.jl supports the HasGraph type from Catlab.jl and the AbstractGraph type from Graphs.jl. Instances of the latter should implement the following subset of the abstract graph interface.

• is_directed
• ne
• nv
• outneighbors
• vertices

Self-edges are always ignored.

Citation

If you use CliqueTrees.jl for a publication, please cite it as follows.

bibtex @misc{cliquetrees2025samuelson, author = {Samuelson, Richard and Fairbanks, James}, url = {https://github.com/AlgebraicJulia/CliqueTrees.jl}, title = {CliqueTrees.jl: A Julia library for computing tree decompositions and chordal completions of graphs}, year = {2025} }