GitHub

Manual for TreeWidthSolver.jl

API

Data Type

TreeWidthSolver.MaskedBitGraph — Type
mutable struct MaskedBitGraph{INT}

A mutable struct representing a masked bit graph.

Fields

  • MaskedBitGraph::Vector{INT}: Stores the adjacency matrix as a vector of BitStr.
  • fadjlist::Vector{Vector{Int}}: Stores the adjacency list, providing information about the sparse graph.
  • mask::INT: The mask for the graph.
source
TreeWidthSolver.DecompositionTreeNode — Type
mutable struct DecompositionTreeNode{T}

A mutable struct representing a node in a tree decomposition.

Fields

  • bag::Set{T}: The bag of the node, which is a set of elements of type T.
  • parent::Union{DecompositionTreeNode{T}, Nothing}: The parent node of the current node. It can be either a DecompositionTreeNode{T} or Nothing if the current node is the root.
  • children::Vector{DecompositionTreeNode{T}}: The children nodes of the current node, stored in a vector.
source
TreeWidthSolver.TreeDecomposition — Type
struct TreeDecomposition{TW, TL}

A struct representing a tree decomposition.

Fields

  • tw::TW: The treewidth of the decomposition.
  • tree::DecompositionTreeNode{TL}: The root node of the decomposition tree.
source

IO for Graphs

TreeWidthSolver.graph_from_gr — Function
graph_from_gr(filename)

Reads a graph from a file in the .gr format (PACE format) and returns a SimpleGraph object.

Arguments

  • filename: The path to the input file.

Returns

  • graph: A SimpleGraph object representing the graph.
source
TreeWidthSolver.save_graph — Function
function save_graph(g::SimpleGraph, filename)

The graph will be saved as .gr format, in PACE format, where the first line is p tw nv ne, and the following lines are the edges src dst

source
TreeWidthSolver.graph_from_tuples — Function
graph_from_tuples(n::Int, edgs)

Constructs a graph from a list of tuples representing edges.

Arguments

  • n::Int: The number of vertices in the graph.
  • edgs: A list of tuples representing the edges of the graph.

Returns

A graph object.

source

Hypergraph

TreeWidthSolver.line_graph — Function
line_graph(adjacency_mat::SparseMatrixCSC)

Constructs the line graph of a given graph represented by its adjacency matrix.

Arguments

  • adjacency_mat::SparseMatrixCSC: The adjacency matrix of the input graph, where the columns represent the vertices and the rows represent the edges. The value is true if the edge is connected to the vertex.

Returns

  • g::SimpleGraph: The line graph of the input graph.
source
TreeWidthSolver.simple_graph — Function
simple_graph(adjacency_mat::SparseMatrixCSC)

Constructs a simple undirected graph from a sparse adjacency matrix.

Arguments

  • adjacency_mat::SparseMatrixCSC: The sparse adjacency matrix representing the graph.

Returns

  • g::SimpleGraph: The constructed simple undirected graph.
source
TreeWidthSolver.adjacency_mat — Function
adjacency_mat(graph::SimpleGraph)

Constructs the adjacency matrix of a given SimpleGraph.

Arguments

  • graph::SimpleGraph: The input graph.

Returns

  • SparseMatrixCSC{Int}: The adjacency matrix of the graph.
source

Treewidth

TreeWidthSolver.exact_treewidth — Function
exact_treewidth(g::SimpleGraph{TG}; weights::Vector{TW} = ones(nv(g)), verbose::Bool = false) where {TG, TW}

Compute the exact treewidth of a given graph g using the BT algorithm.

Arguments

  • g::SimpleGraph{TG}: The input graph.
  • weights::Vector{TW} = ones(nv(g)): The weights of the vertices in the graph. Default is equal weights for all vertices.
  • verbose::Bool = false: Whether to print verbose output. Default is false.

Returns

  • tw: The treewidth of the graph.
source
TreeWidthSolver.decomposition_tree — Function
decomposition_tree(g::SimpleGraph{TG}; labels::Vector{TL} = collect(1:nv(g)), weights::Vector{TW} = ones(nv(g)), verbose::Bool = false) where {TG, TW, TL}

Constructs a decomposition tree for a given simple graph g.

Arguments

  • g::SimpleGraph{TG}: The input graph.
  • labels::Vector{TL}: (optional) The labels for the vertices of the graph. Default is collect(1:nv(g)).
  • weights::Vector{TW}: (optional) The weights for the vertices of the graph. Default is ones(nv(g)).
  • verbose::Bool: (optional) Whether to print verbose output. Default is false.

Returns

  • TreeDecomposition: The resulting decomposition tree, where treewidht is stored in td.tw and the tree is stored in td.tree.
source
decomposition_tree(g::SimpleGraph{TG}, orders::Union{Vector{Vector{TE}}, Vector{TE}}; labels::Vector{TL} = [1:length(vertices(g))...]) where {TG, TE, TL}

Constructs a decomposition tree for a given simple graph g based on the provided orders.

Arguments

  • g::SimpleGraph{TG}: The input graph.
  • orders::Union{Vector{Vector{TE}}, Vector{TE}}: The orders for constructing the decomposition tree. Can be a vector of vectors or a single vector.
  • labels::Vector{TL}: (optional) The labels for the vertices of the graph. Default is collect(1:nv(g)).

Returns

  • TreeDecomposition: The resulting decomposition tree, where the tree is labeled according to the provided labels.

Raises

  • AssertionError: If the length of new_orders does not match the number of vertices in g, if new_orders contains duplicates, or if the length of labels does not match the length of new_orders.
source
TreeWidthSolver.elimination_order — Function
elimination_order(g::SimpleGraph{TG}; labels::Vector{TL} = collect(1:nv(g)), weights::Vector{TW} = ones(nv(g)), verbose::Bool = false) where {TG, TL, TW}

Compute the elimination order of a graph g using the BT algorithm.

Arguments

  • g::SimpleGraph{TG}: The input graph.
  • labels::Vector{TL}: (optional) Labels for the vertices of g. Default is collect(1:nv(g)).
  • weights::Vector{TW}: (optional) Weights for the vertices of g. Default is ones(nv(g)).
  • verbose::Bool: (optional) Whether to print verbose output. Default is false.

Returns

  • labeled_eo::Vector{Vector{TL}}: The elimination order of the graph g, where each vertex is labeled according to labels.
source