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>
62 class TLP_SCOPE VectorGraph {
83 edge existEdge(
const node src,
const node tgt,
const bool directed =
true)
const;
89 bool isElement(
const node n)
const {
90 assert(n.id < _nData.size());
91 return _nodes.isElement(n);
98 bool isElement(
const edge e)
const {
99 assert(e.id < _eData.size());
100 return _edges.isElement(e);
108 void setEdgeOrder(
const node n,
const std::vector<edge> &v);
115 void swapEdgeOrder(
const node n,
const edge e1,
const edge e2);
123 void reserveNodes(
const size_t nbNodes);
131 void reserveEdges(
const size_t nbEdges);
139 void reserveAdj(
const size_t nbEdges);
147 void reserveAdj(
const node n,
const size_t nbEdges);
153 node operator[](
const unsigned int id)
const {
154 assert(
id < _nodes.size());
162 edge operator()(
const unsigned int id)
const {
163 assert(
id < _edges.size());
171 node getOneNode()
const {
181 Iterator<node> *getNodes()
const;
188 Iterator<edge> *getEdges()
const;
195 Iterator<edge> *getInOutEdges(
const node n)
const;
202 Iterator<edge> *getOutEdges(
const node n)
const;
209 Iterator<edge> *getInEdges(
const node n)
const;
216 Iterator<node> *getInOutNodes(
const node n)
const;
224 Iterator<node> *getInNodes(
const node n)
const;
231 Iterator<node> *getOutNodes(
const node n)
const;
237 unsigned int deg(
const node n)
const {
238 assert(isElement(n));
239 return _nData[n]._adjn.size();
246 unsigned int outdeg(
const node n)
const {
247 assert(isElement(n));
248 return _nData[n]._outdeg;
255 unsigned int indeg(
const node n)
const {
256 return deg(n) - _nData[n]._outdeg;
263 unsigned int numberOfEdges()
const {
264 return _edges.size();
271 unsigned int numberOfNodes()
const {
272 return _nodes.size();
279 bool isEmpty()
const {
280 return _nodes.empty();
299 void addNodes(
unsigned int nb, std::vector<node> *addedNodes =
nullptr);
311 void delNode(
const node n);
320 edge addEdge(
const node src,
const node tgt);
329 void addEdges(
const std::vector<std::pair<node, node>> &edges,
330 std::vector<edge> *addedEdges =
nullptr);
342 void delEdge(
const edge e);
355 void delEdges(
const node n);
377 node source(
const edge e)
const {
378 assert(isElement(e));
379 return _eData[e]._ends.first;
387 node target(
const edge e)
const {
388 assert(isElement(e));
389 return _eData[e]._ends.second;
396 node opposite(
const edge e,
const node n)
const;
402 void reverse(
const edge e);
412 void setSource(
const edge e,
const node n) {
413 assert(isElement(e));
414 assert(isElement(n));
415 setEnds(e, n, target(e));
426 void setTarget(
const edge e,
const node n) {
427 assert(isElement(e));
428 assert(isElement(n));
429 setEnds(e, source(e), n);
436 const std::pair<node, node> &ends(
const edge e)
const {
437 assert(isElement(e));
438 return _eData[e]._ends;
448 void setEnds(
const edge e,
const node src,
const node tgt);
475 template <
typename Compare>
476 void sortEdges(Compare cmp,
bool stable =
false) {
478 stable_sort(_edges.begin(), _edges.end(), cmp);
480 sort(_edges.begin(), _edges.end(), cmp);
499 template <
typename Compare>
500 void sortNodes(Compare cmp,
bool stable =
false) {
502 stable_sort(_nodes.begin(), _nodes.end(), cmp);
504 sort(_nodes.begin(), _nodes.end(), cmp);
515 unsigned int edgePos(
const edge e)
const {
516 assert(isElement(e));
517 return _edges.getPos(e);
525 unsigned int nodePos(
const node n)
const {
526 assert(isElement(n));
527 return _nodes.getPos(n);
535 void swap(
const node a,
const node b);
542 void swap(
const edge a,
const edge b);
551 template <
typename TYPE>
552 void alloc(NodeProperty<TYPE> &prop) {
553 auto values =
new typename VectorGraphProperty<TYPE>::ValuesImpl(
554 _nodes.size() + _nodes.numberOfFree(), _nodes.capacity());
555 _nodeValues.insert(values);
556 prop = NodeProperty<TYPE>(values,
this);
566 template <
typename TYPE>
567 void free(NodeProperty<TYPE> &prop) {
568 assert(_nodeValues.find(prop._values) != _nodeValues.end());
570 _nodeValues.erase(prop._values);
580 template <
typename TYPE>
581 void alloc(EdgeProperty<TYPE> &prop) {
582 auto values =
new typename VectorGraphProperty<TYPE>::ValuesImpl(
583 _edges.size() + _edges.numberOfFree(), _edges.capacity());
584 _edgeValues.insert(values);
585 prop = EdgeProperty<TYPE>(values,
this);
595 template <
typename TYPE>
596 void free(EdgeProperty<TYPE> &prop) {
597 assert(_edgeValues.find(prop._values) != _edgeValues.end());
599 _edgeValues.erase(prop._values);
613 const std::vector<node> &adj(
const node n)
const {
614 assert(isElement(n));
615 return _nData[n]._adjn;
629 const std::vector<edge> &star(
const node n)
const {
630 assert(isElement(n));
631 return _nData[n]._adje;
640 const std::vector<node> &nodes()
const {
650 const std::vector<edge> &edges()
const {
660 bool isNodeAttr(VectorGraphValues *values) {
661 return (_nodeValues.find(values) != _nodeValues.end());
664 bool isEdgeAttr(VectorGraphValues *values) {
665 return (_edgeValues.find(values) != _edgeValues.end());
677 void integrityTest();
681 _iNodes() : _outdeg(0) {}
690 void addEdge(
bool t, node n, edge e) {
696 unsigned int _outdeg;
697 std::vector<bool> _adjt;
698 std::vector<node> _adjn;
699 std::vector<edge> _adje;
703 std::pair<node, node> _ends;
704 std::pair<unsigned int, unsigned int> _endsPos;
707 std::vector<_iNodes> _nData;
708 std::vector<_iEdges> _eData;
710 IdContainer<node> _nodes;
711 IdContainer<edge> _edges;
713 std::set<VectorGraphValues *>
715 std::set<VectorGraphValues *>
724 void testCond(std::string str,
bool b);
729 void addNodeToValues(node n);
734 void addEdgeToValues(edge e);
739 void addEdgeInternal(edge e, node src, node tgt);
744 void removeEdge(edge e);
749 void moveEdge(node n,
unsigned int a,
unsigned int b);
753 void partialDelEdge(node n, edge e);
757 #ifndef NDEBUG // these two functions are used to insure that property has been allocated in debug 759 template <
typename TYPE>
760 bool NodeProperty<TYPE>::isValid()
const {
761 if (this->_graph == 0)
764 if (this->_values == 0)
767 return this->_graph->isNodeAttr(this->_values);
770 template <
typename TYPE>
771 bool EdgeProperty<TYPE>::isValid()
const {
772 if (this->_graph == 0)
775 if (this->_values == 0)
778 return this->_graph->isEdgeAttr(this->_values);
782 #endif // VECTORGRAPH_H