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 
( 
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
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
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 
( 
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
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
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)
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)
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)
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)
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)
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)
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)
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 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 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::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 {
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 {
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)
