1101 |
1100 |
1102 }; |
1101 }; |
1103 |
1102 |
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 template <typename _Graph> |
1122 template <typename _Graph> |
1107 class UndirGraphAdaptorBase< |
1123 class AlterableUndirGraphAdaptor< |
1108 _Graph, typename enable_if< |
1124 _Graph, |
1109 typename _Graph::EdgeNotifier::Notifier>::type > |
1125 typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type > |
1110 : public UGraphBaseExtender<GraphAdaptorBase<_Graph> > { |
1126 : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > { |
1111 public: |
1127 public: |
1112 |
1128 |
|
1129 typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent; |
1113 typedef _Graph Graph; |
1130 typedef _Graph Graph; |
1114 typedef UndirGraphAdaptorBase Adaptor; |
1131 typedef typename _Graph::Edge GraphEdge; |
1115 typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent; |
1132 |
1116 |
|
1117 protected: |
1133 protected: |
1118 |
1134 |
1119 UndirGraphAdaptorBase() |
1135 AlterableUndirGraphAdaptor() |
1120 : edge_notifier(*this), edge_notifier_proxy(edge_notifier) {} |
1136 : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {} |
1121 |
1137 |
1122 void setGraph(_Graph& graph) { |
1138 void setGraph(_Graph& graph) { |
1123 Parent::setGraph(graph); |
1139 Parent::setGraph(graph); |
1124 edge_notifier_proxy.setUEdgeNotifier(graph.getNotifier(UEdge())); |
1140 edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge())); |
1125 } |
1141 } |
1126 |
1142 |
1127 public: |
1143 public: |
1128 |
1144 |
1129 ~UndirGraphAdaptorBase() { |
1145 ~AlterableUndirGraphAdaptor() { |
1130 edge_notifier.clear(); |
1146 edge_notifier.clear(); |
1131 } |
1147 } |
1132 |
|
1133 int maxId(typename Parent::Edge) const { |
|
1134 return Parent::maxEdgeId(); |
|
1135 } |
|
1136 |
|
1137 |
1148 |
1138 typedef typename Parent::UEdge UEdge; |
1149 typedef typename Parent::UEdge UEdge; |
1139 typedef typename Parent::Edge Edge; |
1150 typedef typename Parent::Edge Edge; |
1140 |
1151 |
1141 typedef typename Parent::EdgeNotifier UEdgeNotifier; |
1152 typedef typename Parent::EdgeNotifier UEdgeNotifier; |
1142 |
1153 |
1143 using Parent::getNotifier; |
1154 using Parent::getNotifier; |
1144 |
1155 |
1145 typedef AlterationNotifier<UndirGraphAdaptorBase, Edge> EdgeNotifier; |
1156 typedef AlterationNotifier<AlterableUndirGraphAdaptor, |
|
1157 Edge> EdgeNotifier; |
1146 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; } |
1158 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; } |
1147 |
1159 |
1148 protected: |
1160 protected: |
1149 |
1161 |
1150 class NotifierProxy : public UEdgeNotifier::ObserverBase { |
1162 class NotifierProxy : public Graph::EdgeNotifier::ObserverBase { |
1151 public: |
1163 public: |
1152 |
1164 |
1153 typedef typename UEdgeNotifier::ObserverBase Parent; |
1165 typedef typename Graph::EdgeNotifier::ObserverBase Parent; |
1154 typedef UndirGraphAdaptorBase AdaptorBase; |
1166 typedef AlterableUndirGraphAdaptor AdaptorBase; |
1155 |
1167 |
1156 NotifierProxy(EdgeNotifier& _edge_notifier) |
1168 NotifierProxy(const AdaptorBase& _adaptor) |
1157 : Parent(), edge_notifier(_edge_notifier) { |
1169 : Parent(), adaptor(&_adaptor) { |
1158 } |
1170 } |
1159 |
1171 |
1160 virtual ~NotifierProxy() { |
1172 virtual ~NotifierProxy() { |
1161 if (Parent::attached()) { |
1173 if (Parent::attached()) { |
1162 Parent::detach(); |
1174 Parent::detach(); |
1163 } |
1175 } |
1164 } |
1176 } |
1165 |
1177 |
1166 void setUEdgeNotifier(UEdgeNotifier& _uedge_notifier) { |
1178 void setNotifier(typename Graph::EdgeNotifier& notifier) { |
1167 Parent::attach(_uedge_notifier); |
1179 Parent::attach(notifier); |
1168 } |
1180 } |
1169 |
1181 |
1170 |
1182 |
1171 protected: |
1183 protected: |
1172 |
1184 |
1173 virtual void add(const UEdge& uedge) { |
1185 virtual void add(const GraphEdge& ge) { |
1174 std::vector<Edge> edges; |
1186 std::vector<Edge> edges; |
1175 edges.push_back(AdaptorBase::Parent::direct(uedge, true)); |
1187 edges.push_back(AdaptorBase::Parent::direct(ge, true)); |
1176 edges.push_back(AdaptorBase::Parent::direct(uedge, false)); |
1188 edges.push_back(AdaptorBase::Parent::direct(ge, false)); |
1177 edge_notifier.add(edges); |
1189 adaptor->getNotifier(Edge()).add(edges); |
1178 } |
1190 } |
1179 virtual void add(const std::vector<UEdge>& uedges) { |
1191 virtual void add(const std::vector<GraphEdge>& ge) { |
1180 std::vector<Edge> edges; |
1192 std::vector<Edge> edges; |
1181 for (int i = 0; i < (int)uedges.size(); ++i) { |
1193 for (int i = 0; i < (int)ge.size(); ++i) { |
1182 edges.push_back(AdaptorBase::Parent::direct(uedges[i], true)); |
1194 edges.push_back(AdaptorBase::Parent::direct(ge[i], true)); |
1183 edges.push_back(AdaptorBase::Parent::direct(uedges[i], false)); |
1195 edges.push_back(AdaptorBase::Parent::direct(ge[i], false)); |
1184 } |
1196 } |
1185 edge_notifier.add(edges); |
1197 adaptor->getNotifier(Edge()).add(edges); |
1186 } |
1198 } |
1187 virtual void erase(const UEdge& uedge) { |
1199 virtual void erase(const GraphEdge& ge) { |
1188 std::vector<Edge> edges; |
1200 std::vector<Edge> edges; |
1189 edges.push_back(AdaptorBase::Parent::direct(uedge, true)); |
1201 edges.push_back(AdaptorBase::Parent::direct(ge, true)); |
1190 edges.push_back(AdaptorBase::Parent::direct(uedge, false)); |
1202 edges.push_back(AdaptorBase::Parent::direct(ge, false)); |
1191 edge_notifier.erase(edges); |
1203 adaptor->getNotifier(Edge()).erase(edges); |
1192 } |
1204 } |
1193 virtual void erase(const std::vector<UEdge>& uedges) { |
1205 virtual void erase(const std::vector<GraphEdge>& ge) { |
1194 std::vector<Edge> edges; |
1206 std::vector<Edge> edges; |
1195 for (int i = 0; i < (int)uedges.size(); ++i) { |
1207 for (int i = 0; i < (int)ge.size(); ++i) { |
1196 edges.push_back(AdaptorBase::Parent::direct(uedges[i], true)); |
1208 edges.push_back(AdaptorBase::Parent::direct(ge[i], true)); |
1197 edges.push_back(AdaptorBase::Parent::direct(uedges[i], false)); |
1209 edges.push_back(AdaptorBase::Parent::direct(ge[i], false)); |
1198 } |
1210 } |
1199 edge_notifier.erase(edges); |
1211 adaptor->getNotifier(Edge()).erase(edges); |
1200 } |
1212 } |
1201 virtual void build() { |
1213 virtual void build() { |
1202 edge_notifier.build(); |
1214 adaptor->getNotifier(Edge()).build(); |
1203 } |
1215 } |
1204 virtual void clear() { |
1216 virtual void clear() { |
1205 edge_notifier.clear(); |
1217 adaptor->getNotifier(Edge()).clear(); |
1206 } |
1218 } |
1207 |
1219 |
1208 EdgeNotifier& edge_notifier; |
1220 const AdaptorBase* adaptor; |
1209 }; |
1221 }; |
1210 |
1222 |
1211 |
1223 |
1212 mutable EdgeNotifier edge_notifier; |
1224 mutable EdgeNotifier edge_notifier; |
1213 NotifierProxy edge_notifier_proxy; |
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 EdgeMap |
|
1270 : 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 |
1229 |
1319 ///\ingroup graph_adaptors |
1230 /// \brief An undirected graph is made from a directed graph by an adaptor |
|
1231 /// \ingroup graph_adaptors |
1320 /// |
1232 /// |
1321 /// Undocumented, untested!!! |
1233 /// Undocumented, untested!!! |
1322 /// If somebody knows nice demo application, let's polulate it. |
1234 /// If somebody knows nice demo application, let's polulate it. |
1323 /// |
1235 /// |
1324 /// \author Marton Makai |
1236 /// \author Marton Makai |
1325 template<typename _Graph> |
1237 template<typename _Graph> |
1326 class UndirGraphAdaptor : |
1238 class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> { |
1327 public UGraphAdaptorExtender< |
|
1328 UndirGraphAdaptorBase<_Graph> > { |
|
1329 public: |
1239 public: |
1330 typedef _Graph Graph; |
1240 typedef _Graph Graph; |
1331 typedef UGraphAdaptorExtender< |
1241 typedef AlterableUndirGraphAdaptor<_Graph> Parent; |
1332 UndirGraphAdaptorBase<_Graph> > Parent; |
|
1333 protected: |
1242 protected: |
1334 UndirGraphAdaptor() { } |
1243 UndirGraphAdaptor() { } |
1335 public: |
1244 public: |
1336 UndirGraphAdaptor(_Graph& _graph) { |
1245 UndirGraphAdaptor(_Graph& _graph) { |
1337 setGraph(_graph); |
1246 setGraph(_graph); |
1692 setFirstOutEdgesMap(_first_out_edges); |
1601 setFirstOutEdgesMap(_first_out_edges); |
1693 } |
1602 } |
1694 |
1603 |
1695 }; |
1604 }; |
1696 |
1605 |
1697 // template <typename _Graph> |
1606 /// \brief Base class for split graph adaptor |
1698 // class SplitGraphAdaptorBase |
1607 /// |
1699 // : public GraphAdaptorBase<_Graph> { |
1608 /// Base class of split graph adaptor. In most case you do not need to |
1700 // public: |
1609 /// use it directly but the documented member functions of this class can |
1701 // typedef GraphAdaptorBase<_Graph> Parent; |
1610 /// be used with the SplitGraphAdaptor class. |
1702 |
1611 /// \sa SplitGraphAdaptor |
1703 // class Node; |
1612 template <typename _Graph> |
1704 // class Edge; |
1613 class SplitGraphAdaptorBase |
1705 // template <typename T> class NodeMap; |
1614 : public GraphAdaptorBase<const _Graph> { |
1706 // template <typename T> class EdgeMap; |
1615 public: |
1707 |
1616 |
1708 |
1617 typedef _Graph Graph; |
1709 // class Node : public Parent::Node { |
1618 |
1710 // friend class SplitGraphAdaptorBase; |
1619 typedef GraphAdaptorBase<const _Graph> Parent; |
1711 // template <typename T> friend class NodeMap; |
1620 |
1712 // typedef typename Parent::Node NodeParent; |
1621 typedef typename Graph::Node GraphNode; |
1713 // private: |
1622 typedef typename Graph::Edge GraphEdge; |
1714 |
1623 |
1715 // bool entry; |
1624 class Node; |
1716 // Node(typename Parent::Node _node, bool _entry) |
1625 class Edge; |
1717 // : Parent::Node(_node), entry(_entry) {} |
1626 |
1718 |
1627 template <typename T> class NodeMap; |
1719 // public: |
1628 template <typename T> class EdgeMap; |
1720 // Node() {} |
1629 |
1721 // Node(Invalid) : NodeParent(INVALID), entry(true) {} |
1630 |
1722 |
1631 class Node : public GraphNode { |
1723 // bool operator==(const Node& node) const { |
1632 friend class SplitGraphAdaptorBase; |
1724 // return NodeParent::operator==(node) && entry == node.entry; |
1633 template <typename T> friend class NodeMap; |
1725 // } |
1634 private: |
1726 |
1635 |
1727 // bool operator!=(const Node& node) const { |
1636 bool in_node; |
1728 // return !(*this == node); |
1637 Node(GraphNode _node, bool _in_node) |
1729 // } |
1638 : GraphNode(_node), in_node(_in_node) {} |
1730 |
1639 |
1731 // bool operator<(const Node& node) const { |
1640 public: |
1732 // return NodeParent::operator<(node) || |
1641 |
1733 // (NodeParent::operator==(node) && entry < node.entry); |
1642 Node() {} |
1734 // } |
1643 Node(Invalid) : GraphNode(INVALID), in_node(true) {} |
1735 // }; |
1644 |
1736 |
1645 bool operator==(const Node& node) const { |
1737 // /// \todo May we want VARIANT/union type |
1646 return GraphNode::operator==(node) && in_node == node.in_node; |
1738 // class Edge : public Parent::Edge { |
1647 } |
1739 // friend class SplitGraphAdaptorBase; |
1648 |
1740 // template <typename T> friend class EdgeMap; |
1649 bool operator!=(const Node& node) const { |
1741 // private: |
1650 return !(*this == node); |
1742 // typedef typename Parent::Edge EdgeParent; |
1651 } |
1743 // typedef typename Parent::Node NodeParent; |
1652 |
1744 // NodeParent bind; |
1653 bool operator<(const Node& node) const { |
1745 |
1654 return GraphNode::operator<(node) || |
1746 // Edge(const EdgeParent& edge, const NodeParent& node) |
1655 (GraphNode::operator==(node) && in_node < node.in_node); |
1747 // : EdgeParent(edge), bind(node) {} |
1656 } |
1748 // public: |
1657 }; |
1749 // Edge() {} |
1658 |
1750 // Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {} |
1659 class Edge { |
1751 |
1660 friend class SplitGraphAdaptorBase; |
1752 // bool operator==(const Edge& edge) const { |
1661 template <typename T> friend class EdgeMap; |
1753 // return EdgeParent::operator==(edge) && bind == edge.bind; |
1662 private: |
1754 // } |
1663 typedef BiVariant<GraphEdge, GraphNode> EdgeImpl; |
1755 |
1664 |
1756 // bool operator!=(const Edge& edge) const { |
1665 explicit Edge(const GraphEdge& edge) : item(edge) {} |
1757 // return !(*this == edge); |
1666 explicit Edge(const GraphNode& node) : item(node) {} |
1758 // } |
1667 |
1759 |
1668 EdgeImpl item; |
1760 // bool operator<(const Edge& edge) const { |
1669 |
1761 // return EdgeParent::operator<(edge) || |
1670 public: |
1762 // (EdgeParent::operator==(edge) && bind < edge.bind); |
1671 Edge() {} |
1763 // } |
1672 Edge(Invalid) : item(GraphEdge(INVALID)) {} |
1764 // }; |
1673 |
1765 |
1674 bool operator==(const Edge& edge) const { |
1766 // void first(Node& node) const { |
1675 if (item.firstState()) { |
1767 // Parent::first(node); |
1676 if (edge.item.firstState()) { |
1768 // node.entry = true; |
1677 return item.first() == edge.item.first(); |
1769 // } |
1678 } |
1770 |
1679 } else { |
1771 // void next(Node& node) const { |
1680 if (edge.item.secondState()) { |
1772 // if (node.entry) { |
1681 return item.second() == edge.item.second(); |
1773 // node.entry = false; |
1682 } |
1774 // } else { |
1683 } |
1775 // node.entry = true; |
1684 return false; |
1776 // Parent::next(node); |
1685 } |
1777 // } |
1686 |
1778 // } |
1687 bool operator!=(const Edge& edge) const { |
1779 |
1688 return !(*this == edge); |
1780 // void first(Edge& edge) const { |
1689 } |
1781 // Parent::first(edge); |
1690 |
1782 // if ((typename Parent::Edge&)edge == INVALID) { |
1691 bool operator<(const Edge& edge) const { |
1783 // Parent::first(edge.bind); |
1692 if (item.firstState()) { |
1784 // } else { |
1693 if (edge.item.firstState()) { |
1785 // edge.bind = INVALID; |
1694 return item.first() < edge.item.first(); |
1786 // } |
1695 } |
1787 // } |
1696 return false; |
1788 |
1697 } else { |
1789 // void next(Edge& edge) const { |
1698 if (edge.item.secondState()) { |
1790 // if ((typename Parent::Edge&)edge != INVALID) { |
1699 return item.second() < edge.item.second(); |
1791 // Parent::next(edge); |
1700 } |
1792 // if ((typename Parent::Edge&)edge == INVALID) { |
1701 return true; |
1793 // Parent::first(edge.bind); |
1702 } |
1794 // } |
1703 } |
1795 // } else { |
1704 |
1796 // Parent::next(edge.bind); |
1705 operator GraphEdge() const { return item.first(); } |
1797 // } |
1706 operator GraphNode() const { return item.second(); } |
1798 // } |
1707 |
1799 |
1708 }; |
1800 // void firstIn(Edge& edge, const Node& node) const { |
1709 |
1801 // if (node.entry) { |
1710 void first(Node& node) const { |
1802 // Parent::firstIn(edge, node); |
1711 Parent::first(node); |
1803 // edge.bind = INVALID; |
1712 node.in_node = true; |
1804 // } else { |
1713 } |
1805 // (typename Parent::Edge&)edge = INVALID; |
1714 |
1806 // edge.bind = node; |
1715 void next(Node& node) const { |
1807 // } |
1716 if (node.in_node) { |
1808 // } |
1717 node.in_node = false; |
1809 |
1718 } else { |
1810 // void nextIn(Edge& edge) const { |
1719 node.in_node = true; |
1811 // if ((typename Parent::Edge&)edge != INVALID) { |
1720 Parent::next(node); |
1812 // Parent::nextIn(edge); |
1721 } |
1813 // } else { |
1722 } |
1814 // edge.bind = INVALID; |
1723 |
1815 // } |
1724 void first(Edge& edge) const { |
1816 // } |
1725 edge.item.setSecond(); |
1817 |
1726 Parent::first(edge.item.second()); |
1818 // void firstOut(Edge& edge, const Node& node) const { |
1727 if (edge.item.second() == INVALID) { |
1819 // if (!node.entry) { |
1728 edge.item.setFirst(); |
1820 // Parent::firstOut(edge, node); |
1729 Parent::first(edge.item.first()); |
1821 // edge.bind = INVALID; |
1730 } |
1822 // } else { |
1731 } |
1823 // (typename Parent::Edge&)edge = INVALID; |
1732 |
1824 // edge.bind = node; |
1733 void next(Edge& edge) const { |
1825 // } |
1734 if (edge.item.secondState()) { |
1826 // } |
1735 Parent::next(edge.item.second()); |
1827 |
1736 if (edge.item.second() == INVALID) { |
1828 // void nextOut(Edge& edge) const { |
1737 edge.item.setFirst(); |
1829 // if ((typename Parent::Edge&)edge != INVALID) { |
1738 Parent::first(edge.item.first()); |
1830 // Parent::nextOut(edge); |
1739 } |
1831 // } else { |
1740 } else { |
1832 // edge.bind = INVALID; |
1741 Parent::next(edge.item.first()); |
1833 // } |
1742 } |
1834 // } |
1743 } |
1835 |
1744 |
1836 // Node source(const Edge& edge) const { |
1745 void firstOut(Edge& edge, const Node& node) const { |
1837 // if ((typename Parent::Edge&)edge != INVALID) { |
1746 if (node.in_node) { |
1838 // return Node(Parent::source(edge), false); |
1747 edge.item.setSecond(node); |
1839 // } else { |
1748 } else { |
1840 // return Node(edge.bind, true); |
1749 edge.item.setFirst(); |
1841 // } |
1750 Parent::firstOut(edge.item.first(), node); |
1842 // } |
1751 } |
1843 |
1752 } |
1844 // Node target(const Edge& edge) const { |
1753 |
1845 // if ((typename Parent::Edge&)edge != INVALID) { |
1754 void nextOut(Edge& edge) const { |
1846 // return Node(Parent::target(edge), true); |
1755 if (!edge.item.firstState()) { |
1847 // } else { |
1756 edge.item.setFirst(INVALID); |
1848 // return Node(edge.bind, false); |
1757 } else { |
1849 // } |
1758 Parent::nextOut(edge.item.first()); |
1850 // } |
1759 } |
1851 |
1760 } |
1852 // static bool entryNode(const Node& node) { |
1761 |
1853 // return node.entry; |
1762 void firstIn(Edge& edge, const Node& node) const { |
1854 // } |
1763 if (!node.in_node) { |
1855 |
1764 edge.item.setSecond(node); |
1856 // static bool exitNode(const Node& node) { |
1765 } else { |
1857 // return !node.entry; |
1766 edge.item.setFirst(); |
1858 // } |
1767 Parent::firstIn(edge.item.first(), node); |
1859 |
1768 } |
1860 // static Node getEntry(const typename Parent::Node& node) { |
1769 } |
1861 // return Node(node, true); |
1770 |
1862 // } |
1771 void nextIn(Edge& edge) const { |
1863 |
1772 if (!edge.item.firstState()) { |
1864 // static Node getExit(const typename Parent::Node& node) { |
1773 edge.item.setFirst(INVALID); |
1865 // return Node(node, false); |
1774 } else { |
1866 // } |
1775 Parent::nextIn(edge.item.first()); |
1867 |
1776 } |
1868 // static bool originalEdge(const Edge& edge) { |
1777 } |
1869 // return (typename Parent::Edge&)edge != INVALID; |
1778 |
1870 // } |
1779 Node source(const Edge& edge) const { |
1871 |
1780 if (edge.item.firstState()) { |
1872 // static bool bindingEdge(const Edge& edge) { |
1781 return Node(Parent::source(edge.item.first()), false); |
1873 // return edge.bind != INVALID; |
1782 } else { |
1874 // } |
1783 return Node(edge.item.second(), true); |
1875 |
1784 } |
1876 // static Node getBindedNode(const Edge& edge) { |
1785 } |
1877 // return edge.bind; |
1786 |
1878 // } |
1787 Node target(const Edge& edge) const { |
1879 |
1788 if (edge.item.firstState()) { |
1880 // int nodeNum() const { |
1789 return Node(Parent::target(edge.item.first()), true); |
1881 // return Parent::nodeNum() * 2; |
1790 } else { |
1882 // } |
1791 return Node(edge.item.second(), false); |
1883 |
1792 } |
1884 // typedef True EdgeNumTag; |
1793 } |
1885 |
1794 |
1886 // int edgeNum() const { |
1795 int id(const Node& node) const { |
1887 // return countEdges() + Parent::nodeNum(); |
1796 return (Parent::id(node) << 1) | (node.in_node ? 0 : 1); |
1888 // } |
1797 } |
1889 |
1798 Node nodeFromId(int id) const { |
1890 // Edge findEdge(const Node& source, const Node& target, |
1799 return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0); |
1891 // const Edge& prev = INVALID) const { |
1800 } |
1892 // if (exitNode(source) && entryNode(target)) { |
1801 int maxNodeId() const { |
1893 // return Parent::findEdge(source, target, prev); |
1802 return 2 * Parent::maxNodeId() + 1; |
1894 // } else { |
1803 } |
1895 // if (prev == INVALID && entryNode(source) && exitNode(target) && |
1804 |
1896 // (typename Parent::Node&)source == (typename Parent::Node&)target) { |
1805 int id(const Edge& edge) const { |
1897 // return Edge(INVALID, source); |
1806 if (edge.item.firstState()) { |
1898 // } else { |
1807 return Parent::id(edge.item.first()) << 1; |
1899 // return INVALID; |
1808 } else { |
1900 // } |
1809 return (Parent::id(edge.item.second()) << 1) | 1; |
1901 // } |
1810 } |
1902 // } |
1811 } |
1903 |
1812 Edge edgeFromId(int id) const { |
1904 // template <typename T> |
1813 if ((id & 1) == 0) { |
1905 // class NodeMap : public MapBase<Node, T> { |
1814 return Edge(Parent::edgeFromId(id >> 1)); |
1906 // typedef typename Parent::template NodeMap<T> NodeImpl; |
1815 } else { |
1907 // public: |
1816 return Edge(Parent::nodeFromId(id >> 1)); |
1908 // NodeMap(const SplitGraphAdaptorBase& _graph) |
1817 } |
1909 // : entry(_graph), exit(_graph) {} |
1818 } |
1910 // NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) |
1819 int maxEdgeId() const { |
1911 // : entry(_graph, t), exit(_graph, t) {} |
1820 return std::max(Parent::maxNodeId() << 1, |
1912 |
1821 (Parent::maxEdgeId() << 1) | 1); |
1913 // void set(const Node& key, const T& val) { |
1822 } |
1914 // if (key.entry) { entry.set(key, val); } |
1823 |
1915 // else {exit.set(key, val); } |
1824 /// \brief Returns true when the node is in-node. |
1916 // } |
1825 /// |
1917 |
1826 /// Returns true when the node is in-node. |
1918 // typename MapTraits<NodeImpl>::ReturnValue |
1827 static bool inNode(const Node& node) { |
1919 // operator[](const Node& key) { |
1828 return node.in_node; |
1920 // if (key.entry) { return entry[key]; } |
1829 } |
1921 // else { return exit[key]; } |
1830 |
1922 // } |
1831 /// \brief Returns true when the node is out-node. |
1923 |
1832 /// |
1924 // typename MapTraits<NodeImpl>::ConstReturnValue |
1833 /// Returns true when the node is out-node. |
1925 // operator[](const Node& key) const { |
1834 static bool outNode(const Node& node) { |
1926 // if (key.entry) { return entry[key]; } |
1835 return !node.in_node; |
1927 // else { return exit[key]; } |
1836 } |
1928 // } |
1837 |
1929 |
1838 /// \brief Returns true when the edge is edge in the original graph. |
1930 // private: |
1839 /// |
1931 // NodeImpl entry, exit; |
1840 /// Returns true when the edge is edge in the original graph. |
1932 // }; |
1841 static bool origEdge(const Edge& edge) { |
1933 |
1842 return edge.item.firstState(); |
1934 // template <typename T> |
1843 } |
1935 // class EdgeMap : public MapBase<Edge, T> { |
1844 |
1936 // typedef typename Parent::template NodeMap<T> NodeImpl; |
1845 /// \brief Returns true when the edge binds an in-node and an out-node. |
1937 // typedef typename Parent::template EdgeMap<T> EdgeImpl; |
1846 /// |
1938 // public: |
1847 /// Returns true when the edge binds an in-node and an out-node. |
1939 // EdgeMap(const SplitGraphAdaptorBase& _graph) |
1848 static bool bindEdge(const Edge& edge) { |
1940 // : bind(_graph), orig(_graph) {} |
1849 return edge.item.secondState(); |
1941 // EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) |
1850 } |
1942 // : bind(_graph, t), orig(_graph, t) {} |
1851 |
1943 |
1852 /// \brief Gives back the in-node created from the \c node. |
1944 // void set(const Edge& key, const T& val) { |
1853 /// |
1945 // if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); } |
1854 /// Gives back the in-node created from the \c node. |
1946 // else {bind.set(key.bind, val); } |
1855 static Node inNode(const GraphNode& node) { |
1947 // } |
1856 return Node(node, true); |
1948 |
1857 } |
1949 // typename MapTraits<EdgeImpl>::ReturnValue |
1858 |
1950 // operator[](const Edge& key) { |
1859 /// \brief Gives back the out-node created from the \c node. |
1951 // if ((typename Parent::Edge&)key != INVALID) { return orig[key]; } |
1860 /// |
1952 // else {return bind[key.bind]; } |
1861 /// Gives back the out-node created from the \c node. |
1953 // } |
1862 static Node outNode(const GraphNode& node) { |
1954 |
1863 return Node(node, false); |
1955 // typename MapTraits<EdgeImpl>::ConstReturnValue |
1864 } |
1956 // operator[](const Edge& key) const { |
1865 |
1957 // if ((typename Parent::Edge&)key != INVALID) { return orig[key]; } |
1866 /// \brief Gives back the edge binds the two part of the node. |
1958 // else {return bind[key.bind]; } |
1867 /// |
1959 // } |
1868 /// Gives back the edge binds the two part of the node. |
1960 |
1869 static Edge edge(const GraphNode& node) { |
1961 // private: |
1870 return Edge(node); |
1962 // typename Parent::template NodeMap<T> bind; |
1871 } |
1963 // typename Parent::template EdgeMap<T> orig; |
1872 |
1964 // }; |
1873 /// \brief Gives back the edge of the original edge. |
1965 |
1874 /// |
1966 // template <typename EntryMap, typename ExitMap> |
1875 /// Gives back the edge of the original edge. |
1967 // class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> { |
1876 static Edge edge(const GraphEdge& edge) { |
1968 // public: |
1877 return Edge(edge); |
1969 // typedef MapBase<Node, typename EntryMap::Value> Parent; |
1878 } |
1970 |
1879 |
1971 // typedef typename Parent::Key Key; |
1880 typedef True NodeNumTag; |
1972 // typedef typename Parent::Value Value; |
1881 |
1973 |
1882 int nodeNum() const { |
1974 // CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap) |
1883 return 2 * countNodes(*Parent::graph); |
1975 // : entryMap(_entryMap), exitMap(_exitMap) {} |
1884 } |
1976 |
1885 |
1977 // Value& operator[](const Key& key) { |
1886 typedef True EdgeNumTag; |
1978 // if (key.entry) { |
1887 |
1979 // return entryMap[key]; |
1888 int edgeNum() const { |
1980 // } else { |
1889 return countEdges(*Parent::graph) + countNodes(*Parent::graph); |
1981 // return exitMap[key]; |
1890 } |
1982 // } |
1891 |
1983 // } |
1892 typedef True FindEdgeTag; |
1984 |
1893 |
1985 // Value operator[](const Key& key) const { |
1894 Edge findEdge(const Node& source, const Node& target, |
1986 // if (key.entry) { |
1895 const Edge& prev = INVALID) const { |
1987 // return entryMap[key]; |
1896 if (inNode(source)) { |
1988 // } else { |
1897 if (outNode(target)) { |
1989 // return exitMap[key]; |
1898 if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) { |
1990 // } |
1899 return Edge(source); |
1991 // } |
1900 } |
1992 |
1901 } |
1993 // void set(const Key& key, const Value& value) { |
1902 } else { |
1994 // if (key.entry) { |
1903 if (inNode(target)) { |
1995 // entryMap.set(key, value); |
1904 return Edge(findEdge(*Parent::graph, source, target, prev)); |
1996 // } else { |
1905 } |
1997 // exitMap.set(key, value); |
1906 } |
1998 // } |
1907 return INVALID; |
1999 // } |
1908 } |
2000 |
1909 |
2001 // private: |
1910 template <typename T> |
2002 |
1911 class NodeMap : public MapBase<Node, T> { |
2003 // EntryMap& entryMap; |
1912 typedef typename Parent::template NodeMap<T> NodeImpl; |
2004 // ExitMap& exitMap; |
1913 public: |
2005 |
1914 NodeMap(const SplitGraphAdaptorBase& _graph) |
2006 // }; |
1915 : inNodeMap(_graph), outNodeMap(_graph) {} |
2007 |
1916 NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) |
2008 // template <typename EdgeMap, typename NodeMap> |
1917 : inNodeMap(_graph, t), outNodeMap(_graph, t) {} |
2009 // class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> { |
1918 |
2010 // public: |
1919 void set(const Node& key, const T& val) { |
2011 // typedef MapBase<Edge, typename EdgeMap::Value> Parent; |
1920 if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); } |
2012 |
1921 else {outNodeMap.set(key, val); } |
2013 // typedef typename Parent::Key Key; |
1922 } |
2014 // typedef typename Parent::Value Value; |
1923 |
2015 |
1924 typename MapTraits<NodeImpl>::ReturnValue |
2016 // CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap) |
1925 operator[](const Node& key) { |
2017 // : edgeMap(_edgeMap), nodeMap(_nodeMap) {} |
1926 if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; } |
2018 |
1927 else { return outNodeMap[key]; } |
2019 // void set(const Edge& edge, const Value& val) { |
1928 } |
2020 // if (SplitGraphAdaptorBase::originalEdge(edge)) { |
1929 |
2021 // edgeMap.set(edge, val); |
1930 typename MapTraits<NodeImpl>::ConstReturnValue |
2022 // } else { |
1931 operator[](const Node& key) const { |
2023 // nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val); |
1932 if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; } |
2024 // } |
1933 else { return outNodeMap[key]; } |
2025 // } |
1934 } |
2026 |
1935 |
2027 // Value operator[](const Key& edge) const { |
1936 private: |
2028 // if (SplitGraphAdaptorBase::originalEdge(edge)) { |
1937 NodeImpl inNodeMap, outNodeMap; |
2029 // return edgeMap[edge]; |
1938 }; |
2030 // } else { |
1939 |
2031 // return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)]; |
1940 template <typename T> |
2032 // } |
1941 class EdgeMap : public MapBase<Edge, T> { |
2033 // } |
1942 typedef typename Parent::template EdgeMap<T> EdgeMapImpl; |
2034 |
1943 typedef typename Parent::template NodeMap<T> NodeMapImpl; |
2035 // Value& operator[](const Key& edge) { |
1944 public: |
2036 // if (SplitGraphAdaptorBase::originalEdge(edge)) { |
1945 |
2037 // return edgeMap[edge]; |
1946 EdgeMap(const SplitGraphAdaptorBase& _graph) |
2038 // } else { |
1947 : edge_map(_graph), node_map(_graph) {} |
2039 // return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)]; |
1948 EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) |
2040 // } |
1949 : edge_map(_graph, t), node_map(_graph, t) {} |
2041 // } |
1950 |
2042 |
1951 void set(const Edge& key, const T& val) { |
2043 // private: |
1952 if (SplitGraphAdaptorBase::origEdge(key)) { |
2044 // EdgeMap& edgeMap; |
1953 edge_map.set(key.item.first(), val); |
2045 // NodeMap& nodeMap; |
1954 } else { |
2046 // }; |
1955 node_map.set(key.item.second(), val); |
2047 |
1956 } |
2048 // }; |
1957 } |
2049 |
1958 |
2050 // template <typename _Graph> |
1959 typename MapTraits<EdgeMapImpl>::ReturnValue |
2051 // class SplitGraphAdaptor |
1960 operator[](const Edge& key) { |
2052 // : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > { |
1961 if (SplitGraphAdaptorBase::origEdge(key)) { |
2053 // public: |
1962 return edge_map[key.item.first()]; |
2054 // typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent; |
1963 } else { |
2055 |
1964 return node_map[key.item.second()]; |
2056 // SplitGraphAdaptor(_Graph& graph) { |
1965 } |
2057 // Parent::setGraph(graph); |
1966 } |
2058 // } |
1967 |
2059 |
1968 typename MapTraits<EdgeMapImpl>::ConstReturnValue |
2060 |
1969 operator[](const Edge& key) const { |
2061 // }; |
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 in-node |
|
2325 /// and an out-node. 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 } //namespace lemon |
2578 } //namespace lemon |
2064 |
2579 |
2065 #endif //LEMON_GRAPH_ADAPTOR_H |
2580 #endif //LEMON_GRAPH_ADAPTOR_H |
2066 |
2581 |