46 |
46 |
47 ///Creates convenience typedefs for the graph types and iterators |
47 ///Creates convenience typedefs for the graph types and iterators |
48 |
48 |
49 ///This \c \#define creates convenience typedefs for the following types |
49 ///This \c \#define creates convenience typedefs for the following types |
50 ///of \c Graph: \c Node, \c NodeIt, \c Edge, \c EdgeIt, \c InEdgeIt, |
50 ///of \c Graph: \c Node, \c NodeIt, \c Edge, \c EdgeIt, \c InEdgeIt, |
51 ///\c OutEdgeIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, |
51 ///\c OutEdgeIt |
52 ///\c BoolEdgeMap, \c IntEdgeMap, \c DoubleEdgeMap. |
|
53 ///\note If \c G it a template parameter, it should be used in this way. |
52 ///\note If \c G it a template parameter, it should be used in this way. |
54 ///\code |
53 ///\code |
55 /// GRAPH_TYPEDEFS(typename G) |
54 /// GRAPH_TYPEDEFS(typename G) |
56 ///\endcode |
55 ///\endcode |
57 /// |
56 /// |
62 typedef Graph:: NodeIt NodeIt; \ |
61 typedef Graph:: NodeIt NodeIt; \ |
63 typedef Graph:: Edge Edge; \ |
62 typedef Graph:: Edge Edge; \ |
64 typedef Graph:: EdgeIt EdgeIt; \ |
63 typedef Graph:: EdgeIt EdgeIt; \ |
65 typedef Graph:: InEdgeIt InEdgeIt; \ |
64 typedef Graph:: InEdgeIt InEdgeIt; \ |
66 typedef Graph::OutEdgeIt OutEdgeIt; |
65 typedef Graph::OutEdgeIt OutEdgeIt; |
67 // typedef Graph::template NodeMap<bool> BoolNodeMap; |
66 |
68 // typedef Graph::template NodeMap<int> IntNodeMap; |
|
69 // typedef Graph::template NodeMap<double> DoubleNodeMap; |
|
70 // typedef Graph::template EdgeMap<bool> BoolEdgeMap; |
|
71 // typedef Graph::template EdgeMap<int> IntEdgeMap; |
|
72 // typedef Graph::template EdgeMap<double> DoubleEdgeMap; |
|
73 |
|
74 ///Creates convenience typedefs for the undirected graph types and iterators |
67 ///Creates convenience typedefs for the undirected graph types and iterators |
75 |
68 |
76 ///This \c \#define creates the same convenience typedefs as defined by |
69 ///This \c \#define creates the same convenience typedefs as defined by |
77 ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates |
70 ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates |
78 ///\c UEdge, \c UEdgeIt, \c IncEdgeIt, |
71 ///\c UEdge, \c UEdgeIt, \c IncEdgeIt, |
79 ///\c BoolUEdgeMap, \c IntUEdgeMap, \c DoubleUEdgeMap. |
|
80 /// |
72 /// |
81 ///\note If \c G it a template parameter, it should be used in this way. |
73 ///\note If \c G it a template parameter, it should be used in this way. |
82 ///\code |
74 ///\code |
83 /// UGRAPH_TYPEDEFS(typename G) |
75 /// UGRAPH_TYPEDEFS(typename G) |
84 ///\endcode |
76 ///\endcode |
91 typedef Graph:: UEdgeIt UEdgeIt; \ |
83 typedef Graph:: UEdgeIt UEdgeIt; \ |
92 typedef Graph:: IncEdgeIt IncEdgeIt; |
84 typedef Graph:: IncEdgeIt IncEdgeIt; |
93 // typedef Graph::template UEdgeMap<bool> BoolUEdgeMap; |
85 // typedef Graph::template UEdgeMap<bool> BoolUEdgeMap; |
94 // typedef Graph::template UEdgeMap<int> IntUEdgeMap; |
86 // typedef Graph::template UEdgeMap<int> IntUEdgeMap; |
95 // typedef Graph::template UEdgeMap<double> DoubleUEdgeMap; |
87 // typedef Graph::template UEdgeMap<double> DoubleUEdgeMap; |
96 |
88 |
97 |
89 ///\brief Creates convenience typedefs for the bipartite undirected graph |
|
90 ///types and iterators |
|
91 |
|
92 ///This \c \#define creates the same convenience typedefs as defined by |
|
93 ///\ref UGRAPH_TYPEDEFS(Graph) and two more, namely it creates |
|
94 ///\c ANodeIt, \c BNodeIt, |
|
95 /// |
|
96 ///\note If \c G it a template parameter, it should be used in this way. |
|
97 ///\code |
|
98 /// BPUGRAPH_TYPEDEFS(typename G) |
|
99 ///\endcode |
|
100 /// |
|
101 ///\warning There are no typedefs for the graph maps because of the lack of |
|
102 ///template typedefs in C++. |
|
103 #define BPUGRAPH_TYPEDEFS(Graph) \ |
|
104 UGRAPH_TYPEDEFS(Graph) \ |
|
105 typedef Graph::ANodeIt ANodeIt; \ |
|
106 typedef Graph::BNodeIt BNodeIt; |
98 |
107 |
99 /// \brief Function to count the items in the graph. |
108 /// \brief Function to count the items in the graph. |
100 /// |
109 /// |
101 /// This function counts the items (nodes, edges etc) in the graph. |
110 /// This function counts the items (nodes, edges etc) in the graph. |
102 /// The complexity of the function is O(n) because |
111 /// The complexity of the function is O(n) because |
428 typedef typename Graph::UEdge UEdge; |
437 typedef typename Graph::UEdge UEdge; |
429 static UEdge find(const Graph &g, Node u, Node v, UEdge e) { |
438 static UEdge find(const Graph &g, Node u, Node v, UEdge e) { |
430 bool b; |
439 bool b; |
431 if (u != v) { |
440 if (u != v) { |
432 if (e == INVALID) { |
441 if (e == INVALID) { |
433 g.firstInc(e, u, b); |
442 g.firstInc(e, b, u); |
434 } else { |
443 } else { |
435 b = g.source(e) == u; |
444 b = g.source(e) == u; |
436 g.nextInc(e, b); |
445 g.nextInc(e, b); |
437 } |
446 } |
438 while (e != INVALID && g.target(e) != v) { |
447 while (e != INVALID && g.target(e) != v) { |
439 g.nextInc(e, b); |
448 g.nextInc(e, b); |
440 } |
449 } |
441 } else { |
450 } else { |
442 if (e == INVALID) { |
451 if (e == INVALID) { |
443 g.firstInc(e, u, b); |
452 g.firstInc(e, b, u); |
444 } else { |
453 } else { |
445 b = true; |
454 b = true; |
446 g.nextInc(e, b); |
455 g.nextInc(e, b); |
447 } |
456 } |
448 while (e != INVALID && (!b || g.target(e) != v)) { |
457 while (e != INVALID && (!b || g.target(e) != v)) { |
483 /// e = findUEdge(g,u,v,e)) { |
492 /// e = findUEdge(g,u,v,e)) { |
484 /// ... |
493 /// ... |
485 /// } |
494 /// } |
486 ///\endcode |
495 ///\endcode |
487 template <typename Graph> |
496 template <typename Graph> |
488 inline typename Graph::UEdge findEdge(const Graph &g, |
497 inline typename Graph::UEdge findUEdge(const Graph &g, |
489 typename Graph::Node u, |
498 typename Graph::Node u, |
490 typename Graph::Node v, |
499 typename Graph::Node v, |
491 typename Graph::UEdge prev = INVALID) { |
500 typename Graph::UEdge p = INVALID) { |
492 return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, prev); |
501 return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, p); |
493 } |
502 } |
494 |
503 |
495 /// \brief Iterator for iterating on uedges connected the same nodes. |
504 /// \brief Iterator for iterating on uedges connected the same nodes. |
496 /// |
505 /// |
497 /// Iterator for iterating on uedges connected the same nodes. It is |
506 /// Iterator for iterating on uedges connected the same nodes. It is |