tlp::VectorGraph Class Reference

That class provide a simple implementation of graph structure (without subgraphs, observer, metagraph) it enables to obtain very efficient access/modification time. More...

#include <vectorgraph.h>

List of all members.

Classes

• struct _iEdges
• struct _iNodes

Public Member Functions

• VectorGraph ()
• ~VectorGraph ()
• void clear ()

  delete all nodes/edges and Properties of the graph o(N + E + NbProp)
  

• edge existEdge (const node src, const node tgt, const bool directed=true) const

  Test if an edge exist between two nodes, in directed mode the orientation is taken into account.
  

• bool isElement (const node n) const

  Return true if n belongs to the graph o(1).
  

• bool isElement (const edge e) const

  Return true if e belongs to the graph o(1).
  

• void setEdgeOrder (const node n, const std::vector< edge > &v)

  Set the ordering of edges around n according to their order in v.
  

• void swapEdgeOrder (const node n, const edge e1, const edge e2)

  swap to edge in the ordered adjacency vector
  

• void reserveNodes (const size_t nbNodes)

  Enables to reserve memory for nbNodes Reserving memory before to addNode enable to reduce the number of vector resizing and then to speed up significantly construction of graphs. o(N + nbNodes).
  

• void reserveEdges (const size_t nbEdges)

  Enables to reserve memory for nbEdges Reserving memory before to addEdge enable to reduce the number of vector resizing and then to speed up significantly construction of graphs. o(N + nbNodes).
  

• void reserveAdj (const size_t nbEdges)

  Enables to reserve memory for adjacency nodes Reserving memory before to addEdge enable to reduce the number of vector resizing and then to speed up significantly construction of graphs. o(E + nbEdges).
  

• void reserveAdj (const node n, const size_t nbEdges)

  Enables to reserve memory for adjacency nodes Reserving memory before to addEdge enable to reduce the number of vector resizing and then to speed up significantly construction of graphs. o(E + nbEdges).
  

• node operator[] (const unsigned int id) const

  Return the node at position id in the array of nodes o(1).
  

• edge operator() (const unsigned int id) const

  Return the edge at position id in the array of nodes o(1).
  

• node getOneNode () const

  Return the first node of graph (ie first node in the array of nodes) o(1).
  

• Iterator< node > * getNodes () const

  Return a Tulip Iterator on nodes of the graph.
  

• Iterator< edge > * getEdges () const

  Return a Tulip Iterator on edges of the graph.
  

• Iterator< edge > * getInOutEdges (const node n) const

  Return a Tulip Iterator on adjacent edges of the node n.
  

• Iterator< edge > * getOutEdges (const node n) const

  Return a Tulip Iterator on out edges of the node n.
  

• Iterator< edge > * getInEdges (const node n) const

  Return a Tulip Iterator on in edges of the node n.
  

• Iterator< node > * getInOutNodes (const node n) const

  Return a Tulip Iterator on adjacent nodes of the node n.
  

• Iterator< node > * getInNodes (const node n) const

  Return a Tulip Iterator on in nodes of the node n.
  

• Iterator< node > * getOutNodes (const node n) const

  Return a Tulip Iterator on out nodes of the node n.
  

• unsigned int deg (const node n) const

  Return the degree of a node o(1).
  

• unsigned int outdeg (const node n) const

  Return the out degree of a node o(1).
  

• unsigned int indeg (const node n) const

  Return the in degree of a node o(1).
  

• unsigned int numberOfEdges () const

  Return the number of edges in the graph : o(1).
  

• unsigned int numberOfNodes () const

  Return the number of nodes in the graph : o(1).
  

• node addNode ()

  Add a new node in the graph and return it.
  

• void delNode (const node n)

  Delete a node and all its adjacent edges in the graph.
  

• edge addEdge (const node src, const node tgt)

  Add a new edge between src and tgt and return it.
  

• void delEdge (const edge e)

  Delete an edge in the graph.
  

• void delEdges (const node n)

  Delete all adjacent edges (in/out) of a node.
  

• void delAllEdges ()

  Delete all edges in the graph.
  

• void delAllNodes ()

  Delete all nodes in the graph.
  

• node source (const edge e) const

  return the first extremity (considered as source if the graph is directed) of an edge o(1)
  

• node target (const edge e) const

  return the second extremity (considered as target if the graph is directed) of an edge o(1)
  

• node opposite (const edge e, const node n) const

  return the opposite node of n through edge e o(1)
  

• void reverse (const edge e)

  Reverse an edge e, source become target and target become soure o(1).
  

• void setSource (const edge e, const node n)

  change the source of an edge
  

• void setTarget (const edge e, const node n)

  change the target of an edge
  

• std::pair< node, node > ends (const edge e) const

  Return the extremities of an edge (src, target) o(1).
  

• void setEnds (const edge e, const node src, const node tgt)

  Reconnect the edeg e to have the new given extremities.
  

• void shuffleNodes ()

  Shuffle the array of graph nodes dependant of stl::random_shuffle algorithm (should be o(N)).
  

• void shuffleEdges ()

  Shuffle the array of graph edges dependant of stl::random_shuffle algorithm (should be o(E)).
  

• template<typename Compare > void sortEdges (Compare cmp, bool stable=false)

  Sort all edges according to comparison functor given in parameter if stable is true a stable sort algorithm is applied Comparison should be an instance of a class wihch implements operator(): dependant of stl::sort and stl::stable_sort algorithm (should be o(E log (E))).
  

• template<typename Compare > void sortNodes (Compare cmp, bool stable=false)

  Sort all nodes according to comparison functor given in parameter if stable is true a stable sort algorithm is applied Comparison should be an instance of a class wihch implements operator():.
  

• unsigned int edgePos (const edge e) const

  return the position of an edge in the array of edges.
  

• unsigned int nodePos (const node n) const

  return the position of a node in the array of nodes.
  

• void swap (const node a, const node b)

  Swap two nodes in the array of graph nodes o(1).
  

• void swap (const edge a, const edge b)

  Swap two edges in the array of graph edge o(1).
  

• template<typename TYPE > void alloc (NodeProperty< TYPE > &prop)

  Create a new node array of type TYPE NodesAttr can be copied in constant time it is just a pointer NodesAttr is not a smart pointer it must be deleted with freeNodesAttribute o(log(number of arrays) + new of a vector<TYPE> of size N).
  

• template<typename TYPE > void free (NodeProperty< TYPE > array)

  Delete an Array from the set of node arrays.
  

• template<typename TYPE > void alloc (EdgeProperty< TYPE > &prop)

  Create a new edge array of type TYPE EdgesAttr can be copied in constant time it is just a pointer EdgesAttr is not a smart pointer it must be deleted with freeEdgesAttribute o(log(number of node arrays) + new of a vector<TYPE> of size E).
  

• template<typename TYPE > void free (EdgeProperty< TYPE > array)

  Delete an Array from the set of edge arrays.
  

• const std::vector< node > & adj (const node n) const

  Return a const reference on the vector of adjacent nodes of n.
  

• const std::vector< edge > & star (const node n) const

  Return a const reference on the vector of adjacent edges of n.
  

• const std::vector< node > & nodes () const

  Return a const reference on the vector of nodes of the graph It is the fastest way to access to edge adjacency, Iterators are 25% slower.
  

• const std::vector< edge > & edges () const

  Return a const reference on the vector of edges of the graph It is the fastest way to access to edge adjacency, Iterators are 25% slower.
  

• template<typename TYPE > bool isNodeAttr (ValArray< TYPE > *array)
• template<typename TYPE > bool isEdgeAttr (ValArray< TYPE > *array)
• void dump () const
• void integrityTest ()

---

Detailed Description

That class provide a simple implementation of graph structure (without subgraphs, observer, metagraph) it enables to obtain very efficient access/modification time.

User can both use tulip iterators or direct vector to access to the graph structure for better performance. To have maximum speedup, that Graph implementation use only vectors, almost all operations are done in constant time (even modification), however since the class use vectors, modification of adjacency can change the ordering of edges around nodes. If you use it only for standard graph operations there is no problem. However if you want to manipulate maps, be aware that a modification can change the graph embedding. EdgeOrdering function can be used to reorder correctly elements when necessary.

Warning:

the class is not thread safe

modification of the graph structure devalidate iterations.

Use that class only if you need performance.

Todo:

split the file in .h .cpp

---

Constructor & Destructor Documentation

tlp::VectorGraph::VectorGraph

(

)

tlp::VectorGraph::~VectorGraph

(

)

---

Member Function Documentation

edge tlp::VectorGraph::addEdge	(	const node	src,
		const node	tgt
	)

Add a new edge between src and tgt and return it.

Warning:

That operation modify the array of neighboors of extrmities of edges, thus it devalidates iterators on adjacency for the nodes at the extremities od the deleted edges. o(1)

node tlp::VectorGraph::addNode

(

)

Add a new node in the graph and return it.

Warning:

: That operation modify the array of nodes and thus devalidate all iterators on it. : o(1)

const std::vector<node>& tlp::VectorGraph::adj

(

const node

n

)

const

Return a const reference on the vector of adjacent nodes of n.

It is the fastest way to access to node adjacency, Iterators are 25% slower.

Warning:

code that use that function won't be compatible with Tulip Graph API

o(1)

See also:

getInOutNodes

getInNodes

getOutNodes

template<typename TYPE >

void tlp::VectorGraph::alloc

(

EdgeProperty< TYPE > &

prop

)

[inline]

Create a new edge array of type TYPE EdgesAttr can be copied in constant time it is just a pointer EdgesAttr is not a smart pointer it must be deleted with freeEdgesAttribute o(log(number of node arrays) + new of a vector<TYPE> of size E).

Warning:

that function is not compatible with the Tulip Graph API

template<typename TYPE >

void tlp::VectorGraph::alloc

(

NodeProperty< TYPE > &

prop

)

[inline]

Create a new node array of type TYPE NodesAttr can be copied in constant time it is just a pointer NodesAttr is not a smart pointer it must be deleted with freeNodesAttribute o(log(number of arrays) + new of a vector<TYPE> of size N).

Warning:

that function is not compatible with the Tulip Graph API

void tlp::VectorGraph::clear

(

)

delete all nodes/edges and Properties of the graph o(N + E + NbProp)

unsigned int tlp::VectorGraph::deg

(

const node

n

)

const

Return the degree of a node o(1).

void tlp::VectorGraph::delAllEdges

(

)

Delete all edges in the graph.

Warning:

: That operation modify the array of edges and all arrays of nodes and thus devalidate all iterators, only graph nodes iterators are not affected. o(E + V)

void tlp::VectorGraph::delAllNodes

(

)

Delete all nodes in the graph.

Warning:

: That operation modify the array of edges and all arrays of nodes and thus devalidate all iterators. o(E + V)

void tlp::VectorGraph::delEdge

(

const edge

e

)

Delete an edge in the graph.

Warning:

: That operation modify the array of edges and thus devalidate all iterators on it.

That operation modify the array of neighboors of extremities of the edge e, thus it devalidates iterators on adjacency for the nodes at the extremities od the deleted edge.

Orders of edges in the extremities of the deleted edge are affected o(1)

void tlp::VectorGraph::delEdges

(

const node

n

)

Delete all adjacent edges (in/out) of a node.

Warning:

: That operation modify the array of edges and thus devalidate all iterators on it.

That operation modify the array of neighboors of extremities of the edge e, thus it devalidates iterators on adjacency for the nodes at the extremities od the deleted edge.

Orders of edges in the extremities of the deleted edge are affected o(deg(V))

Todo:

test

void tlp::VectorGraph::delNode

(

const node

n

)

Delete a node and all its adjacent edges in the graph.

Warning:

That operation modify the array of nodes and the array of edges and thus devalidate all iterators on it.

That operation modify the array of neighboors of extrmities of edges, thus it devalidates iterators on adjacency for the nodes at the extremities od the deleted edges.

Orders of edges in the extremities of the deleted edges are affected : o(1)

void tlp::VectorGraph::dump

(

)

const

output the graph in a very simple way for debugging

unsigned int tlp::VectorGraph::edgePos

(

const edge

e

)

const

return the position of an edge in the array of edges.

Warning:

that function is not compatible with the Tulip Graph API o(1)

const std::vector<edge>& tlp::VectorGraph::edges

(

)

const

Return a const reference on the vector of edges of the graph It is the fastest way to access to edge adjacency, Iterators are 25% slower.

Warning:

code that use that function won't be compatible with Tulip Graph API o(1)

std::pair<node, node> tlp::VectorGraph::ends

(

const edge

e

)

const

Return the extremities of an edge (src, target) o(1).

edge tlp::VectorGraph::existEdge	(	const node	src,
		const node	tgt,
		const bool	directed = true
	)			const

Test if an edge exist between two nodes, in directed mode the orientation is taken into account.

Returns:

the found edge, else an invalid edge. o(min(deg(src), deg(tgt))

Todo:

test

template<typename TYPE >

void tlp::VectorGraph::free

(

EdgeProperty< TYPE >

array

)

[inline]

Delete an Array from the set of edge arrays.

Warning:

all copy of the ValArray are no more valid (serious bug if they are used after) o(log(number of edge arrays) + free of a vector<TYPE> of size E)

that function is not compatible with the Tulip Graph API

template<typename TYPE >

void tlp::VectorGraph::free

(

NodeProperty< TYPE >

array

)

[inline]

Delete an Array from the set of node arrays.

Warning:

all copy of the ValArray are no more valid (serious bug if they are used after) o(log(number of arrays) + free of a vector<TYPE> of size N)

that function is not compatible with the Tulip Graph API

Iterator<edge>* tlp::VectorGraph::getEdges

(

)

const

Return a Tulip Iterator on edges of the graph.

Warning:

: The returned iterator should be deleted by the caller to prevent memory leaks : o(1)

Iterator<edge>* tlp::VectorGraph::getInEdges

(

const node

n

)

const

Return a Tulip Iterator on in edges of the node n.

Warning:

: The returned iterator should be deleted by the caller to prevent memory leaks : o(1)

Iterator<node>* tlp::VectorGraph::getInNodes

(

const node

n

)

const

Return a Tulip Iterator on in nodes of the node n.

Warning:

: The returned iterator should be deleted by the caller to prevent memory leaks o(1)

Iterator<edge>* tlp::VectorGraph::getInOutEdges

(

const node

n

)

const

Return a Tulip Iterator on adjacent edges of the node n.

Warning:

: The returned iterator should be deleted by the caller to prevent memory leaks : o(1)

Iterator<node>* tlp::VectorGraph::getInOutNodes

(

const node

n

)

const

Return a Tulip Iterator on adjacent nodes of the node n.

Warning:

: The returned iterator should be deleted by the caller to prevent memory leaks : o(1)

Iterator<node>* tlp::VectorGraph::getNodes

(

)

const

Return a Tulip Iterator on nodes of the graph.

Warning:

: The returned iterator should be deleted by the caller to prevent memory leaks : o(1)

node tlp::VectorGraph::getOneNode

(

)

const

Return the first node of graph (ie first node in the array of nodes) o(1).

Iterator<edge>* tlp::VectorGraph::getOutEdges

(

const node

n

)

const

Return a Tulip Iterator on out edges of the node n.

Warning:

: The returned iterator should be deleted by the caller to prevent memory leaks : o(1)

Iterator<node>* tlp::VectorGraph::getOutNodes

(

const node

n

)

const

Return a Tulip Iterator on out nodes of the node n.

Warning:

: The returned iterator should be deleted by the caller to prevent memory leaks o(1)

unsigned int tlp::VectorGraph::indeg

(

const node

n

)

const

Return the in degree of a node o(1).

void tlp::VectorGraph::integrityTest

(

)

internal function to test the integrity of the graph

template<typename TYPE >

bool tlp::VectorGraph::isEdgeAttr

(

ValArray< TYPE > *

array

)

[inline]

bool tlp::VectorGraph::isElement

(

const edge

e

)

const

Return true if e belongs to the graph o(1).

bool tlp::VectorGraph::isElement

(

const node

n

)

const

Return true if n belongs to the graph o(1).

template<typename TYPE >

bool tlp::VectorGraph::isNodeAttr

(

ValArray< TYPE > *

array

)

[inline]

these two function are used internally to insure that property has been allocated in debug mode

Warning:

never used these function directly even in debug mode !!!

unsigned int tlp::VectorGraph::nodePos

(

const node

n

)

const

return the position of a node in the array of nodes.

Warning:

that function is not compatible with the Tulip Graph API o(1)

const std::vector<node>& tlp::VectorGraph::nodes

(

)

const

Return a const reference on the vector of nodes of the graph It is the fastest way to access to edge adjacency, Iterators are 25% slower.

Warning:

code that use that function won't be compatible with Tulip Graph API o(1)

unsigned int tlp::VectorGraph::numberOfEdges

(

)

const

Return the number of edges in the graph : o(1).

unsigned int tlp::VectorGraph::numberOfNodes

(

)

const

Return the number of nodes in the graph : o(1).

edge tlp::VectorGraph::operator()

(

const unsigned int

id

)

const

Return the edge at position id in the array of nodes o(1).

node tlp::VectorGraph::operator[]

(

const unsigned int

id

)

const

Return the node at position id in the array of nodes o(1).

node tlp::VectorGraph::opposite	(	const edge	e,
		const node	n
	)			const

return the opposite node of n through edge e o(1)

unsigned int tlp::VectorGraph::outdeg

(

const node

n

)

const

Return the out degree of a node o(1).

void tlp::VectorGraph::reserveAdj	(	const node	n,
		const size_t	nbEdges
	)

Enables to reserve memory for adjacency nodes Reserving memory before to addEdge enable to reduce the number of vector resizing and then to speed up significantly construction of graphs. o(E + nbEdges).

void tlp::VectorGraph::reserveAdj

(

const size_t

nbEdges

)

Enables to reserve memory for adjacency nodes Reserving memory before to addEdge enable to reduce the number of vector resizing and then to speed up significantly construction of graphs. o(E + nbEdges).

void tlp::VectorGraph::reserveEdges

(

const size_t

nbEdges

)

Enables to reserve memory for nbEdges Reserving memory before to addEdge enable to reduce the number of vector resizing and then to speed up significantly construction of graphs. o(N + nbNodes).

void tlp::VectorGraph::reserveNodes

(

const size_t

nbNodes

)

Enables to reserve memory for nbNodes Reserving memory before to addNode enable to reduce the number of vector resizing and then to speed up significantly construction of graphs. o(N + nbNodes).

void tlp::VectorGraph::reverse

(

const edge

e

)

Reverse an edge e, source become target and target become soure o(1).

void tlp::VectorGraph::setEdgeOrder	(	const node	n,
		const std::vector< edge > &	v
	)

Set the ordering of edges around n according to their order in v.

Warning:

there is no test here, all edge in v must be element of star(e) o(v.size())

void tlp::VectorGraph::setEnds	(	const edge	e,
		const node	src,
		const node	tgt
	)

Reconnect the edeg e to have the new given extremities.

Warning:

That operation modify the array of neighboors of extrmities of edges, thus it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes. o(1)

void tlp::VectorGraph::setSource	(	const edge	e,
		const node	n
	)

change the source of an edge

Warning:

That operation modify the array of neighboors of extrmities of edges, thus it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes. o(1)

See also:

setEnds

void tlp::VectorGraph::setTarget	(	const edge	e,
		const node	n
	)

change the target of an edge

Warning:

That operation modify the array of neighboors of extrmities of edges, thus it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes. o(1)

See also:

setEnds

void tlp::VectorGraph::shuffleEdges

(

)

Shuffle the array of graph edges dependant of stl::random_shuffle algorithm (should be o(E)).

void tlp::VectorGraph::shuffleNodes

(

)

Shuffle the array of graph nodes dependant of stl::random_shuffle algorithm (should be o(N)).

template<typename Compare >

void tlp::VectorGraph::sortEdges	(	Compare	cmp,
		bool	stable = false
	)			[inline]

Sort all edges according to comparison functor given in parameter if stable is true a stable sort algorithm is applied Comparison should be an instance of a class wihch implements operator(): dependant of stl::sort and stl::stable_sort algorithm (should be o(E log (E))).

  class Compare {
  //return true if a < b
  bool operator()(const edge a, const edge b);
  };

Warning:

that function is not compatible with the Tulip Graph API

template<typename Compare >

void tlp::VectorGraph::sortNodes	(	Compare	cmp,
		bool	stable = false
	)			[inline]

Sort all nodes according to comparison functor given in parameter if stable is true a stable sort algorithm is applied Comparison should be an instance of a class wihch implements operator():.

  class Compare {
  //return true if a < b
  bool operator()(const node a, const node b);
  };

dependant of stl::sort and stl::stable_sort algorithm (should be o(N log (N)))

Warning:

that function is not compatible with the Tulip Graph API

node tlp::VectorGraph::source

(

const edge

e

)

const

return the first extremity (considered as source if the graph is directed) of an edge o(1)

const std::vector<edge>& tlp::VectorGraph::star

(

const node

n

)

const

Return a const reference on the vector of adjacent edges of n.

It is the fastest way to access to edge adjacency, Iterators are 25% slower.

Warning:

code that use that function won't be compatible with Tulip Graph API

o(1)

See also:

getInOutEdges

getInEdges

getOutEdges

void tlp::VectorGraph::swap	(	const edge	a,
		const edge	b
	)

Swap two edges in the array of graph edge o(1).

Warning:

that function is not compatible with the Tulip Graph API

void tlp::VectorGraph::swap	(	const node	a,
		const node	b
	)

Swap two nodes in the array of graph nodes o(1).

Warning:

that function is not compatible with the Tulip Graph API

void tlp::VectorGraph::swapEdgeOrder	(	const node	n,
		const edge	e1,
		const edge	e2
	)

swap to edge in the ordered adjacency vector

Warning:

the two edges must be element of star(v) o(1)

node tlp::VectorGraph::target

(

const edge

e

)

const

return the second extremity (considered as target if the graph is directed) of an edge o(1)