Changeset 1697:4c593a4096da in lemon0.x
 Timestamp:
 10/03/05 12:17:53 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2223
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_adaptor.h
r1685 r1697 66 66 public: 67 67 typedef _Graph Graph; 68 /// \todo Is it needed?69 typedef Graph BaseGraph;70 68 typedef Graph ParentGraph; 71 69 … … 94 92 Node target(const Edge& e) const { return graph>target(e); } 95 93 94 typedef NodeNumTagIndicator<Graph> NodeNumTag; 96 95 int nodeNum() const { return graph>nodeNum(); } 96 97 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; 97 98 int edgeNum() const { return graph>edgeNum(); } 99 100 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 101 Edge findEdge(const Node& source, const Node& target, 102 const Edge& prev = INVALID) { 103 return graph>findEdge(source, target, prev); 104 } 98 105 99 Node addNode() const { return Node(graph>addNode()); } 106 Node addNode() const { 107 return Node(graph>addNode()); 108 } 109 100 110 Edge addEdge(const Node& source, const Node& target) const { 101 return Edge(graph>addEdge(source, target)); } 111 return Edge(graph>addEdge(source, target)); 112 } 102 113 103 114 void erase(const Node& i) const { graph>erase(i); } … … 157 168 typedef typename Parent::Edge Edge; 158 169 159 // using Parent::first;160 170 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); } 161 171 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); } 162 172 163 // using Parent::next;164 173 void nextIn(Edge& i) const { Parent::nextOut(i); } 165 174 void nextOut(Edge& i) const { Parent::nextIn(i); } … … 305 314 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 306 315 307 /// \warning This is a linear time operation and works only if s 308 /// \c Graph::NodeIt is defined. 309 /// \todo assign tags. 310 int nodeNum() const { 311 int i=0; 312 Node n; 313 for (first(n); n!=INVALID; next(n)) ++i; 314 return i; 315 } 316 317 /// \warning This is a linear time operation and works only if 318 /// \c Graph::EdgeIt is defined. 319 /// \todo assign tags. 320 int edgeNum() const { 321 int i=0; 322 Edge e; 323 for (first(e); e!=INVALID; next(e)) ++i; 324 return i; 325 } 316 typedef False NodeNumTag; 317 typedef False EdgeNumTag; 326 318 }; 327 319 … … 414 406 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 415 407 416 /// \warning This is a linear time operation and works only if s 417 /// \c Graph::NodeIt is defined. 418 /// \todo assign tags. 419 int nodeNum() const { 420 int i=0; 421 Node n; 422 for (first(n); n!=INVALID; next(n)) ++i; 423 return i; 424 } 425 426 /// \warning This is a linear time operation and works only if 427 /// \c Graph::EdgeIt is defined. 428 /// \todo assign tags. 429 int edgeNum() const { 430 int i=0; 431 Edge e; 432 for (first(e); e!=INVALID; next(e)) ++i; 433 return i; 434 } 408 typedef False NodeNumTag; 409 typedef False EdgeNumTag; 435 410 }; 436 411 … … 441 416 442 417 SubGraphAdaptor shows the graph with filtered nodeset and 443 edgeset. 418 edgeset. If the \c checked parameter is true then it filters the edgeset 419 to do not get invalid edges without source or target. 444 420 Let \f$G=(V, A)\f$ be a directed graph 445 421 and suppose that the graph instance \c g of type ListGraph implements … … 454 430 only on edges leaving and entering a specific node which have true value. 455 431 456 We have to note that this does not mean that an 457 induced subgraph is obtained, the nodeiterator cares only the filter 458 on the nodeset, and the edgeiterators care only the filter on the 459 edgeset. 432 If the \c checked template parameter is false then we have to note that 433 the nodeiterator cares only the filter on the nodeset, and the 434 edgeiterator cares only the filter on the edgeset. This way the edgemap 435 should filter all edges which's source or target is filtered by the 436 nodefilter. 460 437 \code 461 438 typedef ListGraph Graph; … … 520 497 An adaptor for hiding nodes from a graph. 521 498 This adaptor specializes SubGraphAdaptor in the way that only the nodeset 522 can be filtered. Note that this does not mean of considering induced 523 subgraph, the edgeiterators consider the original edgeset. 499 can be filtered. In usual case the checked parameter is true, we get the 500 induced subgraph. But if the checked parameter is false then we can only 501 filter only isolated nodes. 524 502 \author Marton Makai 525 503 */ … … 704 682 typedef typename Parent::Edge Edge; 705 683 706 /// \bug Why cant an edge say that it is forward or not???707 /// By this, a pointer to the graph have to be stored708 /// The implementation709 684 template <typename T> 710 685 class EdgeMap { … … 1123 1098 return 2*this>graph>edgeNum(); 1124 1099 } 1125 // KEEP_MAPS(Parent, BidirGraphAdaptor);1126 1100 }; 1127 1101 … … 1332 1306 1333 1307 template <typename _Graph> 1308 class SplitGraphAdaptorBase 1309 : public GraphAdaptorBase<_Graph> { 1310 public: 1311 typedef GraphAdaptorBase<_Graph> Parent; 1312 1313 class Node; 1314 class Edge; 1315 template <typename T> class NodeMap; 1316 template <typename T> class EdgeMap; 1317 1318 1319 class Node : public Parent::Node { 1320 friend class SplitGraphAdaptorBase; 1321 template <typename T> friend class NodeMap; 1322 typedef typename Parent::Node NodeParent; 1323 private: 1324 1325 bool entry; 1326 Node(typename Parent::Node _node, bool _entry) 1327 : Parent::Node(_node), entry(_entry) {} 1328 1329 public: 1330 Node() {} 1331 Node(Invalid) : NodeParent(INVALID), entry(true) {} 1332 1333 bool operator==(const Node& node) const { 1334 return NodeParent::operator==(node) && entry == node.entry; 1335 } 1336 1337 bool operator!=(const Node& node) const { 1338 return !(*this == node); 1339 } 1340 1341 bool operator<(const Node& node) const { 1342 return NodeParent::operator<(node)  1343 (NodeParent::operator==(node) && entry < node.entry); 1344 } 1345 }; 1346 1347 /// \todo May we want VARIANT/union type 1348 class Edge : public Parent::Edge { 1349 friend class SplitGraphAdaptorBase; 1350 template <typename T> friend class EdgeMap; 1351 private: 1352 typedef typename Parent::Edge EdgeParent; 1353 typedef typename Parent::Node NodeParent; 1354 NodeParent bind; 1355 1356 Edge(const EdgeParent& edge, const NodeParent& node) 1357 : EdgeParent(edge), bind(node) {} 1358 public: 1359 Edge() {} 1360 Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {} 1361 1362 bool operator==(const Edge& edge) const { 1363 return EdgeParent::operator==(edge) && bind == edge.bind; 1364 } 1365 1366 bool operator!=(const Edge& edge) const { 1367 return !(*this == edge); 1368 } 1369 1370 bool operator<(const Edge& edge) const { 1371 return EdgeParent::operator<(edge)  1372 (EdgeParent::operator==(edge) && bind < edge.bind); 1373 } 1374 }; 1375 1376 void first(Node& node) const { 1377 Parent::first(node); 1378 node.entry = true; 1379 } 1380 1381 void next(Node& node) const { 1382 if (node.entry) { 1383 node.entry = false; 1384 } else { 1385 node.entry = true; 1386 Parent::next(node); 1387 } 1388 } 1389 1390 void first(Edge& edge) const { 1391 Parent::first(edge); 1392 if ((typename Parent::Edge&)edge == INVALID) { 1393 Parent::first(edge.bind); 1394 } else { 1395 edge.bind = INVALID; 1396 } 1397 } 1398 1399 void next(Edge& edge) const { 1400 if ((typename Parent::Edge&)edge != INVALID) { 1401 Parent::next(edge); 1402 if ((typename Parent::Edge&)edge == INVALID) { 1403 Parent::first(edge.bind); 1404 } 1405 } else { 1406 Parent::next(edge.bind); 1407 } 1408 } 1409 1410 void firstIn(Edge& edge, const Node& node) const { 1411 if (node.entry) { 1412 Parent::firstIn(edge, node); 1413 edge.bind = INVALID; 1414 } else { 1415 (typename Parent::Edge&)edge = INVALID; 1416 edge.bind = node; 1417 } 1418 } 1419 1420 void nextIn(Edge& edge) const { 1421 if ((typename Parent::Edge&)edge != INVALID) { 1422 Parent::nextIn(edge); 1423 } else { 1424 edge.bind = INVALID; 1425 } 1426 } 1427 1428 void firstOut(Edge& edge, const Node& node) const { 1429 if (!node.entry) { 1430 Parent::firstOut(edge, node); 1431 edge.bind = INVALID; 1432 } else { 1433 (typename Parent::Edge&)edge = INVALID; 1434 edge.bind = node; 1435 } 1436 } 1437 1438 void nextOut(Edge& edge) const { 1439 if ((typename Parent::Edge&)edge != INVALID) { 1440 Parent::nextOut(edge); 1441 } else { 1442 edge.bind = INVALID; 1443 } 1444 } 1445 1446 Node source(const Edge& edge) const { 1447 if ((typename Parent::Edge&)edge != INVALID) { 1448 return Node(Parent::source(edge), false); 1449 } else { 1450 return Node(edge.bind, true); 1451 } 1452 } 1453 1454 Node target(const Edge& edge) const { 1455 if ((typename Parent::Edge&)edge != INVALID) { 1456 return Node(Parent::target(edge), true); 1457 } else { 1458 return Node(edge.bind, false); 1459 } 1460 } 1461 1462 static bool entryNode(const Node& node) { 1463 return node.entry; 1464 } 1465 1466 static bool exitNode(const Node& node) { 1467 return !node.entry; 1468 } 1469 1470 static Node getEntry(const typename Parent::Node& node) { 1471 return Node(node, true); 1472 } 1473 1474 static Node getExit(const typename Parent::Node& node) { 1475 return Node(node, false); 1476 } 1477 1478 static bool originalEdge(const Edge& edge) { 1479 return (typename Parent::Edge&)edge != INVALID; 1480 } 1481 1482 static bool bindingEdge(const Edge& edge) { 1483 return edge.bind != INVALID; 1484 } 1485 1486 static Node getBindedNode(const Edge& edge) { 1487 return edge.bind; 1488 } 1489 1490 int nodeNum() const { 1491 return Parent::nodeNum() * 2; 1492 } 1493 1494 typedef CompileTimeAnd<typename Parent::NodeNumTag, 1495 typename Parent::EdgeNumTag> EdgeNumTag; 1496 1497 int edgeNum() const { 1498 return Parent::edgeNum() + Parent::nodeNum(); 1499 } 1500 1501 Edge findEdge(const Node& source, const Node& target, 1502 const Edge& prev = INVALID) const { 1503 if (exitNode(source) && entryNode(target)) { 1504 return Parent::findEdge(source, target, prev); 1505 } else { 1506 if (prev == INVALID && entryNode(source) && exitNode(target) && 1507 (typename Parent::Node&)source == (typename Parent::Node&)target) { 1508 return Edge(INVALID, source); 1509 } else { 1510 return INVALID; 1511 } 1512 } 1513 } 1514 1515 template <typename T> 1516 class NodeMap : public MapBase<Node, T> { 1517 typedef typename Parent::template NodeMap<T> NodeImpl; 1518 public: 1519 NodeMap(const SplitGraphAdaptorBase& _graph) 1520 : entry(_graph), exit(_graph) {} 1521 NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 1522 : entry(_graph, t), exit(_graph, t) {} 1523 1524 void set(const Node& key, const T& val) { 1525 if (key.entry) { entry.set(key, val); } 1526 else {exit.set(key, val); } 1527 } 1528 1529 typename ReferenceMapTraits<NodeImpl>::Reference 1530 operator[](const Node& key) { 1531 if (key.entry) { return entry[key]; } 1532 else { return exit[key]; } 1533 } 1534 1535 T operator[](const Node& key) const { 1536 if (key.entry) { return entry[key]; } 1537 else { return exit[key]; } 1538 } 1539 1540 private: 1541 NodeImpl entry, exit; 1542 }; 1543 1544 template <typename T> 1545 class EdgeMap : public MapBase<Edge, T> { 1546 typedef typename Parent::template NodeMap<T> NodeImpl; 1547 typedef typename Parent::template EdgeMap<T> EdgeImpl; 1548 public: 1549 EdgeMap(const SplitGraphAdaptorBase& _graph) 1550 : bind(_graph), orig(_graph) {} 1551 EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 1552 : bind(_graph, t), orig(_graph, t) {} 1553 1554 void set(const Edge& key, const T& val) { 1555 if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); } 1556 else {bind.set(key.bind, val); } 1557 } 1558 1559 typename ReferenceMapTraits<EdgeImpl>::Reference 1560 operator[](const Edge& key) { 1561 if ((typename Parent::Edge&)key != INVALID) { return orig[key]; } 1562 else {return bind[key.bind]; } 1563 } 1564 1565 T operator[](const Edge& key) const { 1566 if ((typename Parent::Edge&)key != INVALID) { return orig[key]; } 1567 else {return bind[key.bind]; } 1568 } 1569 1570 private: 1571 typename Parent::template NodeMap<T> bind; 1572 typename Parent::template EdgeMap<T> orig; 1573 }; 1574 1575 template <typename EntryMap, typename ExitMap> 1576 class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> { 1577 public: 1578 typedef MapBase<Node, typename EntryMap::Value> Parent; 1579 1580 typedef typename Parent::Key Key; 1581 typedef typename Parent::Value Value; 1582 1583 CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap) 1584 : entryMap(_entryMap), exitMap(_exitMap) {} 1585 1586 Value& operator[](const Key& key) { 1587 if (key.entry) { 1588 return entryMap[key]; 1589 } else { 1590 return exitMap[key]; 1591 } 1592 } 1593 1594 Value operator[](const Key& key) const { 1595 if (key.entry) { 1596 return entryMap[key]; 1597 } else { 1598 return exitMap[key]; 1599 } 1600 } 1601 1602 void set(const Key& key, const Value& value) { 1603 if (key.entry) { 1604 entryMap.set(key, value); 1605 } else { 1606 exitMap.set(key, value); 1607 } 1608 } 1609 1610 private: 1611 1612 EntryMap& entryMap; 1613 ExitMap& exitMap; 1614 1615 }; 1616 1617 template <typename EdgeMap, typename NodeMap> 1618 class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> { 1619 public: 1620 typedef MapBase<Edge, typename EdgeMap::Value> Parent; 1621 1622 typedef typename Parent::Key Key; 1623 typedef typename Parent::Value Value; 1624 1625 CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap) 1626 : edgeMap(_edgeMap), nodeMap(_nodeMap) {} 1627 1628 void set(const Edge& edge, const Value& val) { 1629 if (SplitGraphAdaptorBase::originalEdge(edge)) { 1630 edgeMap.set(edge, val); 1631 } else { 1632 nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val); 1633 } 1634 } 1635 1636 Value operator[](const Key& edge) const { 1637 if (SplitGraphAdaptorBase::originalEdge(edge)) { 1638 return edgeMap[edge]; 1639 } else { 1640 return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)]; 1641 } 1642 } 1643 1644 Value& operator[](const Key& edge) { 1645 if (SplitGraphAdaptorBase::originalEdge(edge)) { 1646 return edgeMap[edge]; 1647 } else { 1648 return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)]; 1649 } 1650 } 1651 1652 private: 1653 EdgeMap& edgeMap; 1654 NodeMap& nodeMap; 1655 }; 1656 1657 }; 1658 1659 template <typename _Graph> 1660 class SplitGraphAdaptor 1661 : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > { 1662 public: 1663 typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent; 1664 1665 SplitGraphAdaptor(_Graph& graph) { 1666 Parent::setGraph(graph); 1667 } 1668 1669 1670 }; 1671 1672 template <typename _Graph> 1334 1673 class NewEdgeSetAdaptorBase { 1335 1674 public:
Note: See TracChangeset
for help on using the changeset viewer.