That class provide a simple implementation for the storage of graph elts (nodes edges)
More...
#include <GraphStorage.h>
List of all members.
Classes
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.
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)
Return a Tulip Iterator on edges of the graph.
 Warning:
 : The returned iterator should be deleted by the caller to prevent memory leaks
Return the current state of the ids management must be deleted by the caller this can be used for push/pop.
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
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
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
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
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.
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
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.
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.
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
