540 template <typename Target, typename Source> |
542 template <typename Target, typename Source> |
541 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) { |
543 GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) { |
542 return GraphCopy<Target, Source>(target, source); |
544 return GraphCopy<Target, Source>(target, source); |
543 } |
545 } |
544 |
546 |
545 template <typename _Graph, typename _Item> |
547 /// \brief Class to copy an undirected graph. |
546 class ItemSetTraits {}; |
548 /// |
547 |
549 /// Class to copy an undirected graph to an other graph (duplicate a graph). |
548 template <typename _Graph> |
550 /// The simplest way of using it is through the \c copyUndirGraph() function. |
549 class ItemSetTraits<_Graph, typename _Graph::Node> { |
551 template <typename Target, typename Source> |
550 public: |
552 class UndirGraphCopy { |
551 |
553 public: |
552 typedef _Graph Graph; |
554 typedef typename Source::Node Node; |
553 |
555 typedef typename Source::NodeIt NodeIt; |
554 typedef typename Graph::Node Item; |
556 typedef typename Source::Edge Edge; |
555 typedef typename Graph::NodeIt ItemIt; |
557 typedef typename Source::EdgeIt EdgeIt; |
556 |
558 typedef typename Source::UndirEdge UndirEdge; |
557 template <typename _Value> |
559 typedef typename Source::UndirEdgeIt UndirEdgeIt; |
558 class Map : public Graph::template NodeMap<_Value> { |
560 |
559 public: |
561 typedef typename Source:: |
560 typedef typename Graph::template NodeMap<_Value> Parent; |
562 template NodeMap<typename Target::Node> NodeRefMap; |
561 typedef typename Parent::Value Value; |
563 |
562 |
564 typedef typename Source:: |
563 Map(const Graph& _graph) : Parent(_graph) {} |
565 template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap; |
564 Map(const Graph& _graph, const Value& _value) |
566 |
565 : Parent(_graph, _value) {} |
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; |
566 }; |
580 }; |
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; |
568 }; |
739 }; |
569 |
740 |
570 template <typename _Graph> |
741 /// \brief Copy a graph to an other graph. |
571 class ItemSetTraits<_Graph, typename _Graph::Edge> { |
742 /// |
572 public: |
743 /// Copy a graph to an other graph. |
573 |
744 /// The usage of the function: |
574 typedef _Graph Graph; |
745 /// |
575 |
746 /// \code |
576 typedef typename Graph::Edge Item; |
747 /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr); |
577 typedef typename Graph::EdgeIt ItemIt; |
748 /// \endcode |
578 |
749 /// |
579 template <typename _Value> |
750 /// After the copy the \c nr map will contain the mapping from the |
580 class Map : public Graph::template EdgeMap<_Value> { |
751 /// source graph's nodes to the target graph's nodes and the \c ecr will |
581 public: |
752 /// contain the mapping from the target graph's edges to the source's |
582 typedef typename Graph::template EdgeMap<_Value> Parent; |
753 /// edges. |
583 typedef typename Parent::Value Value; |
754 template <typename Target, typename Source> |
584 |
755 UndirGraphCopy<Target, Source> |
585 Map(const Graph& _graph) : Parent(_graph) {} |
756 copyUndirGraph(Target& target, const Source& source) { |
586 Map(const Graph& _graph, const Value& _value) |
757 return UndirGraphCopy<Target, Source>(target, source); |
587 : Parent(_graph, _value) {} |
758 } |
588 }; |
759 |
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 }; |
|
613 |
760 |
614 /// @} |
761 /// @} |
615 |
762 |
616 /// \addtogroup graph_maps |
763 /// \addtogroup graph_maps |
617 /// @{ |
764 /// @{ |
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 }; |
|
639 |
765 |
640 /// Provides an immutable and unique id for each item in the graph. |
766 /// Provides an immutable and unique id for each item in the graph. |
641 |
767 |
642 /// The IdMap class provides a unique and immutable id for each item of the |
768 /// The IdMap class provides a unique and immutable id for each item of the |
643 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique: |
769 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique: |
1190 PotentialDifferenceMap<Graph, NodeMap> |
1316 PotentialDifferenceMap<Graph, NodeMap> |
1191 potentialDifferenceMap(const Graph& graph, const NodeMap& potential) { |
1317 potentialDifferenceMap(const Graph& graph, const NodeMap& potential) { |
1192 return PotentialDifferenceMap<Graph, NodeMap>(graph, potential); |
1318 return PotentialDifferenceMap<Graph, NodeMap>(graph, potential); |
1193 } |
1319 } |
1194 |
1320 |
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 |
|
1423 /// \brief Map of the node in-degrees. |
1321 /// \brief Map of the node in-degrees. |
1424 /// |
1322 /// |
1425 /// This map returns the in-degree of a node. Once it is constructed, |
1323 /// This map returns the in-degree of a node. Once it is constructed, |
1426 /// the degrees are stored in a standard NodeMap, so each query is done |
1324 /// the degrees are stored in a standard NodeMap, so each query is done |
1427 /// in constant time. On the other hand, the values are updated automatically |
1325 /// in constant time. On the other hand, the values are updated automatically |
1428 /// whenever the graph changes. |
1326 /// 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. |
|
1437 /// |
1327 /// |
1438 /// \sa OutDegMap |
1328 /// \sa OutDegMap |
1439 |
1329 |
1440 template <typename _Graph> |
1330 template <typename _Graph> |
1441 class InDegMap |
1331 class InDegMap |