Changeset 1989:d276e88aa48a in lemon0.x for lemon/graph_adaptor.h
 Timestamp:
 03/01/06 11:04:47 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2591
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_adaptor.h
r1980 r1989 1351 1351 }; 1352 1352 1353 template <typename _Graph>1354 class SplitGraphAdaptorBase1355 : public GraphAdaptorBase<_Graph> {1356 public:1357 typedef GraphAdaptorBase<_Graph> Parent;1358 1359 class Node;1360 class Edge;1361 template <typename T> class NodeMap;1362 template <typename T> class EdgeMap;1353 // template <typename _Graph> 1354 // class SplitGraphAdaptorBase 1355 // : public GraphAdaptorBase<_Graph> { 1356 // public: 1357 // typedef GraphAdaptorBase<_Graph> Parent; 1358 1359 // class Node; 1360 // class Edge; 1361 // template <typename T> class NodeMap; 1362 // template <typename T> class EdgeMap; 1363 1363 1364 1364 1365 class Node : public Parent::Node { 1366 friend class SplitGraphAdaptorBase; 1367 template <typename T> friend class NodeMap; 1368 typedef typename Parent::Node NodeParent; 1369 private: 1370 1371 bool entry; 1372 Node(typename Parent::Node _node, bool _entry) 1373 : Parent::Node(_node), entry(_entry) {} 1374 1375 public: 1376 Node() {} 1377 Node(Invalid) : NodeParent(INVALID), entry(true) {} 1378 1379 bool operator==(const Node& node) const { 1380 return NodeParent::operator==(node) && entry == node.entry; 1381 } 1382 1383 bool operator!=(const Node& node) const { 1384 return !(*this == node); 1385 } 1386 1387 bool operator<(const Node& node) const { 1388 return NodeParent::operator<(node)  1389 (NodeParent::operator==(node) && entry < node.entry); 1390 } 1391 }; 1392 1393 /// \todo May we want VARIANT/union type 1394 class Edge : public Parent::Edge { 1395 friend class SplitGraphAdaptorBase; 1396 template <typename T> friend class EdgeMap; 1397 private: 1398 typedef typename Parent::Edge EdgeParent; 1399 typedef typename Parent::Node NodeParent; 1400 NodeParent bind; 1401 1402 Edge(const EdgeParent& edge, const NodeParent& node) 1403 : EdgeParent(edge), bind(node) {} 1404 public: 1405 Edge() {} 1406 Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {} 1407 1408 bool operator==(const Edge& edge) const { 1409 return EdgeParent::operator==(edge) && bind == edge.bind; 1410 } 1411 1412 bool operator!=(const Edge& edge) const { 1413 return !(*this == edge); 1414 } 1415 1416 bool operator<(const Edge& edge) const { 1417 return EdgeParent::operator<(edge)  1418 (EdgeParent::operator==(edge) && bind < edge.bind); 1419 } 1420 }; 1421 1422 void first(Node& node) const { 1423 Parent::first(node); 1424 node.entry = true; 1425 } 1426 1427 void next(Node& node) const { 1428 if (node.entry) { 1429 node.entry = false; 1430 } else { 1431 node.entry = true; 1432 Parent::next(node); 1433 } 1434 } 1435 1436 void first(Edge& edge) const { 1437 Parent::first(edge); 1438 if ((typename Parent::Edge&)edge == INVALID) { 1439 Parent::first(edge.bind); 1440 } else { 1441 edge.bind = INVALID; 1442 } 1443 } 1444 1445 void next(Edge& edge) const { 1446 if ((typename Parent::Edge&)edge != INVALID) { 1447 Parent::next(edge); 1448 if ((typename Parent::Edge&)edge == INVALID) { 1449 Parent::first(edge.bind); 1450 } 1451 } else { 1452 Parent::next(edge.bind); 1453 } 1454 } 1455 1456 void firstIn(Edge& edge, const Node& node) const { 1457 if (node.entry) { 1458 Parent::firstIn(edge, node); 1459 edge.bind = INVALID; 1460 } else { 1461 (typename Parent::Edge&)edge = INVALID; 1462 edge.bind = node; 1463 } 1464 } 1465 1466 void nextIn(Edge& edge) const { 1467 if ((typename Parent::Edge&)edge != INVALID) { 1468 Parent::nextIn(edge); 1469 } else { 1470 edge.bind = INVALID; 1471 } 1472 } 1473 1474 void firstOut(Edge& edge, const Node& node) const { 1475 if (!node.entry) { 1476 Parent::firstOut(edge, node); 1477 edge.bind = INVALID; 1478 } else { 1479 (typename Parent::Edge&)edge = INVALID; 1480 edge.bind = node; 1481 } 1482 } 1483 1484 void nextOut(Edge& edge) const { 1485 if ((typename Parent::Edge&)edge != INVALID) { 1486 Parent::nextOut(edge); 1487 } else { 1488 edge.bind = INVALID; 1489 } 1490 } 1491 1492 Node source(const Edge& edge) const { 1493 if ((typename Parent::Edge&)edge != INVALID) { 1494 return Node(Parent::source(edge), false); 1495 } else { 1496 return Node(edge.bind, true); 1497 } 1498 } 1499 1500 Node target(const Edge& edge) const { 1501 if ((typename Parent::Edge&)edge != INVALID) { 1502 return Node(Parent::target(edge), true); 1503 } else { 1504 return Node(edge.bind, false); 1505 } 1506 } 1507 1508 static bool entryNode(const Node& node) { 1509 return node.entry; 1510 } 1511 1512 static bool exitNode(const Node& node) { 1513 return !node.entry; 1514 } 1515 1516 static Node getEntry(const typename Parent::Node& node) { 1517 return Node(node, true); 1518 } 1519 1520 static Node getExit(const typename Parent::Node& node) { 1521 return Node(node, false); 1522 } 1523 1524 static bool originalEdge(const Edge& edge) { 1525 return (typename Parent::Edge&)edge != INVALID; 1526 } 1527 1528 static bool bindingEdge(const Edge& edge) { 1529 return edge.bind != INVALID; 1530 } 1531 1532 static Node getBindedNode(const Edge& edge) { 1533 return edge.bind; 1534 } 1535 1536 int nodeNum() const { 1537 return Parent::nodeNum() * 2; 1538 } 1539 1540 typedef CompileTimeAnd<typename Parent::NodeNumTag, 1541 typename Parent::EdgeNumTag> EdgeNumTag; 1365 // class Node : public Parent::Node { 1366 // friend class SplitGraphAdaptorBase; 1367 // template <typename T> friend class NodeMap; 1368 // typedef typename Parent::Node NodeParent; 1369 // private: 1370 1371 // bool entry; 1372 // Node(typename Parent::Node _node, bool _entry) 1373 // : Parent::Node(_node), entry(_entry) {} 1374 1375 // public: 1376 // Node() {} 1377 // Node(Invalid) : NodeParent(INVALID), entry(true) {} 1378 1379 // bool operator==(const Node& node) const { 1380 // return NodeParent::operator==(node) && entry == node.entry; 1381 // } 1382 1383 // bool operator!=(const Node& node) const { 1384 // return !(*this == node); 1385 // } 1386 1387 // bool operator<(const Node& node) const { 1388 // return NodeParent::operator<(node)  1389 // (NodeParent::operator==(node) && entry < node.entry); 1390 // } 1391 // }; 1392 1393 // /// \todo May we want VARIANT/union type 1394 // class Edge : public Parent::Edge { 1395 // friend class SplitGraphAdaptorBase; 1396 // template <typename T> friend class EdgeMap; 1397 // private: 1398 // typedef typename Parent::Edge EdgeParent; 1399 // typedef typename Parent::Node NodeParent; 1400 // NodeParent bind; 1401 1402 // Edge(const EdgeParent& edge, const NodeParent& node) 1403 // : EdgeParent(edge), bind(node) {} 1404 // public: 1405 // Edge() {} 1406 // Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {} 1407 1408 // bool operator==(const Edge& edge) const { 1409 // return EdgeParent::operator==(edge) && bind == edge.bind; 1410 // } 1411 1412 // bool operator!=(const Edge& edge) const { 1413 // return !(*this == edge); 1414 // } 1415 1416 // bool operator<(const Edge& edge) const { 1417 // return EdgeParent::operator<(edge)  1418 // (EdgeParent::operator==(edge) && bind < edge.bind); 1419 // } 1420 // }; 1421 1422 // void first(Node& node) const { 1423 // Parent::first(node); 1424 // node.entry = true; 1425 // } 1426 1427 // void next(Node& node) const { 1428 // if (node.entry) { 1429 // node.entry = false; 1430 // } else { 1431 // node.entry = true; 1432 // Parent::next(node); 1433 // } 1434 // } 1435 1436 // void first(Edge& edge) const { 1437 // Parent::first(edge); 1438 // if ((typename Parent::Edge&)edge == INVALID) { 1439 // Parent::first(edge.bind); 1440 // } else { 1441 // edge.bind = INVALID; 1442 // } 1443 // } 1444 1445 // void next(Edge& edge) const { 1446 // if ((typename Parent::Edge&)edge != INVALID) { 1447 // Parent::next(edge); 1448 // if ((typename Parent::Edge&)edge == INVALID) { 1449 // Parent::first(edge.bind); 1450 // } 1451 // } else { 1452 // Parent::next(edge.bind); 1453 // } 1454 // } 1455 1456 // void firstIn(Edge& edge, const Node& node) const { 1457 // if (node.entry) { 1458 // Parent::firstIn(edge, node); 1459 // edge.bind = INVALID; 1460 // } else { 1461 // (typename Parent::Edge&)edge = INVALID; 1462 // edge.bind = node; 1463 // } 1464 // } 1465 1466 // void nextIn(Edge& edge) const { 1467 // if ((typename Parent::Edge&)edge != INVALID) { 1468 // Parent::nextIn(edge); 1469 // } else { 1470 // edge.bind = INVALID; 1471 // } 1472 // } 1473 1474 // void firstOut(Edge& edge, const Node& node) const { 1475 // if (!node.entry) { 1476 // Parent::firstOut(edge, node); 1477 // edge.bind = INVALID; 1478 // } else { 1479 // (typename Parent::Edge&)edge = INVALID; 1480 // edge.bind = node; 1481 // } 1482 // } 1483 1484 // void nextOut(Edge& edge) const { 1485 // if ((typename Parent::Edge&)edge != INVALID) { 1486 // Parent::nextOut(edge); 1487 // } else { 1488 // edge.bind = INVALID; 1489 // } 1490 // } 1491 1492 // Node source(const Edge& edge) const { 1493 // if ((typename Parent::Edge&)edge != INVALID) { 1494 // return Node(Parent::source(edge), false); 1495 // } else { 1496 // return Node(edge.bind, true); 1497 // } 1498 // } 1499 1500 // Node target(const Edge& edge) const { 1501 // if ((typename Parent::Edge&)edge != INVALID) { 1502 // return Node(Parent::target(edge), true); 1503 // } else { 1504 // return Node(edge.bind, false); 1505 // } 1506 // } 1507 1508 // static bool entryNode(const Node& node) { 1509 // return node.entry; 1510 // } 1511 1512 // static bool exitNode(const Node& node) { 1513 // return !node.entry; 1514 // } 1515 1516 // static Node getEntry(const typename Parent::Node& node) { 1517 // return Node(node, true); 1518 // } 1519 1520 // static Node getExit(const typename Parent::Node& node) { 1521 // return Node(node, false); 1522 // } 1523 1524 // static bool originalEdge(const Edge& edge) { 1525 // return (typename Parent::Edge&)edge != INVALID; 1526 // } 1527 1528 // static bool bindingEdge(const Edge& edge) { 1529 // return edge.bind != INVALID; 1530 // } 1531 1532 // static Node getBindedNode(const Edge& edge) { 1533 // return edge.bind; 1534 // } 1535 1536 // int nodeNum() const { 1537 // return Parent::nodeNum() * 2; 1538 // } 1539 1540 // typedef True EdgeNumTag; 1542 1541 1543 int edgeNum() const {1544 return Parent::edgeNum() + Parent::nodeNum();1545 }1546 1547 Edge findEdge(const Node& source, const Node& target,1548 const Edge& prev = INVALID) const {1549 if (exitNode(source) && entryNode(target)) {1550 return Parent::findEdge(source, target, prev);1551 } else {1552 if (prev == INVALID && entryNode(source) && exitNode(target) &&1553 (typename Parent::Node&)source == (typename Parent::Node&)target) {1554 return Edge(INVALID, source);1555 } else {1556 return INVALID;1557 }1558 }1559 }1542 // int edgeNum() const { 1543 // return countEdges() + Parent::nodeNum(); 1544 // } 1545 1546 // Edge findEdge(const Node& source, const Node& target, 1547 // const Edge& prev = INVALID) const { 1548 // if (exitNode(source) && entryNode(target)) { 1549 // return Parent::findEdge(source, target, prev); 1550 // } else { 1551 // if (prev == INVALID && entryNode(source) && exitNode(target) && 1552 // (typename Parent::Node&)source == (typename Parent::Node&)target) { 1553 // return Edge(INVALID, source); 1554 // } else { 1555 // return INVALID; 1556 // } 1557 // } 1558 // } 1560 1559 1561 template <typename T>1562 class NodeMap : public MapBase<Node, T> {1563 typedef typename Parent::template NodeMap<T> NodeImpl;1564 public:1565 NodeMap(const SplitGraphAdaptorBase& _graph)1566 : entry(_graph), exit(_graph) {}1567 NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)1568 : entry(_graph, t), exit(_graph, t) {}1569 1570 void set(const Node& key, const T& val) {1571 if (key.entry) { entry.set(key, val); }1572 else {exit.set(key, val); }1573 }1574 1575 typename MapTraits<NodeImpl>::ReturnValue1576 operator[](const Node& key) {1577 if (key.entry) { return entry[key]; }1578 else { return exit[key]; }1579 }1580 1581 typename MapTraits<NodeImpl>::ConstReturnValue1582 operator[](const Node& key) const {1583 if (key.entry) { return entry[key]; }1584 else { return exit[key]; }1585 }1586 1587 private:1588 NodeImpl entry, exit;1589 };1590 1591 template <typename T>1592 class EdgeMap : public MapBase<Edge, T> {1593 typedef typename Parent::template NodeMap<T> NodeImpl;1594 typedef typename Parent::template EdgeMap<T> EdgeImpl;1595 public:1596 EdgeMap(const SplitGraphAdaptorBase& _graph)1597 : bind(_graph), orig(_graph) {}1598 EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)1599 : bind(_graph, t), orig(_graph, t) {}1600 1601 void set(const Edge& key, const T& val) {1602 if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }1603 else {bind.set(key.bind, val); }1604 }1605 1606 typename MapTraits<EdgeImpl>::ReturnValue1607 operator[](const Edge& key) {1608 if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }1609 else {return bind[key.bind]; }1610 }1611 1612 typename MapTraits<EdgeImpl>::ConstReturnValue1613 operator[](const Edge& key) const {1614 if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }1615 else {return bind[key.bind]; }1616 }1617 1618 private:1619 typename Parent::template NodeMap<T> bind;1620 typename Parent::template EdgeMap<T> orig;1621 };1622 1623 template <typename EntryMap, typename ExitMap>1624 class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {1625 public:1626 typedef MapBase<Node, typename EntryMap::Value> Parent;1627 1628 typedef typename Parent::Key Key;1629 typedef typename Parent::Value Value;1630 1631 CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)1632 : entryMap(_entryMap), exitMap(_exitMap) {}1633 1634 Value& operator[](const Key& key) {1635 if (key.entry) {1636 return entryMap[key];1637 } else {1638 return exitMap[key];1639 }1640 }1641 1642 Value operator[](const Key& key) const {1643 if (key.entry) {1644 return entryMap[key];1645 } else {1646 return exitMap[key];1647 }1648 }1649 1650 void set(const Key& key, const Value& value) {1651 if (key.entry) {1652 entryMap.set(key, value);1653 } else {1654 exitMap.set(key, value);1655 }1656 }1657 1658 private:1659 1660 EntryMap& entryMap;1661 ExitMap& exitMap;1662 1663 };1664 1665 template <typename EdgeMap, typename NodeMap>1666 class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {1667 public:1668 typedef MapBase<Edge, typename EdgeMap::Value> Parent;1669 1670 typedef typename Parent::Key Key;1671 typedef typename Parent::Value Value;1672 1673 CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)1674 : edgeMap(_edgeMap), nodeMap(_nodeMap) {}1675 1676 void set(const Edge& edge, const Value& val) {1677 if (SplitGraphAdaptorBase::originalEdge(edge)) {1678 edgeMap.set(edge, val);1679 } else {1680 nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);1681 }1682 }1683 1684 Value operator[](const Key& edge) const {1685 if (SplitGraphAdaptorBase::originalEdge(edge)) {1686 return edgeMap[edge];1687 } else {1688 return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];1689 }1690 }1691 1692 Value& operator[](const Key& edge) {1693 if (SplitGraphAdaptorBase::originalEdge(edge)) {1694 return edgeMap[edge];1695 } else {1696 return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];1697 }1698 }1699 1700 private:1701 EdgeMap& edgeMap;1702 NodeMap& nodeMap;1703 };1704 1705 };1706 1707 template <typename _Graph>1708 class SplitGraphAdaptor1709 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {1710 public:1711 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;1712 1713 SplitGraphAdaptor(_Graph& graph) {1714 Parent::setGraph(graph);1715 }1716 1717 1718 };1560 // template <typename T> 1561 // class NodeMap : public MapBase<Node, T> { 1562 // typedef typename Parent::template NodeMap<T> NodeImpl; 1563 // public: 1564 // NodeMap(const SplitGraphAdaptorBase& _graph) 1565 // : entry(_graph), exit(_graph) {} 1566 // NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 1567 // : entry(_graph, t), exit(_graph, t) {} 1568 1569 // void set(const Node& key, const T& val) { 1570 // if (key.entry) { entry.set(key, val); } 1571 // else {exit.set(key, val); } 1572 // } 1573 1574 // typename MapTraits<NodeImpl>::ReturnValue 1575 // operator[](const Node& key) { 1576 // if (key.entry) { return entry[key]; } 1577 // else { return exit[key]; } 1578 // } 1579 1580 // typename MapTraits<NodeImpl>::ConstReturnValue 1581 // operator[](const Node& key) const { 1582 // if (key.entry) { return entry[key]; } 1583 // else { return exit[key]; } 1584 // } 1585 1586 // private: 1587 // NodeImpl entry, exit; 1588 // }; 1589 1590 // template <typename T> 1591 // class EdgeMap : public MapBase<Edge, T> { 1592 // typedef typename Parent::template NodeMap<T> NodeImpl; 1593 // typedef typename Parent::template EdgeMap<T> EdgeImpl; 1594 // public: 1595 // EdgeMap(const SplitGraphAdaptorBase& _graph) 1596 // : bind(_graph), orig(_graph) {} 1597 // EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 1598 // : bind(_graph, t), orig(_graph, t) {} 1599 1600 // void set(const Edge& key, const T& val) { 1601 // if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); } 1602 // else {bind.set(key.bind, val); } 1603 // } 1604 1605 // typename MapTraits<EdgeImpl>::ReturnValue 1606 // operator[](const Edge& key) { 1607 // if ((typename Parent::Edge&)key != INVALID) { return orig[key]; } 1608 // else {return bind[key.bind]; } 1609 // } 1610 1611 // typename MapTraits<EdgeImpl>::ConstReturnValue 1612 // operator[](const Edge& key) const { 1613 // if ((typename Parent::Edge&)key != INVALID) { return orig[key]; } 1614 // else {return bind[key.bind]; } 1615 // } 1616 1617 // private: 1618 // typename Parent::template NodeMap<T> bind; 1619 // typename Parent::template EdgeMap<T> orig; 1620 // }; 1621 1622 // template <typename EntryMap, typename ExitMap> 1623 // class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> { 1624 // public: 1625 // typedef MapBase<Node, typename EntryMap::Value> Parent; 1626 1627 // typedef typename Parent::Key Key; 1628 // typedef typename Parent::Value Value; 1629 1630 // CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap) 1631 // : entryMap(_entryMap), exitMap(_exitMap) {} 1632 1633 // Value& operator[](const Key& key) { 1634 // if (key.entry) { 1635 // return entryMap[key]; 1636 // } else { 1637 // return exitMap[key]; 1638 // } 1639 // } 1640 1641 // Value operator[](const Key& key) const { 1642 // if (key.entry) { 1643 // return entryMap[key]; 1644 // } else { 1645 // return exitMap[key]; 1646 // } 1647 // } 1648 1649 // void set(const Key& key, const Value& value) { 1650 // if (key.entry) { 1651 // entryMap.set(key, value); 1652 // } else { 1653 // exitMap.set(key, value); 1654 // } 1655 // } 1656 1657 // private: 1658 1659 // EntryMap& entryMap; 1660 // ExitMap& exitMap; 1661 1662 // }; 1663 1664 // template <typename EdgeMap, typename NodeMap> 1665 // class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> { 1666 // public: 1667 // typedef MapBase<Edge, typename EdgeMap::Value> Parent; 1668 1669 // typedef typename Parent::Key Key; 1670 // typedef typename Parent::Value Value; 1671 1672 // CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap) 1673 // : edgeMap(_edgeMap), nodeMap(_nodeMap) {} 1674 1675 // void set(const Edge& edge, const Value& val) { 1676 // if (SplitGraphAdaptorBase::originalEdge(edge)) { 1677 // edgeMap.set(edge, val); 1678 // } else { 1679 // nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val); 1680 // } 1681 // } 1682 1683 // Value operator[](const Key& edge) const { 1684 // if (SplitGraphAdaptorBase::originalEdge(edge)) { 1685 // return edgeMap[edge]; 1686 // } else { 1687 // return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)]; 1688 // } 1689 // } 1690 1691 // Value& operator[](const Key& edge) { 1692 // if (SplitGraphAdaptorBase::originalEdge(edge)) { 1693 // return edgeMap[edge]; 1694 // } else { 1695 // return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)]; 1696 // } 1697 // } 1698 1699 // private: 1700 // EdgeMap& edgeMap; 1701 // NodeMap& nodeMap; 1702 // }; 1703 1704 // }; 1705 1706 // template <typename _Graph> 1707 // class SplitGraphAdaptor 1708 // : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > { 1709 // public: 1710 // typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent; 1711 1712 // SplitGraphAdaptor(_Graph& graph) { 1713 // Parent::setGraph(graph); 1714 // } 1715 1716 1717 // }; 1719 1718 1720 1719 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.