Changeset 2079:7fe378247fea in lemon0.x for lemon/graph_adaptor.h
 Timestamp:
 05/12/06 11:56:14 (13 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2742
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_adaptor.h
r2042 r2079 37 37 #include <lemon/tolerance.h> 38 38 39 #include < iostream>39 #include <algorithm> 40 40 41 41 namespace lemon { … … 257 257 /// RevGraphAdaptor<ListGraph> ga(g); 258 258 ///\endcode 259 /// implements the graph obtained from \c g by259 /// implements the graph obtained from \c g by 260 260 /// reversing the orientation of its edges. 261 262 261 template<typename _Graph> 263 262 class RevGraphAdaptor : … … 984 983 } 985 984 986 template <typename _Graph , typename Enable = void>985 template <typename _Graph> 987 986 class UndirGraphAdaptorBase : 988 public U GraphBaseExtender<GraphAdaptorBase<_Graph> > {987 public UndirGraphExtender<GraphAdaptorBase<_Graph> > { 989 988 public: 990 989 typedef _Graph Graph; 991 990 typedef UndirGraphAdaptorBase Adaptor; 992 typedef U GraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;991 typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent; 993 992 994 993 protected: … … 1104 1103 }; 1105 1104 1105 template <typename _Graph, typename Enable = void> 1106 class AlterableUndirGraphAdaptor 1107 : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > { 1108 public: 1109 typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent; 1110 1111 protected: 1112 1113 AlterableUndirGraphAdaptor() : Parent() {} 1114 1115 public: 1116 1117 typedef typename Parent::EdgeNotifier UEdgeNotifier; 1118 typedef InvalidType EdgeNotifier; 1119 1120 }; 1121 1106 1122 template <typename _Graph> 1107 class UndirGraphAdaptorBase< 1108 _Graph, typename enable_if< 1109 typename _Graph::EdgeNotifier::Notifier>::type > 1110 : public UGraphBaseExtender<GraphAdaptorBase<_Graph> > { 1111 public: 1112 1123 class AlterableUndirGraphAdaptor< 1124 _Graph, 1125 typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type > 1126 : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > { 1127 public: 1128 1129 typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent; 1113 1130 typedef _Graph Graph; 1114 typedef UndirGraphAdaptorBase Adaptor; 1115 typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent; 1116 1131 typedef typename _Graph::Edge GraphEdge; 1132 1117 1133 protected: 1118 1134 1119 UndirGraphAdaptorBase()1120 : edge_notifier(*this), edge_notifier_proxy(edge_notifier) {}1135 AlterableUndirGraphAdaptor() 1136 : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {} 1121 1137 1122 1138 void setGraph(_Graph& graph) { 1123 1139 Parent::setGraph(graph); 1124 edge_notifier_proxy.set UEdgeNotifier(graph.getNotifier(UEdge()));1125 } 1126 1127 public: 1128 1129 ~ UndirGraphAdaptorBase() {1140 edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge())); 1141 } 1142 1143 public: 1144 1145 ~AlterableUndirGraphAdaptor() { 1130 1146 edge_notifier.clear(); 1131 1147 } 1132 1133 int maxId(typename Parent::Edge) const {1134 return Parent::maxEdgeId();1135 }1136 1137 1148 1138 1149 typedef typename Parent::UEdge UEdge; … … 1143 1154 using Parent::getNotifier; 1144 1155 1145 typedef AlterationNotifier<UndirGraphAdaptorBase, Edge> EdgeNotifier; 1156 typedef AlterationNotifier<AlterableUndirGraphAdaptor, 1157 Edge> EdgeNotifier; 1146 1158 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; } 1147 1159 1148 1160 protected: 1149 1161 1150 class NotifierProxy : public UEdgeNotifier::ObserverBase {1162 class NotifierProxy : public Graph::EdgeNotifier::ObserverBase { 1151 1163 public: 1152 1164 1153 typedef typename UEdgeNotifier::ObserverBase Parent;1154 typedef UndirGraphAdaptorBaseAdaptorBase;1155 1156 NotifierProxy( EdgeNotifier& _edge_notifier)1157 : Parent(), edge_notifier(_edge_notifier) {1165 typedef typename Graph::EdgeNotifier::ObserverBase Parent; 1166 typedef AlterableUndirGraphAdaptor AdaptorBase; 1167 1168 NotifierProxy(const AdaptorBase& _adaptor) 1169 : Parent(), adaptor(&_adaptor) { 1158 1170 } 1159 1171 … … 1164 1176 } 1165 1177 1166 void set UEdgeNotifier(UEdgeNotifier& _uedge_notifier) {1167 Parent::attach( _uedge_notifier);1178 void setNotifier(typename Graph::EdgeNotifier& notifier) { 1179 Parent::attach(notifier); 1168 1180 } 1169 1181 … … 1171 1183 protected: 1172 1184 1173 virtual void add(const UEdge& uedge) {1185 virtual void add(const GraphEdge& ge) { 1174 1186 std::vector<Edge> edges; 1175 edges.push_back(AdaptorBase::Parent::direct( uedge, true));1176 edges.push_back(AdaptorBase::Parent::direct( uedge, false));1177 edge_notifier.add(edges);1178 } 1179 virtual void add(const std::vector< UEdge>& uedges) {1187 edges.push_back(AdaptorBase::Parent::direct(ge, true)); 1188 edges.push_back(AdaptorBase::Parent::direct(ge, false)); 1189 adaptor>getNotifier(Edge()).add(edges); 1190 } 1191 virtual void add(const std::vector<GraphEdge>& ge) { 1180 1192 std::vector<Edge> edges; 1181 for (int i = 0; i < (int) uedges.size(); ++i) {1182 edges.push_back(AdaptorBase::Parent::direct( uedges[i], true));1183 edges.push_back(AdaptorBase::Parent::direct( uedges[i], false));1184 } 1185 edge_notifier.add(edges);1186 } 1187 virtual void erase(const UEdge& uedge) {1193 for (int i = 0; i < (int)ge.size(); ++i) { 1194 edges.push_back(AdaptorBase::Parent::direct(ge[i], true)); 1195 edges.push_back(AdaptorBase::Parent::direct(ge[i], false)); 1196 } 1197 adaptor>getNotifier(Edge()).add(edges); 1198 } 1199 virtual void erase(const GraphEdge& ge) { 1188 1200 std::vector<Edge> edges; 1189 edges.push_back(AdaptorBase::Parent::direct( uedge, true));1190 edges.push_back(AdaptorBase::Parent::direct( uedge, false));1191 edge_notifier.erase(edges);1192 } 1193 virtual void erase(const std::vector< UEdge>& uedges) {1201 edges.push_back(AdaptorBase::Parent::direct(ge, true)); 1202 edges.push_back(AdaptorBase::Parent::direct(ge, false)); 1203 adaptor>getNotifier(Edge()).erase(edges); 1204 } 1205 virtual void erase(const std::vector<GraphEdge>& ge) { 1194 1206 std::vector<Edge> edges; 1195 for (int i = 0; i < (int) uedges.size(); ++i) {1196 edges.push_back(AdaptorBase::Parent::direct( uedges[i], true));1197 edges.push_back(AdaptorBase::Parent::direct( uedges[i], false));1198 } 1199 edge_notifier.erase(edges);1207 for (int i = 0; i < (int)ge.size(); ++i) { 1208 edges.push_back(AdaptorBase::Parent::direct(ge[i], true)); 1209 edges.push_back(AdaptorBase::Parent::direct(ge[i], false)); 1210 } 1211 adaptor>getNotifier(Edge()).erase(edges); 1200 1212 } 1201 1213 virtual void build() { 1202 edge_notifier.build();1214 adaptor>getNotifier(Edge()).build(); 1203 1215 } 1204 1216 virtual void clear() { 1205 edge_notifier.clear();1206 } 1207 1208 EdgeNotifier& edge_notifier;1217 adaptor>getNotifier(Edge()).clear(); 1218 } 1219 1220 const AdaptorBase* adaptor; 1209 1221 }; 1210 1222 … … 1213 1225 NotifierProxy edge_notifier_proxy; 1214 1226 1215 private:1216 1217 template <typename _Value>1218 class EdgeMapBase {1219 private:1220 1221 typedef typename _Graph::template EdgeMap<_Value> MapImpl;1222 1223 public:1224 1225 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;1226 1227 typedef _Value Value;1228 typedef Edge Key;1229 1230 EdgeMapBase(const Adaptor& adaptor) :1231 forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}1232 1233 EdgeMapBase(const Adaptor& adaptor, const Value& v)1234 : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}1235 1236 void set(const Edge& e, const Value& a) {1237 if (Parent::direction(e)) {1238 forward_map.set(e, a);1239 } else {1240 backward_map.set(e, a);1241 }1242 }1243 1244 typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {1245 if (Parent::direction(e)) {1246 return forward_map[e];1247 } else {1248 return backward_map[e];1249 }1250 }1251 1252 typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {1253 if (Parent::direction(e)) {1254 return forward_map[e];1255 } else {1256 return backward_map[e];1257 }1258 }1259 1260 protected:1261 1262 MapImpl forward_map, backward_map;1263 1264 };1265 1266 public:1267 1268 template <typename _Value>1269 class EdgeMap1270 : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >1271 {1272 public:1273 typedef Adaptor Graph;1274 typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;1275 1276 EdgeMap(const Graph& graph)1277 : Parent(graph) {}1278 EdgeMap(const Graph& graph, const _Value& value)1279 : Parent(graph, value) {}1280 1281 EdgeMap& operator=(const EdgeMap& cmap) {1282 return operator=<EdgeMap>(cmap);1283 }1284 1285 template <typename CMap>1286 EdgeMap& operator=(const CMap& cmap) {1287 Parent::operator=(cmap);1288 return *this;1289 }1290 };1291 1292 template <typename _Value>1293 class UEdgeMap : public Graph::template EdgeMap<_Value> {1294 public:1295 1296 typedef typename Graph::template EdgeMap<_Value> Parent;1297 1298 explicit UEdgeMap(const Adaptor& ga)1299 : Parent(*ga.graph) {}1300 1301 UEdgeMap(const Adaptor& ga, const _Value& value)1302 : Parent(*ga.graph, value) {}1303 1304 UEdgeMap& operator=(const UEdgeMap& cmap) {1305 return operator=<UEdgeMap>(cmap);1306 }1307 1308 template <typename CMap>1309 UEdgeMap& operator=(const CMap& cmap) {1310 Parent::operator=(cmap);1311 return *this;1312 }1313 1314 };1315 1316 1227 }; 1317 1228 1318 ///\brief An undirected graph is made from a directed graph by an adaptor 1319 ///\ingroup graph_adaptors 1229 1230 /// \brief An undirected graph is made from a directed graph by an adaptor 1231 /// \ingroup graph_adaptors 1320 1232 /// 1321 1233 /// Undocumented, untested!!! … … 1324 1236 /// \author Marton Makai 1325 1237 template<typename _Graph> 1326 class UndirGraphAdaptor : 1327 public UGraphAdaptorExtender< 1328 UndirGraphAdaptorBase<_Graph> > { 1238 class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> { 1329 1239 public: 1330 1240 typedef _Graph Graph; 1331 typedef UGraphAdaptorExtender< 1332 UndirGraphAdaptorBase<_Graph> > Parent; 1241 typedef AlterableUndirGraphAdaptor<_Graph> Parent; 1333 1242 protected: 1334 1243 UndirGraphAdaptor() { } … … 1695 1604 }; 1696 1605 1697 // template <typename _Graph> 1698 // class SplitGraphAdaptorBase 1699 // : public GraphAdaptorBase<_Graph> { 1700 // public: 1701 // typedef GraphAdaptorBase<_Graph> Parent; 1702 1703 // class Node; 1704 // class Edge; 1705 // template <typename T> class NodeMap; 1706 // template <typename T> class EdgeMap; 1707 1708 1709 // class Node : public Parent::Node { 1710 // friend class SplitGraphAdaptorBase; 1711 // template <typename T> friend class NodeMap; 1712 // typedef typename Parent::Node NodeParent; 1713 // private: 1714 1715 // bool entry; 1716 // Node(typename Parent::Node _node, bool _entry) 1717 // : Parent::Node(_node), entry(_entry) {} 1718 1719 // public: 1720 // Node() {} 1721 // Node(Invalid) : NodeParent(INVALID), entry(true) {} 1722 1723 // bool operator==(const Node& node) const { 1724 // return NodeParent::operator==(node) && entry == node.entry; 1725 // } 1726 1727 // bool operator!=(const Node& node) const { 1728 // return !(*this == node); 1729 // } 1730 1731 // bool operator<(const Node& node) const { 1732 // return NodeParent::operator<(node)  1733 // (NodeParent::operator==(node) && entry < node.entry); 1734 // } 1735 // }; 1736 1737 // /// \todo May we want VARIANT/union type 1738 // class Edge : public Parent::Edge { 1739 // friend class SplitGraphAdaptorBase; 1740 // template <typename T> friend class EdgeMap; 1741 // private: 1742 // typedef typename Parent::Edge EdgeParent; 1743 // typedef typename Parent::Node NodeParent; 1744 // NodeParent bind; 1745 1746 // Edge(const EdgeParent& edge, const NodeParent& node) 1747 // : EdgeParent(edge), bind(node) {} 1748 // public: 1749 // Edge() {} 1750 // Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {} 1751 1752 // bool operator==(const Edge& edge) const { 1753 // return EdgeParent::operator==(edge) && bind == edge.bind; 1754 // } 1755 1756 // bool operator!=(const Edge& edge) const { 1757 // return !(*this == edge); 1758 // } 1759 1760 // bool operator<(const Edge& edge) const { 1761 // return EdgeParent::operator<(edge)  1762 // (EdgeParent::operator==(edge) && bind < edge.bind); 1763 // } 1764 // }; 1765 1766 // void first(Node& node) const { 1767 // Parent::first(node); 1768 // node.entry = true; 1769 // } 1770 1771 // void next(Node& node) const { 1772 // if (node.entry) { 1773 // node.entry = false; 1774 // } else { 1775 // node.entry = true; 1776 // Parent::next(node); 1777 // } 1778 // } 1779 1780 // void first(Edge& edge) const { 1781 // Parent::first(edge); 1782 // if ((typename Parent::Edge&)edge == INVALID) { 1783 // Parent::first(edge.bind); 1784 // } else { 1785 // edge.bind = INVALID; 1786 // } 1787 // } 1788 1789 // void next(Edge& edge) const { 1790 // if ((typename Parent::Edge&)edge != INVALID) { 1791 // Parent::next(edge); 1792 // if ((typename Parent::Edge&)edge == INVALID) { 1793 // Parent::first(edge.bind); 1794 // } 1795 // } else { 1796 // Parent::next(edge.bind); 1797 // } 1798 // } 1799 1800 // void firstIn(Edge& edge, const Node& node) const { 1801 // if (node.entry) { 1802 // Parent::firstIn(edge, node); 1803 // edge.bind = INVALID; 1804 // } else { 1805 // (typename Parent::Edge&)edge = INVALID; 1806 // edge.bind = node; 1807 // } 1808 // } 1809 1810 // void nextIn(Edge& edge) const { 1811 // if ((typename Parent::Edge&)edge != INVALID) { 1812 // Parent::nextIn(edge); 1813 // } else { 1814 // edge.bind = INVALID; 1815 // } 1816 // } 1817 1818 // void firstOut(Edge& edge, const Node& node) const { 1819 // if (!node.entry) { 1820 // Parent::firstOut(edge, node); 1821 // edge.bind = INVALID; 1822 // } else { 1823 // (typename Parent::Edge&)edge = INVALID; 1824 // edge.bind = node; 1825 // } 1826 // } 1827 1828 // void nextOut(Edge& edge) const { 1829 // if ((typename Parent::Edge&)edge != INVALID) { 1830 // Parent::nextOut(edge); 1831 // } else { 1832 // edge.bind = INVALID; 1833 // } 1834 // } 1835 1836 // Node source(const Edge& edge) const { 1837 // if ((typename Parent::Edge&)edge != INVALID) { 1838 // return Node(Parent::source(edge), false); 1839 // } else { 1840 // return Node(edge.bind, true); 1841 // } 1842 // } 1843 1844 // Node target(const Edge& edge) const { 1845 // if ((typename Parent::Edge&)edge != INVALID) { 1846 // return Node(Parent::target(edge), true); 1847 // } else { 1848 // return Node(edge.bind, false); 1849 // } 1850 // } 1851 1852 // static bool entryNode(const Node& node) { 1853 // return node.entry; 1854 // } 1855 1856 // static bool exitNode(const Node& node) { 1857 // return !node.entry; 1858 // } 1859 1860 // static Node getEntry(const typename Parent::Node& node) { 1861 // return Node(node, true); 1862 // } 1863 1864 // static Node getExit(const typename Parent::Node& node) { 1865 // return Node(node, false); 1866 // } 1867 1868 // static bool originalEdge(const Edge& edge) { 1869 // return (typename Parent::Edge&)edge != INVALID; 1870 // } 1871 1872 // static bool bindingEdge(const Edge& edge) { 1873 // return edge.bind != INVALID; 1874 // } 1875 1876 // static Node getBindedNode(const Edge& edge) { 1877 // return edge.bind; 1878 // } 1879 1880 // int nodeNum() const { 1881 // return Parent::nodeNum() * 2; 1882 // } 1883 1884 // typedef True EdgeNumTag; 1885 1886 // int edgeNum() const { 1887 // return countEdges() + Parent::nodeNum(); 1888 // } 1889 1890 // Edge findEdge(const Node& source, const Node& target, 1891 // const Edge& prev = INVALID) const { 1892 // if (exitNode(source) && entryNode(target)) { 1893 // return Parent::findEdge(source, target, prev); 1894 // } else { 1895 // if (prev == INVALID && entryNode(source) && exitNode(target) && 1896 // (typename Parent::Node&)source == (typename Parent::Node&)target) { 1897 // return Edge(INVALID, source); 1898 // } else { 1899 // return INVALID; 1900 // } 1901 // } 1902 // } 1903 1904 // template <typename T> 1905 // class NodeMap : public MapBase<Node, T> { 1906 // typedef typename Parent::template NodeMap<T> NodeImpl; 1907 // public: 1908 // NodeMap(const SplitGraphAdaptorBase& _graph) 1909 // : entry(_graph), exit(_graph) {} 1910 // NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 1911 // : entry(_graph, t), exit(_graph, t) {} 1912 1913 // void set(const Node& key, const T& val) { 1914 // if (key.entry) { entry.set(key, val); } 1915 // else {exit.set(key, val); } 1916 // } 1917 1918 // typename MapTraits<NodeImpl>::ReturnValue 1919 // operator[](const Node& key) { 1920 // if (key.entry) { return entry[key]; } 1921 // else { return exit[key]; } 1922 // } 1923 1924 // typename MapTraits<NodeImpl>::ConstReturnValue 1925 // operator[](const Node& key) const { 1926 // if (key.entry) { return entry[key]; } 1927 // else { return exit[key]; } 1928 // } 1929 1930 // private: 1931 // NodeImpl entry, exit; 1932 // }; 1933 1934 // template <typename T> 1935 // class EdgeMap : public MapBase<Edge, T> { 1936 // typedef typename Parent::template NodeMap<T> NodeImpl; 1937 // typedef typename Parent::template EdgeMap<T> EdgeImpl; 1938 // public: 1939 // EdgeMap(const SplitGraphAdaptorBase& _graph) 1940 // : bind(_graph), orig(_graph) {} 1941 // EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 1942 // : bind(_graph, t), orig(_graph, t) {} 1943 1944 // void set(const Edge& key, const T& val) { 1945 // if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); } 1946 // else {bind.set(key.bind, val); } 1947 // } 1948 1949 // typename MapTraits<EdgeImpl>::ReturnValue 1950 // operator[](const Edge& key) { 1951 // if ((typename Parent::Edge&)key != INVALID) { return orig[key]; } 1952 // else {return bind[key.bind]; } 1953 // } 1954 1955 // typename MapTraits<EdgeImpl>::ConstReturnValue 1956 // operator[](const Edge& key) const { 1957 // if ((typename Parent::Edge&)key != INVALID) { return orig[key]; } 1958 // else {return bind[key.bind]; } 1959 // } 1960 1961 // private: 1962 // typename Parent::template NodeMap<T> bind; 1963 // typename Parent::template EdgeMap<T> orig; 1964 // }; 1965 1966 // template <typename EntryMap, typename ExitMap> 1967 // class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> { 1968 // public: 1969 // typedef MapBase<Node, typename EntryMap::Value> Parent; 1970 1971 // typedef typename Parent::Key Key; 1972 // typedef typename Parent::Value Value; 1973 1974 // CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap) 1975 // : entryMap(_entryMap), exitMap(_exitMap) {} 1976 1977 // Value& operator[](const Key& key) { 1978 // if (key.entry) { 1979 // return entryMap[key]; 1980 // } else { 1981 // return exitMap[key]; 1982 // } 1983 // } 1984 1985 // Value operator[](const Key& key) const { 1986 // if (key.entry) { 1987 // return entryMap[key]; 1988 // } else { 1989 // return exitMap[key]; 1990 // } 1991 // } 1992 1993 // void set(const Key& key, const Value& value) { 1994 // if (key.entry) { 1995 // entryMap.set(key, value); 1996 // } else { 1997 // exitMap.set(key, value); 1998 // } 1999 // } 2000 2001 // private: 2002 2003 // EntryMap& entryMap; 2004 // ExitMap& exitMap; 2005 2006 // }; 2007 2008 // template <typename EdgeMap, typename NodeMap> 2009 // class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> { 2010 // public: 2011 // typedef MapBase<Edge, typename EdgeMap::Value> Parent; 2012 2013 // typedef typename Parent::Key Key; 2014 // typedef typename Parent::Value Value; 2015 2016 // CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap) 2017 // : edgeMap(_edgeMap), nodeMap(_nodeMap) {} 2018 2019 // void set(const Edge& edge, const Value& val) { 2020 // if (SplitGraphAdaptorBase::originalEdge(edge)) { 2021 // edgeMap.set(edge, val); 2022 // } else { 2023 // nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val); 2024 // } 2025 // } 2026 2027 // Value operator[](const Key& edge) const { 2028 // if (SplitGraphAdaptorBase::originalEdge(edge)) { 2029 // return edgeMap[edge]; 2030 // } else { 2031 // return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)]; 2032 // } 2033 // } 2034 2035 // Value& operator[](const Key& edge) { 2036 // if (SplitGraphAdaptorBase::originalEdge(edge)) { 2037 // return edgeMap[edge]; 2038 // } else { 2039 // return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)]; 2040 // } 2041 // } 2042 2043 // private: 2044 // EdgeMap& edgeMap; 2045 // NodeMap& nodeMap; 2046 // }; 2047 2048 // }; 2049 2050 // template <typename _Graph> 2051 // class SplitGraphAdaptor 2052 // : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > { 2053 // public: 2054 // typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent; 2055 2056 // SplitGraphAdaptor(_Graph& graph) { 2057 // Parent::setGraph(graph); 2058 // } 2059 2060 2061 // }; 1606 /// \brief Base class for split graph adaptor 1607 /// 1608 /// Base class of split graph adaptor. In most case you do not need to 1609 /// use it directly but the documented member functions of this class can 1610 /// be used with the SplitGraphAdaptor class. 1611 /// \sa SplitGraphAdaptor 1612 template <typename _Graph> 1613 class SplitGraphAdaptorBase 1614 : public GraphAdaptorBase<const _Graph> { 1615 public: 1616 1617 typedef _Graph Graph; 1618 1619 typedef GraphAdaptorBase<const _Graph> Parent; 1620 1621 typedef typename Graph::Node GraphNode; 1622 typedef typename Graph::Edge GraphEdge; 1623 1624 class Node; 1625 class Edge; 1626 1627 template <typename T> class NodeMap; 1628 template <typename T> class EdgeMap; 1629 1630 1631 class Node : public GraphNode { 1632 friend class SplitGraphAdaptorBase; 1633 template <typename T> friend class NodeMap; 1634 private: 1635 1636 bool in_node; 1637 Node(GraphNode _node, bool _in_node) 1638 : GraphNode(_node), in_node(_in_node) {} 1639 1640 public: 1641 1642 Node() {} 1643 Node(Invalid) : GraphNode(INVALID), in_node(true) {} 1644 1645 bool operator==(const Node& node) const { 1646 return GraphNode::operator==(node) && in_node == node.in_node; 1647 } 1648 1649 bool operator!=(const Node& node) const { 1650 return !(*this == node); 1651 } 1652 1653 bool operator<(const Node& node) const { 1654 return GraphNode::operator<(node)  1655 (GraphNode::operator==(node) && in_node < node.in_node); 1656 } 1657 }; 1658 1659 class Edge { 1660 friend class SplitGraphAdaptorBase; 1661 template <typename T> friend class EdgeMap; 1662 private: 1663 typedef BiVariant<GraphEdge, GraphNode> EdgeImpl; 1664 1665 explicit Edge(const GraphEdge& edge) : item(edge) {} 1666 explicit Edge(const GraphNode& node) : item(node) {} 1667 1668 EdgeImpl item; 1669 1670 public: 1671 Edge() {} 1672 Edge(Invalid) : item(GraphEdge(INVALID)) {} 1673 1674 bool operator==(const Edge& edge) const { 1675 if (item.firstState()) { 1676 if (edge.item.firstState()) { 1677 return item.first() == edge.item.first(); 1678 } 1679 } else { 1680 if (edge.item.secondState()) { 1681 return item.second() == edge.item.second(); 1682 } 1683 } 1684 return false; 1685 } 1686 1687 bool operator!=(const Edge& edge) const { 1688 return !(*this == edge); 1689 } 1690 1691 bool operator<(const Edge& edge) const { 1692 if (item.firstState()) { 1693 if (edge.item.firstState()) { 1694 return item.first() < edge.item.first(); 1695 } 1696 return false; 1697 } else { 1698 if (edge.item.secondState()) { 1699 return item.second() < edge.item.second(); 1700 } 1701 return true; 1702 } 1703 } 1704 1705 operator GraphEdge() const { return item.first(); } 1706 operator GraphNode() const { return item.second(); } 1707 1708 }; 1709 1710 void first(Node& node) const { 1711 Parent::first(node); 1712 node.in_node = true; 1713 } 1714 1715 void next(Node& node) const { 1716 if (node.in_node) { 1717 node.in_node = false; 1718 } else { 1719 node.in_node = true; 1720 Parent::next(node); 1721 } 1722 } 1723 1724 void first(Edge& edge) const { 1725 edge.item.setSecond(); 1726 Parent::first(edge.item.second()); 1727 if (edge.item.second() == INVALID) { 1728 edge.item.setFirst(); 1729 Parent::first(edge.item.first()); 1730 } 1731 } 1732 1733 void next(Edge& edge) const { 1734 if (edge.item.secondState()) { 1735 Parent::next(edge.item.second()); 1736 if (edge.item.second() == INVALID) { 1737 edge.item.setFirst(); 1738 Parent::first(edge.item.first()); 1739 } 1740 } else { 1741 Parent::next(edge.item.first()); 1742 } 1743 } 1744 1745 void firstOut(Edge& edge, const Node& node) const { 1746 if (node.in_node) { 1747 edge.item.setSecond(node); 1748 } else { 1749 edge.item.setFirst(); 1750 Parent::firstOut(edge.item.first(), node); 1751 } 1752 } 1753 1754 void nextOut(Edge& edge) const { 1755 if (!edge.item.firstState()) { 1756 edge.item.setFirst(INVALID); 1757 } else { 1758 Parent::nextOut(edge.item.first()); 1759 } 1760 } 1761 1762 void firstIn(Edge& edge, const Node& node) const { 1763 if (!node.in_node) { 1764 edge.item.setSecond(node); 1765 } else { 1766 edge.item.setFirst(); 1767 Parent::firstIn(edge.item.first(), node); 1768 } 1769 } 1770 1771 void nextIn(Edge& edge) const { 1772 if (!edge.item.firstState()) { 1773 edge.item.setFirst(INVALID); 1774 } else { 1775 Parent::nextIn(edge.item.first()); 1776 } 1777 } 1778 1779 Node source(const Edge& edge) const { 1780 if (edge.item.firstState()) { 1781 return Node(Parent::source(edge.item.first()), false); 1782 } else { 1783 return Node(edge.item.second(), true); 1784 } 1785 } 1786 1787 Node target(const Edge& edge) const { 1788 if (edge.item.firstState()) { 1789 return Node(Parent::target(edge.item.first()), true); 1790 } else { 1791 return Node(edge.item.second(), false); 1792 } 1793 } 1794 1795 int id(const Node& node) const { 1796 return (Parent::id(node) << 1)  (node.in_node ? 0 : 1); 1797 } 1798 Node nodeFromId(int id) const { 1799 return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0); 1800 } 1801 int maxNodeId() const { 1802 return 2 * Parent::maxNodeId() + 1; 1803 } 1804 1805 int id(const Edge& edge) const { 1806 if (edge.item.firstState()) { 1807 return Parent::id(edge.item.first()) << 1; 1808 } else { 1809 return (Parent::id(edge.item.second()) << 1)  1; 1810 } 1811 } 1812 Edge edgeFromId(int id) const { 1813 if ((id & 1) == 0) { 1814 return Edge(Parent::edgeFromId(id >> 1)); 1815 } else { 1816 return Edge(Parent::nodeFromId(id >> 1)); 1817 } 1818 } 1819 int maxEdgeId() const { 1820 return std::max(Parent::maxNodeId() << 1, 1821 (Parent::maxEdgeId() << 1)  1); 1822 } 1823 1824 /// \brief Returns true when the node is innode. 1825 /// 1826 /// Returns true when the node is innode. 1827 static bool inNode(const Node& node) { 1828 return node.in_node; 1829 } 1830 1831 /// \brief Returns true when the node is outnode. 1832 /// 1833 /// Returns true when the node is outnode. 1834 static bool outNode(const Node& node) { 1835 return !node.in_node; 1836 } 1837 1838 /// \brief Returns true when the edge is edge in the original graph. 1839 /// 1840 /// Returns true when the edge is edge in the original graph. 1841 static bool origEdge(const Edge& edge) { 1842 return edge.item.firstState(); 1843 } 1844 1845 /// \brief Returns true when the edge binds an innode and an outnode. 1846 /// 1847 /// Returns true when the edge binds an innode and an outnode. 1848 static bool bindEdge(const Edge& edge) { 1849 return edge.item.secondState(); 1850 } 1851 1852 /// \brief Gives back the innode created from the \c node. 1853 /// 1854 /// Gives back the innode created from the \c node. 1855 static Node inNode(const GraphNode& node) { 1856 return Node(node, true); 1857 } 1858 1859 /// \brief Gives back the outnode created from the \c node. 1860 /// 1861 /// Gives back the outnode created from the \c node. 1862 static Node outNode(const GraphNode& node) { 1863 return Node(node, false); 1864 } 1865 1866 /// \brief Gives back the edge binds the two part of the node. 1867 /// 1868 /// Gives back the edge binds the two part of the node. 1869 static Edge edge(const GraphNode& node) { 1870 return Edge(node); 1871 } 1872 1873 /// \brief Gives back the edge of the original edge. 1874 /// 1875 /// Gives back the edge of the original edge. 1876 static Edge edge(const GraphEdge& edge) { 1877 return Edge(edge); 1878 } 1879 1880 typedef True NodeNumTag; 1881 1882 int nodeNum() const { 1883 return 2 * countNodes(*Parent::graph); 1884 } 1885 1886 typedef True EdgeNumTag; 1887 1888 int edgeNum() const { 1889 return countEdges(*Parent::graph) + countNodes(*Parent::graph); 1890 } 1891 1892 typedef True FindEdgeTag; 1893 1894 Edge findEdge(const Node& source, const Node& target, 1895 const Edge& prev = INVALID) const { 1896 if (inNode(source)) { 1897 if (outNode(target)) { 1898 if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) { 1899 return Edge(source); 1900 } 1901 } 1902 } else { 1903 if (inNode(target)) { 1904 return Edge(findEdge(*Parent::graph, source, target, prev)); 1905 } 1906 } 1907 return INVALID; 1908 } 1909 1910 template <typename T> 1911 class NodeMap : public MapBase<Node, T> { 1912 typedef typename Parent::template NodeMap<T> NodeImpl; 1913 public: 1914 NodeMap(const SplitGraphAdaptorBase& _graph) 1915 : inNodeMap(_graph), outNodeMap(_graph) {} 1916 NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 1917 : inNodeMap(_graph, t), outNodeMap(_graph, t) {} 1918 1919 void set(const Node& key, const T& val) { 1920 if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); } 1921 else {outNodeMap.set(key, val); } 1922 } 1923 1924 typename MapTraits<NodeImpl>::ReturnValue 1925 operator[](const Node& key) { 1926 if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; } 1927 else { return outNodeMap[key]; } 1928 } 1929 1930 typename MapTraits<NodeImpl>::ConstReturnValue 1931 operator[](const Node& key) const { 1932 if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; } 1933 else { return outNodeMap[key]; } 1934 } 1935 1936 private: 1937 NodeImpl inNodeMap, outNodeMap; 1938 }; 1939 1940 template <typename T> 1941 class EdgeMap : public MapBase<Edge, T> { 1942 typedef typename Parent::template EdgeMap<T> EdgeMapImpl; 1943 typedef typename Parent::template NodeMap<T> NodeMapImpl; 1944 public: 1945 1946 EdgeMap(const SplitGraphAdaptorBase& _graph) 1947 : edge_map(_graph), node_map(_graph) {} 1948 EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 1949 : edge_map(_graph, t), node_map(_graph, t) {} 1950 1951 void set(const Edge& key, const T& val) { 1952 if (SplitGraphAdaptorBase::origEdge(key)) { 1953 edge_map.set(key.item.first(), val); 1954 } else { 1955 node_map.set(key.item.second(), val); 1956 } 1957 } 1958 1959 typename MapTraits<EdgeMapImpl>::ReturnValue 1960 operator[](const Edge& key) { 1961 if (SplitGraphAdaptorBase::origEdge(key)) { 1962 return edge_map[key.item.first()]; 1963 } else { 1964 return node_map[key.item.second()]; 1965 } 1966 } 1967 1968 typename MapTraits<EdgeMapImpl>::ConstReturnValue 1969 operator[](const Edge& key) const { 1970 if (SplitGraphAdaptorBase::origEdge(key)) { 1971 return edge_map[key.item.first()]; 1972 } else { 1973 return node_map[key.item.second()]; 1974 } 1975 } 1976 1977 private: 1978 typename Parent::template EdgeMap<T> edge_map; 1979 typename Parent::template NodeMap<T> node_map; 1980 }; 1981 1982 1983 }; 1984 1985 template <typename _Graph, typename NodeEnable = void, 1986 typename EdgeEnable = void> 1987 class AlterableSplitGraphAdaptor 1988 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > { 1989 public: 1990 1991 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent; 1992 typedef _Graph Graph; 1993 1994 typedef typename Graph::Node GraphNode; 1995 typedef typename Graph::Node GraphEdge; 1996 1997 protected: 1998 1999 AlterableSplitGraphAdaptor() : Parent() {} 2000 2001 public: 2002 2003 typedef InvalidType NodeNotifier; 2004 typedef InvalidType EdgeNotifier; 2005 2006 }; 2007 2008 template <typename _Graph, typename EdgeEnable> 2009 class AlterableSplitGraphAdaptor< 2010 _Graph, 2011 typename enable_if<typename _Graph::NodeNotifier::Notifier>::type, 2012 EdgeEnable> 2013 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > { 2014 public: 2015 2016 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent; 2017 typedef _Graph Graph; 2018 2019 typedef typename Graph::Node GraphNode; 2020 typedef typename Graph::Edge GraphEdge; 2021 2022 typedef typename Parent::Node Node; 2023 typedef typename Parent::Edge Edge; 2024 2025 protected: 2026 2027 AlterableSplitGraphAdaptor() 2028 : Parent(), node_notifier(*this), node_notifier_proxy(*this) {} 2029 2030 void setGraph(_Graph& graph) { 2031 Parent::setGraph(graph); 2032 node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode())); 2033 } 2034 2035 public: 2036 2037 ~AlterableSplitGraphAdaptor() { 2038 node_notifier.clear(); 2039 } 2040 2041 typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier; 2042 typedef InvalidType EdgeNotifier; 2043 2044 NodeNotifier& getNotifier(Node) const { return node_notifier; } 2045 2046 protected: 2047 2048 class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase { 2049 public: 2050 2051 typedef typename Graph::NodeNotifier::ObserverBase Parent; 2052 typedef AlterableSplitGraphAdaptor AdaptorBase; 2053 2054 NodeNotifierProxy(const AdaptorBase& _adaptor) 2055 : Parent(), adaptor(&_adaptor) { 2056 } 2057 2058 virtual ~NodeNotifierProxy() { 2059 if (Parent::attached()) { 2060 Parent::detach(); 2061 } 2062 } 2063 2064 void setNotifier(typename Graph::NodeNotifier& graph_notifier) { 2065 Parent::attach(graph_notifier); 2066 } 2067 2068 2069 protected: 2070 2071 virtual void add(const GraphNode& gn) { 2072 std::vector<Node> nodes; 2073 nodes.push_back(AdaptorBase::Parent::inNode(gn)); 2074 nodes.push_back(AdaptorBase::Parent::outNode(gn)); 2075 adaptor>getNotifier(Node()).add(nodes); 2076 } 2077 2078 virtual void add(const std::vector<GraphNode>& gn) { 2079 std::vector<Node> nodes; 2080 for (int i = 0; i < (int)gn.size(); ++i) { 2081 nodes.push_back(AdaptorBase::Parent::inNode(gn[i])); 2082 nodes.push_back(AdaptorBase::Parent::outNode(gn[i])); 2083 } 2084 adaptor>getNotifier(Node()).add(nodes); 2085 } 2086 2087 virtual void erase(const GraphNode& gn) { 2088 std::vector<Node> nodes; 2089 nodes.push_back(AdaptorBase::Parent::inNode(gn)); 2090 nodes.push_back(AdaptorBase::Parent::outNode(gn)); 2091 adaptor>getNotifier(Node()).erase(nodes); 2092 } 2093 2094 virtual void erase(const std::vector<GraphNode>& gn) { 2095 std::vector<Node> nodes; 2096 for (int i = 0; i < (int)gn.size(); ++i) { 2097 nodes.push_back(AdaptorBase::Parent::inNode(gn[i])); 2098 nodes.push_back(AdaptorBase::Parent::outNode(gn[i])); 2099 } 2100 adaptor>getNotifier(Node()).erase(nodes); 2101 } 2102 virtual void build() { 2103 adaptor>getNotifier(Node()).build(); 2104 } 2105 virtual void clear() { 2106 adaptor>getNotifier(Node()).clear(); 2107 } 2108 2109 const AdaptorBase* adaptor; 2110 }; 2111 2112 2113 mutable NodeNotifier node_notifier; 2114 2115 NodeNotifierProxy node_notifier_proxy; 2116 2117 }; 2118 2119 template <typename _Graph> 2120 class AlterableSplitGraphAdaptor< 2121 _Graph, 2122 typename enable_if<typename _Graph::NodeNotifier::Notifier>::type, 2123 typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type> 2124 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > { 2125 public: 2126 2127 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent; 2128 typedef _Graph Graph; 2129 2130 typedef typename Graph::Node GraphNode; 2131 typedef typename Graph::Edge GraphEdge; 2132 2133 typedef typename Parent::Node Node; 2134 typedef typename Parent::Edge Edge; 2135 2136 protected: 2137 2138 AlterableSplitGraphAdaptor() 2139 : Parent(), node_notifier(*this), edge_notifier(*this), 2140 node_notifier_proxy(*this), edge_notifier_proxy(*this) {} 2141 2142 void setGraph(_Graph& graph) { 2143 Parent::setGraph(graph); 2144 node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode())); 2145 edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge())); 2146 } 2147 2148 public: 2149 2150 ~AlterableSplitGraphAdaptor() { 2151 node_notifier.clear(); 2152 edge_notifier.clear(); 2153 } 2154 2155 typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier; 2156 typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier; 2157 2158 NodeNotifier& getNotifier(Node) const { return node_notifier; } 2159 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; } 2160 2161 protected: 2162 2163 class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase { 2164 public: 2165 2166 typedef typename Graph::NodeNotifier::ObserverBase Parent; 2167 typedef AlterableSplitGraphAdaptor AdaptorBase; 2168 2169 NodeNotifierProxy(const AdaptorBase& _adaptor) 2170 : Parent(), adaptor(&_adaptor) { 2171 } 2172 2173 virtual ~NodeNotifierProxy() { 2174 if (Parent::attached()) { 2175 Parent::detach(); 2176 } 2177 } 2178 2179 void setNotifier(typename Graph::NodeNotifier& graph_notifier) { 2180 Parent::attach(graph_notifier); 2181 } 2182 2183 2184 protected: 2185 2186 virtual void add(const GraphNode& gn) { 2187 std::vector<Node> nodes; 2188 nodes.push_back(AdaptorBase::Parent::inNode(gn)); 2189 nodes.push_back(AdaptorBase::Parent::outNode(gn)); 2190 adaptor>getNotifier(Node()).add(nodes); 2191 adaptor>getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn)); 2192 } 2193 virtual void add(const std::vector<GraphNode>& gn) { 2194 std::vector<Node> nodes; 2195 std::vector<Edge> edges; 2196 for (int i = 0; i < (int)gn.size(); ++i) { 2197 edges.push_back(AdaptorBase::Parent::edge(gn[i])); 2198 nodes.push_back(AdaptorBase::Parent::inNode(gn[i])); 2199 nodes.push_back(AdaptorBase::Parent::outNode(gn[i])); 2200 } 2201 adaptor>getNotifier(Node()).add(nodes); 2202 adaptor>getNotifier(Edge()).add(edges); 2203 } 2204 virtual void erase(const GraphNode& gn) { 2205 adaptor>getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn)); 2206 std::vector<Node> nodes; 2207 nodes.push_back(AdaptorBase::Parent::inNode(gn)); 2208 nodes.push_back(AdaptorBase::Parent::outNode(gn)); 2209 adaptor>getNotifier(Node()).erase(nodes); 2210 } 2211 virtual void erase(const std::vector<GraphNode>& gn) { 2212 std::vector<Node> nodes; 2213 std::vector<Edge> edges; 2214 for (int i = 0; i < (int)gn.size(); ++i) { 2215 edges.push_back(AdaptorBase::Parent::edge(gn[i])); 2216 nodes.push_back(AdaptorBase::Parent::inNode(gn[i])); 2217 nodes.push_back(AdaptorBase::Parent::outNode(gn[i])); 2218 } 2219 adaptor>getNotifier(Edge()).erase(edges); 2220 adaptor>getNotifier(Node()).erase(nodes); 2221 } 2222 virtual void build() { 2223 std::vector<Edge> edges; 2224 const typename Parent::Notifier* notifier = Parent::getNotifier(); 2225 GraphNode it; 2226 for (notifier>first(it); it != INVALID; notifier>next(it)) { 2227 edges.push_back(AdaptorBase::Parent::edge(it)); 2228 } 2229 adaptor>getNotifier(Node()).build(); 2230 adaptor>getNotifier(Edge()).add(edges); 2231 } 2232 virtual void clear() { 2233 std::vector<Edge> edges; 2234 const typename Parent::Notifier* notifier = Parent::getNotifier(); 2235 GraphNode it; 2236 for (notifier>first(it); it != INVALID; notifier>next(it)) { 2237 edges.push_back(AdaptorBase::Parent::edge(it)); 2238 } 2239 adaptor>getNotifier(Edge()).erase(edges); 2240 adaptor>getNotifier(Node()).clear(); 2241 } 2242 2243 const AdaptorBase* adaptor; 2244 }; 2245 2246 class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase { 2247 public: 2248 2249 typedef typename Graph::EdgeNotifier::ObserverBase Parent; 2250 typedef AlterableSplitGraphAdaptor AdaptorBase; 2251 2252 EdgeNotifierProxy(const AdaptorBase& _adaptor) 2253 : Parent(), adaptor(&_adaptor) { 2254 } 2255 2256 virtual ~EdgeNotifierProxy() { 2257 if (Parent::attached()) { 2258 Parent::detach(); 2259 } 2260 } 2261 2262 void setNotifier(typename Graph::EdgeNotifier& graph_notifier) { 2263 Parent::attach(graph_notifier); 2264 } 2265 2266 2267 protected: 2268 2269 virtual void add(const GraphEdge& ge) { 2270 adaptor>getNotifier(Edge()).add(AdaptorBase::edge(ge)); 2271 } 2272 virtual void add(const std::vector<GraphEdge>& ge) { 2273 std::vector<Edge> edges; 2274 for (int i = 0; i < (int)ge.size(); ++i) { 2275 edges.push_back(AdaptorBase::edge(ge[i])); 2276 } 2277 adaptor>getNotifier(Edge()).add(edges); 2278 } 2279 virtual void erase(const GraphEdge& ge) { 2280 adaptor>getNotifier(Edge()).erase(AdaptorBase::edge(ge)); 2281 } 2282 virtual void erase(const std::vector<GraphEdge>& ge) { 2283 std::vector<Edge> edges; 2284 for (int i = 0; i < (int)ge.size(); ++i) { 2285 edges.push_back(AdaptorBase::edge(ge[i])); 2286 } 2287 adaptor>getNotifier(Edge()).erase(edges); 2288 } 2289 virtual void build() { 2290 std::vector<Edge> edges; 2291 const typename Parent::Notifier* notifier = Parent::getNotifier(); 2292 GraphEdge it; 2293 for (notifier>first(it); it != INVALID; notifier>next(it)) { 2294 edges.push_back(AdaptorBase::Parent::edge(it)); 2295 } 2296 adaptor>getNotifier(Edge()).add(edges); 2297 } 2298 virtual void clear() { 2299 std::vector<Edge> edges; 2300 const typename Parent::Notifier* notifier = Parent::getNotifier(); 2301 GraphEdge it; 2302 for (notifier>first(it); it != INVALID; notifier>next(it)) { 2303 edges.push_back(AdaptorBase::Parent::edge(it)); 2304 } 2305 adaptor>getNotifier(Edge()).erase(edges); 2306 } 2307 2308 const AdaptorBase* adaptor; 2309 }; 2310 2311 2312 mutable NodeNotifier node_notifier; 2313 mutable EdgeNotifier edge_notifier; 2314 2315 NodeNotifierProxy node_notifier_proxy; 2316 EdgeNotifierProxy edge_notifier_proxy; 2317 2318 }; 2319 2320 /// \ingroup graph_adaptors 2321 /// 2322 /// \brief SplitGraphAdaptor class 2323 /// 2324 /// This is an graph adaptor which splits all node into an innode 2325 /// and an outnode. Formaly, the adaptor replaces each \f$ u \f$ 2326 /// node in the graph with two node, \f$ u_{in} \f$ node and 2327 /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the 2328 /// original graph the new target of the edge will be \f$ u_{in} \f$ and 2329 /// similarly the source of the original \f$ (u, v) \f$ edge will be 2330 /// \f$ u_{out} \f$. The adaptor will add for each node in the 2331 /// original graph an additional edge which will connect 2332 /// \f$ (u_{in}, u_{out}) \f$. 2333 /// 2334 /// The aim of this class is to run algorithm with node costs if the 2335 /// algorithm can use directly just edge costs. In this case we should use 2336 /// a \c SplitGraphAdaptor and set the node cost of the graph to the 2337 /// bind edge in the adapted graph. 2338 /// 2339 /// By example a maximum flow algoritm can compute how many edge 2340 /// disjoint paths are in the graph. But we would like to know how 2341 /// many node disjoint paths are in the graph. First we have to 2342 /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow 2343 /// algorithm on the adapted graph. The bottleneck of the flow will 2344 /// be the bind edges which bounds the flow with the count of the 2345 /// node disjoint paths. 2346 /// 2347 ///\code 2348 /// 2349 /// typedef SplitGraphAdaptor<SmartGraph> SGraph; 2350 /// 2351 /// SGraph sgraph(graph); 2352 /// 2353 /// typedef ConstMap<SGraph::Edge, int> SCapacity; 2354 /// SCapacity scapacity(1); 2355 /// 2356 /// SGraph::EdgeMap<int> sflow(sgraph); 2357 /// 2358 /// Preflow<SGraph, int, SCapacity> 2359 /// spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target), 2360 /// scapacity, sflow); 2361 /// 2362 /// spreflow.run(); 2363 /// 2364 ///\endcode 2365 /// 2366 /// The result of the mamixum flow on the original graph 2367 /// shows the next figure: 2368 /// 2369 /// \image html edge_disjoint.png 2370 /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth 2371 /// 2372 /// And the maximum flow on the adapted graph: 2373 /// 2374 /// \image html node_disjoint.png 2375 /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth 2376 /// 2377 /// The second solution contains just 3 disjoint paths while the first 4. 2378 /// 2379 /// This graph adaptor is fully conform to the 2380 /// \ref concept::StaticGraph "StaticGraph" concept and 2381 /// contains some additional member functions and types. The 2382 /// documentation of some member functions may be found just in the 2383 /// SplitGraphAdaptorBase class. 2384 /// 2385 /// \sa SplitGraphAdaptorBase 2386 template <typename _Graph> 2387 class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> { 2388 public: 2389 typedef AlterableSplitGraphAdaptor<_Graph> Parent; 2390 2391 typedef typename Parent::Node Node; 2392 typedef typename Parent::Edge Edge; 2393 2394 /// \brief Constructor of the adaptor. 2395 /// 2396 /// Constructor of the adaptor. 2397 SplitGraphAdaptor(_Graph& graph) { 2398 Parent::setGraph(graph); 2399 } 2400 2401 /// \brief NodeMap combined from two original NodeMap 2402 /// 2403 /// This class adapt two of the original graph NodeMap to 2404 /// get a node map on the adapted graph. 2405 template <typename InNodeMap, typename OutNodeMap> 2406 class CombinedNodeMap { 2407 public: 2408 2409 typedef Node Key; 2410 typedef typename InNodeMap::Value Value; 2411 2412 /// \brief Constructor 2413 /// 2414 /// Constructor. 2415 CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap) 2416 : inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {} 2417 2418 /// \brief The subscript operator. 2419 /// 2420 /// The subscript operator. 2421 Value& operator[](const Key& key) { 2422 if (Parent::inNode(key)) { 2423 return inNodeMap[key]; 2424 } else { 2425 return outNodeMap[key]; 2426 } 2427 } 2428 2429 /// \brief The const subscript operator. 2430 /// 2431 /// The const subscript operator. 2432 Value operator[](const Key& key) const { 2433 if (Parent::inNode(key)) { 2434 return inNodeMap[key]; 2435 } else { 2436 return outNodeMap[key]; 2437 } 2438 } 2439 2440 /// \brief The setter function of the map. 2441 /// 2442 /// The setter function of the map. 2443 void set(const Key& key, const Value& value) { 2444 if (Parent::inNode(key)) { 2445 inNodeMap.set(key, value); 2446 } else { 2447 outNodeMap.set(key, value); 2448 } 2449 } 2450 2451 private: 2452 2453 InNodeMap& inNodeMap; 2454 OutNodeMap& outNodeMap; 2455 2456 }; 2457 2458 2459 /// \brief Just gives back a combined node map. 2460 /// 2461 /// Just gives back a combined node map. 2462 template <typename InNodeMap, typename OutNodeMap> 2463 static CombinedNodeMap<InNodeMap, OutNodeMap> 2464 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) { 2465 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map); 2466 } 2467 2468 template <typename InNodeMap, typename OutNodeMap> 2469 static CombinedNodeMap<const InNodeMap, OutNodeMap> 2470 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) { 2471 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map); 2472 } 2473 2474 template <typename InNodeMap, typename OutNodeMap> 2475 static CombinedNodeMap<InNodeMap, const OutNodeMap> 2476 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) { 2477 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map); 2478 } 2479 2480 template <typename InNodeMap, typename OutNodeMap> 2481 static CombinedNodeMap<const InNodeMap, const OutNodeMap> 2482 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) { 2483 return CombinedNodeMap<const InNodeMap, 2484 const OutNodeMap>(in_map, out_map); 2485 } 2486 2487 /// \brief EdgeMap combined from an original EdgeMap and NodeMap 2488 /// 2489 /// This class adapt an original graph EdgeMap and NodeMap to 2490 /// get an edge map on the adapted graph. 2491 template <typename GraphEdgeMap, typename GraphNodeMap> 2492 class CombinedEdgeMap 2493 : public MapBase<Edge, typename GraphEdgeMap::Value> { 2494 public: 2495 typedef MapBase<Edge, typename GraphEdgeMap::Value> Parent; 2496 2497 typedef typename Parent::Key Key; 2498 typedef typename Parent::Value Value; 2499 2500 /// \brief Constructor 2501 /// 2502 /// Constructor. 2503 CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map) 2504 : edge_map(_edge_map), node_map(_node_map) {} 2505 2506 /// \brief The subscript operator. 2507 /// 2508 /// The subscript operator. 2509 void set(const Edge& edge, const Value& val) { 2510 if (Parent::origEdge(edge)) { 2511 edge_map.set(edge, val); 2512 } else { 2513 node_map.set(edge, val); 2514 } 2515 } 2516 2517 /// \brief The const subscript operator. 2518 /// 2519 /// The const subscript operator. 2520 Value operator[](const Key& edge) const { 2521 if (Parent::origEdge(edge)) { 2522 return edge_map[edge]; 2523 } else { 2524 return node_map[edge]; 2525 } 2526 } 2527 2528 /// \brief The const subscript operator. 2529 /// 2530 /// The const subscript operator. 2531 Value& operator[](const Key& edge) { 2532 if (Parent::origEdge(edge)) { 2533 return edge_map[edge]; 2534 } else { 2535 return node_map[edge]; 2536 } 2537 } 2538 2539 private: 2540 GraphEdgeMap& edge_map; 2541 GraphNodeMap& node_map; 2542 }; 2543 2544 /// \brief Just gives back a combined edge map. 2545 /// 2546 /// Just gives back a combined edge map. 2547 template <typename GraphEdgeMap, typename GraphNodeMap> 2548 static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap> 2549 combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) { 2550 return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map); 2551 } 2552 2553 template <typename GraphEdgeMap, typename GraphNodeMap> 2554 static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap> 2555 combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) { 2556 return CombinedEdgeMap<const GraphEdgeMap, 2557 GraphNodeMap>(edge_map, node_map); 2558 } 2559 2560 template <typename GraphEdgeMap, typename GraphNodeMap> 2561 static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap> 2562 combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) { 2563 return CombinedEdgeMap<GraphEdgeMap, 2564 const GraphNodeMap>(edge_map, node_map); 2565 } 2566 2567 template <typename GraphEdgeMap, typename GraphNodeMap> 2568 static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap> 2569 combinedEdgeMap(const GraphEdgeMap& edge_map, 2570 const GraphNodeMap& node_map) { 2571 return CombinedEdgeMap<const GraphEdgeMap, 2572 const GraphNodeMap>(edge_map, node_map); 2573 } 2574 2575 }; 2576 2062 2577 2063 2578 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.