CliqueTrees.jl

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

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

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.

References

CliqueTrees.jl was inspired by the book Chordal Graphs and Semidefinite Optimization by Vandenberghe and Andersen.