29 #include <tulip/tulipconf.h>
30 #include <tulip/Node.h>
31 #include <tulip/Edge.h>
32 #include <tulip/IdManager.h>
33 #include <tulip/vectorgraphproperty.h>
37 template <
class itType>
63 class TLP_SCOPE VectorGraph {
71 adjData(
bool t =
false, node n = node(0), edge e = edge(0)) : _out(t), _e(e.id), _n(n) {}
78 node opposite()
const {
101 edge existEdge(node src, node tgt,
bool directed =
true)
const;
107 bool isElement(
const node n)
const {
108 assert(n.id < _nData.size());
109 return _nodes.isElement(n);
116 bool isElement(
const edge e)
const {
117 assert(e.id < _eData.size());
118 return _edges.isElement(e);
126 void setEdgeOrder(
const node n,
const std::vector<edge> &v);
133 void swapEdgeOrder(
const node n,
const edge e1,
const edge e2);
141 void reserveNodes(
const size_t nbNodes);
149 void reserveEdges(
const size_t nbEdges);
157 void reserveAdj(
const size_t nbEdges);
165 void reserveAdj(
const node n,
const size_t nbEdges);
171 node operator[](
const unsigned int id)
const {
172 assert(
id < _nodes.size());
180 edge operator()(
const unsigned int id)
const {
181 assert(
id < _edges.size());
189 node getOneNode()
const {
199 Iterator<node> *getNodes()
const;
206 Iterator<edge> *getEdges()
const;
213 Iterator<edge> *getInOutEdges(
const node n)
const;
220 Iterator<edge> *getOutEdges(
const node n)
const;
227 Iterator<edge> *getInEdges(
const node n)
const;
234 Iterator<node> *getInOutNodes(
const node n)
const;
242 Iterator<node> *getInNodes(
const node n)
const;
249 Iterator<node> *getOutNodes(
const node n)
const;
255 unsigned int deg(
const node n)
const {
256 assert(isElement(n));
257 return _nData[n]._adj.size();
264 unsigned int outdeg(
const node n)
const {
265 assert(isElement(n));
266 return _nData[n]._outdeg;
273 unsigned int indeg(
const node n)
const {
274 return deg(n) - _nData[n]._outdeg;
281 unsigned int numberOfEdges()
const {
282 return _edges.size();
289 unsigned int numberOfNodes()
const {
290 return _nodes.size();
297 bool isEmpty()
const {
298 return _nodes.empty();
317 void addNodes(
unsigned int nb, std::vector<node> *addedNodes =
nullptr);
329 void delNode(
const node n);
338 edge addEdge(
const node src,
const node tgt);
347 void addEdges(
const std::vector<std::pair<node, node>> &edges,
348 std::vector<edge> *addedEdges =
nullptr);
360 void delEdge(
const edge e);
373 void delEdges(
const node n);
395 node source(
const edge e)
const {
396 assert(isElement(e));
397 return _eData[e]._ends.first;
405 node target(
const edge e)
const {
406 assert(isElement(e));
407 return _eData[e]._ends.second;
414 node opposite(
const edge e,
const node n)
const;
420 void reverse(
const edge e);
430 void setSource(
const edge e,
const node n) {
431 assert(isElement(e));
432 assert(isElement(n));
433 setEnds(e, n, target(e));
444 void setTarget(
const edge e,
const node n) {
445 assert(isElement(e));
446 assert(isElement(n));
447 setEnds(e, source(e), n);
454 const std::pair<node, node> &ends(
const edge e)
const {
455 assert(isElement(e));
456 return _eData[e]._ends;
466 void setEnds(
const edge e,
const node src,
const node tgt);
493 template <
typename Compare>
494 void sortEdges(Compare cmp,
bool stable =
false) {
496 stable_sort(_edges.begin(), _edges.end(), cmp);
498 sort(_edges.begin(), _edges.end(), cmp);
517 template <
typename Compare>
518 void sortNodes(Compare cmp,
bool stable =
false) {
520 stable_sort(_nodes.begin(), _nodes.end(), cmp);
522 sort(_nodes.begin(), _nodes.end(), cmp);
533 unsigned int edgePos(
const edge e)
const {
534 assert(isElement(e));
535 return _edges.getPos(e);
543 unsigned int nodePos(
const node n)
const {
544 assert(isElement(n));
545 return _nodes.getPos(n);
553 void swap(
const node a,
const node b);
560 void swap(
const edge a,
const edge b);
569 template <
typename TYPE>
570 void alloc(NodeProperty<TYPE> &prop) {
571 auto values =
new typename VectorGraphProperty<TYPE>::ValuesImpl(
572 _nodes.size() + _nodes.numberOfFree(), _nodes.capacity());
573 _nodeValues.insert(values);
574 prop = NodeProperty<TYPE>(values,
this);
584 template <
typename TYPE>
585 void free(NodeProperty<TYPE> &prop) {
586 assert(_nodeValues.find(prop._values) != _nodeValues.end());
588 _nodeValues.erase(prop._values);
598 template <
typename TYPE>
599 void alloc(EdgeProperty<TYPE> &prop) {
600 auto values =
new typename VectorGraphProperty<TYPE>::ValuesImpl(
601 _edges.size() + _edges.numberOfFree(), _edges.capacity());
602 _edgeValues.insert(values);
603 prop = EdgeProperty<TYPE>(values,
this);
613 template <
typename TYPE>
614 void free(EdgeProperty<TYPE> &prop) {
615 assert(_edgeValues.find(prop._values) != _edgeValues.end());
617 _edgeValues.erase(prop._values);
631 const std::vector<adjData> &adj(
const node n) {
632 assert(isElement(n));
633 return _nData[n]._adj;
642 const std::vector<node> &nodes()
const {
652 const std::vector<edge> &edges()
const {
662 bool isNodeAttr(VectorGraphValues *values) {
663 return (_nodeValues.find(values) != _nodeValues.end());
666 bool isEdgeAttr(VectorGraphValues *values) {
667 return (_edgeValues.find(values) != _edgeValues.end());
679 void integrityTest();
683 nodeData() : _outdeg(0) {}
690 void addEdge(
bool t, node n, edge e) {
691 _adj.emplace_back(t, n, e);
694 unsigned int _outdeg;
695 std::vector<adjData> _adj;
699 std::pair<node, node> _ends;
700 std::pair<unsigned int, unsigned int> _endsPos;
703 std::vector<nodeData> _nData;
704 std::vector<edgeData> _eData;
706 IdContainer<node> _nodes;
707 IdContainer<edge> _edges;
709 std::set<VectorGraphValues *>
711 std::set<VectorGraphValues *>
718 void addNodeToValues(node n);
723 void addEdgeToValues(edge e);
728 void addEdgeInternal(edge e, node src, node tgt);
733 void removeEdge(edge e);
738 void moveEdge(node n,
unsigned int a,
unsigned int b);
742 void partialDelEdge(node n, edge e);
748 template <
typename TYPE>
749 bool NodeProperty<TYPE>::isValid()
const {
750 if (this->_graph == 0)
753 if (this->_values == 0)
756 return this->_graph->isNodeAttr(this->_values);
759 template <
typename TYPE>
760 bool EdgeProperty<TYPE>::isValid()
const {
761 if (this->_graph == 0)
764 if (this->_values == 0)
767 return this->_graph->isEdgeAttr(this->_values);