# \[ANN\] Announcing CliqueTrees.jl: Tree Decompositions in Julia

**URL:** <https://discourse.julialang.org/t/ann-announcing-cliquetrees-jl-tree-decompositions-in-julia/128808>\
**Category:** Package Announcements\
**Tags:** optimization, graphs\
**Created:** [May 7, 2025, 3:57pm UTC](https://discourse.julialang.org/t/ann-announcing-cliquetrees-jl-tree-decompositions-in-julia/128808 "2025-05-07T15:57:07Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![samuelsonric](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/samuelsonric/32/216687_2.png) [@samuelsonric](https://discourse.julialang.org/u/samuelsonric)\
**Post date:** [May 7, 2025, 3:57pm UTC](https://discourse.julialang.org/t/ann-announcing-cliquetrees-jl-tree-decompositions-in-julia/128808/1 "2025-05-07T15:57:07Z")

</div>

# Introduction

CliqueTrees.jl is a Julia package for constructing [tree decompositions](https://en.wikipedia.org/wiki/Tree_decomposition) and [chordal completions](https://en.wikipedia.org/wiki/Chordal_completion) of graphs. Tree decompositions are often used to schedule computations in [dynamic programming algorithms](https://en.wikipedia.org/wiki/Dynamic_programming). In particular, decompositions of low _width_ can generate very fast, practical algorithms for problems like

- Cholesky factorization
- semidefinite optimization
- tensor network contraction
- probabilistic inference

Algorithms for constructing tree decompositions exist in packages like QDLDL.jl, Clarabel.jl, TreeWidthSolver.jl, and JunctionTrees.jl. Some of these use exact algorithms, and others use heuristics. The goal of CliqueTrees.jl is to concentrate this functionality into one easy-to-use, high-performance package.

# Basic Usage

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

```

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

```julia-repl
julia> treewidth(tree)
2

```