tlp::GraphStorage Class Reference

That class provide a simple implementation for the storage of graph elts (nodes edges) More...

#include <GraphStorage.h>

List of all members.

Classes

• struct EdgeContainer

Public Member Functions

• void clear ()
• GraphStorage ()
• ~GraphStorage ()
• bool isElement (const node n) const

  Return true if n belongs to the graph.
  

• bool isElement (const edge e) const

  Return true if e belongs to the graph.
  

• void reserveNodes (size_t nb)

  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.
  

• void reserveEdges (size_t nb)

  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.
  

• void reserveAdj (node n, size_t nb)

  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.
  

• void reserveAdj (size_t nb)

  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.
  

• void restoreAdj (node n, const std::vector< edge > &edges)

  restore adjacency edges of a given node
  

• node getOneNode () const

  Return the first node of graph.
  

• Iterator< node > * getNodes () const

  Return a Tulip Iterator on nodes of the graph.
  

• const GraphStorageIdsMemento * getIdsMemento ()

  Return the current state of the ids management must be deleted by the caller this can be used for push/pop.
  

• void restoreIdsMemento (const GraphStorageIdsMemento *)

  restore a state of the ids management
  

• Iterator< edge > * getEdges () const

  Return a Tulip Iterator on edges of the graph.
  

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

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

• void getInOutEdges (node n, std::vector< edge > &edges, bool loopsOnlyOnce=false) const

  get adjacency edges of a given node
  

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

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

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

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

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

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

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

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

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

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

• unsigned int deg (node n) const

  Return the degree of a node.
  

• unsigned int outdeg (node n) const

  Return the out degree of a node.
  

• unsigned int indeg (node n) const

  Return the in degree of a node.
  

• unsigned int numberOfEdges () const

  Return the number of edges in the graph.
  

• unsigned int numberOfNodes () const

  Return the number of nodes in the graph.
  

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

  Return the extremities of an edge (src, target)
  

• node source (edge e) const

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

• node target (edge e) const

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

• node opposite (edge e, node n) const

  return the opposite node of n through edge e
  

• void setEnds (const edge e, const node newSrc, const node newTgt)

  Reconnect the edge e to have the new given ends.
  

• 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
  

• void reverse (const edge e)

  Reverse an edge e, source become target and target become soure.
  

• 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
  

• node addNode (node n)

  Add the given node in the structure and return it.
  

• node addNode ()

  Add a new node in the structure and return it.
  

• void addNodes (unsigned int nb, std::vector< node > &addedNodes)

  Add nb new nodes in the structure and returns them in the addedNodes vector.
  

• void restoreNodes (const std::vector< node > &addedNodes)

  Add the given nodes in the structure.
  

• void removeFromNodes (const node n)

  remove a node from the nodes structure only
  

• void delNode (node n)

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

• edge addEdge (const node src, const node tgt, const edge e, bool updateEndsEdges)

  Add the given edge between src and tgt and return it the last argument indicates if the edge has to be added in the adjacency edges of its two ends.
  

• edge addEdge (node src, node tgt)

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

• void addEdges (const std::vector< std::pair< node, node > > &edges, std::vector< edge > &addedEdges)

  Add edges in the structure and returns them in the addedEdges vector.
  

• void restoreEdges (const std::vector< edge > &edgesToRestore, const std::vector< std::pair< node, node > > &ends)

  restore edges in the structure and returns them in the addedEdges vector
  

• void delEdge (edge e)

  Delete an edge in the graph.
  

• void delAllEdges ()

  Delete all edges in the graph.
  

• void delAllNodes ()

  Delete all nodes in the graph.
  

---

Detailed Description

That class provide a simple implementation for the storage of graph elts (nodes edges)

---

Constructor & Destructor Documentation

tlp::GraphStorage::GraphStorage

(

)

tlp::GraphStorage::~GraphStorage

(

)

---

Member Function Documentation

edge tlp::GraphStorage::addEdge	(	const node	src,
		const node	tgt,
		const edge	e,
		bool	updateEndsEdges
	)

Add the given edge between src and tgt and return it the last argument indicates if the edge has to be added in the adjacency edges of its two ends.

Warning:

That operation modify the array of edges and the adjacency edges of its ends thus any iterators existing for these structures will be devalidated.

edge tlp::GraphStorage::addEdge	(	node	src,
		node	tgt
	)

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

Warning:

That operation modify the array of edges and the adjacency edges of its ends thus any iterators existing for these structures will be devalidated.

void tlp::GraphStorage::addEdges	(	const std::vector< std::pair< node, node > > &	edges,
		std::vector< edge > &	addedEdges
	)

Add edges in the structure and returns them in the addedEdges vector.

Warning:

: That operation modify the array of edges and the adjacency edges of its ends thus any iterators existing for these structures will be devalidated.

node tlp::GraphStorage::addNode

(

)

Add a new node in the structure and return it.

Warning:

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

node tlp::GraphStorage::addNode

(

node

n

)

Add the given node in the structure and return it.

Warning:

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

void tlp::GraphStorage::addNodes	(	unsigned int	nb,
		std::vector< node > &	addedNodes
	)

Add nb new nodes in the structure and returns them in the addedNodes vector.

Warning:

: That operation modify the array of nodes and thus devalidate all iterators on it. The addedNodes vector is cleared before adding nodes : o(1)

void tlp::GraphStorage::clear

(

)

unsigned int tlp::GraphStorage::deg

(

node

n

)

const

Return the degree of a node.

void tlp::GraphStorage::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.

void tlp::GraphStorage::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.

void tlp::GraphStorage::delEdge

(

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

void tlp::GraphStorage::delNode

(

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)

const std::pair<node, node>& tlp::GraphStorage::ends

(

const edge

e

)

const

Return the extremities of an edge (src, target)

Iterator<edge>* tlp::GraphStorage::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

const GraphStorageIdsMemento* tlp::GraphStorage::getIdsMemento

(

)

Return the current state of the ids management must be deleted by the caller this can be used for push/pop.

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

(

node

n

)

const

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

Warning:

: The returned iterator must be deleted by the caller to prevent memory leaks

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

(

node

n

)

const

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

Warning:

: The returned iterator must be deleted by the caller to prevent memory leaks

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

(

node

n

)

const

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

Warning:

: be careful that loops appear twice

: The returned iterator should be deleted by the caller to prevent memory leaks

void tlp::GraphStorage::getInOutEdges	(	node	n,
		std::vector< edge > &	edges,
		bool	loopsOnlyOnce = false
	)		const

get adjacency edges of a given node

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

(

node

n

)

const

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

Warning:

: The returned iterator must be deleted by the caller to prevent memory leaks

Iterator<node>* tlp::GraphStorage::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::GraphStorage::getOneNode

(

)

const

Return the first node of graph.

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

(

node

n

)

const

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

Warning:

: The returned iterator must be deleted by the caller to prevent memory leaks

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

(

node

n

)

const

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

Warning:

: The returned iterator must be deleted by the caller to prevent memory leaks

unsigned int tlp::GraphStorage::indeg

(

node

n

)

const

Return the in degree of a node.

bool tlp::GraphStorage::isElement

(

const node

n

)

const

Return true if n belongs to the graph.

bool tlp::GraphStorage::isElement

(

const edge

e

)

const

Return true if e belongs to the graph.

unsigned int tlp::GraphStorage::numberOfEdges

(

)

const

Return the number of edges in the graph.

unsigned int tlp::GraphStorage::numberOfNodes

(

)

const

Return the number of nodes in the graph.

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

return the opposite node of n through edge e

unsigned int tlp::GraphStorage::outdeg

(

node

n

)

const

Return the out degree of a node.

void tlp::GraphStorage::removeFromNodes

(

const node

n

)

remove a node from the nodes structure only

Warning:

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

void tlp::GraphStorage::reserveAdj	(	node	n,
		size_t	nb
	)

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.

void tlp::GraphStorage::reserveAdj

(

size_t

nb

)

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.

void tlp::GraphStorage::reserveEdges

(

size_t

nb

)

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.

void tlp::GraphStorage::reserveNodes

(

size_t

nb

)

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.

void tlp::GraphStorage::restoreAdj	(	node	n,
		const std::vector< edge > &	edges
	)

restore adjacency edges of a given node

void tlp::GraphStorage::restoreEdges	(	const std::vector< edge > &	edgesToRestore,
		const std::vector< std::pair< node, node > > &	ends
	)

restore edges in the structure and returns them in the addedEdges vector

Warning:

: That operation modify the array of edges thus any iterators existing for these structures will be devalidated.

void tlp::GraphStorage::restoreIdsMemento

(

const GraphStorageIdsMemento *

)

restore a state of the ids management

void tlp::GraphStorage::restoreNodes

(

const std::vector< node > &

addedNodes

)

Add the given nodes in the structure.

Warning:

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

void tlp::GraphStorage::reverse

(

const edge

e

)

Reverse an edge e, source become target and target become soure.

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

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

void tlp::GraphStorage::setEnds	(	const edge	e,
		const node	newSrc,
		const node	newTgt
	)

Reconnect the edge e to have the new given ends.

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.

void tlp::GraphStorage::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.

See also:

setEnds

void tlp::GraphStorage::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.

See also:

setEnds

node tlp::GraphStorage::source

(

edge

e

)

const

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

void tlp::GraphStorage::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)

node tlp::GraphStorage::target

(

edge

e

)

const

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