Changeset 1186:2e959a5a0c2d in lemon
 Timestamp:
 11/14/10 16:35:31 (11 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 added
 3 edited
Legend:
 Unmodified
 Added
 Removed

lemon/concepts/graph.h
r956 r1186 73 73 class Graph { 74 74 private: 75 /// Graphs are \e not copy constructible. Use DigraphCopy instead.75 /// Graphs are \e not copy constructible. Use GraphCopy instead. 76 76 Graph(const Graph&) {} 77 77 /// \brief Assignment of a graph to another one is \e not allowed. 78 /// Use DigraphCopy instead.78 /// Use GraphCopy instead. 79 79 void operator=(const Graph&) {} 80 80 
lemon/concepts/graph_components.h
r1175 r1186 300 300 }; 301 301 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 welldefined 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 welldefined 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 302 447 /// \brief Skeleton class for \e idable directed graphs. 303 448 /// … … 429 574 const _Graph& graph; 430 575 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; 431 652 }; 432 653 }; … … 905 1126 }; 906 1127 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 907 1214 /// \brief Skeleton class for alterable directed graphs. 908 1215 /// … … 930 1237 ArcNotifier; 931 1238 1239 mutable NodeNotifier node_notifier; 1240 mutable ArcNotifier arc_notifier; 1241 932 1242 /// \brief Return the node alteration notifier. 933 1243 /// 934 1244 /// This function gives back the node alteration notifier. 935 1245 NodeNotifier& notifier(Node) const { 936 return NodeNotifier();1246 return node_notifier; 937 1247 } 938 1248 … … 941 1251 /// This function gives back the arc alteration notifier. 942 1252 ArcNotifier& notifier(Arc) const { 943 return ArcNotifier();1253 return arc_notifier; 944 1254 } 945 1255 … … 977 1287 978 1288 typedef BAS Base; 1289 typedef AlterableDigraphComponent<Base> Parent; 979 1290 typedef typename Base::Edge Edge; 980 1291 … … 984 1295 EdgeNotifier; 985 1296 1297 mutable EdgeNotifier edge_notifier; 1298 1299 using Parent::notifier; 1300 986 1301 /// \brief Return the edge alteration notifier. 987 1302 /// 988 1303 /// This function gives back the edge alteration notifier. 989 1304 EdgeNotifier& notifier(Edge) const { 990 return EdgeNotifier();1305 return edge_notifier; 991 1306 } 992 1307 … … 1002 1317 const _Graph& graph; 1003 1318 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 observernotifier 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; 1004 1381 }; 1005 1382 }; … … 1308 1685 }; 1309 1686 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 1310 1824 /// \brief Skeleton class for extendable directed graphs. 1311 1825 /// … … 1398 1912 }; 1399 1913 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 1400 1966 /// \brief Skeleton class for erasable directed graphs. 1401 1967 /// … … 1478 2044 }; 1479 2045 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 1480 2055 /// \brief Skeleton class for clearable directed graphs. 1481 2056 /// … … 1514 2089 /// This concept requires \ref AlterableGraphComponent. 1515 2090 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> {}; 1537 2101 1538 2102 } 
test/CMakeLists.txt
r1162 r1186 17 17 bellman_ford_test 18 18 bfs_test 19 bpgraph_test 19 20 circulation_test 20 21 connectivity_test
Note: See TracChangeset
for help on using the changeset viewer.