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

Package Announcements
,
1

Introduction

CliqueTrees.jl is a Julia package for constructing tree decompositions and chordal completions of graphs. Tree decompositions are often used to schedule computations in dynamic programming algorithms. 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> 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

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

julia> treewidth(tree)
2
19 Likes