#include <Graph.h>

Inheritance diagram for PBQP::Graph< SolverT >:

Collaboration diagram for PBQP::Graph< SolverT >:

Classes
class	AdjEdgeIdSet
class	EdgeEntry
class	EdgeIdSet
class	EdgeItr
class	NodeEntry
class	NodeIdSet
class	NodeItr
Public Types
typedef SolverT::RawVector	RawVector
typedef SolverT::RawMatrix	RawMatrix
typedef SolverT::Vector	Vector
typedef SolverT::Matrix	Matrix
typedef CostAllocator::VectorPtr	VectorPtr
typedef CostAllocator::MatrixPtr	MatrixPtr
typedef SolverT::NodeMetadata	NodeMetadata
typedef SolverT::EdgeMetadata	EdgeMetadata
typedef NodeEntry::AdjEdgeItr	AdjEdgeItr
Public Member Functions
	Graph ()
	Construct an empty PBQP graph.
void	setSolver (SolverT &S)
	Lock this graph to the given solver instance in preparation for running the solver. This method will call solver.handleAddNode for each node in the graph, and handleAddEdge for each edge, to give the solver an opportunity to set up any requried metadata.
void	unsetSolver ()
	Release from solver instance.
template<typename OtherVectorT >
NodeId	addNode (OtherVectorT Costs)
	Add a node with the given costs.
template<typename OtherVectorT >
EdgeId	addEdge (NodeId N1Id, NodeId N2Id, OtherVectorT Costs)
	Add an edge between the given nodes with the given costs.
bool	empty () const
	Returns true if the graph is empty.
NodeIdSet	nodeIds () const
EdgeIdSet	edgeIds () const
AdjEdgeIdSet	adjEdgeIds (NodeId NId)
unsigned	getNumNodes () const
	Get the number of nodes in the graph.
unsigned	getNumEdges () const
	Get the number of edges in the graph.
template<typename OtherVectorT >
void	setNodeCosts (NodeId NId, OtherVectorT Costs)
	Set a node's cost vector.
const Vector &	getNodeCosts (NodeId NId) const
	Get a node's cost vector (const version).
NodeMetadata &	getNodeMetadata (NodeId NId)
const NodeMetadata &	getNodeMetadata (NodeId NId) const
NodeEntry::AdjEdgeList::size_type	getNodeDegree (NodeId NId) const
template<typename OtherMatrixT >
void	setEdgeCosts (EdgeId EId, OtherMatrixT Costs)
	Set an edge's cost matrix.
const Matrix &	getEdgeCosts (EdgeId EId) const
	Get an edge's cost matrix (const version).
EdgeMetadata &	getEdgeMetadata (EdgeId NId)
const EdgeMetadata &	getEdgeMetadata (EdgeId NId) const
NodeId	getEdgeNode1Id (EdgeId EId)
	Get the first node connected to this edge.
NodeId	getEdgeNode2Id (EdgeId EId)
	Get the second node connected to this edge.
NodeId	getEdgeOtherNodeId (EdgeId EId, NodeId NId)
	Get the "other" node connected to this edge.
EdgeId	findEdge (NodeId N1Id, NodeId N2Id)
	Get the edge connecting two nodes.
void	removeNode (NodeId NId)
	Remove a node from the graph.
void	disconnectEdge (EdgeId EId, NodeId NId)
	Disconnect an edge from the given node.
void	disconnectAllNeighborsFromNode (NodeId NId)
	Convenience method to disconnect all neighbours from the given node.
void	reconnectEdge (EdgeId EId, NodeId NId)
	Re-attach an edge to its nodes.
void	removeEdge (EdgeId EId)
	Remove an edge from the graph.
void	clear ()
	Remove all nodes and edges from the graph.
template<typename OStream >
void	dump (OStream &OS)
	Dump a graph to an output stream.
template<typename OStream >
void	printDot (OStream &OS)
	Print a representation of this graph in DOT format.

Detailed Description

template<typename SolverT>
class PBQP::Graph< SolverT >

PBQP Graph class. Instances of this class describe PBQP problems.

Definition at line 47 of file Graph.h.

Member Typedef Documentation

template<typename SolverT >

typedef NodeEntry::AdjEdgeItr PBQP::Graph< SolverT >::AdjEdgeItr

Definition at line 234 of file Graph.h.

template<typename SolverT >

typedef SolverT::EdgeMetadata PBQP::Graph< SolverT >::EdgeMetadata

Definition at line 58 of file Graph.h.

template<typename SolverT >

typedef SolverT::Matrix PBQP::Graph< SolverT >::Matrix

Definition at line 54 of file Graph.h.

template<typename SolverT >

typedef CostAllocator::MatrixPtr PBQP::Graph< SolverT >::MatrixPtr

Definition at line 56 of file Graph.h.

template<typename SolverT >

typedef SolverT::NodeMetadata PBQP::Graph< SolverT >::NodeMetadata

Definition at line 57 of file Graph.h.

template<typename SolverT >

typedef SolverT::RawMatrix PBQP::Graph< SolverT >::RawMatrix

Definition at line 52 of file Graph.h.

template<typename SolverT >

typedef SolverT::RawVector PBQP::Graph< SolverT >::RawVector

Definition at line 51 of file Graph.h.

template<typename SolverT >

typedef SolverT::Vector PBQP::Graph< SolverT >::Vector

Definition at line 53 of file Graph.h.

template<typename SolverT >

typedef CostAllocator::VectorPtr PBQP::Graph< SolverT >::VectorPtr

Definition at line 55 of file Graph.h.

Constructor & Destructor Documentation

template<typename SolverT >

PBQP::Graph< SolverT >::Graph ( ) [inline]

Construct an empty PBQP graph.

Definition at line 332 of file Graph.h.

Member Function Documentation

template<typename SolverT >

template<typename OtherVectorT >

EdgeId PBQP::Graph< SolverT >::addEdge	(	NodeId	N1Id,
		NodeId	N2Id,
		OtherVectorT	Costs
	)		`[inline]`

Add an edge between the given nodes with the given costs.

Parameters:

N1Id	First node.
N2Id	Second node.

Returns:: Edge iterator for the added edge.

Definition at line 371 of file Graph.h.

References PBQP::Graph< SolverT >::getNodeCosts().

template<typename SolverT >

template<typename OtherVectorT >

NodeId PBQP::Graph< SolverT >::addNode ( OtherVectorT Costs ) [inline]

Add a node with the given costs.

Parameters:

Costs Cost vector for the new node.

Returns:: Node iterator for the added node.

Definition at line 357 of file Graph.h.

template<typename SolverT >

AdjEdgeIdSet PBQP::Graph< SolverT >::adjEdgeIds ( NodeId NId ) [inline]

Definition at line 389 of file Graph.h.

Referenced by PBQP::Graph< SolverT >::disconnectAllNeighborsFromNode(), and PBQP::Graph< SolverT >::findEdge().

template<typename SolverT >

void PBQP::Graph< SolverT >::clear ( ) [inline]

Remove all nodes and edges from the graph.

Definition at line 574 of file Graph.h.

template<typename SolverT >

void PBQP::Graph< SolverT >::disconnectAllNeighborsFromNode ( NodeId NId ) [inline]

Convenience method to disconnect all neighbours from the given node.

Definition at line 546 of file Graph.h.

References PBQP::Graph< SolverT >::adjEdgeIds(), PBQP::Graph< SolverT >::disconnectEdge(), and PBQP::Graph< SolverT >::getEdgeOtherNodeId().

template<typename SolverT >

void PBQP::Graph< SolverT >::disconnectEdge	(	EdgeId	EId,
		NodeId	NId
	)		`[inline]`

Disconnect an edge from the given node.

Removes the given edge from the adjacency list of the given node. This operation leaves the edge in an 'asymmetric' state: It will no longer appear in an iteration over the given node's (NId's) edges, but will appear in an iteration over the 'other', unnamed node's edges.

This does not correspond to any normal graph operation, but exists to support efficient PBQP graph-reduction based solvers. It is used to 'effectively' remove the unnamed node from the graph while the solver is performing the reduction. The solver will later call reconnectNode to restore the edge in the named node's adjacency list.

Since the degree of a node is the number of connected edges, disconnecting an edge from a node 'u' will cause the degree of 'u' to drop by 1.

A disconnected edge WILL still appear in an iteration over the graph edges.

A disconnected edge should not be removed from the graph, it should be reconnected first.

A disconnected edge can be reconnected by calling the reconnectEdge method.

Definition at line 536 of file Graph.h.

Referenced by PBQP::Graph< SolverT >::disconnectAllNeighborsFromNode().

template<typename SolverT >

template<typename OStream >

void PBQP::Graph< SolverT >::dump ( OStream & OS ) [inline]

Dump a graph to an output stream.

Definition at line 583 of file Graph.h.

References PBQP::Graph< SolverT >::edgeIds(), PBQP::Graph< SolverT >::getEdgeCosts(), PBQP::Graph< SolverT >::getEdgeNode1Id(), PBQP::Graph< SolverT >::getEdgeNode2Id(), PBQP::Graph< SolverT >::getNodeCosts(), PBQP::Graph< SolverT >::nodeIds(), PBQP::Graph< SolverT >::NodeIdSet::size(), and PBQP::Graph< SolverT >::EdgeIdSet::size().

template<typename SolverT >

EdgeIdSet PBQP::Graph< SolverT >::edgeIds ( ) const [inline]

Definition at line 387 of file Graph.h.

Referenced by PBQP::Graph< SolverT >::dump(), PBQP::Graph< SolverT >::printDot(), and PBQP::Graph< SolverT >::setSolver().

template<typename SolverT >

bool PBQP::Graph< SolverT >::empty ( ) const [inline]

Returns true if the graph is empty.

Definition at line 384 of file Graph.h.

References PBQP::Graph< SolverT >::NodeIdSet::empty().

template<typename SolverT >

EdgeId PBQP::Graph< SolverT >::findEdge	(	NodeId	N1Id,
		NodeId	N2Id
	)		`[inline]`

Get the edge connecting two nodes.

Parameters:

N1Id	First node id.
N2Id	Second node id.

Returns:: An id for edge (N1Id, N2Id) if such an edge exists, otherwise returns an invalid edge id.

Definition at line 484 of file Graph.h.

References PBQP::Graph< SolverT >::adjEdgeIds(), PBQP::Graph< SolverT >::getEdgeNode1Id(), PBQP::Graph< SolverT >::getEdgeNode2Id(), and PBQP::GraphBase::invalidEdgeId().

template<typename SolverT >

const Matrix& PBQP::Graph< SolverT >::getEdgeCosts ( EdgeId EId ) const [inline]

Get an edge's cost matrix (const version).

Parameters:

EId Edge id.

Returns:: Edge cost matrix.

Definition at line 443 of file Graph.h.

Referenced by PBQP::Graph< SolverT >::dump(), PBQP::RegAlloc::RegAllocSolverImpl::handleDisconnectEdge(), PBQP::RegAlloc::RegAllocSolverImpl::handleReconnectEdge(), and PBQP::Graph< SolverT >::printDot().

template<typename SolverT >

EdgeMetadata& PBQP::Graph< SolverT >::getEdgeMetadata ( EdgeId NId ) [inline]

Definition at line 445 of file Graph.h.

template<typename SolverT >

const EdgeMetadata& PBQP::Graph< SolverT >::getEdgeMetadata ( EdgeId NId ) const [inline]

Definition at line 449 of file Graph.h.

template<typename SolverT >

NodeId PBQP::Graph< SolverT >::getEdgeNode1Id ( EdgeId EId ) [inline]

Get the first node connected to this edge.

Parameters:

EId Edge id.

Returns:: The first node connected to the given edge.

Definition at line 456 of file Graph.h.

Referenced by PBQP::Graph< SolverT >::dump(), PBQP::Graph< SolverT >::findEdge(), PBQP::RegAlloc::RegAllocSolverImpl::handleAddEdge(), PBQP::RegAlloc::RegAllocSolverImpl::handleRemoveEdge(), PBQP::RegAlloc::RegAllocSolverImpl::handleSetEdgeCosts(), and PBQP::Graph< SolverT >::printDot().

template<typename SolverT >

NodeId PBQP::Graph< SolverT >::getEdgeNode2Id ( EdgeId EId ) [inline]

Get the second node connected to this edge.

Parameters:

EId Edge id.

Returns:: The second node connected to the given edge.

Definition at line 463 of file Graph.h.

Referenced by PBQP::Graph< SolverT >::dump(), PBQP::Graph< SolverT >::findEdge(), PBQP::RegAlloc::RegAllocSolverImpl::handleAddEdge(), PBQP::RegAlloc::RegAllocSolverImpl::handleDisconnectEdge(), PBQP::RegAlloc::RegAllocSolverImpl::handleReconnectEdge(), PBQP::RegAlloc::RegAllocSolverImpl::handleRemoveEdge(), PBQP::RegAlloc::RegAllocSolverImpl::handleSetEdgeCosts(), and PBQP::Graph< SolverT >::printDot().

template<typename SolverT >

NodeId PBQP::Graph< SolverT >::getEdgeOtherNodeId	(	EdgeId	EId,
		NodeId	NId
	)		`[inline]`

Get the "other" node connected to this edge.

Parameters:

EId	Edge id.
NId	Node id for the "given" node.

Returns:: The iterator for the "other" node connected to this edge.

Definition at line 471 of file Graph.h.

Referenced by PBQP::Graph< SolverT >::disconnectAllNeighborsFromNode().

template<typename SolverT >

const Vector& PBQP::Graph< SolverT >::getNodeCosts ( NodeId NId ) const [inline]

Get a node's cost vector (const version).

Parameters:

NId Node id.

Returns:: Node cost vector.

Definition at line 413 of file Graph.h.

Referenced by PBQP::Graph< SolverT >::addEdge(), PBQP::Graph< SolverT >::dump(), PBQP::RegAlloc::RegAllocSolverImpl::handleAddNode(), and PBQP::Graph< SolverT >::printDot().

template<typename SolverT >

NodeEntry::AdjEdgeList::size_type PBQP::Graph< SolverT >::getNodeDegree ( NodeId NId ) const [inline]

Definition at line 425 of file Graph.h.

Referenced by PBQP::RegAlloc::RegAllocSolverImpl::handleDisconnectEdge().

template<typename SolverT >

NodeMetadata& PBQP::Graph< SolverT >::getNodeMetadata ( NodeId NId ) [inline]

Definition at line 417 of file Graph.h.

Referenced by PBQP::RegAlloc::RegAllocSolverImpl::handleAddNode(), PBQP::RegAlloc::RegAllocSolverImpl::handleDisconnectEdge(), PBQP::RegAlloc::RegAllocSolverImpl::handleReconnectEdge(), and PBQP::RegAlloc::RegAllocSolverImpl::handleSetEdgeCosts().

template<typename SolverT >

const NodeMetadata& PBQP::Graph< SolverT >::getNodeMetadata ( NodeId NId ) const [inline]

Definition at line 421 of file Graph.h.

template<typename SolverT >

unsigned PBQP::Graph< SolverT >::getNumEdges ( ) const [inline]

Get the number of edges in the graph.

Returns:: Number of edges in the graph.

Definition at line 397 of file Graph.h.

References PBQP::Graph< SolverT >::EdgeIdSet::size().

template<typename SolverT >

unsigned PBQP::Graph< SolverT >::getNumNodes ( ) const [inline]

Get the number of nodes in the graph.

Returns:: Number of nodes in the graph.

Definition at line 393 of file Graph.h.

References PBQP::Graph< SolverT >::NodeIdSet::size().

template<typename SolverT >

NodeIdSet PBQP::Graph< SolverT >::nodeIds ( ) const [inline]

Definition at line 386 of file Graph.h.

Referenced by PBQP::Graph< SolverT >::dump(), PBQP::Graph< SolverT >::printDot(), and PBQP::Graph< SolverT >::setSolver().

template<typename SolverT >

template<typename OStream >

void PBQP::Graph< SolverT >::printDot ( OStream & OS ) [inline]

Print a representation of this graph in DOT format.

Parameters:

OS	Output stream to print on.

Definition at line 619 of file Graph.h.

References PBQP::Graph< SolverT >::edgeIds(), PBQP::Graph< SolverT >::getEdgeCosts(), PBQP::Graph< SolverT >::getEdgeNode1Id(), PBQP::Graph< SolverT >::getEdgeNode2Id(), PBQP::Graph< SolverT >::getNodeCosts(), PBQP::Graph< SolverT >::nodeIds(), and PBQP::Graph< SolverT >::NodeIdSet::size().

template<typename SolverT >

void PBQP::Graph< SolverT >::reconnectEdge	(	EdgeId	EId,
		NodeId	NId
	)		`[inline]`

Re-attach an edge to its nodes.

Adds an edge that had been previously disconnected back into the adjacency set of the nodes that the edge connects.

Definition at line 555 of file Graph.h.

template<typename SolverT >

void PBQP::Graph< SolverT >::removeEdge ( EdgeId EId ) [inline]

Remove an edge from the graph.

Parameters:

EId Edge id.

Definition at line 564 of file Graph.h.

Referenced by PBQP::Graph< SolverT >::removeNode().

template<typename SolverT >

void PBQP::Graph< SolverT >::removeNode ( NodeId NId ) [inline]

Remove a node from the graph.

Parameters:

NId Node id.

Definition at line 496 of file Graph.h.

References PBQP::Graph< SolverT >::removeEdge().

template<typename SolverT >

template<typename OtherMatrixT >

void PBQP::Graph< SolverT >::setEdgeCosts	(	EdgeId	EId,
		OtherMatrixT	Costs
	)		`[inline]`

Set an edge's cost matrix.

Parameters:

EId	Edge id.
Costs	New cost matrix.

Definition at line 433 of file Graph.h.

template<typename SolverT >

template<typename OtherVectorT >

void PBQP::Graph< SolverT >::setNodeCosts	(	NodeId	NId,
		OtherVectorT	Costs
	)		`[inline]`

Set a node's cost vector.

Parameters:

NId	Node to update.
Costs	New costs to set.

Definition at line 403 of file Graph.h.

template<typename SolverT >

void PBQP::Graph< SolverT >::setSolver ( SolverT & S ) [inline]

Lock this graph to the given solver instance in preparation for running the solver. This method will call solver.handleAddNode for each node in the graph, and handleAddEdge for each edge, to give the solver an opportunity to set up any requried metadata.

Definition at line 338 of file Graph.h.

References PBQP::Graph< SolverT >::edgeIds(), and PBQP::Graph< SolverT >::nodeIds().

Referenced by PBQP::RegAlloc::RegAllocSolverImpl::solve().

template<typename SolverT >

void PBQP::Graph< SolverT >::unsetSolver ( ) [inline]

Release from solver instance.

Definition at line 348 of file Graph.h.

Referenced by PBQP::RegAlloc::RegAllocSolverImpl::solve().

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