DynamicGraph< GraphImplementation, Vtype, Etype > Class Template Reference

A dynamic graph type. More...

#include <dynamicGraph.h>

List of all members.

Public Member Functions
EdgeIterator	beginEdges (const NodeIterator &u) const
	Returns the first outgoing edge of a node.
InEdgeIterator	beginInEdges (const NodeIterator &u) const
	Returns the first incoming edge of a node.
NodeIterator	beginNodes () const
	Returns the first node of the graph.
NodeIterator	chooseNode () const
	Returns the random node.
void	clear ()
	Clears the graph, removes all nodes and edges.
SizeType	degree (NodeIterator &u) const
	Returns the degree of a node (number of outgoing and incoming edges).
bool	edgeExists (const EdgeDescriptor &descriptor)
	Checks if an edge exists.
EdgeIterator	endEdges (const NodeIterator &u) const
	Returns the end to the container of the edges of a node.
InEdgeIterator	endInEdges (const NodeIterator &u) const
	Returns the end to the container of the incoming edge of a node.
NodeIterator	endNodes () const
	Returns the end to the container of the nodes.
void	eraseEdge (EdgeDescriptor descriptor)
	Erases an edge from the graph.
void	eraseNode (NodeDescriptor descriptor)
	Erases a node from the graph.
void	generateFrom (GraphGenerator< DynamicGraph > *generator)
	Populates the graph from a generator.
EdgeDescriptor	getEdgeDescriptor (const NodeDescriptor &uD, const NodeDescriptor &vD)
	Returns the descriptor of an edge (u,v).
EdgeDescriptor	getEdgeDescriptor (const NodeIterator &u, const NodeIterator &v)
	Returns the descriptor of an edge (u,v).
EdgeDescriptor	getEdgeDescriptor (const EdgeIterator &e)
	Returns the descriptor of an outgoing edge.
EdgeDescriptor	getEdgeDescriptor (const InEdgeIterator &k)
	Returns the descriptor of an incoming edge.
EdgeIterator	getEdgeIterator (const EdgeDescriptor &descriptor)
	Returns an iterator to an outgoing edge.
EdgeIterator	getEdgeIterator (const NodeIterator &u, const NodeIterator &v) const
	Returns an iterator to an outgoing edge.
EdgeIterator	getEdgeIterator (const InEdgeIterator &k) const
	Returns an iterator to an outgoing edge.
InEdgeIterator	getInEdgeIterator (const EdgeIterator &e) const
	Returns an iterator to an incoming edge.
NodeDescriptor	getNodeDescriptor (const NodeIterator &u)
	Returns the descriptor of a node.
NodeIterator	getNodeIterator (const NodeDescriptor &descriptor)
	Returns iterator to a node.
NodeIterator	getNodeIterator (const void *descriptor)
	Returns iterator to a node.
SizeType	getNumEdges () const
	Returns the number of edges in the graph.
SizeType	getNumNodes () const
	Returns the number of nodes in the graph.
SizeType	getRelativePosition (const NodeIterator &u) const
	Returns the relative position of a node as an id in the range [0, numNodes-1].
bool	hasEdge (const NodeDescriptor &uD, const NodeDescriptor &vD)
	Checks if an edge exists in the graph.
bool	hasEdge (const NodeIterator &u, const NodeIterator &v)
	Checks if an edge exists in the graph.
bool	hasEdges (const NodeIterator &u) const
	Checks if a node has outgoing edges.
bool	hasInEdges (const NodeIterator &u) const
	Checks if a node has incoming edges.
bool	hasNode (const NodeDescriptor &descriptor)
	Checks if a node exists in the graph.
bool	hasValidInEdges ()
	Checks if all outgoing edges are paired to an incoming edge each.
SizeType	indeg (NodeIterator &u) const
	Returns the in degree of a node (number of incoming edges).
EdgeDescriptor	insertEdge (const NodeDescriptor &uD, const NodeDescriptor &vD)
	Inserts an edge in the graph.
NodeDescriptor	insertNode ()
	Inserts a node in the graph.
SizeType	memUsage () const
	Returns the memory usage in bytes.
NodeDescriptor	nilNodeDescriptor () const
	Returns an empty node descriptor.
SizeType	outdeg (NodeIterator &u) const
	Returns the degree of a node (number of outgoing edges).
void	printInternalDot (const std::string &filename)
	Prints a dot representation of the graph to a file.
void	read (GraphReader< DynamicGraph > *reader)
	Populates the graph from a reader.
void	reserve (const SizeType &numNodes, const SizeType &numEdges)
	Reserves memory for the graph.
NodeIterator	source (EdgeIterator &e) const
	Returns the source node of an outgoing edge.
NodeIterator	source (InEdgeIterator &k) const
	Returns the source node of an incoming edge.
NodeIterator	target (EdgeIterator &e) const
	Returns the target node of an outgoingedge.
NodeIterator	target (InEdgeIterator &k) const
	Returns the target node of an incoming edge.
void	write (GraphWriter< DynamicGraph > *writer)
	Outputs the graph to a writer.

---

Detailed Description

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>
class DynamicGraph< GraphImplementation, Vtype, Etype >

A dynamic graph type.

Template Parameters:

	GraphImplementation	The underlying graph implementation to use. Available implementations are 'PackedMemoryArrayImpl' and 'AdjacencyListImpl'
	Vtype	The data to associate with the nodes. It must be a class or struct
	Etype	The data to associate with the edges. It must be a class or struct

Author:

Panos Michail

---

Member Function Documentation

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

EdgeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::beginEdges

(

const NodeIterator &

u

)

const [inline]

Returns the first outgoing edge of a node.

Parameters:

The

node

Returns:

An iterator to the first outgoing edge of a node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

InEdgeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::beginInEdges

(

const NodeIterator &

u

)

const [inline]

Returns the first incoming edge of a node.

Parameters:

The

node

Returns:

An iterator to the first incoming edge of a node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

NodeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::beginNodes

(

)

const [inline]

Returns the first node of the graph.

Returns:

An iterator to the first node of the graph

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

NodeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::chooseNode

(

)

const [inline]

Returns the random node.

Returns:

A random node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

SizeType DynamicGraph< GraphImplementation, Vtype, Etype >::degree

(

NodeIterator &

u

)

const [inline]

Returns the degree of a node (number of outgoing and incoming edges).

Parameters:

u

The node

Returns:

The degree of the node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

bool DynamicGraph< GraphImplementation, Vtype, Etype >::edgeExists

(

const EdgeDescriptor &

descriptor

)

[inline]

Checks if an edge exists.

Parameters:

e

The edge descriptor

Returns:

True if e exists in the graph, false otherwise

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

EdgeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::endEdges

(

const NodeIterator &

u

)

const [inline]

Returns the end to the container of the edges of a node.

Parameters:

u

The node

Returns:

An iterator to the past-the-end edge of the node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

InEdgeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::endInEdges

(

const NodeIterator &

u

)

const [inline]

Returns the end to the container of the incoming edge of a node.

Parameters:

u

The node

Returns:

An iterator to the past-the-end incoming edge of the node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

NodeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::endNodes

(

)

const [inline]

Returns the end to the container of the nodes.

Returns:

An iterator to the past-the-end node of the graph

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

void DynamicGraph< GraphImplementation, Vtype, Etype >::eraseEdge

(

EdgeDescriptor

descriptor

)

[inline]

Erases an edge from the graph.

Parameters:

descriptor

The descriptor of the edge to be erased

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

void DynamicGraph< GraphImplementation, Vtype, Etype >::eraseNode

(

NodeDescriptor

descriptor

)

[inline]

Erases a node from the graph.

Parameters:

descriptor

The descriptor of the node to be erased

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

void DynamicGraph< GraphImplementation, Vtype, Etype >::generateFrom

(

GraphGenerator< DynamicGraph< GraphImplementation, Vtype, Etype > > *

generator

)

[inline]

Populates the graph from a generator.

Parameters:

generator

A graph generator

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

EdgeDescriptor DynamicGraph< GraphImplementation, Vtype, Etype >::getEdgeDescriptor

(

const InEdgeIterator &

k

)

[inline]

Returns the descriptor of an incoming edge.

Parameters:

k

The incoming edge

Returns:

The descriptor of the edge

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

EdgeDescriptor DynamicGraph< GraphImplementation, Vtype, Etype >::getEdgeDescriptor

(

const EdgeIterator &

e

)

[inline]

Returns the descriptor of an outgoing edge.

Parameters:

e

The outgoing edge

Returns:

The descriptor of the edge

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

EdgeDescriptor DynamicGraph< GraphImplementation, Vtype, Etype >::getEdgeDescriptor	(	const NodeIterator &	u,
		const NodeIterator &	v
	)			[inline]

Returns the descriptor of an edge (u,v).

Parameters:

	u	The source node of the edge
	v	The target node of the edge

Returns:

The descriptor of the edge between u and v

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

EdgeDescriptor DynamicGraph< GraphImplementation, Vtype, Etype >::getEdgeDescriptor	(	const NodeDescriptor &	uD,
		const NodeDescriptor &	vD
	)			[inline]

Returns the descriptor of an edge (u,v).

Parameters:

	uD	The descritpor of the source node of the edge
	vD	The descritpor of the target node of the edge

Returns:

The descriptor of the edge between u and v

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

EdgeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::getEdgeIterator

(

const InEdgeIterator &

k

)

const [inline]

Returns an iterator to an outgoing edge.

Parameters:

e

An iterator to an incoming edge

Returns:

An iterator to the corresponding outgoing edge

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

EdgeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::getEdgeIterator	(	const NodeIterator &	u,
		const NodeIterator &	v
	)			const [inline]

Returns an iterator to an outgoing edge.

Parameters:

	u	The source node of the edge
	v	The target node of the edge

Returns:

An iterator to the outgoing edge

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

EdgeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::getEdgeIterator

(

const EdgeDescriptor &

descriptor

)

[inline]

Returns an iterator to an outgoing edge.

Parameters:

descriptor

The descriptor of the edge

Returns:

An iterator to the outgoing edge

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

InEdgeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::getInEdgeIterator

(

const EdgeIterator &

e

)

const [inline]

Returns an iterator to an incoming edge.

Parameters:

e

An iterator an outgoing edge

Returns:

An iterator to the corresponding incoming edge

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

NodeDescriptor DynamicGraph< GraphImplementation, Vtype, Etype >::getNodeDescriptor

(

const NodeIterator &

u

)

[inline]

Returns the descriptor of a node.

Parameters:

u

The node

Returns:

The descriptor of the node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

NodeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::getNodeIterator

(

const void *

descriptor

)

[inline]

Returns iterator to a node.

Parameters:

descriptor

The descriptor of the node as a memory address

Returns:

An iterator to the node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

NodeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::getNodeIterator

(

const NodeDescriptor &

descriptor

)

[inline]

Returns iterator to a node.

Parameters:

descriptor

The descriptor of the node

Returns:

An iterator to the node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

SizeType DynamicGraph< GraphImplementation, Vtype, Etype >::getNumEdges

(

)

const [inline]

Returns the number of edges in the graph.

Returns:

The number of edges in the graph

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

SizeType DynamicGraph< GraphImplementation, Vtype, Etype >::getNumNodes

(

)

const [inline]

Returns the number of nodes in the graph.

Returns:

The number of nodes in the graph

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

SizeType DynamicGraph< GraphImplementation, Vtype, Etype >::getRelativePosition

(

const NodeIterator &

u

)

const [inline]

Returns the relative position of a node as an id in the range [0, numNodes-1].

Returns:

The relative position of a node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

bool DynamicGraph< GraphImplementation, Vtype, Etype >::hasEdge	(	const NodeIterator &	u,
		const NodeIterator &	v
	)			[inline]

Checks if an edge exists in the graph.

Parameters:

	u	The source node
	v	The target node

Returns:

True if there exists and edge (u,v), false otherwise

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

bool DynamicGraph< GraphImplementation, Vtype, Etype >::hasEdge	(	const NodeDescriptor &	uD,
		const NodeDescriptor &	vD
	)			[inline]

Checks if an edge exists in the graph.

Parameters:

	uD	The source node descriptor
	vD	The target node descriptor

Returns:

True if there exists and edge (uD,vD), false otherwise

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

bool DynamicGraph< GraphImplementation, Vtype, Etype >::hasEdges

(

const NodeIterator &

u

)

const [inline]

Checks if a node has outgoing edges.

Parameters:

u

The node

Returns:

True if u has outgoing edges, false otherwise

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

bool DynamicGraph< GraphImplementation, Vtype, Etype >::hasInEdges

(

const NodeIterator &

u

)

const [inline]

Checks if a node has incoming edges.

Parameters:

u

The node

Returns:

True if u has incoming edges, false otherwise

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

bool DynamicGraph< GraphImplementation, Vtype, Etype >::hasNode

(

const NodeDescriptor &

descriptor

)

[inline]

Checks if a node exists in the graph.

Parameters:

descriptor

The node descriptor

Returns:

True if u exists in the graph, false otherwise

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

bool DynamicGraph< GraphImplementation, Vtype, Etype >::hasValidInEdges

(

)

[inline]

Checks if all outgoing edges are paired to an incoming edge each.

Returns:

True if all outgoing edges are paired to an incoming edge each, false otherwise

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

SizeType DynamicGraph< GraphImplementation, Vtype, Etype >::indeg

(

NodeIterator &

u

)

const [inline]

Returns the in degree of a node (number of incoming edges).

Parameters:

u

The node

Returns:

The in degree of the node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

EdgeDescriptor DynamicGraph< GraphImplementation, Vtype, Etype >::insertEdge	(	const NodeDescriptor &	uD,
		const NodeDescriptor &	vD
	)			[inline]

Inserts an edge in the graph.

Parameters:

	uD	The descriptor of the source node of the edge
	vD	The descriptor of the target node of the edge

Returns:

The descriptor of the new edge

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

NodeDescriptor DynamicGraph< GraphImplementation, Vtype, Etype >::insertNode

(

)

[inline]

Inserts a node in the graph.

Returns:

The descriptor of the new node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

SizeType DynamicGraph< GraphImplementation, Vtype, Etype >::memUsage

(

)

const [inline]

Returns the memory usage in bytes.

Returns:

The memory usage in bytes

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

NodeDescriptor DynamicGraph< GraphImplementation, Vtype, Etype >::nilNodeDescriptor

(

)

const [inline]

Returns an empty node descriptor.

Returns:

An empty node descriptor

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

SizeType DynamicGraph< GraphImplementation, Vtype, Etype >::outdeg

(

NodeIterator &

u

)

const [inline]

Returns the degree of a node (number of outgoing edges).

Parameters:

u

The node

Returns:

The out degree of the node

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

void DynamicGraph< GraphImplementation, Vtype, Etype >::printInternalDot

(

const std::string &

filename

)

[inline]

Prints a dot representation of the graph to a file.

Parameters:

filename

The output filename

Returns:

The target node of the edge

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

void DynamicGraph< GraphImplementation, Vtype, Etype >::read

(

GraphReader< DynamicGraph< GraphImplementation, Vtype, Etype > > *

reader

)

[inline]

Populates the graph from a reader.

Parameters:

reader

A graph reader

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

void DynamicGraph< GraphImplementation, Vtype, Etype >::reserve	(	const SizeType &	numNodes,
		const SizeType &	numEdges
	)			[inline]

Reserves memory for the graph.

Parameters:

	numNodes	The expected number of nodes
	numEdges	The expected number of edges

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

NodeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::source

(

InEdgeIterator &

k

)

const [inline]

Returns the source node of an incoming edge.

Parameters:

k

The incoming edge

Returns:

The source node of the edge

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

NodeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::source

(

EdgeIterator &

e

)

const [inline]

Returns the source node of an outgoing edge.

Parameters:

e

The outgoing edge

Returns:

The source node of the edge

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

NodeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::target

(

InEdgeIterator &

k

)

const [inline]

Returns the target node of an incoming edge.

Parameters:

k

The incoming edge

Returns:

The target node of the edge

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

NodeIterator DynamicGraph< GraphImplementation, Vtype, Etype >::target

(

EdgeIterator &

e

)

const [inline]

Returns the target node of an outgoingedge.

Parameters:

e

The outgoing edge

Returns:

The target node of the edge

template<template< typename vtype, typename etype > class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem>

void DynamicGraph< GraphImplementation, Vtype, Etype >::write

(

GraphWriter< DynamicGraph< GraphImplementation, Vtype, Etype > > *

writer

)

[inline]

Outputs the graph to a writer.

Parameters:

writer

A graph writer

---

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

• include/Structs/Graphs/dynamicGraph.h