Graph.h File Reference

Undirected graph used in tree-decomposition computations. More...

#include <cstdlib>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include "BooleanCircuit.h"

Include dependency graph for Graph.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Graph
	Mutable adjacency-list graph over unsigned-long node IDs. More...

Detailed Description

Undirected graph used in tree-decomposition computations.

Originally taken and adapted from https://github.com/smaniu/treewidth

Graph is a mutable, adjacency-list-based undirected (or directed) graph over unsigned long node IDs. It is used during the tree-decomposition algorithm to represent the "primal graph" of a BooleanCircuit: nodes correspond to gates and edges connect gates that are connected by a wire.

The mutating operations (remove_node, fill, contract_edge) are used by the elimination-ordering heuristic implemented in PermutationStrategy and TreeDecomposition.

Definition in file Graph.h.