COIN-OR::LEMON - Graph Library

Changeset 1720:578d8b2b76c6 in lemon-0.x for lemon/graph_utils.h


Ignore:
Timestamp:
10/14/05 12:49:51 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2247
Message:

Matrixmaps moved to own file

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_utils.h

    r1712 r1720  
    2626#include <lemon/utility.h>
    2727#include <lemon/maps.h>
     28#include <lemon/traits.h>
    2829#include <lemon/bits/alteration_notifier.h>
    2930
     
    401402  }
    402403
    403 
    404404  /// \brief Class to copy a graph.
    405405  ///
     
    515515      return edgeRefMap;
    516516    }
     517
     518    void run() {}
    517519
    518520  private:
     
    543545  }
    544546
    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;
    566580    };
    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;
    568739  };
    569740
    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
    613760
    614761  /// @}
     
    616763  /// \addtogroup graph_maps
    617764  /// @{
    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>::type
    632   > {
    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   };
    639765
    640766  /// Provides an immutable and unique id for each item in the graph.
     
    755881    ///
    756882    /// It gives back the value associated with the key.
    757     const Value operator[](const Key& key) const {
     883    Value operator[](const Key& key) const {
    758884      return Map::operator[](key);
    759885    }
     
    11931319  }
    11941320
    1195   /// \brief Container for store values for each ordered pair of nodes
    1196   ///
    1197   /// Container for store values for each ordered pair of nodes.
    1198   template <typename _Graph, typename _Value>
    1199   class NodeMatrixMap
    1200     : 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 graph
    1208     ///
    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 graph
    1214     ///
    1215     /// Creates a node matrix for the given graph and assigns each
    1216     /// 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 right
    1221     /// 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 right
    1229     /// 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 matrix
    1244     ///
    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 operator
    1254       ///
    1255       /// Subscription operator.
    1256       Value& operator[](Node row) {
    1257         return matrix(col, row);
    1258       }
    1259 
    1260       /// \brief Setter function
    1261       ///
    1262       /// Setter function.
    1263       void set(Node row, const Value& val) {
    1264         matrix.set(col, row, val);
    1265       }
    1266      
    1267       /// \brief Subscription operator
    1268       ///
    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 matrix
    1280     ///
    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 operator
    1290       ///
    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 matrix
    1302     ///
    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 operator
    1313       ///
    1314       /// Subscription operator.
    1315       Value& operator[](Node col) {
    1316         return matrix(col, row);
    1317       }
    1318 
    1319       /// \brief Setter function
    1320       ///
    1321       /// Setter function.
    1322       void set(Node col, const Value& val) {
    1323         matrix.set(col, row, val);
    1324       }
    1325      
    1326       /// \brief Subscription operator
    1327       ///
    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 matrix
    1339     ///
    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 operator
    1350       ///
    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 node
    1362     ///
    1363     /// Gives back the column view for the given node
    1364     ConstColMap operator[](Node col) const { return ConstColMap(*this, col); }
    1365     /// \brief Gives back the column view for the given node
    1366     ///
    1367     /// Gives back the column view for the given node
    1368     ColMap operator[](Node col) { return ColMap(*this, col); }
    1369 
    1370     /// \brief Gives back the column view for the given node
    1371     ///
    1372     /// Gives back the column view for the given node
    1373     ConstColMap colMap(Node col) const { return ConstColMap(*this, col); }
    1374     /// \brief Gives back the column view for the given node
    1375     ///
    1376     /// Gives back the column view for the given node
    1377     ColMap colMap(Node col) { return ColMap(*this, col); }
    1378 
    1379     /// \brief Gives back the row view for the given node
    1380     ///
    1381     /// Gives back the row view for the given node
    1382     ConstRowMap rowMap(Node row) const { return ConstRowMap(*this, row); }
    1383     /// \brief Gives back the row view for the given node
    1384     ///
    1385     /// Gives back the row view for the given node
    1386     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 
    14231321  /// \brief Map of the node in-degrees.
    14241322  ///
     
    14271325  /// in constant time. On the other hand, the values are updated automatically
    14281326  /// whenever the graph changes.
    1429   ///
    1430   /// \warning Besides addNode() and addEdge(), a graph structure may provide
    1431   /// alternative ways to mogify the graph. The correct behavior of InDegMap
    1432   /// is not guarantied if these additional featureas are used. For example
    1433   /// the funstions \ref ListGraph::changeSource() "changeSource()",
    1434   /// \ref ListGraph::changeTarget() "changeTarget()" and
    1435   /// \ref ListGraph::reverseEdge() "reverseEdge()"
    1436   /// of \ref ListGraph will \e not update the degree values correctly.
    14371327  ///
    14381328  /// \sa OutDegMap
     
    15021392    }
    15031393
     1394    virtual void signalChange(const Edge& edge) {
     1395      erase(edge);
     1396    }
     1397
     1398    virtual void commitChange(const Edge& edge) {
     1399      add(edge);
     1400    }
    15041401
    15051402    virtual void build() {
     
    15261423  /// in constant time. On the other hand, the values are updated automatically
    15271424  /// whenever the graph changes.
    1528   ///
    1529   /// \warning Besides addNode() and addEdge(), a graph structure may provide
    1530   /// alternative ways to mogify the graph. The correct behavior of OutDegMap
    1531   /// is not guarantied if these additional featureas are used. For example
    1532   /// the funstions \ref ListGraph::changeSource() "changeSource()",
    1533   /// \ref ListGraph::changeTarget() "changeTarget()" and
    1534   /// \ref ListGraph::reverseEdge() "reverseEdge()"
    1535   /// of \ref ListGraph will \e not update the degree values correctly.
    15361425  ///
    15371426  /// \sa InDegMap
     
    16011490    }
    16021491
     1492    virtual void signalChange(const Edge& edge) {
     1493      erase(edge);
     1494    }
     1495
     1496    virtual void commitChange(const Edge& edge) {
     1497      add(edge);
     1498    }
     1499
    16031500
    16041501    virtual void build() {
     
    16191516  };
    16201517
    1621   // Indicators for the tags
    1622 
    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>::type
    1632   > {
    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>::type
    1645   > {
    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>::type
    1658   > {
    1659     static const bool value = true;
    1660   };
    1661 
    16621518
    16631519  /// @}
Note: See TracChangeset for help on using the changeset viewer.