Digraph< T > Class Template Reference

Generic directed graph. More...

#include <Digraph.hpp>

List of all members.

Public Types
typedef std::map< T, std::set < T > >	MapType
typedef std::set< T >::iterator	iterator
typedef std::set< T > ::const_iterator	const_iterator
Public Member Functions
	Digraph ()
	Constructor.
	~Digraph ()
	Destructor.
int	NumVertices () const
	Returns number of vertices in graph.
const std::set< T > &	Vertices () const
	Returns the vertex set.
bool	VertexExists (const T &vertex) const
	Returns true if vertex exists in graph.
bool	IsIsolated (const T &vertex) const
	Returns true if vertex has no outgoing or incoming edges.
std::set< T >	Sources () const
	Returns the vertices with out-degree>0 and in-degree==0.
std::set< T >	Sinks () const
	Returns the vertices with out-degree==0 and in-degree>0.
int	InDegree (const T &target) const
	Returns the number of edges entering target.
int	OutDegree (const T &source) const
	Returns the number of edges leaving source.
bool	IsEdge (const T &x, const T &y) const
	Returns true if there is an edge (x->y).
void	Transpose (Digraph< T > &out) const
	Returns the transpose of this graph (ie, the graph with edge directions reversed).
const std::set< T > &	OutSet (const T &source) const
	Returns set of nodes pointed to by source.
void	OutSet (const std::set< T > &source, std::set< T > &out) const
	Stores all targets of vertices in source.
const std::set< T > &	InSet (const T &target) const
	Returns nodes pointing to target.
void	InSet (const std::set< T > &target, std::set< T > &out) const
	Stores all sources of edges into any member of target.
void	FindTwoCycles (std::set< T > &cycles) const
	Stores all vertices that are on a two cycle in cycles.
void	FindStronglyConnectedComponents (std::vector< std::set< T > > &out) const
	Stores the strongly connected components in out.
const_iterator	out_begin (const T &source) const
const_iterator	out_end (const T &source) const
const_iterator	in_begin (const T &target) const
const_iterator	in_end (const T &target) const
void	Clear ()
	Clears the graph.
void	AddEdge (const T &source, const T &target)
	Adds edge from source to target.
void	AddEdges (const T &source, const std::set< T > &targets)
	Adds edges from source to each of the targets.
void	RemoveEdge (const T &source, const T &target)
	Removes edge from source to target.
void	RemoveVertex (const T &vertex)
	Removes vertex from the graph.
Private Types
typedef std::pair< int, T >	ScoreNodePair
typedef std::set < ScoreNodePair, std::greater < ScoreNodePair > >	OrderedChildren
Private Member Functions
void	OrderChildren (const std::set< T > &children, std::map< T, int > &tiebreaker, std::map< T, int > &finished, OrderedChildren &out) const
void	DFS (int &step, const T &vertex, std::map< T, int > &tiebreaker, std::map< T, int > &finished, std::set< T > &visited) const
Private Attributes
MapType	m_out
MapType	m_in
std::set< T >	m_vertices

---

Detailed Description

template<typename T>
class Digraph< T >

Generic directed graph.

Definition at line 22 of file Digraph.hpp.

---

Member Typedef Documentation

template<typename T>

typedef std::set<T>::const_iterator Digraph< T >::const_iterator

Definition at line 37 of file Digraph.hpp.

template<typename T>

typedef std::set<T>::iterator Digraph< T >::iterator

Definition at line 36 of file Digraph.hpp.

template<typename T>

typedef std::map<T, std::set<T> > Digraph< T >::MapType

Definition at line 34 of file Digraph.hpp.

template<typename T>

typedef std::set<ScoreNodePair, std::greater<ScoreNodePair> > Digraph< T >::OrderedChildren [private]

Definition at line 124 of file Digraph.hpp.

template<typename T>

typedef std::pair<int, T> Digraph< T >::ScoreNodePair [private]

Definition at line 123 of file Digraph.hpp.

---

Constructor & Destructor Documentation

template<typename T >

Digraph< T >::Digraph

(

)

[inline]

Constructor.

Definition at line 147 of file Digraph.hpp.

template<typename T >

Digraph< T >::~Digraph

(

)

[inline]

Destructor.

Definition at line 152 of file Digraph.hpp.

---

Member Function Documentation

template<typename T>

void Digraph< T >::AddEdge	(	const T &	source,
		const T &	target
	)			[inline]

Adds edge from source to target.

Definition at line 320 of file Digraph.hpp.

References Digraph< T >::m_in, Digraph< T >::m_out, and Digraph< T >::m_vertices.

Referenced by InferiorCells::AddDominated(), and Digraph< T >::AddEdges().

template<typename T>

void Digraph< T >::AddEdges	(	const T &	source,
		const std::set< T > &	targets
	)			[inline]

Adds edges from source to each of the targets.

Definition at line 330 of file Digraph.hpp.

References Digraph< T >::AddEdge().

Referenced by InferiorCells::AddDominated().

template<typename T >

void Digraph< T >::Clear

(

)

[inline]

Clears the graph.

Definition at line 312 of file Digraph.hpp.

References Digraph< T >::m_in, Digraph< T >::m_out, and Digraph< T >::m_vertices.

Referenced by InferiorCells::ClearDominated().

template<typename T>

void Digraph< T >::DFS	(	int &	step,
		const T &	vertex,
		std::map< T, int > &	tiebreaker,
		std::map< T, int > &	finished,
		std::set< T > &	visited
	)			const [inline, private]

Definition at line 393 of file Digraph.hpp.

References Digraph< T >::m_out, and Digraph< T >::OrderChildren().

Referenced by Digraph< T >::FindStronglyConnectedComponents().

template<typename T>

void Digraph< T >::FindStronglyConnectedComponents

(

std::vector< std::set< T > > &

out

)

const [inline]

Stores the strongly connected components in out.

Definition at line 418 of file Digraph.hpp.

References Digraph< T >::DFS(), Digraph< T >::m_vertices, Digraph< T >::OrderChildren(), and Digraph< T >::Transpose().

Referenced by InferiorCellsUtil::FindDominationCaptains().

template<typename T>

void Digraph< T >::FindTwoCycles

(

std::set< T > &

cycles

)

const [inline]

Stores all vertices that are on a two cycle in cycles.

Definition at line 263 of file Digraph.hpp.

References Digraph< T >::m_vertices, Digraph< T >::out_begin(), and Digraph< T >::out_end().

template<typename T>

Digraph< T >::const_iterator Digraph< T >::in_begin

(

const T &

target

)

const [inline]

Definition at line 296 of file Digraph.hpp.

References Digraph< T >::m_in, and Digraph< T >::VertexExists().

Referenced by Digraph< T >::InSet().

template<typename T>

Digraph< T >::const_iterator Digraph< T >::in_end

(

const T &

target

)

const [inline]

Definition at line 303 of file Digraph.hpp.

References Digraph< T >::m_in, and Digraph< T >::VertexExists().

Referenced by Digraph< T >::InSet().

template<typename T>

int Digraph< T >::InDegree

(

const T &

target

)

const [inline]

Returns the number of edges entering target.

Definition at line 193 of file Digraph.hpp.

References Digraph< T >::m_in, and Digraph< T >::VertexExists().

template<typename T>

void Digraph< T >::InSet	(	const std::set< T > &	target,
		std::set< T > &	out
	)			const [inline]

Stores all sources of edges into any member of target.

Definition at line 243 of file Digraph.hpp.

References Digraph< T >::in_begin(), Digraph< T >::in_end(), and Digraph< T >::VertexExists().

template<typename T>

const std::set< T > & Digraph< T >::InSet

(

const T &

target

)

const [inline]

Returns nodes pointing to target.

Definition at line 236 of file Digraph.hpp.

References Digraph< T >::m_in, and Digraph< T >::VertexExists().

template<typename T>

bool Digraph< T >::IsEdge	(	const T &	x,
		const T &	y
	)			const [inline]

Returns true if there is an edge (x->y).

Definition at line 213 of file Digraph.hpp.

References Digraph< T >::m_out.

template<typename T>

bool Digraph< T >::IsIsolated

(

const T &

vertex

)

const [inline]

Returns true if vertex has no outgoing or incoming edges.

Definition at line 200 of file Digraph.hpp.

References Digraph< T >::m_in, and Digraph< T >::m_out.

template<typename T >

int Digraph< T >::NumVertices

(

)

const [inline]

Returns number of vertices in graph.

Definition at line 159 of file Digraph.hpp.

References Digraph< T >::m_vertices.

template<typename T>

void Digraph< T >::OrderChildren	(	const std::set< T > &	children,
		std::map< T, int > &	tiebreaker,
		std::map< T, int > &	finished,
		OrderedChildren &	out
	)			const [inline, private]

Definition at line 379 of file Digraph.hpp.

Referenced by Digraph< T >::DFS(), and Digraph< T >::FindStronglyConnectedComponents().

template<typename T>

Digraph< T >::const_iterator Digraph< T >::out_begin

(

const T &

source

)

const [inline]

Definition at line 282 of file Digraph.hpp.

References Digraph< T >::m_out, and Digraph< T >::VertexExists().

Referenced by Digraph< T >::FindTwoCycles(), InferiorCells::GuiOutput(), and Digraph< T >::OutSet().

template<typename T>

Digraph< T >::const_iterator Digraph< T >::out_end

(

const T &

source

)

const [inline]

Definition at line 289 of file Digraph.hpp.

References Digraph< T >::m_out, and Digraph< T >::VertexExists().

Referenced by Digraph< T >::FindTwoCycles(), InferiorCells::GuiOutput(), and Digraph< T >::OutSet().

template<typename T>

int Digraph< T >::OutDegree

(

const T &

source

)

const [inline]

Returns the number of edges leaving source.

Definition at line 206 of file Digraph.hpp.

References Digraph< T >::m_out, and Digraph< T >::VertexExists().

template<typename T>

void Digraph< T >::OutSet	(	const std::set< T > &	source,
		std::set< T > &	out
	)			const [inline]

Stores all targets of vertices in source.

Definition at line 226 of file Digraph.hpp.

References Digraph< T >::out_begin(), Digraph< T >::out_end(), and Digraph< T >::VertexExists().

template<typename T>

const std::set< T > & Digraph< T >::OutSet

(

const T &

source

)

const [inline]

Returns set of nodes pointed to by source.

Definition at line 219 of file Digraph.hpp.

References Digraph< T >::m_out, and Digraph< T >::VertexExists().

Referenced by InferiorCells::AddDominatedFrom(), and InferiorCellsUtil::FindDominationCaptains().

template<typename T>

void Digraph< T >::RemoveEdge	(	const T &	source,
		const T &	target
	)			[inline]

Removes edge from source to target.

Definition at line 338 of file Digraph.hpp.

References Digraph< T >::m_in, and Digraph< T >::m_out.

template<typename T>

void Digraph< T >::RemoveVertex

(

const T &

vertex

)

[inline]

Removes vertex from the graph.

Definition at line 347 of file Digraph.hpp.

References Digraph< T >::m_in, Digraph< T >::m_out, Digraph< T >::m_vertices, and Digraph< T >::VertexExists().

Referenced by InferiorCells::Dominated(), and InferiorCells::RemoveDominated().

template<typename T >

std::set< T > Digraph< T >::Sinks

(

)

const [inline]

Returns the vertices with out-degree==0 and in-degree>0.

Definition at line 182 of file Digraph.hpp.

References Digraph< T >::m_in, and Digraph< T >::m_out.

template<typename T >

std::set< T > Digraph< T >::Sources

(

)

const [inline]

Returns the vertices with out-degree>0 and in-degree==0.

Definition at line 171 of file Digraph.hpp.

References Digraph< T >::m_in, and Digraph< T >::m_out.

template<typename T>

void Digraph< T >::Transpose

(

Digraph< T > &

out

)

const [inline]

Returns the transpose of this graph (ie, the graph with edge directions reversed).

Definition at line 253 of file Digraph.hpp.

References Digraph< T >::m_in, Digraph< T >::m_out, and Digraph< T >::m_vertices.

Referenced by Digraph< T >::FindStronglyConnectedComponents().

template<typename T>

bool Digraph< T >::VertexExists

(

const T &

vertex

)

const [inline]

Returns true if vertex exists in graph.

Definition at line 370 of file Digraph.hpp.

References Digraph< T >::m_vertices.

Referenced by Digraph< T >::in_begin(), Digraph< T >::in_end(), Digraph< T >::InDegree(), Digraph< T >::InSet(), Digraph< T >::out_begin(), Digraph< T >::out_end(), Digraph< T >::OutDegree(), Digraph< T >::OutSet(), and Digraph< T >::RemoveVertex().

template<typename T >

const std::set< T > & Digraph< T >::Vertices

(

)

const [inline]

Returns the vertex set.

Definition at line 165 of file Digraph.hpp.

References Digraph< T >::m_vertices.

Referenced by InferiorCells::AddDominatedFrom(), InferiorCells::Dominated(), and InferiorCells::RemoveDominated().

---

Member Data Documentation

template<typename T>

MapType Digraph< T >::m_in [mutable, private]

Definition at line 140 of file Digraph.hpp.

Referenced by Digraph< T >::AddEdge(), Digraph< T >::Clear(), Digraph< T >::in_begin(), Digraph< T >::in_end(), Digraph< T >::InDegree(), Digraph< T >::InSet(), Digraph< T >::IsIsolated(), Digraph< T >::RemoveEdge(), Digraph< T >::RemoveVertex(), Digraph< T >::Sinks(), Digraph< T >::Sources(), and Digraph< T >::Transpose().

template<typename T>

MapType Digraph< T >::m_out [mutable, private]

Definition at line 139 of file Digraph.hpp.

Referenced by Digraph< T >::AddEdge(), Digraph< T >::Clear(), Digraph< T >::DFS(), Digraph< T >::IsEdge(), Digraph< T >::IsIsolated(), Digraph< T >::out_begin(), Digraph< T >::out_end(), Digraph< T >::OutDegree(), Digraph< T >::OutSet(), Digraph< T >::RemoveEdge(), Digraph< T >::RemoveVertex(), Digraph< T >::Sinks(), Digraph< T >::Sources(), and Digraph< T >::Transpose().

template<typename T>

std::set<T> Digraph< T >::m_vertices [private]

Definition at line 141 of file Digraph.hpp.

Referenced by Digraph< T >::AddEdge(), Digraph< T >::Clear(), Digraph< T >::FindStronglyConnectedComponents(), Digraph< T >::FindTwoCycles(), Digraph< T >::NumVertices(), Digraph< T >::RemoveVertex(), Digraph< T >::Transpose(), Digraph< T >::VertexExists(), and Digraph< T >::Vertices().

---

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

• Digraph.hpp