#include <Graph.h>

Classes
class	EdgeEntry
class	NodeEntry
Public Types
typedef NodeList::iterator	NodeItr
typedef NodeList::const_iterator	ConstNodeItr
typedef EdgeList::iterator	EdgeItr
typedef EdgeList::const_iterator	ConstEdgeItr
typedef AdjEdgeList::iterator	AdjEdgeItr
Public Member Functions
	Graph ()
	Construct an empty PBQP graph.
	Graph (const Graph &other)
	Copy construct this graph from "other". Note: Does not copy node and edge data, only graph structure and costs.
Graph &	operator= (const Graph &other)
	Make this graph a copy of "other". Note: Does not copy node and edge data, only graph structure and costs.
NodeItr	addNode (const Vector &costs)
	Add a node with the given costs.
EdgeItr	addEdge (Graph::NodeItr n1Itr, Graph::NodeItr n2Itr, const Matrix &costs)
	Add an edge between the given nodes with the given costs.
unsigned	getNumNodes () const
	Get the number of nodes in the graph.
unsigned	getNumEdges () const
	Get the number of edges in the graph.
Vector &	getNodeCosts (NodeItr nItr)
	Get a node's cost vector.
const Vector &	getNodeCosts (ConstNodeItr nItr) const
	Get a node's cost vector (const version).
void	setNodeData (NodeItr nItr, void *data)
	Set a node's data pointer.
void *	getNodeData (NodeItr nItr)
	Get the node's data pointer.
Matrix &	getEdgeCosts (EdgeItr eItr)
	Get an edge's cost matrix.
const Matrix &	getEdgeCosts (ConstEdgeItr eItr) const
	Get an edge's cost matrix (const version).
void	setEdgeData (EdgeItr eItr, void *data)
	Set an edge's data pointer.
void *	getEdgeData (EdgeItr eItr)
	Get an edge's data pointer.
unsigned	getNodeDegree (NodeItr nItr) const
	Get a node's degree.
NodeItr	nodesBegin ()
	Begin iterator for node set.
ConstNodeItr	nodesBegin () const
	Begin const iterator for node set.
NodeItr	nodesEnd ()
	End iterator for node set.
ConstNodeItr	nodesEnd () const
	End const iterator for node set.
EdgeItr	edgesBegin ()
	Begin iterator for edge set.
EdgeItr	edgesEnd ()
	End iterator for edge set.
AdjEdgeItr	adjEdgesBegin (NodeItr nItr)
	Get begin iterator for adjacent edge set.
AdjEdgeItr	adjEdgesEnd (NodeItr nItr)
	Get end iterator for adjacent edge set.
NodeItr	getEdgeNode1 (EdgeItr eItr)
	Get the first node connected to this edge.
NodeItr	getEdgeNode2 (EdgeItr eItr)
	Get the second node connected to this edge.
NodeItr	getEdgeOtherNode (EdgeItr eItr, NodeItr nItr)
	Get the "other" node connected to this edge.
EdgeItr	findEdge (NodeItr n1Itr, NodeItr n2Itr)
	Get the edge connecting two nodes.
void	removeNode (NodeItr nItr)
	Remove a node from the graph.
void	removeEdge (EdgeItr eItr)
	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

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

Definition at line 28 of file Graph.h.

Member Typedef Documentation

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

Definition at line 52 of file Graph.h.

typedef EdgeList::const_iterator PBQP::Graph::ConstEdgeItr

Definition at line 44 of file Graph.h.

typedef NodeList::const_iterator PBQP::Graph::ConstNodeItr

Definition at line 41 of file Graph.h.

typedef EdgeList::iterator PBQP::Graph::EdgeItr

Definition at line 43 of file Graph.h.

typedef NodeList::iterator PBQP::Graph::NodeItr

Definition at line 40 of file Graph.h.

Constructor & Destructor Documentation

PBQP::Graph::Graph ( ) [inline]

Construct an empty PBQP graph.

Definition at line 148 of file Graph.h.

PBQP::Graph::Graph ( const Graph & other ) [inline]

Copy construct this graph from "other". Note: Does not copy node and edge data, only graph structure and costs.

Parameters:

other Source graph to copy from.

Definition at line 153 of file Graph.h.

Member Function Documentation

EdgeItr PBQP::Graph::addEdge	(	Graph::NodeItr	n1Itr,
		Graph::NodeItr	n2Itr,
		const Matrix &	costs
	)		`[inline]`

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

Parameters:

n1Itr	First node.
n2Itr	Second node.

Returns:: Edge iterator for the added edge.

Definition at line 181 of file Graph.h.

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

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

NodeItr 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 173 of file Graph.h.

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

AdjEdgeItr PBQP::Graph::adjEdgesBegin ( NodeItr nItr ) [inline]

Get begin iterator for adjacent edge set.

Parameters:

nItr	Node iterator.

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

Definition at line 273 of file Graph.h.

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

AdjEdgeItr PBQP::Graph::adjEdgesEnd ( NodeItr nItr ) [inline]

Get end iterator for adjacent edge set.

Parameters:

nItr	Node iterator.

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

Definition at line 280 of file Graph.h.

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

void PBQP::Graph::clear ( ) [inline]

Remove all nodes and edges from the graph.

Definition at line 352 of file Graph.h.

References llvm::iplist< NodeTy, Traits >::clear().

Referenced by operator=().

template<typename OStream >

void PBQP::Graph::dump ( OStream & os ) [inline]

Dump a graph to an output stream.

Definition at line 360 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 ( ) [inline]

Begin iterator for edge set.

Definition at line 265 of file Graph.h.

References llvm::iplist< NodeTy, Traits >::begin().

Referenced by dump(), and printDot().

EdgeItr PBQP::Graph::edgesEnd ( ) [inline]

End iterator for edge set.

Definition at line 268 of file Graph.h.

References llvm::iplist< NodeTy, Traits >::end().

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

EdgeItr PBQP::Graph::findEdge	(	NodeItr	n1Itr,
		NodeItr	n2Itr
	)		`[inline]`

Get the edge connecting two nodes.

Parameters:

n1Itr	First node iterator.
n2Itr	Second node iterator.

Returns:: An iterator for edge (n1Itr, n2Itr) if such an edge exists, otherwise returns edgesEnd().

Definition at line 315 of file Graph.h.

References adjEdgesBegin(), adjEdgesEnd(), llvm::iplist< NodeTy, Traits >::end(), getEdgeNode1(), and getEdgeNode2().

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

Matrix& PBQP::Graph::getEdgeCosts ( EdgeItr eItr ) [inline]

Get an edge's cost matrix.

Parameters:

eItr	Edge iterator.

Returns:: Edge cost matrix.

Definition at line 224 of file Graph.h.

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

const Matrix& PBQP::Graph::getEdgeCosts ( ConstEdgeItr eItr ) const [inline]

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

Parameters:

eItr	Edge iterator.

Returns:: Edge cost matrix.

Definition at line 229 of file Graph.h.

void* PBQP::Graph::getEdgeData ( EdgeItr eItr ) [inline]

Get an edge's data pointer.

Parameters:

eItr	Edge iterator.

Returns:: Pointer to edge data.

Definition at line 243 of file Graph.h.

NodeItr PBQP::Graph::getEdgeNode1 ( EdgeItr eItr ) [inline]

Get the first node connected to this edge.

Parameters:

eItr	Edge iterator.

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

Definition at line 287 of file Graph.h.

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

NodeItr PBQP::Graph::getEdgeNode2 ( EdgeItr eItr ) [inline]

Get the second node connected to this edge.

Parameters:

eItr	Edge iterator.

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

Definition at line 294 of file Graph.h.

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

NodeItr PBQP::Graph::getEdgeOtherNode	(	EdgeItr	eItr,
		NodeItr	nItr
	)		`[inline]`

Get the "other" node connected to this edge.

Parameters:

eItr	Edge iterator.
nItr	Node iterator for the "given" node.

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

Definition at line 302 of file Graph.h.

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

Vector& PBQP::Graph::getNodeCosts ( NodeItr nItr ) [inline]

Get a node's cost vector.

Parameters:

nItr	Node iterator.

Returns:: Node cost vector.

Definition at line 200 of file Graph.h.

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

const Vector& PBQP::Graph::getNodeCosts ( ConstNodeItr nItr ) const [inline]

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

Parameters:

nItr	Node iterator.

Returns:: Node cost vector.

Definition at line 205 of file Graph.h.

void* PBQP::Graph::getNodeData ( NodeItr nItr ) [inline]

Get the node's data pointer.

Parameters:

nItr	Node iterator.

Returns:: Pointer to node data.

Definition at line 219 of file Graph.h.

unsigned PBQP::Graph::getNodeDegree ( NodeItr nItr ) const [inline]

Get a node's degree.

Parameters:

nItr	Node iterator.

Returns:: The degree of the node.

Definition at line 248 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 195 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 191 of file Graph.h.

Referenced by dump(), and printDot().

NodeItr PBQP::Graph::nodesBegin ( ) [inline]

Begin iterator for node set.

Definition at line 253 of file Graph.h.

References llvm::iplist< NodeTy, Traits >::begin().

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

ConstNodeItr PBQP::Graph::nodesBegin ( ) const [inline]

Begin const iterator for node set.

Definition at line 256 of file Graph.h.

References llvm::iplist< NodeTy, Traits >::begin().

NodeItr PBQP::Graph::nodesEnd ( ) [inline]

End iterator for node set.

Definition at line 259 of file Graph.h.

References llvm::iplist< NodeTy, Traits >::end().

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

ConstNodeItr PBQP::Graph::nodesEnd ( ) const [inline]

End const iterator for node set.

Definition at line 262 of file Graph.h.

References llvm::iplist< NodeTy, Traits >::end().

Graph& PBQP::Graph::operator= ( const Graph & other ) [inline]

Make this graph a copy of "other". Note: Does not copy node and edge data, only graph structure and costs.

Parameters:

other The graph to copy from.

Returns:: A reference to this graph.

This will clear the current graph, erasing any nodes and edges added, before copying from other.

Definition at line 164 of file Graph.h.

References clear().

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 398 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 ( EdgeItr eItr ) [inline]

Remove an edge from the graph.

Parameters:

eItr	Edge iterator.

Definition at line 341 of file Graph.h.

References llvm::iplist< NodeTy, Traits >::erase().

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

void PBQP::Graph::removeNode ( NodeItr nItr ) [inline]

Remove a node from the graph.

Parameters:

nItr	Node iterator.

Definition at line 328 of file Graph.h.

References llvm::sys::path::end(), llvm::iplist< NodeTy, Traits >::erase(), and removeEdge().

void PBQP::Graph::setEdgeData	(	EdgeItr	eItr,
		void *	data
	)		`[inline]`

Set an edge's data pointer.

Parameters:

eItr	Edge iterator.
data	Pointer to edge data.

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

Definition at line 238 of file Graph.h.

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

void PBQP::Graph::setNodeData	(	NodeItr	nItr,
		void *	data
	)		`[inline]`

Set a node's data pointer.

Parameters:

nItr	Node iterator.
data	Pointer to node data.

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

Definition at line 214 of file Graph.h.

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

Graph.h

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation