COIN-OR::LEMON - Graph Library

Changeset 1842:8abf74160dc4 in lemon-0.x for lemon/graph_adaptor.h


Ignore:
Timestamp:
12/01/05 16:08:46 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2396
Message:

NewEdgeSetAdaptor? -> ListEdgeSet?
and moved to edge_set.h

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_adaptor.h

    r1839 r1842  
    16741674  };
    16751675
    1676   template <typename _Graph>
    1677   class NewEdgeSetAdaptorBase {
    1678   public:
    1679 
    1680     typedef _Graph Graph;
    1681     typedef typename Graph::Node Node;
    1682     typedef typename Graph::NodeIt NodeIt;
    1683 
    1684   protected:
    1685 
    1686     struct NodeT {
    1687       int first_out, first_in;
    1688       NodeT() : first_out(-1), first_in(-1) {}
    1689     };
    1690    
    1691     class NodesImpl : protected Graph::template NodeMap<NodeT> {
    1692 
    1693       typedef typename Graph::template NodeMap<NodeT> Parent;
    1694       typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
    1695 
    1696       Adaptor& adaptor;
    1697 
    1698     public:
    1699 
    1700       NodesImpl(Adaptor& _adaptor, const Graph& _graph)
    1701         : Parent(_graph), adaptor(_adaptor) {}
    1702 
    1703       virtual ~NodesImpl() {}
    1704 
    1705       virtual void build() {
    1706         Parent::build();
    1707       }
    1708 
    1709       virtual void clear() {
    1710         adaptor._clear();
    1711         Parent::clear();
    1712       }
    1713      
    1714       virtual void add(const Node& node) {
    1715         Parent::add(node);
    1716         adaptor._add(node);
    1717       }
    1718      
    1719       virtual void erase(const Node& node) {
    1720         adaptor._erase(node);
    1721         Parent::erase(node);
    1722       }
    1723 
    1724       NodeT& operator[](const Node& node) {
    1725         return Parent::operator[](node);
    1726       }
    1727 
    1728       const NodeT& operator[](const Node& node) const {
    1729         return Parent::operator[](node);
    1730       }
    1731      
    1732     };
    1733 
    1734     NodesImpl* nodes;
    1735 
    1736     struct EdgeT {
    1737       Node source, target;
    1738       int next_out, next_in;
    1739       int prev_out, prev_in;
    1740       EdgeT() : prev_out(-1), prev_in(-1) {}
    1741     };
    1742 
    1743     std::vector<EdgeT> edges;
    1744 
    1745     int first_edge;
    1746     int first_free_edge;
    1747 
    1748     virtual void _clear() = 0;
    1749     virtual void _add(const Node& node) = 0;
    1750     virtual void _erase(const Node& node) = 0;
    1751    
    1752     const Graph* graph;
    1753 
    1754     void initalize(const Graph& _graph, NodesImpl& _nodes) {
    1755       graph = &_graph;
    1756       nodes = &_nodes;
    1757     }
    1758    
    1759   public:
    1760 
    1761     class Edge {
    1762       friend class NewEdgeSetAdaptorBase<Graph>;
    1763     protected:
    1764       Edge(int _id) : id(_id) {}
    1765       int id;
    1766     public:
    1767       Edge() {}
    1768       Edge(Invalid) : id(-1) {}
    1769       bool operator==(const Edge& edge) const { return id == edge.id; }
    1770       bool operator!=(const Edge& edge) const { return id != edge.id; }
    1771       bool operator<(const Edge& edge) const { return id < edge.id; }
    1772     };
    1773 
    1774     NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
    1775     virtual ~NewEdgeSetAdaptorBase() {}
    1776 
    1777     Edge addEdge(const Node& source, const Node& target) {
    1778       int n;
    1779       if (first_free_edge == -1) {
    1780         n = edges.size();
    1781         edges.push_back(EdgeT());
    1782       } else {
    1783         n = first_free_edge;
    1784         first_free_edge = edges[first_free_edge].next_in;
    1785       }
    1786       edges[n].next_in = (*nodes)[target].first_in;
    1787       (*nodes)[target].first_in = n;
    1788       edges[n].next_out = (*nodes)[source].first_out;
    1789       (*nodes)[source].first_out = n;
    1790       edges[n].source = source;
    1791       edges[n].target = target;
    1792       return Edge(n);
    1793     }
    1794 
    1795     void erase(const Edge& edge) {
    1796       int n = edge.id;
    1797       if (edges[n].prev_in != -1) {
    1798         edges[edges[n].prev_in].next_in = edges[n].next_in;
    1799       } else {
    1800         (*nodes)[edges[n].target].first_in = edges[n].next_in;
    1801       }
    1802       if (edges[n].next_in != -1) {
    1803         edges[edges[n].next_in].prev_in = edges[n].prev_in;
    1804       }
    1805 
    1806       if (edges[n].prev_out != -1) {
    1807         edges[edges[n].prev_out].next_out = edges[n].next_out;
    1808       } else {
    1809         (*nodes)[edges[n].source].first_out = edges[n].next_out;
    1810       }
    1811       if (edges[n].next_out != -1) {
    1812         edges[edges[n].next_out].prev_out = edges[n].prev_out;
    1813       }
    1814            
    1815     }
    1816 
    1817     void first(Node& node) const {
    1818       graph->first(node);
    1819     }
    1820 
    1821     void next(Node& node) const {
    1822       graph->next(node);
    1823     }
    1824 
    1825     void first(Edge& edge) const {
    1826       Node node;
    1827       for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
    1828            next(node));
    1829       edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
    1830     }
    1831 
    1832     void next(Edge& edge) const {
    1833       if (edges[edge.id].next_in != -1) {
    1834         edge.id = edges[edge.id].next_in;
    1835       } else {
    1836         Node node = edges[edge.id].target;
    1837         for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
    1838              next(node));
    1839         edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
    1840       }     
    1841     }
    1842 
    1843     void firstOut(Edge& edge, const Node& node) const {
    1844       edge.id = (*nodes)[node].first_out;   
    1845     }
    1846    
    1847     void nextOut(Edge& edge) const {
    1848       edge.id = edges[edge.id].next_out;       
    1849     }
    1850 
    1851     void firstIn(Edge& edge, const Node& node) const {
    1852       edge.id = (*nodes)[node].first_in;         
    1853     }
    1854 
    1855     void nextIn(Edge& edge) const {
    1856       edge.id = edges[edge.id].next_in;   
    1857     }
    1858 
    1859     int id(const Node& node) const { return graph->id(node); }
    1860     int id(const Edge& edge) const { return edge.id; }
    1861 
    1862     Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
    1863     Edge edgeFromId(int id) const { return Edge(id); }
    1864 
    1865     int maxNodeId() const { return graph->maxId(Node()); };
    1866     int maxEdgeId() const { return edges.size() - 1; }
    1867 
    1868     Node source(const Edge& edge) const { return edges[edge.id].source;}
    1869     Node target(const Edge& edge) const { return edges[edge.id].target;}
    1870 
    1871   };
    1872 
    1873 
    1874   /// \brief Graph adaptor using a node set of another graph and an
    1875   /// own edge set.
    1876   ///
    1877   /// This structure can be used to establish another graph over a node set
    1878   /// of an existing one. The node iterator will go through the nodes of the
    1879   /// original graph.
    1880   ///
    1881   /// \param _Graph The type of the graph which shares its node set with
    1882   /// this class. Its interface must conform to the \ref concept::StaticGraph
    1883   /// "StaticGraph" concept.
    1884   ///
    1885   /// In the edge extension and removing it conforms to the
    1886   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
    1887   template <typename _Graph>
    1888   class NewEdgeSetAdaptor :
    1889     public ErasableGraphExtender<
    1890     ClearableGraphExtender<
    1891     ExtendableGraphExtender<
    1892     MappableGraphExtender<
    1893     IterableGraphExtender<
    1894     AlterableGraphExtender<
    1895     GraphExtender<
    1896     NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
    1897 
    1898   public:
    1899 
    1900     typedef ErasableGraphExtender<
    1901       ClearableGraphExtender<
    1902       ExtendableGraphExtender<
    1903       MappableGraphExtender<
    1904       IterableGraphExtender<
    1905       AlterableGraphExtender<
    1906       GraphExtender<
    1907       NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
    1908    
    1909 
    1910     typedef typename Parent::Node Node;
    1911     typedef typename Parent::Edge Edge;
    1912 
    1913   private:
    1914 
    1915     virtual void _clear() {
    1916       Parent::edges.clear();
    1917       Parent::first_edge = -1;
    1918       Parent::first_free_edge = -1;
    1919       Parent::getNotifier(Edge()).clear();
    1920       Parent::getNotifier(Node()).clear();
    1921     }
    1922 
    1923     virtual void _add(const Node& node) {
    1924       Parent::getNotifier(Node()).add(node);
    1925     }
    1926 
    1927     virtual void _erase(const Node& node) {
    1928       Edge edge;
    1929       Parent::firstOut(edge, node);
    1930       while (edge != INVALID) {
    1931         Parent::erase(edge);
    1932         Parent::firstOut(edge, node);
    1933       }
    1934 
    1935       Parent::firstIn(edge, node);
    1936       while (edge != INVALID) {
    1937         Parent::erase(edge);
    1938         Parent::firstIn(edge, node);
    1939       }
    1940      
    1941       Parent::getNotifier(Node()).erase(node);
    1942     }
    1943 
    1944 
    1945     typedef typename Parent::NodesImpl NodesImpl;
    1946 
    1947     NodesImpl nodes;
    1948    
    1949   public:
    1950 
    1951     /// \brief Constructor of the adaptor.
    1952     ///
    1953     /// Constructor of the adaptor.
    1954     NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
    1955       Parent::initalize(_graph, nodes);
    1956     }
    1957 
    1958     void clear() {
    1959       Parent::getNotifier(Edge()).clear();     
    1960 
    1961       Parent::edges.clear();
    1962       Parent::first_edge = -1;
    1963       Parent::first_free_edge = -1;
    1964     }
    1965    
    1966   };
    1967 
    1968   /// \brief Graph adaptor using a node set of another graph and an
    1969   /// own undir edge set.
    1970   ///
    1971   /// This structure can be used to establish another undirected graph over
    1972   /// a node set of an existing one. The node iterator will go through the
    1973   /// nodes of the original graph.
    1974   ///
    1975   /// \param _Graph The type of the graph which shares its node set with
    1976   /// this class. Its interface must conform to the \ref concept::StaticGraph
    1977   /// "StaticGraph" concept.
    1978   ///
    1979   /// In the edge extension and removing it conforms to the
    1980   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
    1981   template <typename _Graph>
    1982   class NewUndirEdgeSetAdaptor :
    1983     public ErasableUndirGraphExtender<
    1984     ClearableUndirGraphExtender<
    1985     ExtendableUndirGraphExtender<
    1986     MappableUndirGraphExtender<
    1987     IterableUndirGraphExtender<
    1988     AlterableUndirGraphExtender<
    1989     UndirGraphExtender<
    1990     NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
    1991 
    1992   public:
    1993 
    1994     typedef ErasableUndirGraphExtender<
    1995       ClearableUndirGraphExtender<
    1996       ExtendableUndirGraphExtender<
    1997       MappableUndirGraphExtender<
    1998       IterableUndirGraphExtender<
    1999       AlterableUndirGraphExtender<
    2000       UndirGraphExtender<
    2001       NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
    2002    
    2003 
    2004     typedef typename Parent::Node Node;
    2005     typedef typename Parent::Edge Edge;
    2006     typedef typename Parent::UndirEdge UndirEdge;
    2007 
    2008   private:
    2009 
    2010     virtual void _clear() {
    2011       Parent::edges.clear();
    2012       Parent::first_edge = -1;
    2013       Parent::first_free_edge = -1;
    2014       Parent::getNotifier(Edge()).clear();
    2015       Parent::getNotifier(Node()).clear();
    2016     }
    2017 
    2018     virtual void _add(const Node& node) {
    2019       Parent::getNotifier(Node()).add(node);
    2020     }
    2021 
    2022     virtual void _erase(const Node& node) {
    2023       Edge edge;
    2024       Parent::firstOut(edge, node);
    2025       while (edge != INVALID) {
    2026         Parent::erase(edge);
    2027         Parent::firstOut(edge, node);
    2028       }
    2029 
    2030       Parent::firstIn(edge, node);
    2031       while (edge != INVALID) {
    2032         Parent::erase(edge);
    2033         Parent::firstIn(edge, node);
    2034       }
    2035      
    2036       Parent::getNotifier(Node()).erase(node);
    2037     }
    2038 
    2039     typedef typename Parent::NodesImpl NodesImpl;
    2040 
    2041     NodesImpl nodes;
    2042    
    2043   public:
    2044 
    2045 
    2046     /// \brief Constructor of the adaptor.
    2047     ///
    2048     /// Constructor of the adaptor.
    2049     NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
    2050       Parent::initalize(_graph, nodes);
    2051     }
    2052 
    2053     void clear() {
    2054       Parent::getNotifier(Edge()).clear();     
    2055       Parent::getNotifier(UndirEdge()).clear();     
    2056 
    2057       Parent::edges.clear();
    2058       Parent::first_edge = -1;
    2059       Parent::first_free_edge = -1;
    2060     }
    2061    
    2062   };
    2063 
    20641676  ///@}
    20651677
Note: See TracChangeset for help on using the changeset viewer.