Changeset 1720:578d8b2b76c6 in lemon0.x for lemon/graph_utils.h
 Timestamp:
 10/14/05 12:49:51 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2247
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_utils.h
r1712 r1720 26 26 #include <lemon/utility.h> 27 27 #include <lemon/maps.h> 28 #include <lemon/traits.h> 28 29 #include <lemon/bits/alteration_notifier.h> 29 30 … … 401 402 } 402 403 403 404 404 /// \brief Class to copy a graph. 405 405 /// … … 515 515 return edgeRefMap; 516 516 } 517 518 void run() {} 517 519 518 520 private: … … 543 545 } 544 546 545 template <typename _Graph, typename _Item> 546 class ItemSetTraits {}; 547 548 template <typename _Graph> 549 class ItemSetTraits<_Graph, typename _Graph::Node> { 550 public: 551 552 typedef _Graph Graph; 553 554 typedef typename Graph::Node Item; 555 typedef typename Graph::NodeIt ItemIt; 556 557 template <typename _Value> 558 class Map : public Graph::template NodeMap<_Value> { 559 public: 560 typedef typename Graph::template NodeMap<_Value> Parent; 561 typedef typename Parent::Value Value; 562 563 Map(const Graph& _graph) : Parent(_graph) {} 564 Map(const Graph& _graph, const Value& _value) 565 : Parent(_graph, _value) {} 547 /// \brief Class to copy an undirected graph. 548 /// 549 /// Class to copy an undirected graph to an other graph (duplicate a graph). 550 /// The simplest way of using it is through the \c copyUndirGraph() function. 551 template <typename Target, typename Source> 552 class UndirGraphCopy { 553 public: 554 typedef typename Source::Node Node; 555 typedef typename Source::NodeIt NodeIt; 556 typedef typename Source::Edge Edge; 557 typedef typename Source::EdgeIt EdgeIt; 558 typedef typename Source::UndirEdge UndirEdge; 559 typedef typename Source::UndirEdgeIt UndirEdgeIt; 560 561 typedef typename Source:: 562 template NodeMap<typename Target::Node> NodeRefMap; 563 564 typedef typename Source:: 565 template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap; 566 567 private: 568 569 struct EdgeRefMap { 570 EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {} 571 typedef typename Source::Edge Key; 572 typedef typename Target::Edge Value; 573 574 Value operator[](const Key& key) { 575 return gc.target.direct(gc.undirEdgeRef[key], 576 gc.target.direction(key)); 577 } 578 579 UndirGraphCopy& gc; 566 580 }; 567 581 582 public: 583 584 /// \brief Constructor for the UndirGraphCopy. 585 /// 586 /// It copies the content of the \c _source graph into the 587 /// \c _target graph. It creates also two references, one beetween 588 /// the two nodeset and one beetween the two edgesets. 589 UndirGraphCopy(Target& _target, const Source& _source) 590 : source(_source), target(_target), 591 nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) { 592 for (NodeIt it(source); it != INVALID; ++it) { 593 nodeRefMap[it] = target.addNode(); 594 } 595 for (UndirEdgeIt it(source); it != INVALID; ++it) { 596 undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 597 nodeRefMap[source.target(it)]); 598 } 599 } 600 601 /// \brief Copies the node references into the given map. 602 /// 603 /// Copies the node references into the given map. 604 template <typename NodeRef> 605 const UndirGraphCopy& nodeRef(NodeRef& map) const { 606 for (NodeIt it(source); it != INVALID; ++it) { 607 map.set(it, nodeRefMap[it]); 608 } 609 return *this; 610 } 611 612 /// \brief Reverse and copies the node references into the given map. 613 /// 614 /// Reverse and copies the node references into the given map. 615 template <typename NodeRef> 616 const UndirGraphCopy& nodeCrossRef(NodeRef& map) const { 617 for (NodeIt it(source); it != INVALID; ++it) { 618 map.set(nodeRefMap[it], it); 619 } 620 return *this; 621 } 622 623 /// \brief Copies the edge references into the given map. 624 /// 625 /// Copies the edge references into the given map. 626 template <typename EdgeRef> 627 const UndirGraphCopy& edgeRef(EdgeRef& map) const { 628 for (EdgeIt it(source); it != INVALID; ++it) { 629 map.set(edgeRefMap[it], it); 630 } 631 return *this; 632 } 633 634 /// \brief Reverse and copies the undirected edge references into the 635 /// given map. 636 /// 637 /// Reverse and copies the undirected edge references into the given map. 638 template <typename EdgeRef> 639 const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const { 640 for (EdgeIt it(source); it != INVALID; ++it) { 641 map.set(it, edgeRefMap[it]); 642 } 643 return *this; 644 } 645 646 /// \brief Copies the undirected edge references into the given map. 647 /// 648 /// Copies the undirected edge references into the given map. 649 template <typename EdgeRef> 650 const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const { 651 for (UndirEdgeIt it(source); it != INVALID; ++it) { 652 map.set(it, undirEdgeRefMap[it]); 653 } 654 return *this; 655 } 656 657 /// \brief Reverse and copies the undirected edge references into the 658 /// given map. 659 /// 660 /// Reverse and copies the undirected edge references into the given map. 661 template <typename EdgeRef> 662 const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const { 663 for (UndirEdgeIt it(source); it != INVALID; ++it) { 664 map.set(undirEdgeRefMap[it], it); 665 } 666 return *this; 667 } 668 669 /// \brief Make copy of the given map. 670 /// 671 /// Makes copy of the given map for the newly created graph. 672 /// The new map's key type is the target graph's node type, 673 /// and the copied map's key type is the source graph's node 674 /// type. 675 template <typename TargetMap, typename SourceMap> 676 const UndirGraphCopy& nodeMap(TargetMap& tMap, 677 const SourceMap& sMap) const { 678 copyMap(tMap, sMap, NodeIt(source), nodeRefMap); 679 return *this; 680 } 681 682 /// \brief Make copy of the given map. 683 /// 684 /// Makes copy of the given map for the newly created graph. 685 /// The new map's key type is the target graph's edge type, 686 /// and the copied map's key type is the source graph's edge 687 /// type. 688 template <typename TargetMap, typename SourceMap> 689 const UndirGraphCopy& edgeMap(TargetMap& tMap, 690 const SourceMap& sMap) const { 691 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap); 692 return *this; 693 } 694 695 /// \brief Make copy of the given map. 696 /// 697 /// Makes copy of the given map for the newly created graph. 698 /// The new map's key type is the target graph's edge type, 699 /// and the copied map's key type is the source graph's edge 700 /// type. 701 template <typename TargetMap, typename SourceMap> 702 const UndirGraphCopy& undirEdgeMap(TargetMap& tMap, 703 const SourceMap& sMap) const { 704 copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap); 705 return *this; 706 } 707 708 /// \brief Gives back the stored node references. 709 /// 710 /// Gives back the stored node references. 711 const NodeRefMap& nodeRef() const { 712 return nodeRefMap; 713 } 714 715 /// \brief Gives back the stored edge references. 716 /// 717 /// Gives back the stored edge references. 718 const EdgeRefMap& edgeRef() const { 719 return edgeRefMap; 720 } 721 722 /// \brief Gives back the stored undir edge references. 723 /// 724 /// Gives back the stored undir edge references. 725 const UndirEdgeRefMap& undirEdgeRef() const { 726 return undirEdgeRefMap; 727 } 728 729 void run() {} 730 731 private: 732 733 const Source& source; 734 Target& target; 735 736 NodeRefMap nodeRefMap; 737 EdgeRefMap edgeRefMap; 738 UndirEdgeRefMap undirEdgeRefMap; 568 739 }; 569 740 570 template <typename _Graph> 571 class ItemSetTraits<_Graph, typename _Graph::Edge> { 572 public: 573 574 typedef _Graph Graph; 575 576 typedef typename Graph::Edge Item; 577 typedef typename Graph::EdgeIt ItemIt; 578 579 template <typename _Value> 580 class Map : public Graph::template EdgeMap<_Value> { 581 public: 582 typedef typename Graph::template EdgeMap<_Value> Parent; 583 typedef typename Parent::Value Value; 584 585 Map(const Graph& _graph) : Parent(_graph) {} 586 Map(const Graph& _graph, const Value& _value) 587 : Parent(_graph, _value) {} 588 }; 589 590 }; 591 592 template <typename _Graph> 593 class ItemSetTraits<_Graph, typename _Graph::UndirEdge> { 594 public: 595 596 typedef _Graph Graph; 597 598 typedef typename Graph::UndirEdge Item; 599 typedef typename Graph::UndirEdgeIt ItemIt; 600 601 template <typename _Value> 602 class Map : public Graph::template UndirEdgeMap<_Value> { 603 public: 604 typedef typename Graph::template UndirEdgeMap<_Value> Parent; 605 typedef typename Parent::Value Value; 606 607 Map(const Graph& _graph) : Parent(_graph) {} 608 Map(const Graph& _graph, const Value& _value) 609 : Parent(_graph, _value) {} 610 }; 611 612 }; 741 /// \brief Copy a graph to an other graph. 742 /// 743 /// Copy a graph to an other graph. 744 /// The usage of the function: 745 /// 746 /// \code 747 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr); 748 /// \endcode 749 /// 750 /// After the copy the \c nr map will contain the mapping from the 751 /// source graph's nodes to the target graph's nodes and the \c ecr will 752 /// contain the mapping from the target graph's edges to the source's 753 /// edges. 754 template <typename Target, typename Source> 755 UndirGraphCopy<Target, Source> 756 copyUndirGraph(Target& target, const Source& source) { 757 return UndirGraphCopy<Target, Source>(target, source); 758 } 759 613 760 614 761 /// @} … … 616 763 /// \addtogroup graph_maps 617 764 /// @{ 618 619 template <typename Map, typename Enable = void>620 struct ReferenceMapTraits {621 typedef typename Map::Value Value;622 typedef typename Map::Value& Reference;623 typedef const typename Map::Value& ConstReference;624 typedef typename Map::Value* Pointer;625 typedef const typename Map::Value* ConstPointer;626 };627 628 template <typename Map>629 struct ReferenceMapTraits<630 Map,631 typename enable_if<typename Map::FullTypeTag, void>::type632 > {633 typedef typename Map::Value Value;634 typedef typename Map::Reference Reference;635 typedef typename Map::ConstReference ConstReference;636 typedef typename Map::Pointer Pointer;637 typedef typename Map::ConstPointer ConstPointer;638 };639 765 640 766 /// Provides an immutable and unique id for each item in the graph. … … 755 881 /// 756 882 /// It gives back the value associated with the key. 757 constValue operator[](const Key& key) const {883 Value operator[](const Key& key) const { 758 884 return Map::operator[](key); 759 885 } … … 1193 1319 } 1194 1320 1195 /// \brief Container for store values for each ordered pair of nodes1196 ///1197 /// Container for store values for each ordered pair of nodes.1198 template <typename _Graph, typename _Value>1199 class NodeMatrixMap1200 : protected AlterationNotifier<typename _Graph::Node>::ObserverBase {1201 public:1202 typedef _Graph Graph;1203 typedef typename Graph::Node Node;1204 typedef Node Key;1205 typedef _Value Value;1206 1207 /// \brief Creates a node matrix for the given graph1208 ///1209 /// Creates a node matrix for the given graph.1210 NodeMatrixMap(const Graph& _graph)1211 : graph(_graph), values(size(_graph.maxId(Node()) + 1)) {}1212 1213 /// \brief Creates a node matrix for the given graph1214 ///1215 /// Creates a node matrix for the given graph and assigns each1216 /// initial value to the given parameter.1217 NodeMatrixMap(const Graph& _graph, const Value& _val)1218 : graph(_graph), values(size(_graph.maxId(Node()) + 1), _val) {}1219 1220 /// \brief Gives back the value assigned to the \c left  \c right1221 /// ordered pair.1222 ///1223 /// Gives back the value assigned to the \c left  \c right ordered pair.1224 const Value& operator()(const Node& left, const Node& right) const {1225 return values[index(graph.id(left), graph.id(right))];1226 }1227 1228 /// \brief Gives back the value assigned to the \c left  \c right1229 /// ordered pair.1230 ///1231 /// Gives back the value assigned to the \c left  \c right ordered pair.1232 Value& operator()(const Node& left, const Node& right) {1233 return values[index(graph.id(left), graph.id(right))];1234 }1235 1236 /// \brief Setter function for the matrix map.1237 ///1238 /// Setter function for the matrix map.1239 void set(const Node& left, const Node& right, const Value& val) {1240 values[index(graph.id(left), graph.id(right))] = val;1241 }1242 1243 /// \brief Map for the coloumn view of the matrix1244 ///1245 /// Map for the coloumn view of the matrix.1246 class ColMap : public MapBase<Node, Value> {1247 friend class NodeMatrixMap;1248 private:1249 ColMap(NodeMatrixMap& _matrix, Node _col)1250 : matrix(_matrix), col(_col) {}1251 1252 public:1253 /// \brief Subscription operator1254 ///1255 /// Subscription operator.1256 Value& operator[](Node row) {1257 return matrix(col, row);1258 }1259 1260 /// \brief Setter function1261 ///1262 /// Setter function.1263 void set(Node row, const Value& val) {1264 matrix.set(col, row, val);1265 }1266 1267 /// \brief Subscription operator1268 ///1269 /// Subscription operator.1270 const Value& operator[](Node row) const {1271 return matrix(col, row);1272 }1273 1274 private:1275 NodeMatrixMap& matrix;1276 Node col;1277 };1278 1279 /// \brief Map for the const coloumn view of the matrix1280 ///1281 /// Map for the const coloumn view of the matrix.1282 class ConstColMap : public MapBase<Node, Value> {1283 friend class NodeMatrixMap;1284 private:1285 ConstColMap(const NodeMatrixMap& _matrix, Node _col)1286 : matrix(_matrix), col(_col) {}1287 1288 public:1289 /// \brief Subscription operator1290 ///1291 /// Subscription operator.1292 const Value& operator[](Node row) const {1293 return matrix(col, row);1294 }1295 1296 private:1297 const NodeMatrixMap& matrix;1298 Node col;1299 };1300 1301 /// \brief Map for the row view of the matrix1302 ///1303 /// Map for the row view of the matrix.1304 class RowMap : public MapBase<Node, Value> {1305 public:1306 friend class NodeMatrixMap;1307 private:1308 RowMap(NodeMatrixMap& _matrix, Node _row)1309 : matrix(_matrix), row(_row) {}1310 1311 public:1312 /// \brief Subscription operator1313 ///1314 /// Subscription operator.1315 Value& operator[](Node col) {1316 return matrix(col, row);1317 }1318 1319 /// \brief Setter function1320 ///1321 /// Setter function.1322 void set(Node col, const Value& val) {1323 matrix.set(col, row, val);1324 }1325 1326 /// \brief Subscription operator1327 ///1328 /// Subscription operator.1329 const Value& operator[](Node col) const {1330 return matrix(col, row);1331 }1332 1333 private:1334 NodeMatrixMap& matrix;1335 Node row;1336 };1337 1338 /// \brief Map for the const row view of the matrix1339 ///1340 /// Map for the row const view of the matrix.1341 class ConstRowMap : public MapBase<Node, Value> {1342 public:1343 friend class NodeMatrixMap;1344 private:1345 ConstRowMap(const NodeMatrixMap& _matrix, Node _row)1346 : matrix(_matrix), row(_row) {}1347 1348 public:1349 /// \brief Subscription operator1350 ///1351 /// Subscription operator.1352 const Value& operator[](Node col) const {1353 return matrix(col, row);1354 }1355 1356 private:1357 const NodeMatrixMap& matrix;1358 Node row;1359 };1360 1361 /// \brief Gives back the column view for the given node1362 ///1363 /// Gives back the column view for the given node1364 ConstColMap operator[](Node col) const { return ConstColMap(*this, col); }1365 /// \brief Gives back the column view for the given node1366 ///1367 /// Gives back the column view for the given node1368 ColMap operator[](Node col) { return ColMap(*this, col); }1369 1370 /// \brief Gives back the column view for the given node1371 ///1372 /// Gives back the column view for the given node1373 ConstColMap colMap(Node col) const { return ConstColMap(*this, col); }1374 /// \brief Gives back the column view for the given node1375 ///1376 /// Gives back the column view for the given node1377 ColMap colMap(Node col) { return ColMap(*this, col); }1378 1379 /// \brief Gives back the row view for the given node1380 ///1381 /// Gives back the row view for the given node1382 ConstRowMap rowMap(Node row) const { return ConstRowMap(*this, row); }1383 /// \brief Gives back the row view for the given node1384 ///1385 /// Gives back the row view for the given node1386 RowMap rowMap(Node row) { return RowMap(*this, row); }1387 1388 protected:1389 1390 static int index(int i, int j) {1391 if (i < j) {1392 return j * j + i;1393 } else {1394 return i * i + i + j;1395 }1396 }1397 1398 static int size(int s) {1399 return s * s;1400 }1401 1402 void add(const Node& node) {1403 if (size(graph.id(node) + 1) >= (int)values.size()) {1404 values.resize(size(graph.id(node) + 1));1405 }1406 }1407 1408 void erase(const Node&) {}1409 1410 void build() {1411 values.resize(size(graph.maxId(Node()) + 1));1412 }1413 1414 void clear() {1415 values.clear();1416 }1417 1418 private:1419 const Graph& graph;1420 std::vector<Value> values;1421 };1422 1423 1321 /// \brief Map of the node indegrees. 1424 1322 /// … … 1427 1325 /// in constant time. On the other hand, the values are updated automatically 1428 1326 /// whenever the graph changes. 1429 ///1430 /// \warning Besides addNode() and addEdge(), a graph structure may provide1431 /// alternative ways to mogify the graph. The correct behavior of InDegMap1432 /// is not guarantied if these additional featureas are used. For example1433 /// the funstions \ref ListGraph::changeSource() "changeSource()",1434 /// \ref ListGraph::changeTarget() "changeTarget()" and1435 /// \ref ListGraph::reverseEdge() "reverseEdge()"1436 /// of \ref ListGraph will \e not update the degree values correctly.1437 1327 /// 1438 1328 /// \sa OutDegMap … … 1502 1392 } 1503 1393 1394 virtual void signalChange(const Edge& edge) { 1395 erase(edge); 1396 } 1397 1398 virtual void commitChange(const Edge& edge) { 1399 add(edge); 1400 } 1504 1401 1505 1402 virtual void build() { … … 1526 1423 /// in constant time. On the other hand, the values are updated automatically 1527 1424 /// whenever the graph changes. 1528 ///1529 /// \warning Besides addNode() and addEdge(), a graph structure may provide1530 /// alternative ways to mogify the graph. The correct behavior of OutDegMap1531 /// is not guarantied if these additional featureas are used. For example1532 /// the funstions \ref ListGraph::changeSource() "changeSource()",1533 /// \ref ListGraph::changeTarget() "changeTarget()" and1534 /// \ref ListGraph::reverseEdge() "reverseEdge()"1535 /// of \ref ListGraph will \e not update the degree values correctly.1536 1425 /// 1537 1426 /// \sa InDegMap … … 1601 1490 } 1602 1491 1492 virtual void signalChange(const Edge& edge) { 1493 erase(edge); 1494 } 1495 1496 virtual void commitChange(const Edge& edge) { 1497 add(edge); 1498 } 1499 1603 1500 1604 1501 virtual void build() { … … 1619 1516 }; 1620 1517 1621 // Indicators for the tags1622 1623 template <typename Graph, typename Enable = void>1624 struct NodeNumTagIndicator {1625 static const bool value = false;1626 };1627 1628 template <typename Graph>1629 struct NodeNumTagIndicator<1630 Graph,1631 typename enable_if<typename Graph::NodeNumTag, void>::type1632 > {1633 static const bool value = true;1634 };1635 1636 template <typename Graph, typename Enable = void>1637 struct EdgeNumTagIndicator {1638 static const bool value = false;1639 };1640 1641 template <typename Graph>1642 struct EdgeNumTagIndicator<1643 Graph,1644 typename enable_if<typename Graph::EdgeNumTag, void>::type1645 > {1646 static const bool value = true;1647 };1648 1649 template <typename Graph, typename Enable = void>1650 struct FindEdgeTagIndicator {1651 static const bool value = false;1652 };1653 1654 template <typename Graph>1655 struct FindEdgeTagIndicator<1656 Graph,1657 typename enable_if<typename Graph::FindEdgeTag, void>::type1658 > {1659 static const bool value = true;1660 };1661 1662 1518 1663 1519 /// @}
Note: See TracChangeset
for help on using the changeset viewer.