README.md

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 1 0 0 0 0 0
           1 0 1 0 0 1 0 0
           1 1 0 1 1 0 0 0
           0 0 1 0 1 0 0 0
           0 0 1 1 0 0 1 1
           0 1 0 0 0 0 1 0
           0 0 0 0 1 1 0 1
           0 0 0 0 1 0 1 0
       ];

julia> label, tree = cliquetree(graph);

julia> tree
6-element CliqueTree{Int64, Int64}:
 [6, 7, 8]
 ├─ [1, 6, 7]
 ├─ [4, 6, 8]
 │  └─ [3, 4, 6]
 │     └─ [2, 3, 6]
 └─ [5, 7, 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 3 by typing tree[3].

julia> tree[3]
3-element Clique{Int64, Int64}:
 3
 4
 6

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, 13} FilledGraph{Int64, Int64}

julia> sparse(filledgraph)
8×8 SparseMatrixCSC{Bool, Int64} with 13 stored entries:
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅
 ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅
 ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅
 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
 ⋅  ⋅  ⋅  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

Weights and self-edges are always ignored.

References

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