4 |
4 |
5 #include <invalid.h> |
5 #include <invalid.h> |
6 |
6 |
7 namespace hugo { |
7 namespace hugo { |
8 |
8 |
|
9 /// Graph wrappers |
|
10 |
|
11 /// The main parts of HUGOlib are the different graph structures, |
|
12 /// generic graph algorithms, graph concepts which couple these, and |
|
13 /// graph wrappers. While the previous ones are more or less clear, the |
|
14 /// latter notion needs further explanation. |
|
15 /// Graph wrappers are graph classes which serve for considering graph |
|
16 /// structures in different ways. A short example makes the notion much more |
|
17 /// clear. |
|
18 /// Suppose that we have an instance \code g \endcode of a directed graph |
|
19 /// type say \code ListGraph \endcode and an algorithm |
|
20 /// \code template<typename Graph> int algorithm(const Graph&); \endcode |
|
21 /// is needed to run on the reversed oriented graph. |
|
22 /// It can be expensive (in time or in memory usage) to copy |
|
23 /// \code g \endcode with the reversed orientation. |
|
24 /// Thus, a wrapper class |
|
25 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. |
|
26 /// The code looks as follows |
|
27 /// \code |
|
28 /// ListGraph g; |
|
29 /// RevGraphWrapper<ListGraph> rgw(g); |
|
30 /// int result=algorithm(rgw); |
|
31 /// \endcode |
|
32 /// After running the algorithm, the original graph \code g \endcode |
|
33 /// is untouched. Thus the above used graph wrapper is to consider the |
|
34 /// original graph with reversed orientation. |
|
35 /// This techniques gives rise to an elegant code, and |
|
36 /// based on stable graph wrappers, complex algorithms can be |
|
37 /// implemented easily. |
|
38 /// In flow, circulation and bipartite matching problems, the residual |
|
39 /// graph is of particualar significance. Combining a wrapper impleneting |
|
40 /// this, shortest path algorithms and mimimum mean cycle algorithms, |
|
41 /// a range of weighted and cardinality optimization algorithms can be |
|
42 /// obtained. For lack of space, for other examples, |
|
43 /// the interested user is referred to the detailed domumentation of graph |
|
44 /// wrappers. |
|
45 /// The behavior of graph wrappers are very different. Some of them keep |
|
46 /// capabilities of the original graph while in other cases this would be |
|
47 /// meaningless. This means that the concepts that they are model of depend |
|
48 /// on the graph wrapper, and the wrapped graph(s). |
|
49 /// If an edge of \code rgw \endcode is deleted, this is carried out by |
|
50 /// deleting the corresponding edge of \code g \endcode. But for a residual |
|
51 /// graph, this operation has no sense. |
|
52 /// Let we stand one more example here to simplify your work. |
|
53 /// wrapper class |
|
54 /// \code template<typename Graph> class RevGraphWrapper; \endcode |
|
55 /// has constructor |
|
56 /// \code RevGraphWrapper(Graph& _g); \endcode. |
|
57 /// This means that in a situation, |
|
58 /// when a \code const ListGraph& \endcode reference to a graph is given, |
|
59 /// then it have to be instatiated with Graph=const ListGraph. |
|
60 /// \code |
|
61 /// int algorithm1(const ListGraph& g) { |
|
62 /// RevGraphWrapper<const ListGraph> rgw(g); |
|
63 /// return algorithm2(rgw); |
|
64 /// } |
|
65 /// \endcode |
9 template<typename Graph> |
66 template<typename Graph> |
10 class GraphWrapper { |
67 class GraphWrapper { |
11 protected: |
68 protected: |
12 Graph* graph; |
69 Graph* graph; |
13 |
70 |
107 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
164 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
108 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
165 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
109 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
166 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
110 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } |
167 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } |
111 // template<typename I> I& next(I &i) const { graph->next(i); return i; } |
168 // template<typename I> I& next(I &i) const { graph->next(i); return i; } |
112 template< typename It > It first() const { |
169 // template< typename It > It first() const { |
113 It e; this->first(e); return e; } |
170 // It e; this->first(e); return e; } |
114 |
171 |
115 template< typename It > It first(const Node& v) const { |
172 // template< typename It > It first(const Node& v) const { |
116 It e; this->first(e, v); return e; } |
173 // It e; this->first(e, v); return e; } |
117 |
174 |
118 Node head(const Edge& e) const { |
175 Node head(const Edge& e) const { |
119 return Node(graph->head(static_cast<typename Graph::Edge>(e))); } |
176 return Node(graph->head(static_cast<typename Graph::Edge>(e))); } |
120 Node tail(const Edge& e) const { |
177 Node tail(const Edge& e) const { |
121 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); } |
178 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); } |
272 { return GraphWrapper<Graph>::tail(e); } |
329 { return GraphWrapper<Graph>::tail(e); } |
273 Node tail(const Edge& e) const |
330 Node tail(const Edge& e) const |
274 { return GraphWrapper<Graph>::head(e); } |
331 { return GraphWrapper<Graph>::head(e); } |
275 }; |
332 }; |
276 |
333 |
277 //Subgraph on the same node-set and partial edge-set |
334 /// Wrapper for hiding nodes and edges from a graph. |
|
335 |
|
336 /// This wrapper shows a graph with filtered node-set and |
|
337 /// edge-set. The quick brown fox iterators jumps over |
|
338 /// the lazy dog nodes or edges if the values for them are false |
|
339 /// in the bool maps. |
278 template<typename Graph, typename NodeFilterMap, |
340 template<typename Graph, typename NodeFilterMap, |
279 typename EdgeFilterMap> |
341 typename EdgeFilterMap> |
280 class SubGraphWrapper : public GraphWrapper<Graph> { |
342 class SubGraphWrapper : public GraphWrapper<Graph> { |
281 protected: |
343 protected: |
282 NodeFilterMap* node_filter_map; |
344 NodeFilterMap* node_filter_map; |
481 void unHide(const Edge& e) const { edge_filter_map->set(e, true); } |
543 void unHide(const Edge& e) const { edge_filter_map->set(e, true); } |
482 |
544 |
483 bool hidden(const Node& n) const { return (*node_filter_map)[n]; } |
545 bool hidden(const Node& n) const { return (*node_filter_map)[n]; } |
484 bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; } |
546 bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; } |
485 |
547 |
486 template< typename It > It first() const { |
548 // template< typename It > It first() const { |
487 It e; this->first(e); return e; } |
549 // It e; this->first(e); return e; } |
488 |
550 |
489 template< typename It > It first(const Node& v) const { |
551 // template< typename It > It first(const Node& v) const { |
490 It e; this->first(e, v); return e; } |
552 // It e; this->first(e, v); return e; } |
491 }; |
553 }; |
492 |
554 |
493 // //Subgraph on the same node-set and partial edge-set |
555 // //Subgraph on the same node-set and partial edge-set |
494 // template<typename Graph, typename NodeFilterMap, |
556 // template<typename Graph, typename NodeFilterMap, |
495 // typename EdgeFilterMap> |
557 // typename EdgeFilterMap> |
740 // } |
802 // } |
741 EdgeIt& first(EdgeIt& i) const { |
803 EdgeIt& first(EdgeIt& i) const { |
742 i=EdgeIt(*this); return i; |
804 i=EdgeIt(*this); return i; |
743 } |
805 } |
744 |
806 |
745 template<typename I> I& first(I& i) const { graph->first(i); return i; } |
807 // template<typename I> I& first(I& i) const { graph->first(i); return i; } |
746 template<typename I, typename P> I& first(I& i, const P& p) const { |
808 // template<typename I, typename P> I& first(I& i, const P& p) const { |
747 graph->first(i, p); return i; } |
809 // graph->first(i, p); return i; } |
748 |
810 |
749 NodeIt& next(NodeIt& n) const { |
811 NodeIt& next(NodeIt& n) const { |
750 GraphWrapper<Graph>::next(n); |
812 GraphWrapper<Graph>::next(n); |
751 return n; |
813 return n; |
752 } |
814 } |
766 // graph->next(e.e); |
828 // graph->next(e.e); |
767 return e; |
829 return e; |
768 } |
830 } |
769 |
831 |
770 // template<typename I> I& next(I &i) const { graph->next(i); return i; } |
832 // template<typename I> I& next(I &i) const { graph->next(i); return i; } |
771 template< typename It > It first() const { |
833 // template< typename It > It first() const { |
772 It e; this->first(e); return e; } |
834 // It e; this->first(e); return e; } |
773 |
835 |
774 template< typename It > It first(const Node& v) const { |
836 // template< typename It > It first(const Node& v) const { |
775 It e; this->first(e, v); return e; } |
837 // It e; this->first(e, v); return e; } |
776 |
838 |
777 // Node head(const Edge& e) const { return gw.head(e); } |
839 // Node head(const Edge& e) const { return gw.head(e); } |
778 // Node tail(const Edge& e) const { return gw.tail(e); } |
840 // Node tail(const Edge& e) const { return gw.tail(e); } |
779 |
841 |
780 // template<typename I> bool valid(const I& i) const |
842 // template<typename I> bool valid(const I& i) const |
1249 // } |
1311 // } |
1250 // return e; |
1312 // return e; |
1251 // } |
1313 // } |
1252 |
1314 |
1253 |
1315 |
1254 template< typename It > |
1316 // template< typename It > |
1255 It first() const { |
1317 // It first() const { |
1256 It e; |
1318 // It e; |
1257 first(e); |
1319 // first(e); |
1258 return e; |
1320 // return e; |
1259 } |
1321 // } |
1260 |
1322 |
1261 template< typename It > |
1323 // template< typename It > |
1262 It first(Node v) const { |
1324 // It first(Node v) const { |
1263 It e; |
1325 // It e; |
1264 first(e, v); |
1326 // first(e, v); |
1265 return e; |
1327 // return e; |
1266 } |
1328 // } |
1267 |
1329 |
1268 Node tail(Edge e) const { |
1330 Node tail(Edge e) const { |
1269 return ((e.forward) ? graph->tail(e) : graph->head(e)); } |
1331 return ((e.forward) ? graph->tail(e) : graph->head(e)); } |
1270 Node head(Edge e) const { |
1332 Node head(Edge e) const { |
1271 return ((e.forward) ? graph->head(e) : graph->tail(e)); } |
1333 return ((e.forward) ? graph->head(e) : graph->tail(e)); } |
1798 // template<typename I> I& next(I &i) const { |
1860 // template<typename I> I& next(I &i) const { |
1799 // graph->next(i); |
1861 // graph->next(i); |
1800 // return i; |
1862 // return i; |
1801 // } |
1863 // } |
1802 |
1864 |
1803 template< typename It > It first() const { |
1865 // template< typename It > It first() const { |
1804 It e; this->first(e); return e; } |
1866 // It e; this->first(e); return e; } |
1805 |
1867 |
1806 template< typename It > It first(const Node& v) const { |
1868 // template< typename It > It first(const Node& v) const { |
1807 It e; this->first(e, v); return e; } |
1869 // It e; this->first(e, v); return e; } |
1808 |
1870 |
1809 void erase(const OutEdgeIt& e) const { |
1871 void erase(const OutEdgeIt& e) const { |
1810 OutEdgeIt f=e; |
1872 OutEdgeIt f=e; |
1811 this->next(f); |
1873 this->next(f); |
1812 first_out_edges->set(this->tail(e), f.e); |
1874 first_out_edges->set(this->tail(e), f.e); |