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.

Installation

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

pkg> add CliqueTrees

Basic Usage

Tree Decompositions

The function cliquetree computes tree decompositions.

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> 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> 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> treewidth(tree)
2

Chordal Completions

Clique trees can be used to construct chordal completions.

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

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.

@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}
}