PBQP::Graph Class Reference

#include <Graph.h>

Classes
class	EdgeItr
class	NodeItr

Public Types
typedef unsigned	NodeId
typedef unsigned	EdgeId
typedef AdjEdgeList::iterator	AdjEdgeItr

Public Member Functions
	Graph ()
	Construct an empty PBQP graph. More...
NodeId	addNode (const Vector &costs)
	Add a node with the given costs. More...
EdgeId	addEdge (NodeId n1Id, NodeId n2Id, const Matrix &costs)
	Add an edge between the given nodes with the given costs. More...
unsigned	getNumNodes () const
	Get the number of nodes in the graph. More...
unsigned	getNumEdges () const
	Get the number of edges in the graph. More...
Vector &	getNodeCosts (NodeId nId)
	Get a node's cost vector. More...
const Vector &	getNodeCosts (NodeId nId) const
	Get a node's cost vector (const version). More...
void	setNodeData (NodeId nId, void *data)
	Set a node's data pointer. More...
void *	getNodeData (NodeId nId)
	Get the node's data pointer. More...
Matrix &	getEdgeCosts (EdgeId eId)
	Get an edge's cost matrix. More...
const Matrix &	getEdgeCosts (EdgeId eId) const
	Get an edge's cost matrix (const version). More...
void	setEdgeData (EdgeId eId, void *data)
	Set an edge's data pointer. More...
void *	getEdgeData (EdgeId eId)
	Get an edge's data pointer. More...
unsigned	getNodeDegree (NodeId nId) const
	Get a node's degree. More...
NodeItr	nodesBegin () const
	Begin iterator for node set. More...
NodeItr	nodesEnd () const
	End iterator for node set. More...
EdgeItr	edgesBegin () const
	Begin iterator for edge set. More...
EdgeItr	edgesEnd () const
	End iterator for edge set. More...
AdjEdgeItr	adjEdgesBegin (NodeId nId)
	Get begin iterator for adjacent edge set. More...
AdjEdgeItr	adjEdgesEnd (NodeId nId)
	Get end iterator for adjacent edge set. More...
NodeId	getEdgeNode1 (EdgeId eId)
	Get the first node connected to this edge. More...
NodeId	getEdgeNode2 (EdgeId eId)
	Get the second node connected to this edge. More...
NodeId	getEdgeOtherNode (EdgeId eId, NodeId nId)
	Get the "other" node connected to this edge. More...
EdgeId	invalidEdgeId () const
EdgeId	findEdge (NodeId n1Id, NodeId n2Id)
	Get the edge connecting two nodes. More...
void	removeNode (NodeId nId)
	Remove a node from the graph. More...
void	removeEdge (EdgeId eId)
	Remove an edge from the graph. More...
void	clear ()
	Remove all nodes and edges from the graph. More...
template<typename OStream >
void	dump (OStream &os)
	Dump a graph to an output stream. More...
template<typename OStream >
void	printDot (OStream &os)
	Print a representation of this graph in DOT format. More...

Detailed Description

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

Definition at line 29 of file Graph.h.

Member Typedef Documentation

typedef AdjEdgeList::iterator PBQP::Graph::AdjEdgeItr

Definition at line 41 of file Graph.h.

typedef unsigned PBQP::Graph::EdgeId

Definition at line 33 of file Graph.h.

typedef unsigned PBQP::Graph::NodeId

Definition at line 32 of file Graph.h.

Constructor & Destructor Documentation

PBQP::Graph::Graph ( )

inline

Construct an empty PBQP graph.

Definition at line 208 of file Graph.h.

Member Function Documentation

EdgeId PBQP::Graph::addEdge ( NodeId  n1Id, NodeId  n2Id, const Matrix &  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 221 of file Graph.h.

References PBQP::Matrix::getCols(), PBQP::Vector::getLength(), getNodeCosts(), and PBQP::Matrix::getRows().

Referenced by PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR2(), llvm::PBQPBuilder::build(), and llvm::PBQPBuilderWithCoalescing::build().

NodeId PBQP::Graph::addNode ( const Vector &  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 213 of file Graph.h.

Referenced by llvm::PBQPBuilder::build().

AdjEdgeItr PBQP::Graph::adjEdgesBegin ( NodeId  nId )

inline

Get begin iterator for adjacent edge set.

Parameters

nId

Node id.

Returns

Begin iterator for the set of edges connected to the given node.

Definition at line 306 of file Graph.h.

Referenced by findEdge(), and PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::setSolution().

AdjEdgeItr PBQP::Graph::adjEdgesEnd ( NodeId  nId )

inline

Get end iterator for adjacent edge set.

Parameters

nId

Node id.

Returns

End iterator for the set of edges connected to the given node.

Definition at line 313 of file Graph.h.

Referenced by findEdge(), and PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::setSolution().

void PBQP::Graph::clear ( )

inline

Remove all nodes and edges from the graph.

Definition at line 386 of file Graph.h.

template<typename OStream >

void PBQP::Graph::dump ( OStream &  os )

inline

Dump a graph to an output stream.

Definition at line 395 of file Graph.h.

References edgesBegin(), edgesEnd(), PBQP::Matrix::getCols(), getEdgeCosts(), getEdgeNode1(), getEdgeNode2(), PBQP::Vector::getLength(), getNodeCosts(), getNumEdges(), getNumNodes(), PBQP::Matrix::getRows(), nodesBegin(), and nodesEnd().

EdgeItr PBQP::Graph::edgesBegin ( ) const

inline

Begin iterator for edge set.

Definition at line 298 of file Graph.h.

Referenced by dump(), and printDot().

EdgeItr PBQP::Graph::edgesEnd ( ) const

inline

End iterator for edge set.

Definition at line 301 of file Graph.h.

Referenced by dump(), and printDot().

EdgeId PBQP::Graph::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 352 of file Graph.h.

References adjEdgesBegin(), adjEdgesEnd(), getEdgeNode1(), getEdgeNode2(), and invalidEdgeId().

Referenced by PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR2(), and llvm::PBQPBuilderWithCoalescing::build().

Matrix& PBQP::Graph::getEdgeCosts ( EdgeId  eId )

inline

Get an edge's cost matrix.

Parameters

eId

Edge id.

Returns

Edge cost matrix.

Definition at line 263 of file Graph.h.

Referenced by PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR1(), PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR2(), llvm::PBQPBuilder::build(), llvm::PBQPBuilderWithCoalescing::build(), dump(), and printDot().

const Matrix& PBQP::Graph::getEdgeCosts ( EdgeId  eId ) const

inline

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

Parameters

eId

Edge id.

Returns

Edge cost matrix.

Definition at line 268 of file Graph.h.

void* PBQP::Graph::getEdgeData ( EdgeId  eId )

inline

Get an edge's data pointer.

Parameters

eId

Edge id.

Returns

Pointer to edge data.

Definition at line 282 of file Graph.h.

NodeId PBQP::Graph::getEdgeNode1 ( 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 320 of file Graph.h.

Referenced by PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR1(), PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR2(), llvm::PBQPBuilderWithCoalescing::build(), dump(), findEdge(), PBQP::Heuristics::Briggs::handleAddEdge(), PBQP::Heuristics::Briggs::preUpdateEdgeCosts(), printDot(), and PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::removeSolverEdge().

NodeId PBQP::Graph::getEdgeNode2 ( 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 327 of file Graph.h.

Referenced by PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR1(), dump(), findEdge(), PBQP::Heuristics::Briggs::handleAddEdge(), PBQP::Heuristics::Briggs::preUpdateEdgeCosts(), printDot(), and PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::removeSolverEdge().

NodeId PBQP::Graph::getEdgeOtherNode ( 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 335 of file Graph.h.

Referenced by PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR2(), and PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::setSolution().

Vector& PBQP::Graph::getNodeCosts ( NodeId  nId )

inline

Get a node's cost vector.

Parameters

nId

Node id.

Returns

Node cost vector.

Definition at line 239 of file Graph.h.

Referenced by addEdge(), PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR1(), PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR2(), llvm::PBQPBuilder::build(), llvm::PBQPBuilderWithCoalescing::build(), dump(), and printDot().

const Vector& PBQP::Graph::getNodeCosts ( NodeId  nId ) const

inline

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

Parameters

nId

Node id.

Returns

Node cost vector.

Definition at line 244 of file Graph.h.

void* PBQP::Graph::getNodeData ( NodeId  nId )

inline

Get the node's data pointer.

Parameters

nId

Node id.

Returns

Pointer to node data.

Definition at line 258 of file Graph.h.

unsigned PBQP::Graph::getNodeDegree ( NodeId  nId ) const

inline

Get a node's degree.

Parameters

nId

Node id.

Returns

The degree of the node.

Definition at line 287 of file Graph.h.

Referenced by PBQP::HeuristicBase< Briggs >::shouldOptimallyReduce().

unsigned PBQP::Graph::getNumEdges ( ) const

inline

Get the number of edges in the graph.

Returns

Number of edges in the graph.

Definition at line 234 of file Graph.h.

Referenced by dump().

unsigned PBQP::Graph::getNumNodes ( ) const

inline

Get the number of nodes in the graph.

Returns

Number of nodes in the graph.

Definition at line 230 of file Graph.h.

Referenced by dump(), and printDot().

EdgeId PBQP::Graph::invalidEdgeId ( ) const

inline

Definition at line 343 of file Graph.h.

Referenced by PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR2(), llvm::PBQPBuilderWithCoalescing::build(), and findEdge().

NodeItr PBQP::Graph::nodesBegin ( ) const

inline

Begin iterator for node set.

Definition at line 292 of file Graph.h.

Referenced by dump(), printDot(), and PBQP::HeuristicBase< Briggs >::setup().

NodeItr PBQP::Graph::nodesEnd ( ) const

inline

End iterator for node set.

Definition at line 295 of file Graph.h.

Referenced by dump(), printDot(), and PBQP::HeuristicBase< Briggs >::setup().

template<typename OStream >

void PBQP::Graph::printDot ( OStream &  os )

inline

Print a representation of this graph in DOT format.

Parameters

os	Output stream to print on.

Definition at line 433 of file Graph.h.

References edgesBegin(), edgesEnd(), getEdgeCosts(), getEdgeNode1(), getEdgeNode2(), getNodeCosts(), getNumNodes(), PBQP::Matrix::getRowAsVector(), PBQP::Matrix::getRows(), nodesBegin(), and nodesEnd().

void PBQP::Graph::removeEdge ( EdgeId  eId )

inline

Remove an edge from the graph.

Parameters

eId

Edge id.

Definition at line 376 of file Graph.h.

Referenced by PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR2(), and removeNode().

void PBQP::Graph::removeNode ( NodeId  nId )

inline

Remove a node from the graph.

Parameters

nId

Node id.

Definition at line 365 of file Graph.h.

References llvm::sys::path::end(), and removeEdge().

void PBQP::Graph::setEdgeData ( EdgeId  eId, void *  data  )

inline

Set an edge's data pointer.

Parameters

eId	Edge id.
data	Pointer to edge data.

Typically used by a PBQP solver to attach data to aid in solution.

Definition at line 277 of file Graph.h.

Referenced by PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR2().

void PBQP::Graph::setNodeData ( NodeId  nId, void *  data  )

inline

Set a node's data pointer.

Parameters

nId	Node id.
data	Pointer to node data.

Typically used by a PBQP solver to attach data to aid in solution.

Definition at line 253 of file Graph.h.

---

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

• Graph.h