It defines a graph that in each node can store additional data. More...

#include <capd/invset/Graph.h>

Public Types
typedef VertexT	VertexType

typedef std::set< VertexT, lessT >	VertexSet

typedef NodeDataT	NodeData

typedef lessT	OrderType

typedef GraphNode< VertexSet, NodeDataT >	Node

typedef std::map< VertexType, Node, lessT >	Nodes

typedef Nodes::iterator	iterator

typedef Nodes::const_iterator	const_iterator

Public Member Functions
Nodes &	nodes ()

const Node &	getNode (const VertexType &vertex) const

void	setNode (const VertexType &vertex, const Node &node)

void	insertNode (const VertexType &vertex)

const NodeData &	getNodeData (const VertexType &vertex) const

NodeData &	nodeData (const VertexType &vertex)

void	setNodeData (const VertexType &vertex, const NodeData &nodeData)

void	clearEdges ()
	removes all edges for the graph More...

void	clearInEdges ()
	removes all in-edges from the graph More...

void	insertInEdges ()
	creates inverted graph More...

void	eraseNodeAndEdges (iterator &node)
	it removes node given by iterator and all edges pointing to it More...

void	erase (iterator &node)
	removes node given by iterator and all edges pointing to it More...

void	eraseAcyclicVertices ()
	It iteratively erases acyclic vertices We assume that inverse graph is already created (e.g. by calling insertInEdges()) More...

void	eraseNoInVertices ()
	It iteratively erase vertices that do not have any inward edges. More...

void	eraseNoOutVertices ()
	It iteratively erase vertices that do not have any outward edges. More...

VertexSet	findFixedPoints () const
	returns set of vertices that have self-loop (edge that connects vertex to itself) More...

template<typename VertexContainer >
void	findCycles (VertexContainer result[], int maxlength) const
	finds cyclic vertices to a given maximal cycle length More...

int	findCycleLength (const_iterator vertex, int maxlength) const
	for given vertex returns the shortest cycle length starting at this vertex More...

Detailed Description

template<typename VertexT, typename lessT, typename NodeDataT>
class capd::invset::Graph< VertexT, lessT, NodeDataT >

It defines a graph that in each node can store additional data.

Graph is stored as association lists using standard map and set data types VertexT defines how to encode vertices lessT is a strict ordering of vertices needed by map and set containers NodeData type of data stored in each node

Member Typedef Documentation

◆ const_iterator

template<typename VertexT , typename lessT , typename NodeDataT >

typedef Nodes::const_iterator capd::invset::Graph< VertexT, lessT, NodeDataT >::const_iterator

◆ iterator

template<typename VertexT , typename lessT , typename NodeDataT >

typedef Nodes::iterator capd::invset::Graph< VertexT, lessT, NodeDataT >::iterator

◆ Node

template<typename VertexT , typename lessT , typename NodeDataT >

typedef GraphNode<VertexSet, NodeDataT> capd::invset::Graph< VertexT, lessT, NodeDataT >::Node

◆ NodeData

template<typename VertexT , typename lessT , typename NodeDataT >

typedef NodeDataT capd::invset::Graph< VertexT, lessT, NodeDataT >::NodeData

◆ Nodes

template<typename VertexT , typename lessT , typename NodeDataT >

typedef std::map<VertexType, Node, lessT> capd::invset::Graph< VertexT, lessT, NodeDataT >::Nodes

◆ OrderType

template<typename VertexT , typename lessT , typename NodeDataT >

typedef lessT capd::invset::Graph< VertexT, lessT, NodeDataT >::OrderType

◆ VertexSet

template<typename VertexT , typename lessT , typename NodeDataT >

typedef std::set<VertexT, lessT> capd::invset::Graph< VertexT, lessT, NodeDataT >::VertexSet

◆ VertexType

template<typename VertexT , typename lessT , typename NodeDataT >

typedef VertexT capd::invset::Graph< VertexT, lessT, NodeDataT >::VertexType

Member Function Documentation

◆ clearEdges()

template<typename VertexT , typename lessT , typename NodeDataT >

void capd::invset::Graph< VertexT, lessT, NodeDataT >::clearEdges ( )

inline

removes all edges for the graph

◆ clearInEdges()

template<typename VertexT , typename lessT , typename NodeDataT >

void capd::invset::Graph< VertexT, lessT, NodeDataT >::clearInEdges ( )

inline

removes all in-edges from the graph

◆ erase()

template<typename VertexT , typename lessT , typename NodeDataT >

void capd::invset::Graph< VertexT, lessT, NodeDataT >::erase ( iterator & node )

inline

removes node given by iterator and all edges pointing to it

◆ eraseAcyclicVertices()

template<typename VertexT , typename lessT , typename NodeDataT >

void capd::invset::Graph< VertexT, lessT, NodeDataT >::eraseAcyclicVertices ( )

inline

It iteratively erases acyclic vertices We assume that inverse graph is already created (e.g. by calling insertInEdges())

◆ eraseNodeAndEdges()

template<typename VertexT , typename lessT , typename NodeDataT >

void capd::invset::Graph< VertexT, lessT, NodeDataT >::eraseNodeAndEdges ( iterator & node )

inline

it removes node given by iterator and all edges pointing to it

◆ eraseNoInVertices()

template<typename VertexT , typename lessT , typename NodeDataT >

void capd::invset::Graph< VertexT, lessT, NodeDataT >::eraseNoInVertices ( )

inline

It iteratively erase vertices that do not have any inward edges.

◆ eraseNoOutVertices()

template<typename VertexT , typename lessT , typename NodeDataT >

void capd::invset::Graph< VertexT, lessT, NodeDataT >::eraseNoOutVertices ( )

inline

It iteratively erase vertices that do not have any outward edges.

◆ findCycleLength()

template<typename VertexT , typename lessT , typename NodeDataT >

int capd::invset::Graph< VertexT, lessT, NodeDataT >::findCycleLength	(	const_iterator	vertex,
		int	maxlength
	)		const

inline

for given vertex returns the shortest cycle length starting at this vertex

(for self-loop length = 0, for a-b-a length=1 etc.) returns -1 if it does not find cycle with length less or equal to maxlength.

◆ findCycles()

template<typename VertexT , typename lessT , typename NodeDataT >

template<typename VertexContainer >

void capd::invset::Graph< VertexT, lessT, NodeDataT >::findCycles	(	VertexContainer	result[],
		int	maxlength
	)		const

inline

finds cyclic vertices to a given maximal cycle length

in result[n] it returns vertices that belongs to some cycle of length n + 1 if vertex belongs to more than one cycle than the shortest cycle is concerned

◆ findFixedPoints()

template<typename VertexT , typename lessT , typename NodeDataT >

VertexSet capd::invset::Graph< VertexT, lessT, NodeDataT >::findFixedPoints ( ) const

inline

returns set of vertices that have self-loop (edge that connects vertex to itself)

◆ getNode()

template<typename VertexT , typename lessT , typename NodeDataT >

const Node& capd::invset::Graph< VertexT, lessT, NodeDataT >::getNode ( const VertexType & vertex ) const

inline

◆ getNodeData()

template<typename VertexT , typename lessT , typename NodeDataT >

const NodeData& capd::invset::Graph< VertexT, lessT, NodeDataT >::getNodeData ( const VertexType & vertex ) const

inline

◆ insertInEdges()

template<typename VertexT , typename lessT , typename NodeDataT >

void capd::invset::Graph< VertexT, lessT, NodeDataT >::insertInEdges ( )

inline

creates inverted graph

◆ insertNode()

template<typename VertexT , typename lessT , typename NodeDataT >

void capd::invset::Graph< VertexT, lessT, NodeDataT >::insertNode ( const VertexType & vertex )

inline

◆ nodeData()

template<typename VertexT , typename lessT , typename NodeDataT >

NodeData& capd::invset::Graph< VertexT, lessT, NodeDataT >::nodeData ( const VertexType & vertex )

inline

◆ nodes()

template<typename VertexT , typename lessT , typename NodeDataT >

Nodes& capd::invset::Graph< VertexT, lessT, NodeDataT >::nodes ( )

inline

◆ setNode()

template<typename VertexT , typename lessT , typename NodeDataT >

void capd::invset::Graph< VertexT, lessT, NodeDataT >::setNode	(	const VertexType &	vertex,
		const Node &	node
	)

inline

◆ setNodeData()

template<typename VertexT , typename lessT , typename NodeDataT >

void capd::invset::Graph< VertexT, lessT, NodeDataT >::setNodeData	(	const VertexType &	vertex,
		const NodeData &	nodeData
	)

inline

Public Types

Public Member Functions

Detailed Description

template<typename VertexT, typename lessT, typename NodeDataT> class capd::invset::Graph< VertexT, lessT, NodeDataT >

Member Typedef Documentation

◆ const_iterator

◆ iterator

◆ Node

◆ NodeData

◆ Nodes

◆ OrderType

◆ VertexSet

◆ VertexType

Member Function Documentation

◆ clearEdges()

◆ clearInEdges()

◆ erase()

◆ eraseAcyclicVertices()

◆ eraseNodeAndEdges()

◆ eraseNoInVertices()

◆ eraseNoOutVertices()

◆ findCycleLength()

◆ findCycles()

◆ findFixedPoints()

◆ getNode()

◆ getNodeData()

◆ insertInEdges()

◆ insertNode()

◆ nodeData()

◆ nodes()

◆ setNode()

◆ setNodeData()

template<typename VertexT, typename lessT, typename NodeDataT>
class capd::invset::Graph< VertexT, lessT, NodeDataT >