COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2079:7fe378247fea in lemon-0.x for lemon/graph_adaptor.h


Ignore:
Timestamp:
05/12/06 11:56:14 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2742
Message:

Remade SplitGraphAdaptor?

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/graph_adaptor.h

    r2042 r2079  
    3737#include <lemon/tolerance.h>
    3838
    39 #include <iostream>
     39#include <algorithm>
    4040
    4141namespace lemon {
    … …  
    257257  /// RevGraphAdaptor<ListGraph> ga(g);
    258258  ///\endcode
    259   ///implements the graph obtained from \c g by
     259  /// implements the graph obtained from \c g by
    260260  /// reversing the orientation of its edges.
    261 
    262261  template<typename _Graph>
    263262  class RevGraphAdaptor :
    … …  
    984983  }
    985984
    986   template <typename _Graph, typename Enable = void>
     985  template <typename _Graph>
    987986  class UndirGraphAdaptorBase :
    988     public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
     987    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
    989988  public:
    990989    typedef _Graph Graph;
    991990    typedef UndirGraphAdaptorBase Adaptor;
    992     typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
     991    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
    993992
    994993  protected:
    … …  
    11041103  };
    11051104
     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
    11061122  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;
    11131130    typedef _Graph Graph;
    1114     typedef UndirGraphAdaptorBase Adaptor;
    1115     typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
    1116 
     1131    typedef typename _Graph::Edge GraphEdge;
     1132   
    11171133  protected:
    11181134
    1119     UndirGraphAdaptorBase()
    1120       : edge_notifier(*this), edge_notifier_proxy(edge_notifier) {}
     1135    AlterableUndirGraphAdaptor()
     1136      : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {}
    11211137
    11221138    void setGraph(_Graph& graph) {
    11231139      Parent::setGraph(graph);
    1124       edge_notifier_proxy.setUEdgeNotifier(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() {
    11301146      edge_notifier.clear();
    11311147    }
    1132 
    1133     int maxId(typename Parent::Edge) const {
    1134       return Parent::maxEdgeId();
    1135     }
    1136 
    11371148
    11381149    typedef typename Parent::UEdge UEdge;
    … …  
    11431154    using Parent::getNotifier;
    11441155
    1145     typedef AlterationNotifier<UndirGraphAdaptorBase, Edge> EdgeNotifier;
     1156    typedef AlterationNotifier<AlterableUndirGraphAdaptor,
     1157                               Edge> EdgeNotifier;
    11461158    EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
    11471159
    11481160  protected:
    11491161
    1150     class NotifierProxy : public UEdgeNotifier::ObserverBase {
     1162    class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {
    11511163    public:
    11521164
    1153       typedef typename UEdgeNotifier::ObserverBase Parent;
    1154       typedef UndirGraphAdaptorBase AdaptorBase;
    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) {
    11581170      }
    11591171
    … …  
    11641176      }
    11651177
    1166       void setUEdgeNotifier(UEdgeNotifier& _uedge_notifier) {
    1167         Parent::attach(_uedge_notifier);
     1178      void setNotifier(typename Graph::EdgeNotifier& notifier) {
     1179        Parent::attach(notifier);
    11681180      }
    11691181
    … …  
    11711183    protected:
    11721184
    1173       virtual void add(const UEdge& uedge) {
     1185      virtual void add(const GraphEdge& ge) {
    11741186        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) {
    11801192        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) {
    11881200        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) {
    11941206        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);
    12001212      }
    12011213      virtual void build() {
    1202         edge_notifier.build();
     1214        adaptor->getNotifier(Edge()).build();
    12031215      }
    12041216      virtual void clear() {
    1205         edge_notifier.clear();
    1206       }
    1207 
    1208       EdgeNotifier& edge_notifier;
     1217        adaptor->getNotifier(Edge()).clear();
     1218      }
     1219
     1220      const AdaptorBase* adaptor;
    12091221    };
    12101222
    … …  
    12131225    NotifierProxy edge_notifier_proxy;
    12141226
    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      
    13161227  };
    13171228
    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
    13201232  ///
    13211233  /// Undocumented, untested!!!
    … …  
    13241236  /// \author Marton Makai
    13251237  template<typename _Graph>
    1326   class UndirGraphAdaptor :
    1327     public UGraphAdaptorExtender<
    1328     UndirGraphAdaptorBase<_Graph> > {
     1238  class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
    13291239  public:
    13301240    typedef _Graph Graph;
    1331     typedef UGraphAdaptorExtender<
    1332       UndirGraphAdaptorBase<_Graph> > Parent;
     1241    typedef AlterableUndirGraphAdaptor<_Graph> Parent;
    13331242  protected:
    13341243    UndirGraphAdaptor() { }
    … …  
    16951604  };
    16961605
    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 in-node.
     1825    ///
     1826    /// Returns true when the node is in-node.
     1827    static bool inNode(const Node& node) {
     1828      return node.in_node;
     1829    }
     1830
     1831    /// \brief Returns true when the node is out-node.
     1832    ///
     1833    /// Returns true when the node is out-node.
     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 in-node and an out-node.
     1846    ///
     1847    /// Returns true when the edge binds an in-node and an out-node.
     1848    static bool bindEdge(const Edge& edge) {
     1849      return edge.item.secondState();
     1850    }
     1851
     1852    /// \brief Gives back the in-node created from the \c node.
     1853    ///
     1854    /// Gives back the in-node created from the \c node.
     1855    static Node inNode(const GraphNode& node) {
     1856      return Node(node, true);
     1857    }
     1858
     1859    /// \brief Gives back the out-node created from the \c node.
     1860    ///
     1861    /// Gives back the out-node 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 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
    20622577
    20632578} //namespace lemon
Note: See TracChangeset for help on using the changeset viewer.