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

#include "Graph.h"

Public Member Functions
	Graph (const BooleanCircuit &bc)
	Construct the primal graph of a `BooleanCircuit`.

void	add_edge (unsigned long src, unsigned long tgt, bool undirected=true)
	Add an edge between `src` and `tgt`.

void	add_node (unsigned long node)
	Add `node` to the graph (no edges).

std::unordered_set< unsigned long >	remove_node (unsigned long node)
	Remove `node` and all its incident edges.

bool	neighbour_improved (unsigned k, unsigned long n1, unsigned long n2)
	Test whether two nodes share more than `k-1` common neighbours.

void	fill (const std::unordered_set< unsigned long > &nodes, bool undirected=true)
	Add all missing edges within `nodes` (clique fill).

void	contract_edge (unsigned long src, unsigned long tgt)
	Contract the edge (src, tgt) by merging `tgt` into `src`.

bool	has_neighbours (unsigned long node) const
	Return `true` if `node` has any adjacent edges.

bool	has_node (unsigned long node) const
	Return `true` if `node` is present in the graph.

bool	has_edge (unsigned long src, unsigned long tgt)
	Return `true` if a directed edge from `src` to `tgt` exists.

const std::unordered_set< unsigned long > &	get_neighbours (unsigned long node) const
	Return the neighbour set of `node`.

const std::unordered_set< unsigned long > &	get_nodes () const
	Return the set of all node IDs in the graph.

unsigned long	number_nodes () const
	Return the number of nodes in the graph.

unsigned long	number_edges () const
	Return the number of edges in the graph.

Private Attributes
std::unordered_map< unsigned long, std::unordered_set< unsigned long > >	adj_list
	Adjacency lists.

std::unordered_set< unsigned long >	node_set
	Set of all node IDs.

unsigned long	num_edges = 0
	Current edge count.

Detailed Description

Mutable adjacency-list graph over unsigned-long node IDs.

Supports both directed and undirected edges, node/edge removal, clique-fill operations, and edge contraction, as needed by the min-fill tree-decomposition algorithm.

Definition at line 33 of file Graph.h.

Constructor & Destructor Documentation

◆ Graph()

Graph::Graph ( const BooleanCircuit & bc )

inline

Construct the primal graph of a BooleanCircuit.

Each gate (except UNDETERMINED and MULVAR) becomes a node. Each wire between two gates becomes an undirected edge.

Parameters

bc	The Boolean circuit whose structure defines the graph.

Definition at line 48 of file Graph.h.

Here is the call graph for this function:

Member Function Documentation

◆ add_edge()

void Graph::add_edge	(	unsigned long	src,
		unsigned long	tgt,
		bool	undirected = `true`
	)

inline

Add an edge between src and tgt.

If the edge already exists the call is a no-op. Both endpoint nodes are added to node_set if not already present.

Parameters

src	Source node.
tgt	Target node.
undirected	If `true`, also add the reverse edge.

Definition at line 72 of file Graph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ add_node()

void Graph::add_node ( unsigned long node )

inline

Add node to the graph (no edges).

Parameters

node	Node ID to insert.

Definition at line 86 of file Graph.h.

Here is the caller graph for this function:

◆ contract_edge()

void Graph::contract_edge	(	unsigned long	src,
		unsigned long	tgt
	)

inline

Contract the edge (src, tgt) by merging tgt into src.

All edges from tgt are redirected to src, then tgt is removed.

Parameters

src	The node that survives the contraction.
tgt	The node to be merged into `src`.

Definition at line 175 of file Graph.h.

Here is the call graph for this function:

◆ fill()

void Graph::fill	(	const std::unordered_set< unsigned long > &	nodes,
		bool	undirected = `true`
	)

inline

Add all missing edges within nodes (clique fill).

Connects every pair of nodes in nodes that is not already connected, making the subgraph induced by nodes into a clique.

Parameters

nodes	Set of node IDs to fill.
undirected	If `true`, add edges in both directions.

Definition at line 152 of file Graph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_neighbours()

const std::unordered_set< unsigned long > & Graph::get_neighbours ( unsigned long node ) const

inline

Return the neighbour set of node.

node must be present in the graph (asserted in debug builds).

Parameters

node	Node to query.

Returns: Const reference to the adjacency set.

Definition at line 222 of file Graph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_nodes()

const std::unordered_set< unsigned long > & Graph::get_nodes ( ) const

inline

Return the set of all node IDs in the graph.

Returns: Const reference to the node set.

Definition at line 232 of file Graph.h.

Here is the caller graph for this function:

◆ has_edge()

bool Graph::has_edge	(	unsigned long	src,
		unsigned long	tgt
	)

inline

Return true if a directed edge from src to tgt exists.

Parameters

src	Source node.
tgt	Target node.

Returns: true if the edge src → tgt is present.

Definition at line 205 of file Graph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ has_neighbours()

bool Graph::has_neighbours ( unsigned long node ) const

inline

Return true if node has any adjacent edges.

Parameters

node	Node to query.

Returns: true if the adjacency list contains an entry for node.

Definition at line 186 of file Graph.h.

Here is the caller graph for this function:

◆ has_node()

bool Graph::has_node ( unsigned long node ) const

inline

Return true if node is present in the graph.

Parameters

node	Node to query.

Returns: true if node exists in the node set.

Definition at line 195 of file Graph.h.

Here is the caller graph for this function:

◆ neighbour_improved()

bool Graph::neighbour_improved	(	unsigned	k,
		unsigned long	n1,
		unsigned long	n2
	)

inline

Test whether two nodes share more than k-1 common neighbours.

Used by the min-fill heuristic to decide whether eliminating a node improves the treewidth bound.

Parameters

k	Treewidth bound being tested.
n1	First node.
n2	Second node.

Returns: true if the common-neighbour count exceeds k-1.

Definition at line 119 of file Graph.h.

Here is the call graph for this function:

◆ number_edges()

unsigned long Graph::number_edges ( ) const

inline

Return the number of edges in the graph.

Returns: Total edge count.

Definition at line 248 of file Graph.h.

◆ number_nodes()

unsigned long Graph::number_nodes ( ) const

inline

Return the number of nodes in the graph.

Returns: Total node count.

Definition at line 240 of file Graph.h.

Here is the caller graph for this function:

◆ remove_node()

std::unordered_set< unsigned long > Graph::remove_node ( unsigned long node )

inline

Remove node and all its incident edges.

Parameters

node	Node ID to remove.

Returns: The adjacency set of node before removal.

Definition at line 96 of file Graph.h.

Here is the caller graph for this function:

Member Data Documentation

◆ adj_list

std::unordered_map<unsigned long, std::unordered_set<unsigned long> > Graph::adj_list

private

Adjacency lists.

Definition at line 35 of file Graph.h.

◆ node_set

std::unordered_set<unsigned long> Graph::node_set

private

Set of all node IDs.

Definition at line 36 of file Graph.h.

◆ num_edges

unsigned long Graph::num_edges = 0

private

Current edge count.

Definition at line 37 of file Graph.h.

The documentation for this class was generated from the following file:

/home/pierre/git/software/provsql/src/Graph.h

Public Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Graph()

Member Function Documentation

◆ add_edge()

◆ add_node()

◆ contract_edge()

◆ fill()

◆ get_neighbours()

◆ get_nodes()

◆ has_edge()

◆ has_neighbours()

◆ has_node()

◆ neighbour_improved()

◆ number_edges()

◆ number_nodes()

◆ remove_node()

Member Data Documentation

◆ adj_list

◆ node_set

◆ num_edges