COIN-OR::LEMON - Graph Library

Changeset 1695:e6f99fe1723f in lemon-0.x


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

Potential difference map
NodeMatrixMap? -- Matrix over the nodes
Indicators for common tags

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_utils.h

    r1679 r1695  
    2121#include <vector>
    2222#include <map>
     23#include <cmath>
    2324
    2425#include <lemon/invalid.h>
     
    10611062  }
    10621063
    1063   template <typename _Graph>
    1064   class DegMapBase {
    1065   public:
    1066    
     1064  /// \brief Potential difference map
     1065  ///
     1066  /// If there is an potential map on the nodes then we
     1067  /// can get an edge map as we get the substraction of the
     1068  /// values of the target and source.
     1069  template <typename Graph, typename NodeMap>
     1070  class PotentialDifferenceMap {
     1071  public:
     1072    typedef typename Graph::Edge Key;
     1073    typedef typename NodeMap::Value Value;
     1074
     1075    /// \brief Constructor
     1076    ///
     1077    /// Contructor of the map
     1078    PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
     1079      : graph(_graph), potential(_potential) {}
     1080
     1081    /// \brief Const subscription operator
     1082    ///
     1083    /// Const subscription operator
     1084    Value operator[](const Key& edge) const {
     1085      return potential[graph.target(edge)] - potential[graph.source(edge)];
     1086    }
     1087
     1088  private:
     1089    const Graph& graph;
     1090    const NodeMap& potential;
     1091  };
     1092
     1093  /// \brief Just returns a PotentialDifferenceMap
     1094  ///
     1095  /// Just returns a PotentialDifferenceMap
     1096  /// \relates PotentialDifferenceMap
     1097  template <typename Graph, typename NodeMap>
     1098  PotentialDifferenceMap<Graph, NodeMap>
     1099  potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
     1100    return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
     1101  }
     1102
     1103  /// \brief Container for store values for each ordered pair of nodes
     1104  ///
     1105  /// Container for store values for each ordered pair of nodes.
     1106  template <typename _Graph, typename _Value>
     1107  class NodeMatrixMap
     1108    : protected AlterationNotifier<typename _Graph::Node>::ObserverBase {
     1109  public:
    10671110    typedef _Graph Graph;
     1111    typedef typename Graph::Node Node;
     1112    typedef Node Key;
     1113    typedef _Value Value;
     1114
     1115    /// \brief Creates a node matrix for the given graph
     1116    ///
     1117    /// Creates a node matrix for the given graph.
     1118    NodeMatrixMap(const Graph& _graph)
     1119      : graph(_graph), values(size(_graph.maxId(Node()) + 1)) {}
     1120
     1121    /// \brief Creates a node matrix for the given graph
     1122    ///
     1123    /// Creates a node matrix for the given graph and assigns each
     1124    /// initial value to the given parameter.
     1125    NodeMatrixMap(const Graph& _graph, const Value& _val)
     1126      : graph(_graph), values(size(_graph.maxId(Node()) + 1), _val) {}
     1127
     1128    /// \brief Gives back the value assigned to the \c left - \c right
     1129    /// ordered pair.
     1130    ///
     1131    /// Gives back the value assigned to the \c left - \c right ordered pair.
     1132    const Value& operator()(const Node& left, const Node& right) const {
     1133      return values[index(graph.id(left), graph.id(right))];
     1134    }
     1135   
     1136    /// \brief Gives back the value assigned to the \c left - \c right
     1137    /// ordered pair.
     1138    ///
     1139    /// Gives back the value assigned to the \c left - \c right ordered pair.
     1140    Value& operator()(const Node& left, const Node& right) {
     1141      return values[index(graph.id(left), graph.id(right))];
     1142    }
     1143
     1144    /// \brief Setter function for the matrix map.
     1145    ///
     1146    /// Setter function for the matrix map.
     1147    void set(const Node& left, const Node& right, const Value& val) {
     1148      values[index(graph.id(left), graph.id(right))] = val;
     1149    }
     1150
     1151    /// \brief Map for the coloumn view of the matrix
     1152    ///
     1153    /// Map for the coloumn view of the matrix.
     1154    class ColMap : public MapBase<Node, Value> {
     1155      friend class NodeMatrixMap;
     1156    private:
     1157      ColMap(NodeMatrixMap& _matrix, Node _col)
     1158        : matrix(_matrix), col(_col) {}
     1159
     1160    public:
     1161      /// \brief Subscription operator
     1162      ///
     1163      /// Subscription operator.
     1164      Value& operator[](Node row) {
     1165        return matrix(col, row);
     1166      }
     1167
     1168      /// \brief Setter function
     1169      ///
     1170      /// Setter function.
     1171      void set(Node row, const Value& val) {
     1172        matrix.set(col, row, val);
     1173      }
     1174     
     1175      /// \brief Subscription operator
     1176      ///
     1177      /// Subscription operator.
     1178      const Value& operator[](Node row) const {
     1179        return matrix(col, row);
     1180      }
     1181
     1182    private:
     1183      NodeMatrixMap& matrix;
     1184      Node col;
     1185    };
     1186
     1187    /// \brief Map for the const coloumn view of the matrix
     1188    ///
     1189    /// Map for the const coloumn view of the matrix.
     1190    class ConstColMap : public MapBase<Node, Value> {
     1191      friend class NodeMatrixMap;
     1192    private:
     1193      ConstColMap(const NodeMatrixMap& _matrix, Node _col)
     1194        : matrix(_matrix), col(_col) {}
     1195     
     1196    public:
     1197      /// \brief Subscription operator
     1198      ///
     1199      /// Subscription operator.
     1200      const Value& operator[](Node row) const {
     1201        return matrix(col, row);
     1202      }
     1203     
     1204    private:
     1205      const NodeMatrixMap& matrix;
     1206      Node col;
     1207    };
     1208
     1209    /// \brief Map for the row view of the matrix
     1210    ///
     1211    /// Map for the row view of the matrix.
     1212    class RowMap : public MapBase<Node, Value> {
     1213    public:
     1214      friend class NodeMatrixMap;
     1215    private:
     1216      RowMap(NodeMatrixMap& _matrix, Node _row)
     1217        : matrix(_matrix), row(_row) {}
     1218     
     1219    public:
     1220      /// \brief Subscription operator
     1221      ///
     1222      /// Subscription operator.
     1223      Value& operator[](Node col) {
     1224        return matrix(col, row);
     1225      }
     1226
     1227      /// \brief Setter function
     1228      ///
     1229      /// Setter function.
     1230      void set(Node col, const Value& val) {
     1231        matrix.set(col, row, val);
     1232      }
     1233     
     1234      /// \brief Subscription operator
     1235      ///
     1236      /// Subscription operator.
     1237      const Value& operator[](Node col) const {
     1238        return matrix(col, row);
     1239      }
     1240
     1241    private:
     1242      NodeMatrixMap& matrix;
     1243      Node row;
     1244    };
     1245
     1246    /// \brief Map for the const row view of the matrix
     1247    ///
     1248    /// Map for the row const view of the matrix.
     1249    class ConstRowMap : public MapBase<Node, Value> {
     1250    public:
     1251      friend class NodeMatrixMap;
     1252    private:
     1253      ConstRowMap(const NodeMatrixMap& _matrix, Node _row)
     1254        : matrix(_matrix), row(_row) {}
     1255     
     1256    public:
     1257      /// \brief Subscription operator
     1258      ///
     1259      /// Subscription operator.
     1260      const Value& operator[](Node col) const {
     1261        return matrix(col, row);
     1262      }
     1263     
     1264    private:
     1265      const NodeMatrixMap& matrix;
     1266      Node row;
     1267    };
     1268
     1269    /// \brief Gives back the column view for the given node
     1270    ///
     1271    /// Gives back the column view for the given node
     1272    ConstColMap operator[](Node col) const { return ConstColMap(*this, col); }
     1273    /// \brief Gives back the column view for the given node
     1274    ///
     1275    /// Gives back the column view for the given node
     1276    ColMap operator[](Node col) { return ColMap(*this, col); }
     1277
     1278    /// \brief Gives back the column view for the given node
     1279    ///
     1280    /// Gives back the column view for the given node
     1281    ConstColMap colMap(Node col) const { return ConstColMap(*this, col); }
     1282    /// \brief Gives back the column view for the given node
     1283    ///
     1284    /// Gives back the column view for the given node
     1285    ColMap colMap(Node col) { return ColMap(*this, col); }
     1286
     1287    /// \brief Gives back the row view for the given node
     1288    ///
     1289    /// Gives back the row view for the given node
     1290    ConstRowMap rowMap(Node row) const { return ConstRowMap(*this, row); }
     1291    /// \brief Gives back the row view for the given node
     1292    ///
     1293    /// Gives back the row view for the given node
     1294    RowMap rowMap(Node row) { return RowMap(*this, row); }
    10681295
    10691296  protected:
    10701297
    1071     typedef typename Graph::template NodeMap<int> IntNodeMap;
    1072    
     1298    static int index(int i, int j) {
     1299      int m = i > j ? i : j;
     1300      if (i < j) {
     1301        return m * m + i;
     1302      } else {
     1303        return m * m + m + j;
     1304      }
     1305    }
     1306
     1307    static int size(int s) {
     1308      return s * s;
     1309    }
     1310
     1311    void add(const Node& node) {
     1312      if (size(graph.id(node) + 1) > values.size()) {
     1313        values.resize(size(graph.id(node) + 1));       
     1314      }
     1315    }
     1316
     1317    void erase(const Node&) {}
     1318
     1319    void build() {
     1320      values.resize(size(graph.maxId(Node()) + 1));
     1321    }
     1322
     1323    void clear() {
     1324      values.clear();
     1325    }   
     1326   
     1327  private:
     1328    const Graph& graph;
     1329    std::vector<Value> values;
    10731330  };
    10741331
     
    12711528  };
    12721529
     1530  // Indicators for the tags
     1531
     1532  template <typename Graph, typename Enable = void>
     1533  struct NodeNumTagIndicator {
     1534    static const bool value = false;
     1535  };
     1536
     1537  template <typename Graph>
     1538  struct NodeNumTagIndicator<
     1539    Graph,
     1540    typename enable_if<typename Graph::NodeNumTag, void>::type
     1541  > {
     1542    static const bool value = true;
     1543  };
     1544
     1545  template <typename Graph, typename Enable = void>
     1546  struct EdgeNumTagIndicator {
     1547    static const bool value = false;
     1548  };
     1549
     1550  template <typename Graph>
     1551  struct EdgeNumTagIndicator<
     1552    Graph,
     1553    typename enable_if<typename Graph::EdgeNumTag, void>::type
     1554  > {
     1555    static const bool value = true;
     1556  };
     1557
     1558  template <typename Graph, typename Enable = void>
     1559  struct FindEdgeTagIndicator {
     1560    static const bool value = false;
     1561  };
     1562
     1563  template <typename Graph>
     1564  struct FindEdgeTagIndicator<
     1565    Graph,
     1566    typename enable_if<typename Graph::FindEdgeTag, void>::type
     1567  > {
     1568    static const bool value = true;
     1569  };
     1570
     1571
    12731572  /// @}
    12741573
  • lemon/maps.h

    r1691 r1695  
    1818#define LEMON_MAPS_H
    1919
    20 #include <lemon/graph_utils.h>
    2120#include <lemon/utility.h>
    2221
Note: See TracChangeset for help on using the changeset viewer.