COIN-OR::LEMON - Graph Library

Changeset 1018:2e959a5a0c2d in lemon-main


Ignore:
Timestamp:
11/14/10 16:35:31 (14 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Add bipartite graph concepts (#69)

Files:
2 added
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/concepts/graph.h

    r877 r1018  
    7373    class Graph {
    7474    private:
    75       /// Graphs are \e not copy constructible. Use DigraphCopy instead.
     75      /// Graphs are \e not copy constructible. Use GraphCopy instead.
    7676      Graph(const Graph&) {}
    7777      /// \brief Assignment of a graph to another one is \e not allowed.
    78       /// Use DigraphCopy instead.
     78      /// Use GraphCopy instead.
    7979      void operator=(const Graph&) {}
    8080
  • lemon/concepts/graph_components.h

    r1010 r1018  
    300300    };
    301301
     302    /// \brief Base skeleton class for undirected bipartite graphs.
     303    ///
     304    /// This class describes the base interface of undirected
     305    /// bipartite graph types.  All bipartite graph %concepts have to
     306    /// conform to this class.  It extends the interface of \ref
     307    /// BaseGraphComponent with an \c Edge type and functions to get
     308    /// the end nodes of edges, to convert from arcs to edges and to
     309    /// get both direction of edges.
     310    class BaseBpGraphComponent : public BaseGraphComponent {
     311    public:
     312
     313      typedef BaseBpGraphComponent BpGraph;
     314
     315      typedef BaseDigraphComponent::Node Node;
     316      typedef BaseDigraphComponent::Arc Arc;
     317
     318      /// \brief Class to represent red nodes.
     319      ///
     320      /// This class represents the red nodes of the graph. It does
     321      /// not supposed to be used directly, because the nodes can be
     322      /// represented as Node instances. This class can be used as
     323      /// template parameter for special map classes.
     324      class RedNode : public Node {
     325        typedef Node Parent;
     326
     327      public:
     328        /// \brief Default constructor.
     329        ///
     330        /// Default constructor.
     331        /// \warning The default constructor is not required to set
     332        /// the item to some well-defined value. So you should consider it
     333        /// as uninitialized.
     334        RedNode() {}
     335
     336        /// \brief Copy constructor.
     337        ///
     338        /// Copy constructor.
     339        RedNode(const RedNode &) : Parent() {}
     340
     341        /// \brief Constructor for conversion from \c INVALID.
     342        ///
     343        /// Constructor for conversion from \c INVALID.
     344        /// It initializes the item to be invalid.
     345        /// \sa Invalid for more details.
     346        RedNode(Invalid) {}
     347
     348        /// \brief Constructor for conversion from a node.
     349        ///
     350        /// Constructor for conversion from a node. The conversion can
     351        /// be invalid, since the Node can be member of the blue
     352        /// set.
     353        RedNode(const Node&) {}
     354      };
     355
     356      /// \brief Class to represent blue nodes.
     357      ///
     358      /// This class represents the blue nodes of the graph. It does
     359      /// not supposed to be used directly, because the nodes can be
     360      /// represented as Node instances. This class can be used as
     361      /// template parameter for special map classes.
     362      class BlueNode : public Node {
     363        typedef Node Parent;
     364
     365      public:
     366        /// \brief Default constructor.
     367        ///
     368        /// Default constructor.
     369        /// \warning The default constructor is not required to set
     370        /// the item to some well-defined value. So you should consider it
     371        /// as uninitialized.
     372        BlueNode() {}
     373
     374        /// \brief Copy constructor.
     375        ///
     376        /// Copy constructor.
     377        BlueNode(const BlueNode &) : Parent() {}
     378
     379        /// \brief Constructor for conversion from \c INVALID.
     380        ///
     381        /// Constructor for conversion from \c INVALID.
     382        /// It initializes the item to be invalid.
     383        /// \sa Invalid for more details.
     384        BlueNode(Invalid) {}
     385
     386        /// \brief Constructor for conversion from a node.
     387        ///
     388        /// Constructor for conversion from a node. The conversion can
     389        /// be invalid, since the Node can be member of the red
     390        /// set.
     391        BlueNode(const Node&) {}
     392      };
     393
     394      /// \brief Gives back %true for red nodes.
     395      ///
     396      /// Gives back %true for red nodes.
     397      bool red(const Node&) const { return true; }
     398
     399      /// \brief Gives back %true for blue nodes.
     400      ///
     401      /// Gives back %true for blue nodes.
     402      bool blue(const Node&) const { return true; }
     403
     404      /// \brief Gives back the red end node of the edge.
     405      ///
     406      /// Gives back the red end node of the edge.
     407      Node redNode(const Edge&) const { return Node(); }
     408
     409      /// \brief Gives back the blue end node of the edge.
     410      ///
     411      /// Gives back the blue end node of the edge.
     412      Node blueNode(const Edge&) const { return Node(); }
     413
     414      template <typename _BpGraph>
     415      struct Constraints {
     416        typedef typename _BpGraph::Node Node;
     417        typedef typename _BpGraph::RedNode RedNode;
     418        typedef typename _BpGraph::BlueNode BlueNode;
     419        typedef typename _BpGraph::Arc Arc;
     420        typedef typename _BpGraph::Edge Edge;
     421
     422        void constraints() {
     423          checkConcept<BaseGraphComponent, _BpGraph>();
     424          checkConcept<GraphItem<'n'>, RedNode>();
     425          checkConcept<GraphItem<'n'>, BlueNode>();
     426          {
     427            Node n;
     428            RedNode rn = n;
     429            BlueNode bn = bn;
     430            Edge e;
     431            bool b;
     432            b = bpgraph.red(n);
     433            b = bpgraph.blue(n);
     434            ignore_unused_variable_warning(b);
     435            n = bpgraph.redNode(e);
     436            n = bpgraph.blueNode(e);
     437            rn = n;
     438            bn = n;
     439          }
     440        }
     441
     442        const _BpGraph& bpgraph;
     443      };
     444
     445    };
     446
    302447    /// \brief Skeleton class for \e idable directed graphs.
    303448    ///
     
    429574        const _Graph& graph;
    430575        Constraints() {}
     576      };
     577    };
     578
     579    /// \brief Skeleton class for \e idable undirected bipartite graphs.
     580    ///
     581    /// This class describes the interface of \e idable undirected
     582    /// bipartite graphs. It extends \ref IDableGraphComponent with
     583    /// the core ID functions of undirected bipartite graphs. Beside
     584    /// the regular node ids, this class also provides ids within the
     585    /// the red and blue sets of the nodes. This concept is part of
     586    /// the BpGraph concept.
     587    template <typename BAS = BaseBpGraphComponent>
     588    class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
     589    public:
     590
     591      typedef BAS Base;
     592      typedef IDableGraphComponent<BAS> Parent;
     593      typedef typename Base::Node Node;
     594      typedef typename Base::RedNode RedNode;
     595      typedef typename Base::BlueNode BlueNode;
     596
     597      using Parent::id;
     598
     599      /// \brief Return a unique integer id for the given node in the red set.
     600      ///
     601      /// Return a unique integer id for the given node in the red set.
     602      int redId(const Node&) const { return -1; }
     603
     604      /// \brief Return the same value as redId().
     605      ///
     606      /// Return the same value as redId().
     607      int id(const RedNode&) const { return -1; }
     608
     609      /// \brief Return a unique integer id for the given node in the blue set.
     610      ///
     611      /// Return a unique integer id for the given node in the blue set.
     612      int blueId(const Node&) const { return -1; }
     613
     614      /// \brief Return the same value as blueId().
     615      ///
     616      /// Return the same value as blueId().
     617      int id(const BlueNode&) const { return -1; }
     618
     619      /// \brief Return an integer greater or equal to the maximum
     620      /// node id in the red set.
     621      ///
     622      /// Return an integer greater or equal to the maximum
     623      /// node id in the red set.
     624      int maxRedId() const { return -1; }
     625
     626      /// \brief Return an integer greater or equal to the maximum
     627      /// node id in the blue set.
     628      ///
     629      /// Return an integer greater or equal to the maximum
     630      /// node id in the blue set.
     631      int maxBlueId() const { return -1; }
     632
     633      template <typename _BpGraph>
     634      struct Constraints {
     635
     636        void constraints() {
     637          checkConcept<IDableGraphComponent<Base>, _BpGraph>();
     638          typename _BpGraph::Node node;
     639          typename _BpGraph::RedNode red;
     640          typename _BpGraph::BlueNode blue;
     641          int rid = bpgraph.redId(node);
     642          int bid = bpgraph.blueId(node);
     643          rid = bpgraph.id(red);
     644          bid = bpgraph.id(blue);
     645          rid = bpgraph.maxRedId();
     646          bid = bpgraph.maxBlueId();
     647          ignore_unused_variable_warning(rid);
     648          ignore_unused_variable_warning(bid);
     649        }
     650
     651        const _BpGraph& bpgraph;
    431652      };
    432653    };
     
    9051126    };
    9061127
     1128    /// \brief Skeleton class for iterable undirected bipartite graphs.
     1129    ///
     1130    /// This class describes the interface of iterable undirected
     1131    /// bipartite graphs. It extends \ref IterableGraphComponent with
     1132    /// the core iterable interface of undirected bipartite graphs.
     1133    /// This concept is part of the BpGraph concept.
     1134    template <typename BAS = BaseBpGraphComponent>
     1135    class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
     1136    public:
     1137
     1138      typedef BAS Base;
     1139      typedef typename Base::Node Node;
     1140      typedef typename Base::Arc Arc;
     1141      typedef typename Base::Edge Edge;
     1142
     1143
     1144      typedef IterableBpGraphComponent BpGraph;
     1145
     1146      /// \name Base Iteration
     1147      ///
     1148      /// This interface provides functions for iteration on red and blue nodes.
     1149      ///
     1150      /// @{
     1151
     1152      /// \brief Return the first red node.
     1153      ///
     1154      /// This function gives back the first red node in the iteration order.
     1155      void firstRed(Node&) const {}
     1156
     1157      /// \brief Return the next red node.
     1158      ///
     1159      /// This function gives back the next red node in the iteration order.
     1160      void nextRed(Node&) const {}
     1161
     1162      /// \brief Return the first blue node.
     1163      ///
     1164      /// This function gives back the first blue node in the iteration order.
     1165      void firstBlue(Node&) const {}
     1166
     1167      /// \brief Return the next blue node.
     1168      ///
     1169      /// This function gives back the next blue node in the iteration order.
     1170      void nextBlue(Node&) const {}
     1171
     1172
     1173      /// @}
     1174
     1175      /// \name Class Based Iteration
     1176      ///
     1177      /// This interface provides iterator classes for red and blue nodes.
     1178      ///
     1179      /// @{
     1180
     1181      /// \brief This iterator goes through each red node.
     1182      ///
     1183      /// This iterator goes through each red node.
     1184      typedef GraphItemIt<BpGraph, Node> RedIt;
     1185
     1186      /// \brief This iterator goes through each blue node.
     1187      ///
     1188      /// This iterator goes through each blue node.
     1189      typedef GraphItemIt<BpGraph, Node> BlueIt;
     1190
     1191      /// @}
     1192
     1193      template <typename _BpGraph>
     1194      struct Constraints {
     1195        void constraints() {
     1196          checkConcept<IterableGraphComponent<Base>, _BpGraph>();
     1197
     1198          typename _BpGraph::Node node(INVALID);
     1199          bpgraph.firstRed(node);
     1200          bpgraph.nextRed(node);
     1201          bpgraph.firstBlue(node);
     1202          bpgraph.nextBlue(node);
     1203
     1204          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>,
     1205            typename _BpGraph::RedIt>();
     1206          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>,
     1207            typename _BpGraph::BlueIt>();
     1208        }
     1209
     1210        const _BpGraph& bpgraph;
     1211      };
     1212    };
     1213
    9071214    /// \brief Skeleton class for alterable directed graphs.
    9081215    ///
     
    9301237      ArcNotifier;
    9311238
     1239      mutable NodeNotifier node_notifier;
     1240      mutable ArcNotifier arc_notifier;
     1241
    9321242      /// \brief Return the node alteration notifier.
    9331243      ///
    9341244      /// This function gives back the node alteration notifier.
    9351245      NodeNotifier& notifier(Node) const {
    936          return NodeNotifier();
     1246        return node_notifier;
    9371247      }
    9381248
     
    9411251      /// This function gives back the arc alteration notifier.
    9421252      ArcNotifier& notifier(Arc) const {
    943         return ArcNotifier();
     1253        return arc_notifier;
    9441254      }
    9451255
     
    9771287
    9781288      typedef BAS Base;
     1289      typedef AlterableDigraphComponent<Base> Parent;
    9791290      typedef typename Base::Edge Edge;
    9801291
     
    9841295      EdgeNotifier;
    9851296
     1297      mutable EdgeNotifier edge_notifier;
     1298
     1299      using Parent::notifier;
     1300
    9861301      /// \brief Return the edge alteration notifier.
    9871302      ///
    9881303      /// This function gives back the edge alteration notifier.
    9891304      EdgeNotifier& notifier(Edge) const {
    990         return EdgeNotifier();
     1305        return edge_notifier;
    9911306      }
    9921307
     
    10021317        const _Graph& graph;
    10031318        Constraints() {}
     1319      };
     1320    };
     1321
     1322    /// \brief Skeleton class for alterable undirected bipartite graphs.
     1323    ///
     1324    /// This class describes the interface of alterable undirected
     1325    /// bipartite graphs. It extends \ref AlterableGraphComponent with
     1326    /// the alteration notifier interface of bipartite graphs. It
     1327    /// implements an observer-notifier pattern for the red and blue
     1328    /// nodes. More obsevers can be registered into the notifier and
     1329    /// whenever an alteration occured in the graph all the observers
     1330    /// will be notified about it.
     1331    template <typename BAS = BaseBpGraphComponent>
     1332    class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
     1333    public:
     1334
     1335      typedef BAS Base;
     1336      typedef AlterableGraphComponent<Base> Parent;
     1337      typedef typename Base::RedNode RedNode;
     1338      typedef typename Base::BlueNode BlueNode;
     1339
     1340
     1341      /// Red node alteration notifier class.
     1342      typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
     1343      RedNodeNotifier;
     1344
     1345      /// Blue node alteration notifier class.
     1346      typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
     1347      BlueNodeNotifier;
     1348
     1349      mutable RedNodeNotifier red_node_notifier;
     1350      mutable BlueNodeNotifier blue_node_notifier;
     1351
     1352      using Parent::notifier;
     1353
     1354      /// \brief Return the red node alteration notifier.
     1355      ///
     1356      /// This function gives back the red node alteration notifier.
     1357      RedNodeNotifier& notifier(RedNode) const {
     1358        return red_node_notifier;
     1359      }
     1360
     1361      /// \brief Return the blue node alteration notifier.
     1362      ///
     1363      /// This function gives back the blue node alteration notifier.
     1364      BlueNodeNotifier& notifier(BlueNode) const {
     1365        return blue_node_notifier;
     1366      }
     1367
     1368      template <typename _BpGraph>
     1369      struct Constraints {
     1370        void constraints() {
     1371          checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
     1372          typename _BpGraph::RedNodeNotifier& rnn
     1373            = bpgraph.notifier(typename _BpGraph::RedNode());
     1374          typename _BpGraph::BlueNodeNotifier& bnn
     1375            = bpgraph.notifier(typename _BpGraph::BlueNode());
     1376          ignore_unused_variable_warning(rnn);
     1377          ignore_unused_variable_warning(bnn);
     1378        }
     1379
     1380        const _BpGraph& bpgraph;
    10041381      };
    10051382    };
     
    13081685    };
    13091686
     1687    /// \brief Skeleton class for mappable undirected bipartite graphs.
     1688    ///
     1689    /// This class describes the interface of mappable undirected
     1690    /// bipartite graphs.  It extends \ref MappableGraphComponent with
     1691    /// the standard graph map class for red and blue nodes (\c
     1692    /// RedMap and BlueMap). This concept is part of the BpGraph concept.
     1693    template <typename BAS = BaseBpGraphComponent>
     1694    class MappableBpGraphComponent : public MappableGraphComponent<BAS>  {
     1695    public:
     1696
     1697      typedef BAS Base;
     1698      typedef typename Base::Node Node;
     1699
     1700      typedef MappableBpGraphComponent BpGraph;
     1701
     1702      /// \brief Standard graph map for the red nodes.
     1703      ///
     1704      /// Standard graph map for the red nodes.
     1705      /// It conforms to the ReferenceMap concept.
     1706      template <typename V>
     1707      class RedMap : public GraphMap<MappableBpGraphComponent, Node, V> {
     1708        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
     1709
     1710      public:
     1711        /// \brief Construct a new map.
     1712        ///
     1713        /// Construct a new map for the graph.
     1714        explicit RedMap(const MappableBpGraphComponent& graph)
     1715          : Parent(graph) {}
     1716
     1717        /// \brief Construct a new map with default value.
     1718        ///
     1719        /// Construct a new map for the graph and initalize the values.
     1720        RedMap(const MappableBpGraphComponent& graph, const V& value)
     1721          : Parent(graph, value) {}
     1722
     1723      private:
     1724        /// \brief Copy constructor.
     1725        ///
     1726        /// Copy Constructor.
     1727        RedMap(const RedMap& nm) : Parent(nm) {}
     1728
     1729        /// \brief Assignment operator.
     1730        ///
     1731        /// Assignment operator.
     1732        template <typename CMap>
     1733        RedMap& operator=(const CMap&) {
     1734          checkConcept<ReadMap<Node, V>, CMap>();
     1735          return *this;
     1736        }
     1737
     1738      };
     1739
     1740      /// \brief Standard graph map for the blue nodes.
     1741      ///
     1742      /// Standard graph map for the blue nodes.
     1743      /// It conforms to the ReferenceMap concept.
     1744      template <typename V>
     1745      class BlueMap : public GraphMap<MappableBpGraphComponent, Node, V> {
     1746        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
     1747
     1748      public:
     1749        /// \brief Construct a new map.
     1750        ///
     1751        /// Construct a new map for the graph.
     1752        explicit BlueMap(const MappableBpGraphComponent& graph)
     1753          : Parent(graph) {}
     1754
     1755        /// \brief Construct a new map with default value.
     1756        ///
     1757        /// Construct a new map for the graph and initalize the values.
     1758        BlueMap(const MappableBpGraphComponent& graph, const V& value)
     1759          : Parent(graph, value) {}
     1760
     1761      private:
     1762        /// \brief Copy constructor.
     1763        ///
     1764        /// Copy Constructor.
     1765        BlueMap(const BlueMap& nm) : Parent(nm) {}
     1766
     1767        /// \brief Assignment operator.
     1768        ///
     1769        /// Assignment operator.
     1770        template <typename CMap>
     1771        BlueMap& operator=(const CMap&) {
     1772          checkConcept<ReadMap<Node, V>, CMap>();
     1773          return *this;
     1774        }
     1775
     1776      };
     1777
     1778
     1779      template <typename _BpGraph>
     1780      struct Constraints {
     1781
     1782        struct Dummy {
     1783          int value;
     1784          Dummy() : value(0) {}
     1785          Dummy(int _v) : value(_v) {}
     1786        };
     1787
     1788        void constraints() {
     1789          checkConcept<MappableGraphComponent<Base>, _BpGraph>();
     1790
     1791          { // int map test
     1792            typedef typename _BpGraph::template RedMap<int> IntRedMap;
     1793            checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>,
     1794              IntRedMap >();
     1795          } { // bool map test
     1796            typedef typename _BpGraph::template RedMap<bool> BoolRedMap;
     1797            checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>,
     1798              BoolRedMap >();
     1799          } { // Dummy map test
     1800            typedef typename _BpGraph::template RedMap<Dummy> DummyRedMap;
     1801            checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>,
     1802              DummyRedMap >();
     1803          }
     1804
     1805          { // int map test
     1806            typedef typename _BpGraph::template BlueMap<int> IntBlueMap;
     1807            checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>,
     1808              IntBlueMap >();
     1809          } { // bool map test
     1810            typedef typename _BpGraph::template BlueMap<bool> BoolBlueMap;
     1811            checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>,
     1812              BoolBlueMap >();
     1813          } { // Dummy map test
     1814            typedef typename _BpGraph::template BlueMap<Dummy> DummyBlueMap;
     1815            checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>,
     1816              DummyBlueMap >();
     1817          }
     1818        }
     1819
     1820        const _BpGraph& bpgraph;
     1821      };
     1822    };
     1823
    13101824    /// \brief Skeleton class for extendable directed graphs.
    13111825    ///
     
    13981912    };
    13991913
     1914    /// \brief Skeleton class for extendable undirected bipartite graphs.
     1915    ///
     1916    /// This class describes the interface of extendable undirected
     1917    /// bipartite graphs. It extends \ref BaseGraphComponent with
     1918    /// functions for adding nodes and edges to the graph. This
     1919    /// concept requires \ref AlterableBpGraphComponent.
     1920    template <typename BAS = BaseBpGraphComponent>
     1921    class ExtendableBpGraphComponent : public BAS {
     1922    public:
     1923
     1924      typedef BAS Base;
     1925      typedef typename Base::Node Node;
     1926      typedef typename Base::Edge Edge;
     1927
     1928      /// \brief Add a new red node to the digraph.
     1929      ///
     1930      /// This function adds a red new node to the digraph.
     1931      Node addRedNode() {
     1932        return INVALID;
     1933      }
     1934
     1935      /// \brief Add a new blue node to the digraph.
     1936      ///
     1937      /// This function adds a blue new node to the digraph.
     1938      Node addBlueNode() {
     1939        return INVALID;
     1940      }
     1941
     1942      /// \brief Add a new edge connecting the given two nodes.
     1943      ///
     1944      /// This function adds a new edge connecting the given two nodes
     1945      /// of the graph. The first node has to be a red node, and the
     1946      /// second one a blue node.
     1947      Edge addEdge(const Node&, const Node&) {
     1948        return INVALID;
     1949      }
     1950
     1951      template <typename _BpGraph>
     1952      struct Constraints {
     1953        void constraints() {
     1954          checkConcept<Base, _BpGraph>();
     1955          typename _BpGraph::Node red_node, blue_node;
     1956          red_node = bpgraph.addRedNode();
     1957          blue_node = bpgraph.addBlueNode();
     1958          typename _BpGraph::Edge edge;
     1959          edge = bpgraph.addEdge(red_node, blue_node);
     1960        }
     1961
     1962        _BpGraph& bpgraph;
     1963      };
     1964    };
     1965
    14001966    /// \brief Skeleton class for erasable directed graphs.
    14011967    ///
     
    14782044    };
    14792045
     2046    /// \brief Skeleton class for erasable undirected graphs.
     2047    ///
     2048    /// This class describes the interface of erasable undirected
     2049    /// bipartite graphs. It extends \ref BaseBpGraphComponent with
     2050    /// functions for removing nodes and edges from the graph. This
     2051    /// concept requires \ref AlterableBpGraphComponent.
     2052    template <typename BAS = BaseBpGraphComponent>
     2053    class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
     2054
    14802055    /// \brief Skeleton class for clearable directed graphs.
    14812056    ///
     
    15142089    /// This concept requires \ref AlterableGraphComponent.
    15152090    template <typename BAS = BaseGraphComponent>
    1516     class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
    1517     public:
    1518 
    1519       typedef BAS Base;
    1520 
    1521       /// \brief Erase all nodes and edges from the graph.
    1522       ///
    1523       /// This function erases all nodes and edges from the graph.
    1524       void clear() {}
    1525 
    1526       template <typename _Graph>
    1527       struct Constraints {
    1528         void constraints() {
    1529           checkConcept<Base, _Graph>();
    1530           graph.clear();
    1531         }
    1532 
    1533         _Graph& graph;
    1534         Constraints() {}
    1535       };
    1536     };
     2091    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
     2092
     2093    /// \brief Skeleton class for clearable undirected biparite graphs.
     2094    ///
     2095    /// This class describes the interface of clearable undirected
     2096    /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
     2097    /// function for clearing the graph.  This concept requires \ref
     2098    /// AlterableBpGraphComponent.
     2099    template <typename BAS = BaseBpGraphComponent>
     2100    class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};
    15372101
    15382102  }
  • test/CMakeLists.txt

    r1000 r1018  
    1717  bellman_ford_test
    1818  bfs_test
     19  bpgraph_test
    1920  circulation_test
    2021  connectivity_test
Note: See TracChangeset for help on using the changeset viewer.