COIN-OR::LEMON - Graph Library

Changeset 2189:de2b77e3868c in lemon-0.x


Ignore:
Timestamp:
09/04/06 13:08:32 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2914
Message:

Bug fix in ListBpUGraph

Snapshot improvments

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r2160 r2189  
    503503    /// restore() function.
    504504    ///
    505     /// \warning Edge and node deletions cannot be restored.
     505    /// \warning Edge and node deletions cannot be restored. This
     506    /// events invalidate the snapshot.
    506507    class Snapshot {
    507     public:
    508      
    509       class UnsupportedOperation : public LogicError {
    510       public:
    511         virtual const char* what() const throw() {
    512           return "lemon::ListGraph::Snapshot::UnsupportedOperation";
    513         }
    514       };
    515            
    516 
    517508    protected:
    518509
     
    544535        virtual void erase(const std::vector<Node>& nodes) {
    545536          for (int i = 0; i < (int)nodes.size(); ++i) {
    546             if (!snapshot.eraseNode(nodes[i])) break;
     537            snapshot.eraseNode(nodes[i]);
    547538          }
    548539        }
     
    562553          Node node;
    563554          for (notifier->first(node); node != INVALID; notifier->next(node)) {
    564             if (!snapshot.eraseNode(node)) break;
     555            snapshot.eraseNode(node);
    565556          }
    566557        }
     
    594585        virtual void erase(const std::vector<Edge>& edges) {
    595586          for (int i = 0; i < (int)edges.size(); ++i) {
    596             if (!snapshot.eraseEdge(edges[i])) break;
     587            snapshot.eraseEdge(edges[i]);
    597588          }
    598589        }
     
    612603          Edge edge;
    613604          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
    614             if (!snapshot.eraseEdge(edge)) break;
     605            snapshot.eraseEdge(edge);
    615606          }
    616607        }
     
    631622        added_nodes.push_front(node);       
    632623      }
    633       bool eraseNode(const Node& node) {
     624      void eraseNode(const Node& node) {
    634625        std::list<Node>::iterator it =
    635626          std::find(added_nodes.begin(), added_nodes.end(), node);
    636627        if (it == added_nodes.end()) {
    637628          clear();
    638           return false;
     629          edge_observer_proxy.detach();
     630          throw NodeNotifier::ImmediateDetach();
    639631        } else {
    640632          added_nodes.erase(it);
    641           return true;
    642633        }
    643634      }
     
    646637        added_edges.push_front(edge);       
    647638      }
    648       bool eraseEdge(const Edge& edge) {
     639      void eraseEdge(const Edge& edge) {
    649640        std::list<Edge>::iterator it =
    650641          std::find(added_edges.begin(), added_edges.end(), edge);
    651642        if (it == added_edges.end()) {
    652643          clear();
    653           return false;
     644          node_observer_proxy.detach();
     645          throw EdgeNotifier::ImmediateDetach();
    654646        } else {
    655647          added_edges.erase(it);
    656           return true;
    657648        }       
    658649      }
     
    669660      }
    670661
     662      bool attached() const {
     663        return node_observer_proxy.attached();
     664      }
     665
    671666      void clear() {
    672         detach();
    673667        added_nodes.clear();
    674668        added_edges.clear();       
     
    703697      /// \param _graph The graph we make the snapshot of.
    704698      void save(ListGraph &_graph) {
    705         clear();
     699        if (attached()) {
     700          detach();
     701          clear();
     702        }
    706703        attach(_graph);
    707704      }
     
    712709      void restore() {
    713710        detach();
    714         while(!added_edges.empty()) {
    715           graph->erase(added_edges.front());
    716           added_edges.pop_front();
     711        for(std::list<Edge>::iterator it = added_edges.begin();
     712            it != added_edges.end(); ++it) {
     713          graph->erase(*it);
    717714        }
    718         while(!added_nodes.empty()) {
    719           graph->erase(added_nodes.front());
    720           added_nodes.pop_front();
     715        for(std::list<Node>::iterator it = added_nodes.begin();
     716            it != added_nodes.end(); ++it) {
     717          graph->erase(*it);
    721718        }
     719        clear();
    722720      }
    723721
     
    726724      /// Gives back true when the snapshot is valid.
    727725      bool valid() const {
    728         return node_observer_proxy.attached();
     726        return attached();
    729727      }
    730728    };
     
    860858      erase(b);
    861859    }
     860
     861
     862    /// \brief Class to make a snapshot of the graph and restore
     863    /// to it later.
     864    ///
     865    /// Class to make a snapshot of the graph and to restore it
     866    /// later.
     867    ///
     868    /// The newly added nodes and undirected edges can be removed
     869    /// using the restore() function.
     870    ///
     871    /// \warning Edge and node deletions cannot be restored. This
     872    /// events invalidate the snapshot.
     873    class Snapshot {
     874    protected:
     875
     876      typedef Parent::NodeNotifier NodeNotifier;
     877
     878      class NodeObserverProxy : public NodeNotifier::ObserverBase {
     879      public:
     880
     881        NodeObserverProxy(Snapshot& _snapshot)
     882          : snapshot(_snapshot) {}
     883
     884        using NodeNotifier::ObserverBase::attach;
     885        using NodeNotifier::ObserverBase::detach;
     886        using NodeNotifier::ObserverBase::attached;
     887       
     888      protected:
     889       
     890        virtual void add(const Node& node) {
     891          snapshot.addNode(node);
     892        }
     893        virtual void add(const std::vector<Node>& nodes) {
     894          for (int i = nodes.size() - 1; i >= 0; ++i) {
     895            snapshot.addNode(nodes[i]);
     896          }
     897        }
     898        virtual void erase(const Node& node) {
     899          snapshot.eraseNode(node);
     900        }
     901        virtual void erase(const std::vector<Node>& nodes) {
     902          for (int i = 0; i < (int)nodes.size(); ++i) {
     903            snapshot.eraseNode(nodes[i]);
     904          }
     905        }
     906        virtual void build() {
     907          NodeNotifier* notifier = getNotifier();
     908          Node node;
     909          std::vector<Node> nodes;
     910          for (notifier->first(node); node != INVALID; notifier->next(node)) {
     911            nodes.push_back(node);
     912          }
     913          for (int i = nodes.size() - 1; i >= 0; --i) {
     914            snapshot.addNode(nodes[i]);
     915          }
     916        }
     917        virtual void clear() {
     918          NodeNotifier* notifier = getNotifier();
     919          Node node;
     920          for (notifier->first(node); node != INVALID; notifier->next(node)) {
     921            snapshot.eraseNode(node);
     922          }
     923        }
     924
     925        Snapshot& snapshot;
     926      };
     927
     928      class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
     929      public:
     930
     931        UEdgeObserverProxy(Snapshot& _snapshot)
     932          : snapshot(_snapshot) {}
     933
     934        using UEdgeNotifier::ObserverBase::attach;
     935        using UEdgeNotifier::ObserverBase::detach;
     936        using UEdgeNotifier::ObserverBase::attached;
     937       
     938      protected:
     939
     940        virtual void add(const UEdge& edge) {
     941          snapshot.addUEdge(edge);
     942        }
     943        virtual void add(const std::vector<UEdge>& edges) {
     944          for (int i = edges.size() - 1; i >= 0; ++i) {
     945            snapshot.addUEdge(edges[i]);
     946          }
     947        }
     948        virtual void erase(const UEdge& edge) {
     949          snapshot.eraseUEdge(edge);
     950        }
     951        virtual void erase(const std::vector<UEdge>& edges) {
     952          for (int i = 0; i < (int)edges.size(); ++i) {
     953            snapshot.eraseUEdge(edges[i]);
     954          }
     955        }
     956        virtual void build() {
     957          UEdgeNotifier* notifier = getNotifier();
     958          UEdge edge;
     959          std::vector<UEdge> edges;
     960          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
     961            edges.push_back(edge);
     962          }
     963          for (int i = edges.size() - 1; i >= 0; --i) {
     964            snapshot.addUEdge(edges[i]);
     965          }
     966        }
     967        virtual void clear() {
     968          UEdgeNotifier* notifier = getNotifier();
     969          UEdge edge;
     970          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
     971            snapshot.eraseUEdge(edge);
     972          }
     973        }
     974
     975        Snapshot& snapshot;
     976      };
     977     
     978      ListUGraph *graph;
     979
     980      NodeObserverProxy node_observer_proxy;
     981      UEdgeObserverProxy edge_observer_proxy;
     982
     983      std::list<Node> added_nodes;
     984      std::list<UEdge> added_edges;
     985
     986
     987      void addNode(const Node& node) {
     988        added_nodes.push_front(node);       
     989      }
     990      void eraseNode(const Node& node) {
     991        std::list<Node>::iterator it =
     992          std::find(added_nodes.begin(), added_nodes.end(), node);
     993        if (it == added_nodes.end()) {
     994          clear();
     995          edge_observer_proxy.detach();
     996          throw NodeNotifier::ImmediateDetach();
     997        } else {
     998          added_nodes.erase(it);
     999        }
     1000      }
     1001
     1002      void addUEdge(const UEdge& edge) {
     1003        added_edges.push_front(edge);       
     1004      }
     1005      void eraseUEdge(const UEdge& edge) {
     1006        std::list<UEdge>::iterator it =
     1007          std::find(added_edges.begin(), added_edges.end(), edge);
     1008        if (it == added_edges.end()) {
     1009          clear();
     1010          node_observer_proxy.detach();
     1011          throw UEdgeNotifier::ImmediateDetach();
     1012        } else {
     1013          added_edges.erase(it);
     1014        }       
     1015      }
     1016
     1017      void attach(ListUGraph &_graph) {
     1018        graph = &_graph;
     1019        node_observer_proxy.attach(graph->getNotifier(Node()));
     1020        edge_observer_proxy.attach(graph->getNotifier(UEdge()));
     1021      }
     1022           
     1023      void detach() {
     1024        node_observer_proxy.detach();
     1025        edge_observer_proxy.detach();
     1026      }
     1027
     1028      bool attached() const {
     1029        return node_observer_proxy.attached();
     1030      }
     1031
     1032      void clear() {
     1033        added_nodes.clear();
     1034        added_edges.clear();       
     1035      }
     1036
     1037    public:
     1038
     1039      /// \brief Default constructor.
     1040      ///
     1041      /// Default constructor.
     1042      /// To actually make a snapshot you must call save().
     1043      Snapshot()
     1044        : graph(0), node_observer_proxy(*this),
     1045          edge_observer_proxy(*this) {}
     1046     
     1047      /// \brief Constructor that immediately makes a snapshot.
     1048      ///     
     1049      /// This constructor immediately makes a snapshot of the graph.
     1050      /// \param _graph The graph we make a snapshot of.
     1051      Snapshot(ListUGraph &_graph)
     1052        : node_observer_proxy(*this),
     1053          edge_observer_proxy(*this) {
     1054        attach(_graph);
     1055      }
     1056     
     1057      /// \brief Make a snapshot.
     1058      ///
     1059      /// Make a snapshot of the graph.
     1060      ///
     1061      /// This function can be called more than once. In case of a repeated
     1062      /// call, the previous snapshot gets lost.
     1063      /// \param _graph The graph we make the snapshot of.
     1064      void save(ListUGraph &_graph) {
     1065        if (attached()) {
     1066          detach();
     1067          clear();
     1068        }
     1069        attach(_graph);
     1070      }
     1071     
     1072      /// \brief Undo the changes until the last snapshot.
     1073      //
     1074      /// Undo the changes until the last snapshot created by save().
     1075      void restore() {
     1076        detach();
     1077        for(std::list<UEdge>::iterator it = added_edges.begin();
     1078            it != added_edges.end(); ++it) {
     1079          graph->erase(*it);
     1080        }
     1081        for(std::list<Node>::iterator it = added_nodes.begin();
     1082            it != added_nodes.end(); ++it) {
     1083          graph->erase(*it);
     1084        }
     1085        clear();
     1086      }
     1087
     1088      /// \brief Gives back true when the snapshot is valid.
     1089      ///
     1090      /// Gives back true when the snapshot is valid.
     1091      bool valid() const {
     1092        return attached();
     1093      }
     1094    };
    8621095  };
    8631096
     
    11061339        bNodes[bNodeId].next = -1;
    11071340      }
     1341      bNodes[bNodeId].prev = -1;
    11081342      first_bnode = bNodeId;
    11091343      bNodes[bNodeId].first_edge = -1;
     
    11491383          aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
    11501384        } else {
    1151           first_anode = aNodes[aNodeId].next >> 1;
     1385          first_anode =
     1386            aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1;
    11521387        }
    11531388        if (aNodes[aNodeId].next != -1) {
     
    11611396          bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
    11621397        } else {
    1163           first_bnode = bNodes[bNodeId].next >> 1;
     1398          first_bnode =
     1399            bNodes[bNodeId].next != -1 ? bNodes[bNodeId].next >> 1 : -1;
    11641400        }
    11651401        if (bNodes[bNodeId].next != -1) {
     
    13971633    }
    13981634
     1635    /// \brief Class to make a snapshot of the graph and restore
     1636    /// to it later.
     1637    ///
     1638    /// Class to make a snapshot of the graph and to restore it
     1639    /// later.
     1640    ///
     1641    /// The newly added nodes and undirected edges can be removed
     1642    /// using the restore() function.
     1643    ///
     1644    /// \warning Edge and node deletions cannot be restored. This
     1645    /// events invalidate the snapshot.
     1646    class Snapshot {
     1647    protected:
     1648
     1649      typedef Parent::NodeNotifier NodeNotifier;
     1650
     1651      class NodeObserverProxy : public NodeNotifier::ObserverBase {
     1652      public:
     1653
     1654        NodeObserverProxy(Snapshot& _snapshot)
     1655          : snapshot(_snapshot) {}
     1656
     1657        using NodeNotifier::ObserverBase::attach;
     1658        using NodeNotifier::ObserverBase::detach;
     1659        using NodeNotifier::ObserverBase::attached;
     1660       
     1661      protected:
     1662       
     1663        virtual void add(const Node& node) {
     1664          snapshot.addNode(node);
     1665        }
     1666        virtual void add(const std::vector<Node>& nodes) {
     1667          for (int i = nodes.size() - 1; i >= 0; ++i) {
     1668            snapshot.addNode(nodes[i]);
     1669          }
     1670        }
     1671        virtual void erase(const Node& node) {
     1672          snapshot.eraseNode(node);
     1673        }
     1674        virtual void erase(const std::vector<Node>& nodes) {
     1675          for (int i = 0; i < (int)nodes.size(); ++i) {
     1676            snapshot.eraseNode(nodes[i]);
     1677          }
     1678        }
     1679        virtual void build() {
     1680          NodeNotifier* notifier = getNotifier();
     1681          Node node;
     1682          std::vector<Node> nodes;
     1683          for (notifier->first(node); node != INVALID; notifier->next(node)) {
     1684            nodes.push_back(node);
     1685          }
     1686          for (int i = nodes.size() - 1; i >= 0; --i) {
     1687            snapshot.addNode(nodes[i]);
     1688          }
     1689        }
     1690        virtual void clear() {
     1691          NodeNotifier* notifier = getNotifier();
     1692          Node node;
     1693          for (notifier->first(node); node != INVALID; notifier->next(node)) {
     1694            snapshot.eraseNode(node);
     1695          }
     1696        }
     1697
     1698        Snapshot& snapshot;
     1699      };
     1700
     1701      class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
     1702      public:
     1703
     1704        UEdgeObserverProxy(Snapshot& _snapshot)
     1705          : snapshot(_snapshot) {}
     1706
     1707        using UEdgeNotifier::ObserverBase::attach;
     1708        using UEdgeNotifier::ObserverBase::detach;
     1709        using UEdgeNotifier::ObserverBase::attached;
     1710       
     1711      protected:
     1712
     1713        virtual void add(const UEdge& edge) {
     1714          snapshot.addUEdge(edge);
     1715        }
     1716        virtual void add(const std::vector<UEdge>& edges) {
     1717          for (int i = edges.size() - 1; i >= 0; ++i) {
     1718            snapshot.addUEdge(edges[i]);
     1719          }
     1720        }
     1721        virtual void erase(const UEdge& edge) {
     1722          snapshot.eraseUEdge(edge);
     1723        }
     1724        virtual void erase(const std::vector<UEdge>& edges) {
     1725          for (int i = 0; i < (int)edges.size(); ++i) {
     1726            snapshot.eraseUEdge(edges[i]);
     1727          }
     1728        }
     1729        virtual void build() {
     1730          UEdgeNotifier* notifier = getNotifier();
     1731          UEdge edge;
     1732          std::vector<UEdge> edges;
     1733          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
     1734            edges.push_back(edge);
     1735          }
     1736          for (int i = edges.size() - 1; i >= 0; --i) {
     1737            snapshot.addUEdge(edges[i]);
     1738          }
     1739        }
     1740        virtual void clear() {
     1741          UEdgeNotifier* notifier = getNotifier();
     1742          UEdge edge;
     1743          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
     1744            snapshot.eraseUEdge(edge);
     1745          }
     1746        }
     1747
     1748        Snapshot& snapshot;
     1749      };
     1750     
     1751      ListBpUGraph *graph;
     1752
     1753      NodeObserverProxy node_observer_proxy;
     1754      UEdgeObserverProxy edge_observer_proxy;
     1755
     1756      std::list<Node> added_nodes;
     1757      std::list<UEdge> added_edges;
     1758
     1759
     1760      void addNode(const Node& node) {
     1761        added_nodes.push_front(node);       
     1762      }
     1763      void eraseNode(const Node& node) {
     1764        std::list<Node>::iterator it =
     1765          std::find(added_nodes.begin(), added_nodes.end(), node);
     1766        if (it == added_nodes.end()) {
     1767          clear();
     1768          edge_observer_proxy.detach();
     1769          throw NodeNotifier::ImmediateDetach();
     1770        } else {
     1771          added_nodes.erase(it);
     1772        }
     1773      }
     1774
     1775      void addUEdge(const UEdge& edge) {
     1776        added_edges.push_front(edge);       
     1777      }
     1778      void eraseUEdge(const UEdge& edge) {
     1779        std::list<UEdge>::iterator it =
     1780          std::find(added_edges.begin(), added_edges.end(), edge);
     1781        if (it == added_edges.end()) {
     1782          clear();
     1783          node_observer_proxy.detach();
     1784          throw UEdgeNotifier::ImmediateDetach();
     1785        } else {
     1786          added_edges.erase(it);
     1787        }       
     1788      }
     1789
     1790      void attach(ListBpUGraph &_graph) {
     1791        graph = &_graph;
     1792        node_observer_proxy.attach(graph->getNotifier(Node()));
     1793        edge_observer_proxy.attach(graph->getNotifier(UEdge()));
     1794      }
     1795           
     1796      void detach() {
     1797        node_observer_proxy.detach();
     1798        edge_observer_proxy.detach();
     1799      }
     1800
     1801      bool attached() const {
     1802        return node_observer_proxy.attached();
     1803      }
     1804
     1805      void clear() {
     1806        added_nodes.clear();
     1807        added_edges.clear();       
     1808      }
     1809
     1810    public:
     1811
     1812      /// \brief Default constructor.
     1813      ///
     1814      /// Default constructor.
     1815      /// To actually make a snapshot you must call save().
     1816      Snapshot()
     1817        : graph(0), node_observer_proxy(*this),
     1818          edge_observer_proxy(*this) {}
     1819     
     1820      /// \brief Constructor that immediately makes a snapshot.
     1821      ///     
     1822      /// This constructor immediately makes a snapshot of the graph.
     1823      /// \param _graph The graph we make a snapshot of.
     1824      Snapshot(ListBpUGraph &_graph)
     1825        : node_observer_proxy(*this),
     1826          edge_observer_proxy(*this) {
     1827        attach(_graph);
     1828      }
     1829     
     1830      /// \brief Make a snapshot.
     1831      ///
     1832      /// Make a snapshot of the graph.
     1833      ///
     1834      /// This function can be called more than once. In case of a repeated
     1835      /// call, the previous snapshot gets lost.
     1836      /// \param _graph The graph we make the snapshot of.
     1837      void save(ListBpUGraph &_graph) {
     1838        if (attached()) {
     1839          detach();
     1840          clear();
     1841        }
     1842        attach(_graph);
     1843      }
     1844     
     1845      /// \brief Undo the changes until the last snapshot.
     1846      //
     1847      /// Undo the changes until the last snapshot created by save().
     1848      void restore() {
     1849        detach();
     1850        for(std::list<UEdge>::iterator it = added_edges.begin();
     1851            it != added_edges.end(); ++it) {
     1852          graph->erase(*it);
     1853        }
     1854        for(std::list<Node>::iterator it = added_nodes.begin();
     1855            it != added_nodes.end(); ++it) {
     1856          graph->erase(*it);
     1857        }
     1858        clear();
     1859      }
     1860
     1861      /// \brief Gives back true when the snapshot is valid.
     1862      ///
     1863      /// Gives back true when the snapshot is valid.
     1864      bool valid() const {
     1865        return attached();
     1866      }
     1867    };
    13991868  };
    14001869
Note: See TracChangeset for help on using the changeset viewer.