1/*
2 * map_graph.hpp
3 *
4 * Created on: Nov 21, 2014
5 * Author: Pietro Incardona
6 *
7 *
8 * Graph structure that store a CSR graph format
9 *
10 * This Graph format is suppose to have a list of vertex that store an index x that indicate where
11 * in the adjacency list we have the list of all the neighborhood vertex, plus an adjacency list
12 * that store all the neighborhood for each vertex:
13 *
14 * In reality inside Graph_CSR
15 *
16 * VertexList store the Vertex index that indicate the end of the neighborhood list,
17 * the start is indicated by i * v_slot (id of the vertex, v_slot maximum number of
18 * neighborhood for a vertex)
19 *
20 * EdgeList store for each vertex at position i * v_slot (id of the vertex, v_slot maximum
21 * number of neighborhood for a vertex) the list of all the neighborhood of the vertex i
22 *
23 * Example
24 *
25 * Suppose an undirected graph of 4 vertex
26 *
27 * 1 -> 2 3 4
28 * 2 -> 1
29 * 3 -> 4 1
30 * 4 -> 1 3
31 *
32 * suppose that v_slot is 4 ( each vertex has less tha 4 neighborhood )
33 *
34 * we will have
35 *
36 * Vertex list 3 5 10 14
37 * Edge list 2 3 4 0 1 0 0 0 4 1 0 0 1 3 0 0
38 *
39 * Vertex properties and edge properties are stored in a separate structure
40 *
41 */
42
43#ifndef MAP_GRAPH_HPP_
44#define MAP_GRAPH_HPP_
45
46#include "Vector/map_vector.hpp"
47#include <unordered_map>
48#ifdef METIS_GP
49#include "metis_util.hpp"
50#endif
51
52#define NO_EDGE -1
53
54/*! \brief class with no edge
55 *
56 */
57class no_edge
58{
59public:
60
61 //! type in case of no edge
62 typedef boost::fusion::vector<> type;
63
64 //! empty edge
65 type data;
66
67 //! no properties
68 static const unsigned int max_prop = 0;
69
70 static inline bool noPointers()
71 {
72 return true;
73 }
74};
75
76template<typename V, typename E,
77 typename Memory,
78 typename layout_v,
79 typename layout_e,
80 template <typename> class layout_v_base,
81 template <typename> class layout_e_base,
82 typename grow_p>
83class Graph_CSR;
84
85/*! \brief Structure used inside GraphCSR an edge
86 *
87 * For each vertex the first number "vid" store the target node, the second number store
88 * edge id that store all the properties
89 *
90 */
91
92class e_map
93{
94public:
95 typedef boost::fusion::vector<size_t, size_t> type;
96
97 type data;
98
99 static const unsigned int vid = 0;
100 static const unsigned int eid = 1;
101 static const unsigned int max_prop = 2;
102
103 // Setter method
104
105 inline void setvid(size_t vid_)
106 {
107 boost::fusion::at_c<0>(data) = vid_;
108 }
109
110 inline void seteid(size_t eid_)
111 {
112 boost::fusion::at_c<1>(data) = eid_;
113 }
114
115 static inline bool noPointers()
116 {
117 return true;
118 }
119};
120
121class edge_key
122{
123public:
124
125 //! Actual source node
126 size_t pos;
127
128 //! Actual target node
129 size_t pos_e;
130
131 /*! \brief Reset the counter
132 *
133 *
134 *
135 */
136 void begin()
137 {
138 pos = 0;
139 pos_e = 0;
140 }
141
142 /*! \brief Get the source id of this edge
143 *
144 * \return the source of this edge
145 *
146 */
147 size_t & source()
148 {
149 return pos;
150 }
151
152 /*! \brief Return the target of this edge
153 *
154 * \return the target of this edge
155 *
156 */
157
158 size_t & target_t()
159 {
160 return pos_e;
161 }
162};
163
164/*! \brief Graph edge iterator
165 *
166 */
167
168template<typename Graph>
169class edge_iterator
170{
171 //! Graph
172 const Graph & g;
173
174 // Actual edge key
175 edge_key ek;
176
177public:
178
179 /*! \brief Constructor
180 *
181 * \param g Graph on where iterate
182 *
183 */
184
185 edge_iterator(const Graph & g) :
186 g(g)
187 {
188 ek.begin();
189 }
190
191 /*! \brief Get the next element
192 *
193 * \return the next grid_key
194 *
195 */
196
197 edge_iterator & operator++()
198 {
199 // Check if reach the end of the edge list
200 if (ek.pos_e + 1 >= g.getNChilds(ek.pos))
201 {
202 // increment the node position and reset
203 ek.pos++;
204 ek.pos_e = 0;
205
206 // skip every vertex without edges
207 while (ek.pos < g.getNVertex() && g.getNChilds(ek.pos) == 0)
208 {
209 ek.pos++;
210 }
211 }
212 else
213 {
214 // increment the edge position
215 ek.pos_e++;
216 }
217
218 return *this;
219 }
220
221 /*! \brief Check if there is the next element
222 *
223 * Check if there is the next element
224 *
225 * \return true if there is the next, false otherwise
226 *
227 */
228
229 bool isNext()
230 {
231 if (ek.pos < g.getNVertex())
232 {
233 //! we did not reach the end of the node
234
235 return true;
236 }
237
238 //! we reach the end of the node
239 return false;
240 }
241
242 /*! \brief Get the actual key
243 *
244 * Get the actual key
245 *
246 * \return the actual key
247 *
248 */
249 edge_key get()
250 {
251 return ek;
252 }
253
254 /*! \brief Return the source node
255 *
256 * \return the source node
257 *
258 */
259 size_t source()
260 {
261 return ek.pos;
262 }
263
264 /*! \brief Return the target node
265 *
266 * \return the target node
267 *
268 */
269 size_t target()
270 {
271 return g.getChild(ek.pos, ek.pos_e);
272 }
273};
274
275/*! \brief Structure that store a graph in CSR format or basically in compressed adjacency matrix format
276 *
277 * \param V each vertex will encapsulate have this type
278 * \param E each edge will encapsulate this type
279 * \param device Type of device / basicaly it select the layout
280 * for device_cpu is (x_1, p1_1, p2_1, p3_1 ....), ... ( x_n, p1_1, p2_1, p3_1, ...)
281 * for device_gpu is (x_1, ... , x_n) ... (p1_n, ... pn_n)
282 * where x_1 is the index where it end the list of the neighborhood list and pj_k is
283 * the property j for the vertex j. Basically in the first case one array will store
284 * index and property of each vertex, in the second case several array will store
285 * index and property
286 *
287 * \param VertexList structure that store the list of Vertex
288 * \param EdgeList structure that store the list of edge
289 *
290 * \warning This graph is suitable only when we know the graph structure and we build
291 * the graph adding vertexes and edges, removing vertex and edge is EXTREMLY expensive
292 *
293 * ### Define vertex and edge of the graph
294 * \snippet graph_unit_tests.hpp Define vertex and edge of the graph
295 * ### Create a Cartesian graph
296 * \snippet graph_unit_tests.hpp Create a Cartesian graph
297 * ### Create a tree graph with no edge properties
298 * \snippet graph_unit_tests.hpp Create a tree graph with no edge properties
299 *
300 */
301template<typename V, typename E = no_edge,
302 typename Memory = HeapMemory,
303 typename layout_v = typename memory_traits_lin<V>::type,
304 typename layout_e = typename memory_traits_lin<E>::type,
305 template<typename> class layout_v_base = memory_traits_lin,
306 template<typename> class layout_e_base = memory_traits_lin,
307 typename grow_p = openfpm::grow_policy_double>
308class Graph_CSR
309{
310 //! number of slot per vertex
311 size_t v_slot;
312
313 //! Structure that store the vertex properties
314 openfpm::vector<V, Memory, layout_v_base,grow_p, openfpm::vect_isel<V>::value> v;
315
316 //! Structure that store the number of adjacent vertex in e_l for each vertex
317 openfpm::vector<size_t, Memory, layout_v_base,grow_p, openfpm::vect_isel<size_t>::value> v_l;
318
319 //! Structure that store the edge properties
320 openfpm::vector<E, Memory, layout_e_base, grow_p, openfpm::vect_isel<E>::value> e;
321
322 //! Structure that store for each vertex the adjacent the vertex id and edge id (for property into e)
323 openfpm::vector<e_map, Memory, layout_e_base , grow_p, openfpm::vect_isel<e_map>::value> e_l;
324
325 //! invalid edge element, when a function try to create an in valid edge this object is returned
326 openfpm::vector<E, Memory, layout_e_base, grow_p, openfpm::vect_isel<E>::value> e_invalid;
327
328 /*! \brief add edge on the graph
329 *
330 * add edge on the graph
331 *
332 * \param v1 start vertex
333 * \param v2 end vertex
334 *
335 * \return the edge id
336 *
337 */
338
339 template<typename CheckPolicy = NoCheck> inline size_t addEdge_(size_t v1, size_t v2)
340 {
341 // If v1 and v2 does not satisfy some criteria return
342 if (CheckPolicy::valid(v1, v.size()) == false)
343 return (size_t)NO_EDGE;
344 if (CheckPolicy::valid(v2, v.size()) == false)
345 return (size_t)NO_EDGE;
346
347 // get the number of adjacent vertex
348 size_t id_x_end = v_l.template get<0>(v1);
349
350#ifdef SE_CLASS1
351 // Check that v1 and v2 exist
352
353 if (v1 >= v.size() || v2 >= v.size())
354 {
355 std::cout << "Warning graph: creating an edge between vertex that does not exist" << std::endl;
356 }
357
358 // Check that the edge does not already exist
359
360 for (size_t s = 0; s < id_x_end; s++)
361 {
362 if (e_l.template get<e_map::vid>(v1 * v_slot + s) == v2)
363 {
364 std::cerr << "Error graph: the edge already exist" << std::endl;
365 }
366 }
367#endif
368
369 // Check if there is space for another edge
370
371 if (id_x_end >= v_slot)
372 {
373 // Unfortunately there is not space we need to reallocate memory
374 // Reallocate with double slot
375
376 // Create an new Graph
377
378 Graph_CSR<V, E> g_new(2 * v_slot, v.size());
379
380 // Copy the graph
381
382 for (size_t i = 0; i < v.size(); i++)
383 {
384 // copy the property from the old graph
385
386 g_new.v.set(i, v, 2 * i);
387 }
388
389 // swap the new graph with the old one
390
391 swap(g_new);
392 }
393
394 // Here we are sure than v and e has enough slots to store a new edge
395 // Check that e_l has enough space to store new edge
396 // should be always e.size == e_l.size
397
398 if (id_x_end >= e_l.size())
399 {
400 // Resize the basic structure
401
402 e_l.resize(v.size() * v_slot);
403 }
404
405 // add in e_l the adjacent vertex for v1 and fill the edge id
406 e_l.template get<e_map::vid>(v1 * v_slot + id_x_end) = v2;
407 e_l.template get<e_map::eid>(v1 * v_slot + id_x_end) = e.size();
408
409 // add an empty edge
410 e.resize(e.size() + 1);
411
412 // Increment the ending point
413 ++v_l.template get<0>(v1);
414
415 // return the created edge
416 return e.size() - 1;
417 }
418
419public:
420
421 //! Vertex typedef
422 typedef V V_type;
423
424 //! Edge typedef
425 typedef E E_type;
426
427 //! Object container for the vertex, for example can be encap<...> (map_grid or openfpm::vector)
428 typedef typename openfpm::vector<V, Memory, layout_v_base, grow_p, openfpm::vect_isel<V>::value>::container V_container;
429
430 //! Object container for the edge, for example can be encap<...> (map_grid or openfpm::vector)
431 typedef typename openfpm::vector<E, Memory, layout_e_base, grow_p, openfpm::vect_isel<E>::value>::container E_container;
432
433 /*! \brief Check if two graph exactly match
434 *
435 * \warning The requirement to match is more restrictive than simply content matching
436 *
437 * \param g Graph to compare
438 *
439 * \return true if they match
440 *
441 */
442 bool operator==(const Graph_CSR<V, E, Memory, layout_v,layout_e,layout_v_base, layout_e_base, grow_p> & g) const
443 {
444 bool ret = true;
445
446 // Check if they match
447
448 ret &= (v_slot == g.v_slot);
449 ret &= (v == g.v);
450 ret &= (v_l == g.v_l);
451 ret &= (e == g.e);
452 ret &= (e_l == g.e_l);
453
454 return ret;
455 }
456
457
458 /*! \brief It duplicate the graph
459 *
460 * \return a graph duplicate of the first
461 *
462 */
463 Graph_CSR<V, E, Memory, layout_v, layout_e,layout_v_base,layout_e_base, grow_p> duplicate() const
464 {
465 Graph_CSR<V, E, Memory, layout_v, layout_e,layout_v_base,layout_e_base, grow_p> dup;
466
467 dup.v_slot = v_slot;
468
469 //! duplicate all the structures
470
471 dup.v.swap(v.duplicate());
472 dup.v_l.swap(v_l.duplicate());
473 dup.e.swap(e.duplicate());
474 dup.e_l.swap(e_l.duplicate());
475 dup.e_invalid.swap(e_invalid.duplicate());
476
477 return dup;
478 }
479
480 /*! \brief Constructor
481 *
482 * Constructor
483 *
484 */
485 Graph_CSR()
486 :Graph_CSR(0, 16)
487 {
488 }
489
490 /*! \brief Constructor
491 *
492 * Constructor
493 *
494 * \param n_vertex number of vertex has a graph
495 *
496 */
497 Graph_CSR(size_t n_vertex) :
498 Graph_CSR(n_vertex, 16)
499 {
500 }
501
502 /*! \brief Constructor
503 *
504 * \param n_vertex number of vertices
505 * \param n_slot number of slots (around how many edge has
506 * a vertex, it is not fundamental parameter is just
507 * an indication)
508 *
509 */
510 Graph_CSR(size_t n_vertex, size_t n_slot)
511 :v_slot(n_slot)
512 {
513 //! Creating n_vertex into the graph
514 v.resize(n_vertex);
515 //! Creating n_vertex adjacency list counters
516 v_l.resize(n_vertex);
517 //! no edge set the counter to zero
518 v_l.fill(0);
519 //! create one invalid edge
520 e_invalid.resize(1);
521 }
522
523 /*! \brief Copy constructor
524 *
525 * \param g Graph to copy
526 *
527 */
528 Graph_CSR(Graph_CSR<V, E, Memory> && g)
529 {
530 this->operator=(g);
531 }
532
533 /*! \breif Copy the graph
534 *
535 * \param g graph to copy
536 *
537 * \return itself
538 *
539 */
540 Graph_CSR<V, E, Memory> & operator=(Graph_CSR<V, E, Memory> && g)
541 {
542 size_t vs_tmp = v_slot;
543 v_slot = g.v_slot;
544 g.v_slot = vs_tmp;
545 swap(g);
546
547 return *this;
548 }
549
550 /*! \breif Copy the graph
551 *
552 * \param g graph to copy
553 *
554 */
555 Graph_CSR<V, E, Memory> & operator=(const Graph_CSR<V, E, Memory> & g)
556 {
557 swap(g.duplicate());
558
559 v_slot = g.v_slot;
560
561 return *this;
562 }
563
564 /*! \brief operator to access the vertex
565 *
566 * operator to access the vertex
567 *
568 * \tparam i property to access
569 * \param id of the vertex to access
570 *
571 * \return the reference of the property vertex
572 *
573 */
574 template<unsigned int i> auto vertex_p(size_t id) -> decltype( v.template get<i>(id) )
575 {
576 return v.template get<i>(id);
577 }
578
579 /*! \brief Access the vertex
580 *
581 * \tparam i property to access
582 *
583 * \param id of the vertex to access
584 *
585 * \return the reference of the property vertex
586 *
587 */
588 template<unsigned int i> auto vertex_p(grid_key_dx<1> id) -> decltype( v.template get<i>(id) )
589 {
590 return v.template get<i>(id);
591 }
592
593 /*! \brief Function to access the vertex
594 *
595 * \param id of the vertex to access
596 *
597 * \return vertex object
598 *
599 */
600 auto vertex(size_t id) -> decltype( v.get(id) )
601 {
602 return v.get(id);
603 }
604
605 /*! \brief Function to access the vertex
606 *
607 * \param id of the vertex to access
608 *
609 * \return the vertex object
610 *
611 */
612 auto vertex(grid_key_dx<1> id) -> decltype( v.get(id.get(0)) )
613 {
614 return v.get(id.get(0));
615 }
616
617 /*! \brief Fuction to access the vertex
618 *
619 * \param id of the vertex to access
620 *
621 * \return the vertex object
622 *
623 */
624 auto vertex(openfpm::vector_key_iterator id) -> decltype( v.get(0) )
625 {
626 return v.get(id.get());
627 }
628
629 /*! \brief Function to access the vertex
630 *
631 * \param id of the vertex to access
632 *
633 * \return the vertex object
634 *
635 */
636 auto vertex(size_t id) const -> const decltype( v.get(id) )
637 {
638 return v.get(id);
639 }
640
641 /*! \brief Fuction to access the vertex
642 *
643 * operator to access the vertex
644 *
645 * \param id of the vertex to access
646 *
647 * \return the vertex object
648 *
649 */
650 auto vertex(grid_key_dx<1> id) const -> const decltype( v.get(id.get(0)) )
651 {
652 return v.get(id.get(0));
653 }
654
655 /*! \brief operator to access the vertex
656 *
657 * \param id of the vertex to access
658 *
659 * \return the vertex object
660 *
661 */
662 auto vertex(openfpm::vector_key_iterator id) const -> const decltype( v.get(0) )
663 {
664 return v.get(id.get());
665 }
666
667 /*! \brief operator to clear the whole graph
668 *
669 * operator to clear all
670 *
671 */
672 void clear()
673 {
674 v.clear();
675 e.clear();
676 v_l.clear();
677 e_l.clear();
678 e_invalid.clear();
679 }
680
681
682 /*! \brief operator to clear the whole graph
683 *
684 * operator to clear all
685 *
686 */
687 void destroy()
688 {
689 v.clear();
690 v.shrink_to_fit();
691 e.clear();
692 e.shrink_to_fit();
693 v_l.clear();
694 v_l.shrink_to_fit();
695 e_l.clear();
696 e_l.shrink_to_fit();
697 e_invalid.clear();
698 e_invalid.shrink_to_fit();
699 }
700
701 /*! \brief Access the edge
702 *
703 * \tparam i property to access
704 * \param id of the edge to access
705 *
706 * \return a reference to the edge property
707 *
708 */
709 template<unsigned int i> auto edge_p(grid_key_dx<1> id) -> decltype ( e.template get<i>(id) )
710 {
711 return e.template get<i>(id);
712 }
713
714 /*! \brief Access the edge
715 *
716 * \tparam i property to access
717 * \param id of the edge to access
718 *
719 * \return a reference to the edge property
720 *
721 */
722 template<unsigned int i> auto edge_p(size_t id) -> decltype ( e.template get<i>(id) )
723 {
724 return e.template get<i>(id);
725 }
726
727
728 /*! \brief operator to access the edge
729 *
730 * \param ek key of the edge
731 *
732 * \return the edge object
733 *
734 */
735 auto edge(edge_key ek) const -> const decltype ( e.get(0) )
736 {
737 return e.get(e_l.template get<e_map::eid>(ek.pos * v_slot + ek.pos_e));
738 }
739
740 /*! \brief operator to access the edge
741 *
742 * \param id of the edge to access
743 *
744 * \return the edge object
745 *
746 */
747 auto edge(size_t id) const -> const decltype ( e.get(id) )
748 {
749 return e.get(id);
750 }
751
752 /*! \brief Access the edge
753 *
754 * \param id of the edge to access
755 *
756 * \return the edge object
757 *
758 */
759 auto edge(grid_key_dx<1> id) const -> const decltype ( e.get(id.get(0)) )
760 {
761 return e.get(id.get(0));
762 }
763
764 /*! \brief Return the number of childs of a vertex
765 *
766 * \param c Child id
767 *
768 * \return the number of childs
769 *
770 */
771
772 inline size_t getNChilds(size_t c) const
773 {
774 // Get the number of childs
775
776 return v_l.template get<0>(c);
777 }
778
779 /*! \brief Return the number of childs of a vertex
780 *
781 * \param c child id
782 *
783 * \return the number of childs
784 *
785 */
786 inline size_t getNChilds(typename openfpm::vector<V, Memory, layout_v_base, grow_p, openfpm::vect_isel<V>::value>::iterator_key & c)
787 {
788 // Get the number of childs
789
790 return v_l.template get<0>(c.get());
791 }
792
793 /*! \brief Get the vertex edge
794 *
795 * \param v vertex
796 * \param v_e edge id
797 *
798 * \return the edge object
799 *
800 */
801 inline auto getChildEdge(size_t v, size_t v_e) -> decltype(e.get(0))
802 {
803 // Get the edge id
804 return e.get(e_l.template get<e_map::eid>(v * v_slot + v_e));
805 }
806
807 /*! \brief Get the child vertex id
808 *
809 * \param v node
810 * \param i child at position i
811 *
812 * \return the target vertex id that connect v with the target vertex at position i
813 *
814 */
815
816 inline size_t getChild(size_t v, size_t i) const
817 {
818#ifdef SE_CLASS1
819 if (i >= v_l.template get<0>(v))
820 {
821 std::cerr << "Error " << __FILE__ << " line: " << __LINE__ << " vertex " << v << " does not have edge " << i << std::endl;
822 }
823
824 if (i >= v_l.template get<0>(v))
825 {
826 std::cerr << "Error " << __FILE__ << " " << __LINE__ << " vertex " << v << " does not have edge "<< i << std::endl;
827 }
828#endif
829 // Get the target vertex id
830 return e_l.template get<e_map::vid>(v * v_slot + i);
831 }
832
833 /*! \brief Get the child edge
834 *
835 * \param v node
836 * \param i child at position i
837 *
838 * \return the target i connected by an edge node, for the node v
839 *
840 */
841 inline size_t getChild(typename openfpm::vector<V, Memory, layout_v_base, grow_p>::iterator_key & v, size_t i)
842 {
843#ifdef SE_CLASS1
844 if (i >= v_l.template get<0>(v.get()))
845 {
846 std::cerr << "Error " << __FILE__ << " line: " << __LINE__ << " vertex " << v.get() << " does not have edge " << i << std::endl;
847 }
848
849 if (e.size() <= e_l.template get<e_map::eid>(v.get() * v_slot + i))
850 {
851 std::cerr << "Error " << __FILE__ << " " << __LINE__ << " vertex " << v.get() << " does not have edge "<< i << std::endl;
852 }
853#endif
854
855 // Get the edge id
856 return e_l.template get<e_map::vid>(v.get() * v_slot + i);
857 }
858
859 /*! \brief add vertex
860 *
861 * \param vrt Vertex properties
862 *
863 */
864 inline void addVertex(const V & vrt)
865 {
866
867 v.add(vrt);
868
869 // Set the number of adjacent vertex for this vertex to 0
870
871 v_l.add(0ul);
872
873 // Add a slot for the vertex adjacency list
874
875 e_l.resize(e_l.size() + v_slot);
876 }
877
878 /*! \brief add an empty vertex
879 *
880 */
881 inline void addVertex()
882 {
883
884 v.add();
885
886 // Set the number of adjacent vertex for this vertex to 0
887
888 v_l.add(0ul);
889
890 // Add a slot for the vertex adjacency list
891
892 e_l.resize(e_l.size() + v_slot);
893 }
894
895 /*! \brief add edge on the graph
896 *
897 * \param v1 source edge
898 * \param v2 destination edge
899 * \param ed edge object to add
900 *
901 * \return edge object
902 *
903 */
904 template<typename CheckPolicy = NoCheck> inline auto addEdge(size_t v1, size_t v2, const E & ed) -> decltype(e.get(0))
905 {
906 long int id_x_end = addEdge_<CheckPolicy>(v1, v2);
907
908 // If there is not edge return an invalid edge, is a kind of stub object
909 if (id_x_end == NO_EDGE)
910 return e_invalid.get(0);
911
912 // add in e_l the edge properties
913 e.set(id_x_end, ed);
914
915 return e.get(id_x_end);
916 }
917
918 /*! \brief add edge on the graph
919 *
920 * add edge on the graph
921 *
922 * \param v1 start vertex
923 * \param v2 end vertex
924 *
925 * \return the edge object
926 *
927 */
928 template<typename CheckPolicy = NoCheck> inline auto addEdge(size_t v1, size_t v2) -> decltype(e.get(0))
929 {
930 //! add an edge
931 long int id_x_end = addEdge_<CheckPolicy>(v1, v2);
932 // If there is not edge return an invalid edge, is a kind of stub object
933 if (id_x_end == NO_EDGE)
934 return e_invalid.get(0);
935
936 //! return the edge to change the properties
937 return e.get(id_x_end);
938 }
939
940 /*! \brief add edge on the graph and fill source and destination informations
941 *
942 * add edge on the graph
943 *
944 * \param v1 start vertex
945 * \param v2 end vertex
946 *
947 * \param srcgid source global id
948 * \param dstgid destination global id
949 *
950 * \tparam sgid property id filled with the source vertex global id
951 * \tparam dgid property id filled with the destination vertex global id
952 *
953 * \return the edge object
954 *
955 */
956 template<typename CheckPolicy = NoCheck, int sgid, int dgid> inline auto addEdge(size_t v1, size_t v2, size_t srcgid, size_t dstgid) -> decltype(e.get(0))
957 {
958 //! add an edge
959 long int id_x_end = addEdge_<CheckPolicy>(v1, v2);
960 //! If there is not edge return an invalid edge, is a kind of stub object
961 if (id_x_end == NO_EDGE)
962 return e_invalid.get(0);
963
964 //! set source and destination ids of the edge
965 e.get(id_x_end).template get<sgid>() = srcgid;
966 e.get(id_x_end).template get<dgid>() = dstgid;
967
968 //! return the edge to change the properties
969 return e.get(id_x_end);
970 }
971
972 /*! \brief swap the memory of g with this graph
973 *
974 * it is basically used for move semantic
975 *
976 * \param g graph to swap
977 *
978 */
979
980 inline void swap(Graph_CSR<V, E> & g)
981 {
982 // switch the memory
983
984 v.swap(g.v);
985 e.swap(g.e);
986 v_l.swap(g.v_l);
987 e_l.swap(g.e_l);
988 e_invalid.swap(g.e_invalid);
989
990 size_t v_slot_tmp = g.v_slot;
991 g.v_slot = v_slot;
992 v_slot = v_slot_tmp;
993 }
994
995 /*! \brief swap the memory of g with this graph
996 *
997 * it is basically used for move semantic
998 *
999 * \param g graph to swap
1000 *
1001 */
1002 inline void swap(Graph_CSR<V, E> && g)
1003 {
1004 // switch the memory
1005
1006 v.swap(g.v);
1007 e.swap(g.e);
1008 v_l.swap(g.v_l);
1009 e_l.swap(g.e_l);
1010 e_invalid.swap(g.e_invalid);
1011
1012 size_t v_slot_tmp = g.v_slot;
1013 g.v_slot = v_slot;
1014 v_slot = v_slot_tmp;
1015 }
1016
1017 /*! \brief Get the vertex iterator
1018 *
1019 * Get the vertex iterator
1020 *
1021 * \return an iterator to iterate through all the vertex
1022 *
1023 */
1024
1025 inline auto getVertexIterator() const -> decltype(v.getIterator())
1026 {
1027 return v.getIterator();
1028 }
1029
1030 /*! \brief Get the vertex iterator
1031 *
1032 * Get the vertex iterator
1033 *
1034 * \return an iterator to iterate through all the edges
1035 *
1036 */
1037
1038 inline edge_iterator<Graph_CSR<V, E, Memory>> getEdgeIterator() const
1039 {
1040 return edge_iterator<Graph_CSR<V, E, Memory>>(*this);
1041 }
1042
1043 /*! \brief Return the number of the vertex
1044 *
1045 * \return the number of vertex
1046 *
1047 */
1048
1049 inline size_t getNVertex() const
1050 {
1051 return v.size();
1052 }
1053
1054 /*! \brief Return the number of edges
1055 *
1056 * \return the number of edges
1057 *
1058 */
1059
1060 inline size_t getNEdge() const
1061 {
1062 return e.size();
1063 }
1064};
1065
1066/*! \brief Simplified implementation of Graph_CSR
1067 *
1068 * Used when Graph_CSR is used as a default template argument to avoid 7 arguments
1069 *
1070 * [Example]
1071 *
1072 * template<template<typename,typename> class T=Graph_CSR_s>
1073 * class cool_structure
1074 * {
1075 * T<Vertex,Edge> graph
1076 * }
1077 *
1078 * only 2 parameter are needed, if you use Graph_CSR you have to define 7 regardless that
1079 * Graph_CSR has some default template
1080 *
1081 * template<template<typename,typename> class T=Graph_CSR>
1082 * class cool_structure
1083 * {
1084 * T<Vertex,Edge> graph
1085 * }
1086 *
1087 * THIS DO NOT COMPILE
1088 *
1089 */
1090template<typename V, typename E>
1091class Graph_CSR_s: public Graph_CSR<V, E>
1092{
1093
1094};
1095
1096#endif /* MAP_GRAPH_HPP_ */
1097