COIN-OR::LEMON - Graph Library

Changeset 1697:4c593a4096da in lemon-0.x


Ignore:
Timestamp:
10/03/05 12:17:53 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2223
Message:

Preliminary SplitGraphAdaptor?
And some other improvments

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_adaptor.h

    r1685 r1697  
    6666  public:
    6767    typedef _Graph Graph;
    68     /// \todo Is it needed?
    69     typedef Graph BaseGraph;
    7068    typedef Graph ParentGraph;
    7169
     
    9492    Node target(const Edge& e) const { return graph->target(e); }
    9593
     94    typedef NodeNumTagIndicator<Graph> NodeNumTag;
    9695    int nodeNum() const { return graph->nodeNum(); }
     96   
     97    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
    9798    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    }
    98105 
    99     Node addNode() const { return Node(graph->addNode()); }
     106    Node addNode() const {
     107      return Node(graph->addNode());
     108    }
     109
    100110    Edge addEdge(const Node& source, const Node& target) const {
    101       return Edge(graph->addEdge(source, target)); }
     111      return Edge(graph->addEdge(source, target));
     112    }
    102113
    103114    void erase(const Node& i) const { graph->erase(i); }
     
    157168    typedef typename Parent::Edge Edge;
    158169
    159     //    using Parent::first;
    160170    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
    161171    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
    162172
    163     //    using Parent::next;
    164173    void nextIn(Edge& i) const { Parent::nextOut(i); }
    165174    void nextOut(Edge& i) const { Parent::nextIn(i); }
     
    305314    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    306315
    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;
    326318  };
    327319
     
    414406    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    415407
    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;
    435410  };
    436411
     
    441416 
    442417  SubGraphAdaptor shows the graph with filtered node-set and
    443   edge-set.
     418  edge-set. If the \c checked parameter is true then it filters the edgeset
     419  to do not get invalid edges without source or target.
    444420  Let \f$G=(V, A)\f$ be a directed graph
    445421  and suppose that the graph instance \c g of type ListGraph implements
     
    454430  only on edges leaving and entering a specific node which have true value.
    455431
    456   We have to note that this does not mean that an
    457   induced subgraph is obtained, the node-iterator cares only the filter
    458   on the node-set, and the edge-iterators care only the filter on the
    459   edge-set.
     432  If the \c checked template parameter is false then we have to note that
     433  the node-iterator cares only the filter on the node-set, and the
     434  edge-iterator cares only the filter on the edge-set. This way the edge-map
     435  should filter all edges which's source or target is filtered by the
     436  node-filter.
    460437  \code
    461438  typedef ListGraph Graph;
     
    520497  An adaptor for hiding nodes from a graph.
    521498  This adaptor specializes SubGraphAdaptor in the way that only the node-set
    522   can be filtered. Note that this does not mean of considering induced
    523   subgraph, the edge-iterators consider the original edge-set.
     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.
    524502  \author Marton Makai
    525503  */
     
    704682    typedef typename Parent::Edge Edge;
    705683   
    706     /// \bug Why cant an edge say that it is forward or not???
    707     /// By this, a pointer to the graph have to be stored
    708     /// The implementation
    709684    template <typename T>
    710685    class EdgeMap {
     
    11231098      return 2*this->graph->edgeNum();
    11241099    }
    1125     //    KEEP_MAPS(Parent, BidirGraphAdaptor);
    11261100  };
    11271101
     
    13321306
    13331307  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>
    13341673  class NewEdgeSetAdaptorBase {
    13351674  public:
Note: See TracChangeset for help on using the changeset viewer.