TreeDecomposition.cpp File Reference

Tree decomposition construction, manipulation, and I/O. More...

#include <cassert>
#include <set>
#include <algorithm>
#include <string>
#include <type_traits>
#include "TreeDecomposition.h"
#include "BooleanCircuit.h"
#include "PermutationStrategy.h"
#include "dDNNFTreeDecompositionBuilder.h"

Include dependency graph for TreeDecomposition.cpp:

Go to the source code of this file.

Functions
std::istream &	operator>> (std::istream &in, TreeDecomposition &td)
	Read a tree decomposition in PACE challenge format.

Detailed Description

Tree decomposition construction, manipulation, and I/O.

Implements the TreeDecomposition class declared in TreeDecomposition.h:

• TreeDecomposition(const BooleanCircuit&): constructs the tree decomposition of the circuit's primal graph using the min-fill elimination-ordering heuristic (PermutationStrategy). Throws TreeDecompositionException if the treewidth exceeds MAX_TREEWIDTH.
• TreeDecomposition(std::istream&): parses a PACE-format decomposition from a stream.
• Copy constructor and copy-assignment operator.
• makeFriendly(): restructures the tree into the friendly normal form expected by dDNNFTreeDecompositionBuilder.
• toDot(): GraphViz DOT string for visualising the tree.
• operator>>(): stream extraction in PACE format.

The reroot() helper and addEmptyBag(), addGateToBag(), findGateConnection() are private utilities for tree restructuring.

Definition in file TreeDecomposition.cpp.

Function Documentation

operator>>()

std::istream & operator>>	(	std::istream &	in,
		TreeDecomposition &	td
	)

Read a tree decomposition in PACE challenge format.

Parameters

in	Input stream.
td	Tree decomposition to populate.

Returns

Reference to in.

Definition at line 232 of file TreeDecomposition.cpp.