File indexing completed on 2025-01-19 03:53:35
0001 /* ============================================================ 0002 * 0003 * This file is a part of digiKam project 0004 * https://www.digikam.org 0005 * 0006 * Date : 2010-10-22 0007 * Description : Boost Graph Library: a graph class 0008 * 0009 * SPDX-FileCopyrightText: 2010-2011 by Marcel Wiesweg <marcel dot wiesweg at gmx dot de> 0010 * 0011 * SPDX-License-Identifier: GPL-2.0-or-later 0012 * 0013 * ============================================================ */ 0014 0015 #ifndef DIGIKAM_ITEM_HISTORY_GRAPH_BOOST_H 0016 #define DIGIKAM_ITEM_HISTORY_GRAPH_BOOST_H 0017 0018 // To include pragma directives for MSVC 0019 #include "digikam_config.h" 0020 0021 #ifdef Q_CC_MSVC 0022 # include <ciso646> 0023 # pragma warning(disable : 4267) 0024 #endif 0025 0026 #if !defined(Q_OS_DARWIN) && defined(Q_CC_GNU) 0027 # pragma GCC diagnostic push 0028 # pragma GCC diagnostic ignored "-Wdeprecated-declarations" 0029 # pragma GCC diagnostic ignored "-Wunused-local-typedefs" 0030 #endif 0031 0032 #if defined(Q_CC_CLANG) 0033 # pragma clang diagnostic push 0034 # pragma clang diagnostic ignored "-Wdeprecated-declarations" 0035 # pragma clang diagnostic ignored "-Wundef" 0036 # pragma clang diagnostic ignored "-Wunused-parameter" 0037 # pragma clang diagnostic ignored "-Wcast-align" 0038 # pragma clang diagnostic ignored "-Wunused-local-typedef" 0039 #endif 0040 0041 // C++ includes 0042 0043 #include <utility> 0044 #include <algorithm> 0045 #include <vector> 0046 #include <stdbool.h> 0047 0048 // Boost includes 0049 0050 // Prohibit boost using deprecated header files 0051 #define BOOST_NO_HASH 0052 #define BOOST_BIND_GLOBAL_PLACEHOLDERS 0053 #define BOOST_ALLOW_DEPRECATED_HEADERS 0054 0055 #include <boost/graph/transitive_closure.hpp> 0056 #include <boost/graph/adjacency_list.hpp> 0057 #include <boost/graph/topological_sort.hpp> 0058 #include <boost/graph/graph_utility.hpp> 0059 #include <boost/graph/dag_shortest_paths.hpp> 0060 #include <boost/graph/dijkstra_shortest_paths.hpp> 0061 #include <boost/graph/reverse_graph.hpp> 0062 #include <boost/graph/dominator_tree.hpp> 0063 #include <boost/graph/depth_first_search.hpp> 0064 #include <boost/graph/breadth_first_search.hpp> 0065 #include <boost/graph/transitive_reduction.hpp> 0066 0067 // Local includes 0068 0069 #include "digikam_debug.h" 0070 #include "digikam_export.h" 0071 0072 /** 0073 * Install custom property ids, out-of-namespace 0074 */ 0075 enum vertex_properties_t { vertex_properties }; 0076 enum edge_properties_t { edge_properties }; 0077 0078 namespace boost 0079 { 0080 BOOST_INSTALL_PROPERTY(vertex, properties); 0081 BOOST_INSTALL_PROPERTY(edge, properties); 0082 } 0083 0084 namespace Digikam 0085 { 0086 0087 /** 0088 * Adds the necessary typedefs so that associative_property_map 0089 * accepts a QMap, and it can be used as a Boost Property Map 0090 */ 0091 template <typename Key, typename Value> 0092 class QMapForAdaptors : public QMap<Key, Value> 0093 { 0094 public: 0095 0096 typedef Key key_type; 0097 typedef Value data_type; 0098 typedef typename std::pair<const Key, Value> value_type; 0099 0100 QMapForAdaptors() 0101 { 0102 } 0103 }; 0104 0105 /** 0106 * Each edge is directed: "vertex1 -> vertex2". 0107 * This direction has a meaning with methods such as 0108 * roots() or leaves(). 0109 */ 0110 enum MeaningOfDirection 0111 { 0112 ParentToChild, ///< Edges are directed from a parent to its child 0113 ChildToParent ///< Edges are direct from a child to its parent 0114 }; 0115 0116 /** 0117 * The graph base class template 0118 */ 0119 template <class VertexProperties, class EdgeProperties> 0120 class DIGIKAM_DATABASE_EXPORT Graph // clazy:exclude=missing-typeinfo,copyable-polymorphic 0121 { 0122 public: 0123 0124 typedef boost::adjacency_list< 0125 boost::vecS, ///< Standard storage. listS was desirable, but many algorithms work only with vecS 0126 boost::vecS, 0127 boost::bidirectionalS, ///< directed graph 0128 boost::property<boost::vertex_index_t, int, 0129 boost::property<vertex_properties_t, VertexProperties> >, 0130 boost::property<edge_properties_t, EdgeProperties> ///< One property for each edge: EdgeProperties 0131 > GraphContainer; 0132 0133 /** 0134 * a bunch of graph-specific typedefs that make the long boost types manageable 0135 */ 0136 typedef typename boost::graph_traits<GraphContainer> graph_traits; 0137 0138 typedef typename graph_traits::vertex_descriptor vertex_t; 0139 typedef typename graph_traits::edge_descriptor edge_t; 0140 0141 typedef typename graph_traits::vertex_iterator vertex_iter; 0142 typedef typename graph_traits::edge_iterator edge_iter; 0143 typedef typename graph_traits::adjacency_iterator adjacency_iter; 0144 typedef typename graph_traits::out_edge_iterator out_edge_iter; 0145 typedef typename graph_traits::in_edge_iterator in_edge_iter; 0146 typedef typename boost::inv_adjacency_iterator_generator<GraphContainer, 0147 vertex_t, 0148 in_edge_iter>::type inv_adjacency_iter; 0149 0150 typedef typename graph_traits::degree_size_type degree_t; 0151 0152 typedef std::pair<adjacency_iter, adjacency_iter> adjacency_vertex_range_t; 0153 typedef std::pair<inv_adjacency_iter, inv_adjacency_iter> inv_adjacency_vertex_range_t; 0154 typedef std::pair<out_edge_iter, out_edge_iter> out_edge_range_t; 0155 typedef std::pair<vertex_iter, vertex_iter> vertex_range_t; 0156 typedef std::pair<edge_iter, edge_iter> edge_range_t; 0157 0158 typedef typename boost::property_map<GraphContainer, boost::vertex_index_t>::type vertex_index_map_t; 0159 typedef typename boost::property_map<GraphContainer, boost::vertex_index_t>::const_type const_vertex_index_map_t; 0160 typedef typename boost::property_map<GraphContainer, vertex_properties_t>::type vertex_property_map_t; 0161 typedef typename boost::property_map<GraphContainer, vertex_properties_t>::const_type const_vertex_property_map_t; 0162 typedef typename boost::property_map<GraphContainer, edge_properties_t>::type edge_property_map_t; 0163 typedef typename boost::property_map<GraphContainer, edge_properties_t>::const_type const_edge_property_map_t; 0164 0165 /** 0166 * These two classes provide source-compatible wrappers for the vertex and edge descriptors, 0167 * providing default construction to null and the isNull() method. 0168 */ 0169 class DIGIKAM_DATABASE_EXPORT Vertex // clazy:exclude=missing-typeinfo 0170 { 0171 public: 0172 0173 Vertex() 0174 : v(graph_traits::null_vertex()) 0175 { 0176 } 0177 0178 // cppcheck-suppress noExplicitConstructor 0179 Vertex(const vertex_t& v) // krazy:exclude=explicit 0180 : v(v) 0181 { 0182 } 0183 0184 Vertex& operator=(const vertex_t& other) 0185 { 0186 v = other; 0187 0188 return *this; 0189 } 0190 0191 operator const vertex_t&() const 0192 { 0193 return v; 0194 } 0195 0196 operator vertex_t&() 0197 { 0198 return v; 0199 } 0200 0201 bool operator==(const vertex_t& other) const 0202 { 0203 return (v == other); 0204 } 0205 0206 bool isNull() const 0207 { 0208 return (v == graph_traits::null_vertex()); 0209 } 0210 0211 protected: 0212 0213 vertex_t v; 0214 }; 0215 0216 class DIGIKAM_DATABASE_EXPORT Edge // clazy:exclude=missing-typeinfo 0217 { 0218 public: 0219 0220 Edge() 0221 : null(true) 0222 { 0223 } 0224 0225 // cppcheck-suppress noExplicitConstructor 0226 Edge(const edge_t& e) // krazy:exclude=explicit 0227 : e (e), 0228 null(false) 0229 { 0230 } 0231 0232 Edge& operator=(const edge_t& other) 0233 { 0234 e = other; 0235 null = false; 0236 0237 return *this; 0238 } 0239 0240 operator const edge_t&() const 0241 { 0242 return e; 0243 } 0244 0245 operator edge_t&() 0246 { 0247 return e; 0248 } 0249 0250 const edge_t& toEdge() const 0251 { 0252 return e; 0253 } 0254 0255 edge_t& toEdge() 0256 { 0257 return e; 0258 } 0259 0260 bool operator==(const edge_t& other) const 0261 { 0262 return (e == other); 0263 } 0264 0265 bool isNull() const 0266 { 0267 return null; 0268 } 0269 0270 protected: 0271 0272 edge_t e; 0273 0274 /// there is not null_edge, we must emulate it 0275 bool null; 0276 }; 0277 0278 public: 0279 0280 typedef QPair<Vertex, Vertex> VertexPair; 0281 typedef QPair<Edge, Edge> EdgePair; 0282 0283 typedef QMapForAdaptors<Vertex, Vertex> VertexVertexMap; 0284 typedef QMapForAdaptors<Vertex, int> VertexIntMap; 0285 0286 typedef boost::associative_property_map<VertexVertexMap> VertexVertexMapAdaptor; 0287 typedef boost::associative_property_map<VertexIntMap> VertexIntMapAdaptor; 0288 0289 public: 0290 0291 explicit Graph(MeaningOfDirection direction = ParentToChild) 0292 : direction(direction) 0293 { 0294 } 0295 0296 Graph(const Graph& g) 0297 : graph (g.graph), 0298 direction(g.direction) 0299 { 0300 } 0301 0302 virtual ~Graph() 0303 { 0304 } 0305 0306 Graph& operator=(const Graph& other) 0307 { 0308 graph = other.graph; 0309 direction = other.direction; 0310 0311 return *this; 0312 } 0313 0314 MeaningOfDirection meaningOfDirection() const 0315 { 0316 return direction; 0317 } 0318 0319 void clear() 0320 { 0321 graph.clear(); 0322 } 0323 0324 Vertex addVertex() 0325 { 0326 Vertex v = boost::add_vertex(graph); 0327 0328 return v; 0329 } 0330 0331 Vertex addVertex(const VertexProperties& properties) 0332 { 0333 Vertex v = addVertex(); 0334 setProperties(v, properties); 0335 0336 return v; 0337 } 0338 0339 void remove(const Vertex& v) 0340 { 0341 if (v.isNull()) 0342 { 0343 return; 0344 } 0345 0346 boost::clear_vertex(v, graph); 0347 boost::remove_vertex(v, graph); 0348 } 0349 0350 Edge addEdge(const Vertex& v1, const Vertex& v2) 0351 { 0352 Edge e = edge(v1, v2); 0353 0354 if (e.isNull()) 0355 { 0356 e = boost::add_edge(v1, v2, graph).first; 0357 } 0358 0359 return e; 0360 } 0361 0362 Edge edge(const Vertex& v1, const Vertex& v2) const 0363 { 0364 std::pair<edge_t, bool> pair = boost::edge(v1, v2, graph); 0365 0366 if (pair.second) 0367 { 0368 return pair.first; 0369 } 0370 0371 return Edge(); 0372 } 0373 0374 bool hasEdge(const Vertex& v1, const Vertex& v2) const 0375 { 0376 return boost::edge(v1, v2, graph).second; 0377 } 0378 0379 /// Does not care for direction 0380 bool isConnected(const Vertex& v1, const Vertex& v2) const 0381 { 0382 if (boost::edge(v1, v2, graph).second) 0383 { 0384 return true; 0385 } 0386 0387 if (boost::edge(v2, v1, graph).second) 0388 { 0389 return true; 0390 } 0391 0392 return false; 0393 } 0394 0395 void setProperties(const Vertex& v, const VertexProperties& props) 0396 { 0397 boost::put(vertex_properties, graph, v, props); 0398 } 0399 0400 const VertexProperties& properties(const Vertex& v) const 0401 { 0402 return boost::get(vertex_properties, graph, v); 0403 } 0404 0405 VertexProperties& properties(const Vertex& v) 0406 { 0407 return boost::get(vertex_properties, graph, v); 0408 } 0409 0410 void setProperties(const Edge& e, const EdgeProperties& props) 0411 { 0412 boost::put(edge_properties, graph, e, props); 0413 } 0414 0415 template <class T> 0416 Vertex findVertexByProperties(const T& value) const 0417 { 0418 vertex_range_t range = boost::vertices(graph); 0419 0420 for (vertex_iter it = range.first ; it != range.second ; ++it) 0421 { 0422 const VertexProperties& props = properties(*it); 0423 0424 // must implement operator==(const T&) 0425 0426 if (props == value) 0427 { 0428 return *it; 0429 } 0430 } 0431 0432 return Vertex(); 0433 } 0434 0435 EdgeProperties properties(const Vertex& v1, const Vertex& v2) const 0436 { 0437 Edge e = edge(v1, v2); 0438 0439 if (e.isNull()) 0440 { 0441 return EdgeProperties(); 0442 } 0443 0444 return properties(e); 0445 } 0446 0447 const EdgeProperties& properties(const Edge& e) const 0448 { 0449 return boost::get(edge_properties, graph, e); 0450 } 0451 0452 EdgeProperties& properties(const Edge& e) 0453 { 0454 return boost::get(edge_properties, graph, e); 0455 } 0456 0457 /** 0458 * Accessing vertices and edges 0459 */ 0460 const GraphContainer& getGraph() const 0461 { 0462 return graph; 0463 } 0464 0465 QList<Vertex> vertices() const 0466 { 0467 return toVertexList(boost::vertices(graph)); 0468 } 0469 0470 enum AdjacencyFlags 0471 { 0472 OutboundEdges = 1 << 0, 0473 InboundEdges = 1 << 1, 0474 0475 /// These resolve to one of the flags above, depending on MeaningOfDirection 0476 EdgesToLeaf = 1 << 2, 0477 EdgesToRoot = 1 << 3, 0478 AllEdges = InboundEdges | OutboundEdges 0479 }; 0480 0481 QList<Vertex> adjacentVertices(const Vertex& v, AdjacencyFlags flags = AllEdges) const 0482 { 0483 if (flags & EdgesToLeaf) 0484 { 0485 flags = (AdjacencyFlags)(flags | ((direction == ParentToChild) ? OutboundEdges 0486 : InboundEdges)); 0487 } 0488 0489 if (flags & EdgesToRoot) 0490 { 0491 flags = (AdjacencyFlags)(flags | ((direction == ParentToChild) ? InboundEdges 0492 : OutboundEdges)); 0493 } 0494 0495 QList<Vertex> verticesLst; 0496 0497 if (flags & OutboundEdges) 0498 { 0499 verticesLst << toVertexList(boost::adjacent_vertices(v, graph)); 0500 } 0501 0502 if (flags & InboundEdges) 0503 { 0504 verticesLst << toVertexList(boost::inv_adjacent_vertices(v, graph)); 0505 } 0506 0507 return verticesLst; 0508 } 0509 0510 /// NOTE: for "hasAdjacentVertices", simply use hasEdges(v, flags) 0511 int vertexCount() const 0512 { 0513 return (int)boost::num_vertices(graph); 0514 } 0515 0516 bool isEmpty() const 0517 { 0518 return isEmptyRange(boost::vertices(graph)); 0519 } 0520 0521 int outDegree(const Vertex& v) const 0522 { 0523 return (int)boost::out_degree(v, graph); 0524 } 0525 0526 int inDegree(const Vertex& v) const 0527 { 0528 return boost::in_degree(v, graph); 0529 } 0530 0531 bool isRoot(const Vertex& v) const 0532 { 0533 return !hasEdges(v, EdgesToRoot); 0534 } 0535 0536 bool isLeaf(const Vertex& v) const 0537 { 0538 return !hasEdges(v, EdgesToLeaf); 0539 } 0540 0541 Vertex source(const Edge& e) const 0542 { 0543 return boost::source(e.toEdge(), graph); 0544 } 0545 0546 Vertex target(const Edge& e) const 0547 { 0548 return boost::target(e.toEdge(), graph); 0549 } 0550 0551 QList<Edge> edges(const Vertex& v, AdjacencyFlags flags = AllEdges) const 0552 { 0553 if (flags & EdgesToLeaf) 0554 { 0555 flags = (AdjacencyFlags)(flags | ((direction == ParentToChild) ? OutboundEdges 0556 : InboundEdges)); 0557 } 0558 0559 if (flags & EdgesToRoot) 0560 { 0561 flags = (AdjacencyFlags)(flags | ((direction == ParentToChild) ? InboundEdges 0562 : OutboundEdges)); 0563 } 0564 0565 QList<Edge> es; 0566 0567 if (flags & OutboundEdges) 0568 { 0569 es << toEdgeList(boost::out_edges(v, graph)); 0570 } 0571 0572 if (flags & InboundEdges) 0573 { 0574 es << toEdgeList(boost::in_edges(v, graph)); 0575 } 0576 0577 return es; 0578 } 0579 0580 int edgeCount() const 0581 { 0582 return boost::num_edges(graph); 0583 } 0584 0585 bool hasEdges(const Vertex& v, AdjacencyFlags flags = AllEdges) const 0586 { 0587 if (flags & EdgesToLeaf) 0588 { 0589 flags = (AdjacencyFlags)(flags | ((direction == ParentToChild) ? OutboundEdges 0590 : InboundEdges)); 0591 } 0592 0593 if (flags & EdgesToRoot) 0594 { 0595 flags = (AdjacencyFlags)(flags | ((direction == ParentToChild) ? InboundEdges 0596 : OutboundEdges)); 0597 } 0598 0599 if (flags & OutboundEdges) 0600 { 0601 if (!isEmptyRange(boost::out_edges(v, graph))) 0602 { 0603 return true; 0604 } 0605 } 0606 0607 if (flags & InboundEdges) 0608 { 0609 if (!isEmptyRange(boost::in_edges(v, graph))) 0610 { 0611 return true; 0612 } 0613 } 0614 0615 return false; 0616 } 0617 0618 bool hasEdges() const 0619 { 0620 return !isEmptyRange(boost::edges(graph)); 0621 } 0622 0623 QList<Edge> edges() const 0624 { 0625 return toEdgeList(boost::edges(graph)); 0626 } 0627 0628 QList<VertexPair> edgePairs() const 0629 { 0630 QList<VertexPair> pairs; 0631 edge_range_t range = boost::edges(graph); 0632 0633 for (edge_iter it = range.first ; it != range.second ; ++it) 0634 { 0635 pairs << VertexPair(boost::source(*it, graph), boost::target(*it, graph)); 0636 } 0637 0638 return pairs; 0639 } 0640 0641 /* ---- Algorithms ---- */ 0642 0643 /** 0644 * Returns the vertex ids of this graph, in topological order. 0645 */ 0646 QList<Vertex> topologicalSort() const 0647 { 0648 std::list<Vertex> verticesLst; 0649 0650 try 0651 { 0652 boost::topological_sort(graph, std::back_inserter(verticesLst)); 0653 } 0654 catch (boost::bad_graph& e) 0655 { 0656 qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); 0657 0658 return QList<Vertex>(); 0659 } 0660 0661 typedef typename std::list<Vertex>::iterator vertex_list_iter; 0662 0663 return toVertexList(std::pair<vertex_list_iter, vertex_list_iter>(verticesLst.begin(), verticesLst.end())); 0664 } 0665 0666 enum GraphCopyFlags 0667 { 0668 CopyVertexProperties = 1 << 0, 0669 CopyEdgeProperties = 1 << 1, 0670 CopyAllProperties = CopyVertexProperties | CopyEdgeProperties 0671 }; 0672 0673 /** 0674 * Returns a copy of this graph with all edges added to form the transitive closure 0675 */ 0676 Graph transitiveClosure(GraphCopyFlags flags = CopyAllProperties) const 0677 { 0678 // make_iterator_property_map: 0679 // 1. The second parameter, our verteX_index map, converts the key (Vertex) into an index 0680 // 2. The index is used to store the value (Vertex) in the first argument, which is our vector 0681 0682 std::vector<vertex_t> copiedVertices(vertexCount(), Vertex()); 0683 Graph closure; 0684 0685 try 0686 { 0687 boost::transitive_closure( 0688 graph, 0689 closure.graph, 0690 orig_to_copy(make_iterator_property_map(copiedVertices.begin(), 0691 get(boost::vertex_index, graph))) 0692 ); 0693 } 0694 catch (boost::bad_graph& e) 0695 { 0696 qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); 0697 0698 return Graph(); 0699 } 0700 0701 copyProperties(closure, flags, copiedVertices); 0702 0703 return closure; 0704 } 0705 0706 /** 0707 * Returns a copy of this graph, with edges removed so that the transitive reduction is formed. 0708 * Optionally, a list of edges of this graph that have been removed in the returned graph is given. 0709 */ 0710 Graph transitiveReduction(QList<Edge>* removedEdges = 0, GraphCopyFlags flags = CopyAllProperties) const 0711 { 0712 std::vector<vertex_t> copiedVertices(vertexCount(), Vertex()); 0713 Graph reduction; 0714 0715 // NOTE: named parameters is not implemented 0716 0717 try 0718 { 0719 boost::transitive_reduction(graph, reduction.graph, 0720 make_iterator_property_map(copiedVertices.begin(), get(boost::vertex_index, graph)), 0721 get(boost::vertex_index, graph)); 0722 } 0723 catch (boost::bad_graph& e) 0724 { 0725 qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); 0726 0727 return Graph(); 0728 } 0729 0730 copyProperties(reduction, flags, copiedVertices); 0731 0732 if (removedEdges) 0733 { 0734 *removedEdges = edgeDifference(reduction, copiedVertices); 0735 } 0736 0737 return reduction; 0738 } 0739 0740 /** 0741 * Returns all roots, i.e. vertices with no parents. 0742 * Takes the graph direction into account. 0743 */ 0744 QList<Vertex> roots() const 0745 { 0746 return findZeroDegree(direction == ParentToChild ? true : false); 0747 } 0748 0749 /** 0750 * Returns all roots of vertex v. Subset of roots(). 0751 * I case any leaves have roots that are not roots of v, 0752 * they will not be contained in this list. 0753 */ 0754 QList<Vertex> rootsOf(const Vertex& v) const 0755 { 0756 return findZeroDegreeFrom(v, direction == ParentToChild ? true : false); 0757 } 0758 0759 /** 0760 * Returns all leaves, i.e. vertices with no children 0761 * Takes the graph direction into account. 0762 */ 0763 QList<Vertex> leaves() const 0764 { 0765 return findZeroDegree((direction == ParentToChild) ? false : true); 0766 } 0767 0768 QList<Vertex> leavesFrom(const Vertex& v) const 0769 { 0770 return findZeroDegreeFrom(v, (direction == ParentToChild) ? false : true); 0771 } 0772 0773 template <typename T> static bool alwaysFalse(const T&, const T&) 0774 { 0775 return false; 0776 } 0777 0778 /** 0779 * Returns the longest path through the graph, starting from a vertex in roots(), 0780 * ending on a vertex in leaves(), and passing vertex v. 0781 * The returned list is given in that order, root - v - leave. 0782 * If there is more than one candidate for root or leave, lessThan is used to determine the first candidate. 0783 */ 0784 QList<Vertex> longestPathTouching(const Vertex& v) const 0785 { 0786 return longestPathTouching(v, alwaysFalse<Vertex>); 0787 } 0788 0789 template <typename LessThan> 0790 QList<Vertex> longestPathTouching(const Vertex& v, LessThan lessThan) const 0791 { 0792 if (v.isNull()) 0793 { 0794 return QList<Vertex>(); 0795 } 0796 0797 QList<Vertex> fromRoot; 0798 QList<Vertex> toLeave; 0799 Path path; 0800 0801 path.longestPath(boost::make_reverse_graph(graph), v); 0802 0803 QList<Vertex> rootCandidates = mostRemoteNodes(path.distances); 0804 0805 if (!rootCandidates.isEmpty()) 0806 { 0807 std::stable_sort(rootCandidates.begin(), rootCandidates.end(), lessThan); 0808 Vertex root = rootCandidates.first(); 0809 fromRoot << listPath(root, v, path.predecessors, ChildToParent); 0810 } 0811 0812 path.longestPath(graph, v); 0813 0814 QList<Vertex> leaveCandidates = mostRemoteNodes(path.distances); 0815 0816 if (!leaveCandidates.isEmpty()) 0817 { 0818 std::stable_sort(leaveCandidates.begin(), leaveCandidates.end(), lessThan); 0819 Vertex leave = leaveCandidates.first(); 0820 toLeave << listPath(leave, v, path.predecessors); 0821 } 0822 0823 if (direction == ParentToChild) 0824 { 0825 return (fromRoot << v << toLeave); 0826 } 0827 else 0828 { 0829 return (toLeave << v << fromRoot); 0830 } 0831 } 0832 0833 /** 0834 * Returns the shortestPath between id1 and id2. 0835 * If s2 is not reachable from s1, the path is searched from s2 to s1. 0836 * The returned list always starts with s1, contains the intermediate vertices, and ends with s2. 0837 * If no path is available, an empty list is returned. 0838 */ 0839 QList<Vertex> shortestPath(const Vertex& v1, const Vertex& v2) const 0840 { 0841 if (v1.isNull() || v2.isNull()) 0842 { 0843 return QList<Vertex>(); 0844 } 0845 0846 QList<Vertex> verticesLst; 0847 0848 Path path; 0849 path.shortestPath(graph, v1); 0850 0851 if (path.isReachable(v2)) 0852 { 0853 verticesLst = listPath(v2, v1, path.predecessors, ChildToParent); 0854 verticesLst.prepend(v1); 0855 } 0856 else 0857 { 0858 // assume inverted parameters 0859 0860 path.shortestPath(graph, v2); 0861 0862 if (path.isReachable(v1)) 0863 { 0864 verticesLst = listPath(v1, v2, path.predecessors); 0865 verticesLst.append(v2); 0866 } 0867 } 0868 0869 return verticesLst; 0870 } 0871 0872 /** 0873 * Returns the shortest distances from Vertex to all vertices in the graph. 0874 * If the value is -1, a vertex is not reachable from v. 0875 */ 0876 QMap<Vertex, int> shortestDistancesFrom(const Vertex& v) const 0877 { 0878 Path path; 0879 0880 if (direction == ParentToChild) 0881 { 0882 path.shortestPath(graph, v); 0883 } 0884 else 0885 { 0886 path.shortestPath(boost::make_reverse_graph(graph), v); 0887 } 0888 0889 // Change 2147483647 to -1 0890 0891 typename QMap<Vertex, int>::iterator it; 0892 0893 for (it = path.distances.begin() ; it != path.distances.end() ; ++it) 0894 { 0895 if (it.value() == std::numeric_limits<int>::max()) 0896 { 0897 it.value() = -1; 0898 } 0899 } 0900 0901 return path.distances; 0902 } 0903 0904 enum ReturnOrder 0905 { 0906 BreadthFirstOrder, 0907 DepthFirstOrder 0908 }; 0909 0910 /** 0911 * For a vertex v reachable from a vertex root, 0912 * returns, in depth-first or breadth-first order, all vertices dominated by v 0913 * starting from root. 0914 */ 0915 QList<Vertex> verticesDominatedBy(const Vertex& v, 0916 const Vertex& root, 0917 ReturnOrder order = BreadthFirstOrder) const 0918 { 0919 if (v.isNull() || isEmpty()) 0920 { 0921 return QList<Vertex>(); 0922 } 0923 0924 GraphSearch search; 0925 0926 if (order == BreadthFirstOrder) 0927 { 0928 search.breadthFirstSearch(graph, root, (direction == ChildToParent)); 0929 } 0930 else 0931 { 0932 search.depthFirstSearch(graph, root, (direction == ChildToParent)); 0933 } 0934 0935 return verticesDominatedBy(v, root, search.vertices); 0936 } 0937 0938 /** 0939 * For a vertex v reachable from a vertex root all vertices dominated by v starting from root. 0940 * The returned list is in depth-first order, using root as starting point, and 0941 * when discovering a vertex, sorting the adjacent vertices with the given lessThan. 0942 */ 0943 template <typename LessThan> 0944 QList<Vertex> verticesDominatedByDepthFirstSorted(const Vertex& v, 0945 const Vertex& root, 0946 LessThan lessThan) const 0947 { 0948 return verticesDominatedBy(v, root, verticesDepthFirstSorted(root, lessThan)); 0949 } 0950 0951 /** 0952 * For a vertex v reachable from a vertex root returns 0953 * all vertices dominated by v starting from root. 0954 * The order is the same as in the given, sorted list of all vertices in this graph 0955 * (or all vertices expected to be returned. The returned list is the intersection 0956 * of the dominated vertices and presortedVertices, in order of presortedVertices) 0957 */ 0958 QList<Vertex> verticesDominatedBy(const Vertex& v, 0959 const Vertex& root, 0960 const QList<Vertex>& presortedVertices) const 0961 { 0962 if (v.isNull() || isEmpty()) 0963 { 0964 return QList<Vertex>(); 0965 } 0966 0967 DominatorTree tree; 0968 tree.enter(graph, root, direction); 0969 0970 QList<Vertex> dominatedTree = treeFromPredecessors(v, tree.predecessors); 0971 0972 /// remove all vertices from the DFS of v that are not in the dominated tree 0973 0974 QList<Vertex> orderedTree; 0975 0976 Q_FOREACH (const Vertex& vv, presortedVertices) 0977 { 0978 if (dominatedTree.contains(vv)) 0979 { 0980 orderedTree << vv; 0981 } 0982 } 0983 0984 return orderedTree; 0985 } 0986 0987 /** 0988 * Orders all vertices of the graph in a breadth-first manner. 0989 * A single vertex is taken as reference to distinguish main root and side paths. 0990 * Otherwise the first root is taken as reference. 0991 */ 0992 QList<Vertex> verticesBreadthFirst(const Vertex& givenRef = Vertex()) const 0993 { 0994 if (isEmpty()) 0995 { 0996 return QList<Vertex>(); 0997 } 0998 0999 Vertex ref(givenRef); 1000 1001 if (ref.isNull()) 1002 { 1003 ref = roots().first(); 1004 } 1005 1006 QList<Vertex> verticesLst; 1007 verticesLst << rootsOf(ref); 1008 1009 if (verticesLst.size() == vertexCount()) 1010 { 1011 return verticesLst; 1012 } 1013 1014 GraphSearch search; 1015 search.breadthFirstSearch(graph, verticesLst.first(), direction == ChildToParent); 1016 QList<Vertex> bfs = search.verticesLst; 1017 1018 Q_FOREACH (const Vertex& v, verticesLst) 1019 { 1020 bfs.removeOne(v); 1021 } 1022 1023 verticesLst << bfs; 1024 1025 if (verticesLst.size() == vertexCount()) 1026 { 1027 return verticesLst; 1028 } 1029 1030 // Sort in any so far unreachable nodes 1031 1032 vertex_range_t range = boost::vertices(graph); 1033 1034 for (vertex_iter it = range.first ; it != range.second ; ++it) 1035 { 1036 if (!verticesLst.contains(*it)) 1037 { 1038 GraphSearch childSearch; 1039 childSearch.breadthFirstSearch(graph, *it, direction == ChildToParent); 1040 QList<Vertex> childBfs = childSearch.vertices; 1041 QList<Vertex> toInsert; 1042 1043 // Any item reachable from *it should come after it 1044 1045 int minIndex = verticesLst.size(); 1046 1047 Q_FOREACH (const Vertex& c, childBfs) 1048 { 1049 int foundAt = verticesLst.indexOf(c); 1050 1051 if (foundAt == -1) 1052 { 1053 toInsert << c; 1054 } 1055 else 1056 { 1057 minIndex = qMin(foundAt, minIndex); 1058 } 1059 } 1060 1061 Q_FOREACH (const Vertex& c, toInsert) 1062 { 1063 verticesLst.insert(minIndex++, c); 1064 } 1065 } 1066 } 1067 1068 return verticesLst; 1069 } 1070 1071 /** 1072 * Orders all vertices of the graph in a depth-first manner. 1073 * When discovering a vertex, the adjacent vertices are sorted with the given lessThan. 1074 * A single vertex is taken as starting point. 1075 * If null, the first root is taken as reference. 1076 */ 1077 template <typename LessThan> 1078 QList<Vertex> verticesDepthFirstSorted(const Vertex& givenRef, LessThan lessThan) const 1079 { 1080 if (isEmpty()) 1081 { 1082 return QList<Vertex>(); 1083 } 1084 1085 Vertex ref(givenRef); 1086 1087 if (ref.isNull()) 1088 { 1089 ref = roots().first(); 1090 } 1091 1092 QList<Vertex> verticesLst; 1093 verticesLst = rootsOf(ref); 1094 1095 if ((verticesLst.size() == vertexCount()) || verticesLst.isEmpty()) 1096 { 1097 return verticesLst; 1098 } 1099 1100 GraphSearch search; 1101 search.depthFirstSearchSorted(graph, verticesLst.first(), direction == ChildToParent, lessThan); 1102 QList<Vertex> dfs = search.vertices; 1103 1104 Q_FOREACH (const Vertex& v, verticesLst) 1105 { 1106 dfs.removeOne(v); 1107 } 1108 1109 verticesLst << dfs; 1110 1111 return search.vertices; 1112 } 1113 1114 protected: 1115 1116 QList<Vertex> treeFromPredecessors(const Vertex& v, const VertexVertexMap& predecessors) const 1117 { 1118 QList<Vertex> verticesLst; 1119 verticesLst << v; 1120 treeFromPredecessorsRecursive(v, verticesLst, predecessors); 1121 1122 return verticesLst; 1123 } 1124 1125 void treeFromPredecessorsRecursive(const Vertex& v, 1126 QList<Vertex>& vertices, 1127 const VertexVertexMap& predecessors) const 1128 { 1129 QList<Vertex> children = predecessors.keys(v); 1130 vertices << children; 1131 1132 Q_FOREACH (const Vertex& child, children) 1133 { 1134 treeFromPredecessorsRecursive(child, vertices, predecessors); 1135 } 1136 } 1137 1138 /** 1139 * Returns a list of vertex ids of vertices in the given range 1140 */ 1141 template <typename Value, typename range_t> 1142 static QList<Value> toList(const range_t& range) 1143 { 1144 typedef typename range_t::first_type iterator_t; 1145 QList<Value> list; 1146 1147 for (iterator_t it = range.first ; it != range.second ; ++it) 1148 { 1149 list << *it; 1150 } 1151 1152 return list; 1153 } 1154 1155 template <typename range_t> static QList<Vertex> toVertexList(const range_t& range) 1156 { 1157 return toList<Vertex, range_t>(range); 1158 } 1159 1160 template <typename range_t> static QList<Edge> toEdgeList(const range_t& range) 1161 { 1162 return toList<Edge, range_t>(range); 1163 } 1164 1165 template <typename range_t> 1166 static bool isEmptyRange(const range_t& range) 1167 { 1168 return (range.first == range.second); 1169 } 1170 1171 /** 1172 * According to the given flags and based on the map, 1173 * copies vertex and edge properties from this to the other graph 1174 */ 1175 void copyProperties(Graph& other, GraphCopyFlags flags, const std::vector<vertex_t>& copiedVertices) const 1176 { 1177 other.direction = direction; 1178 1179 if (flags & CopyVertexProperties) 1180 { 1181 vertex_index_map_t indexMap = boost::get(boost::vertex_index, graph); 1182 vertex_range_t range = boost::vertices(graph); 1183 1184 for (vertex_iter it = range.first ; it != range.second ; ++it) 1185 { 1186 Vertex copiedVertex = copiedVertices[boost::get(indexMap, *it)]; 1187 1188 if (copiedVertex.isNull()) 1189 { 1190 continue; 1191 } 1192 1193 other.setProperties(copiedVertex, properties(*it)); 1194 } 1195 } 1196 1197 if (flags & CopyEdgeProperties) 1198 { 1199 vertex_index_map_t indexMap = boost::get(boost::vertex_index, graph); 1200 edge_range_t range = boost::edges(graph); 1201 1202 for (edge_iter it = range.first ; it != range.second ; ++it) 1203 { 1204 Vertex s = boost::source(*it, graph); 1205 Vertex t = boost::target(*it, graph); 1206 Vertex copiedS = copiedVertices[boost::get(indexMap, s)]; 1207 Vertex copiedT = copiedVertices[boost::get(indexMap, t)]; 1208 1209 if (copiedS.isNull() || copiedT.isNull()) 1210 { 1211 continue; 1212 } 1213 1214 Edge copiedEdge = other.edge(copiedS, copiedT); 1215 1216 if (!copiedEdge.isNull()) 1217 { 1218 other.setProperties(copiedEdge, properties(s, t)); 1219 } 1220 } 1221 } 1222 } 1223 1224 /** 1225 * Returns a list of edges of this graph that have been removed in other. 1226 * copiedVertices maps the vertices of this graph to other. 1227 */ 1228 QList<Edge> edgeDifference(const Graph& other, const std::vector<vertex_t>& copiedVertices) const 1229 { 1230 QList<Edge> removed; 1231 vertex_index_map_t indexMap = boost::get(boost::vertex_index, graph); 1232 edge_range_t range = boost::edges(graph); 1233 1234 for (edge_iter it = range.first ; it != range.second ; ++it) 1235 { 1236 Vertex s = boost::source(*it, graph); 1237 Vertex t = boost::target(*it, graph); 1238 Vertex copiedS = copiedVertices[boost::get(indexMap, s)]; 1239 Vertex copiedT = copiedVertices[boost::get(indexMap, t)]; 1240 1241 if (copiedS.isNull() || copiedT.isNull()) 1242 { 1243 continue; 1244 } 1245 1246 Edge copiedEdge = other.edge(copiedS, copiedT); 1247 1248 if (copiedEdge.isNull()) 1249 { 1250 removed << *it; 1251 } 1252 } 1253 1254 return removed; 1255 } 1256 1257 /** 1258 * Finds vertex ids of all vertices with zero in- our out-degree. 1259 */ 1260 QList<Vertex> findZeroDegree(bool inOrOut) const 1261 { 1262 QList<Vertex> verticesLst; 1263 vertex_range_t range = boost::vertices(graph); 1264 1265 for (vertex_iter it = range.first ; it != range.second ; ++it) 1266 { 1267 if ((inOrOut ? in_degree(*it, graph) 1268 : out_degree(*it, graph)) == 0) 1269 { 1270 verticesLst << *it; 1271 } 1272 } 1273 1274 return verticesLst; 1275 } 1276 1277 QList<Vertex> findZeroDegreeFrom(const Vertex& v, bool inOrOut) const 1278 { 1279 bool invertGraph = (direction == ChildToParent); 1280 1281 if (!inOrOut) 1282 { 1283 invertGraph = !invertGraph; 1284 } 1285 1286 GraphSearch search; 1287 search.breadthFirstSearch(graph, v, invertGraph); 1288 1289 QList<Vertex> verticesLst; 1290 1291 Q_FOREACH (const Vertex& candidate, search.vertices) 1292 { 1293 if ((inOrOut ? in_degree(candidate, graph) 1294 : out_degree(candidate, graph)) == 0) 1295 { 1296 verticesLst << candidate; 1297 } 1298 } 1299 1300 return verticesLst; 1301 } 1302 1303 /** 1304 * Helper class to find paths through the graph. 1305 * Call one of the methods and then read the maps. 1306 */ 1307 class Path 1308 { 1309 public: 1310 1311 template <class GraphType> 1312 void shortestPath(const GraphType& graph, const Vertex& v) 1313 { 1314 int weight = 1; 1315 1316 try 1317 { 1318 boost::dag_shortest_paths(graph, v, 1319 /// we provide a constant weight of 1 1320 weight_map(boost::ref_property_map<typename boost::graph_traits<GraphType>::edge_descriptor,int>(weight)). 1321 1322 /// Store distance and predecessors in QMaps, wrapped to serve as property maps 1323 distance_map(VertexIntMapAdaptor(distances)). 1324 predecessor_map(VertexVertexMapAdaptor(predecessors)) 1325 ); 1326 } 1327 catch (boost::bad_graph& e) 1328 { 1329 qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); 1330 } 1331 } 1332 1333 template <class GraphType> 1334 void longestPath(const GraphType& graph, const Vertex& v) 1335 { 1336 int weight = 1; 1337 1338 try 1339 { 1340 boost::dag_shortest_paths(graph, v, 1341 /// we provide a constant weight of 1 1342 weight_map(boost::ref_property_map<typename boost::graph_traits<GraphType>::edge_descriptor,int>(weight)). 1343 1344 /// Invert the default compare method: With greater, we get the longest path 1345 distance_compare(std::greater<int>()). 1346 1347 /// will be returned if a node is unreachable 1348 distance_inf(-1). 1349 1350 /// Store distance and predecessors in QMaps, wrapped to serve as property maps 1351 distance_map(VertexIntMapAdaptor(distances)). 1352 predecessor_map(VertexVertexMapAdaptor(predecessors)) 1353 ); 1354 } 1355 catch (boost::bad_graph& e) 1356 { 1357 qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); 1358 } 1359 } 1360 1361 bool isReachable(const Vertex& v) const 1362 { 1363 return (predecessors.value(v, v) != v); 1364 } 1365 1366 VertexVertexMap predecessors; 1367 VertexIntMap distances; 1368 }; 1369 1370 class DominatorTree 1371 { 1372 public: 1373 1374 template <class GraphType> 1375 void enter(const GraphType& graph, const Vertex& v, MeaningOfDirection direction = ParentToChild) 1376 { 1377 try 1378 { 1379 if (direction == ParentToChild) 1380 { 1381 boost::lengauer_tarjan_dominator_tree(graph, v, VertexVertexMapAdaptor(predecessors)); 1382 } 1383 else 1384 { 1385 boost::lengauer_tarjan_dominator_tree(boost::make_reverse_graph(graph), v, 1386 VertexVertexMapAdaptor(predecessors)); 1387 } 1388 } 1389 catch (boost::bad_graph& e) 1390 { 1391 qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); 1392 } 1393 } 1394 1395 VertexVertexMap predecessors; 1396 }; 1397 1398 class GraphSearch 1399 { 1400 public: 1401 1402 template <class GraphType> 1403 void depthFirstSearch(const GraphType& graph, const Vertex& v, bool invertGraph) 1404 { 1405 // remember that the visitor is passed by value 1406 1407 DepthFirstSearchVisitor vis(this); 1408 1409 try 1410 { 1411 if (invertGraph) 1412 { 1413 boost::depth_first_search(boost::make_reverse_graph(graph), visitor(vis).root_vertex(v)); 1414 } 1415 else 1416 { 1417 boost::depth_first_search(graph, visitor(vis).root_vertex(v)); 1418 } 1419 } 1420 catch (boost::bad_graph& e) 1421 { 1422 qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); 1423 } 1424 } 1425 1426 template <class GraphType, typename LessThan> 1427 void depthFirstSearchSorted(const GraphType& graph, const Vertex& v, bool invertGraph, LessThan lessThan) 1428 { 1429 // Remember that the visitor is passed by value 1430 1431 DepthFirstSearchVisitor vis(this); 1432 std::vector<boost::default_color_type> color_vec(boost::num_vertices(graph), boost::white_color); 1433 1434 try 1435 { 1436 if (invertGraph) 1437 { 1438 depth_first_search_sorted(boost::make_reverse_graph(graph), v, vis, 1439 make_iterator_property_map(color_vec.begin(), get(boost::vertex_index, graph)), lessThan); 1440 } 1441 else 1442 { 1443 depth_first_search_sorted(graph, v, vis, 1444 make_iterator_property_map(color_vec.begin(), get(boost::vertex_index, graph)), lessThan); 1445 } 1446 } 1447 catch (boost::bad_graph& e) 1448 { 1449 qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); 1450 } 1451 } 1452 1453 template <class GraphType> 1454 void breadthFirstSearch(const GraphType& graph, const Vertex& v, bool invertGraph) 1455 { 1456 BreadthFirstSearchVisitor vis(this); 1457 1458 try 1459 { 1460 if (invertGraph) 1461 { 1462 boost::breadth_first_search(boost::make_reverse_graph(graph), v, visitor(vis)); 1463 } 1464 else 1465 { 1466 boost::breadth_first_search(graph, v, visitor(vis)); 1467 } 1468 } 1469 catch (boost::bad_graph& e) 1470 { 1471 qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); 1472 } 1473 } 1474 1475 class CommonVisitor 1476 { 1477 protected: 1478 1479 explicit CommonVisitor(GraphSearch* const q) 1480 : q(q) 1481 { 1482 } 1483 1484 void record(const Vertex& v) const 1485 { 1486 q->vertices << v; 1487 } 1488 1489 GraphSearch* const q; 1490 }; 1491 1492 class DepthFirstSearchVisitor : public boost::default_dfs_visitor, 1493 public CommonVisitor 1494 { 1495 public: 1496 1497 explicit DepthFirstSearchVisitor(GraphSearch* const q) 1498 : CommonVisitor(q) 1499 { 1500 } 1501 1502 template <typename VertexType, typename GraphType> 1503 void discover_vertex(VertexType u, const GraphType&) const 1504 { 1505 this->record(u); 1506 } 1507 }; 1508 1509 class BreadthFirstSearchVisitor : public boost::default_bfs_visitor, 1510 public CommonVisitor 1511 { 1512 public: 1513 1514 explicit BreadthFirstSearchVisitor(GraphSearch* const q) 1515 : CommonVisitor(q) 1516 { 1517 } 1518 1519 template <typename VertexType, typename GraphType> 1520 void discover_vertex(VertexType u, const GraphType&) const 1521 { 1522 this->record(u); 1523 } 1524 }; 1525 1526 QList<Vertex> vertices; 1527 1528 protected: 1529 1530 template <class GraphType, typename VertexLessThan> 1531 class lessThanMapEdgeToTarget 1532 { 1533 typedef typename boost::graph_traits<GraphType>::edge_descriptor edge_descriptor; 1534 1535 public: 1536 1537 lessThanMapEdgeToTarget(const GraphType& g, VertexLessThan vertexLessThan) 1538 : g (g), 1539 vertexLessThan(vertexLessThan) 1540 { 1541 } 1542 1543 bool operator()(const edge_descriptor& a, const edge_descriptor& b) 1544 { 1545 return vertexLessThan(boost::target(a, g), boost::target(b, g)); 1546 } 1547 1548 public: 1549 1550 const GraphType& g; 1551 VertexLessThan vertexLessThan; 1552 }; 1553 1554 /// This is boost's simple, old, recursive DFS algorithm adapted with lessThan 1555 template <class IncidenceGraph, class DFSVisitor, class ColorMap, typename LessThan> 1556 void depth_first_search_sorted(const IncidenceGraph& g, 1557 Vertex u, 1558 DFSVisitor& vis, 1559 ColorMap color, 1560 LessThan lessThan) 1561 { 1562 //typedef std::pair<Vertex, QList<Edge> > VertexInfo; 1563 1564 typedef typename boost::graph_traits<IncidenceGraph>::edge_descriptor edge_descriptor; 1565 QList<edge_descriptor> outEdges; 1566 /* 1567 std::vector<VertexInfo> stack; 1568 */ 1569 boost::put(color, u, boost::gray_color); 1570 vis.discover_vertex(u, g); 1571 1572 outEdges = toList<edge_descriptor>(boost::out_edges(u, g)); 1573 1574 /** 1575 * Sort edges. The lessThan we have takes vertices, so we use a lessThan which 1576 * maps the given edges to their targets, and calls our vertex lessThan. 1577 */ 1578 std::sort(outEdges.begin(), 1579 outEdges.end(), 1580 lessThanMapEdgeToTarget<IncidenceGraph, LessThan>(g, lessThan)); 1581 1582 Q_FOREACH (const edge_descriptor& e, outEdges) 1583 { 1584 Vertex v = boost::target(e, g); 1585 vis.examine_edge(e, g); 1586 boost::default_color_type v_color = boost::get(color, v); 1587 1588 if (v_color == boost::white_color) 1589 { 1590 vis.tree_edge(e, g); 1591 depth_first_search_sorted(g, v, vis, color, lessThan); 1592 } 1593 else if (v_color == boost::gray_color) 1594 { 1595 vis.back_edge(e, g); 1596 } 1597 else 1598 { 1599 vis.forward_or_cross_edge(e, g); 1600 } 1601 } 1602 1603 put(color, u, boost::black_color); 1604 vis.finish_vertex(u, g); 1605 } 1606 }; 1607 1608 /** 1609 * Get the list of vertices with the largest value in the given distance map 1610 */ 1611 QList<Vertex> mostRemoteNodes(const VertexIntMap& distances) const 1612 { 1613 typename VertexIntMap::const_iterator it; 1614 int maxDist = 1; 1615 QList<Vertex> candidates; 1616 1617 for (it = distances.begin() ; it != distances.end() ; ++it) 1618 { 1619 if (it.value() > maxDist) 1620 { 1621 maxDist = it.value(); 1622 1623 //qDebug() << "Increasing maxDist to" << maxDist; 1624 1625 candidates.clear(); 1626 } 1627 1628 if (it.value() >= maxDist) 1629 { 1630 //qDebug() << "Adding candidate" << id(it.key()) << "at distance" << maxDist; 1631 1632 candidates << it.key(); 1633 } 1634 1635 /* 1636 if (it.value() == -1) 1637 { 1638 qDebug() << id(it.key()) << "unreachable"; 1639 } 1640 else 1641 { 1642 qDebug() << "Distance to" << id(it.key()) << "is" << it.value(); 1643 } 1644 */ 1645 } 1646 1647 return candidates; 1648 } 1649 1650 /** 1651 * Get a list of vertex ids for the path from root to target, using the given predecessors. 1652 * Depending on MeaningOfDirection, the ids are listed inverted, from target to root. 1653 */ 1654 QList<Vertex> listPath(const Vertex& root, 1655 const Vertex& target, 1656 const VertexVertexMap& predecessors, 1657 MeaningOfDirection dir = ParentToChild) const 1658 { 1659 QList<Vertex> verticesLst; 1660 1661 for (Vertex v = root ; v != target ; v = predecessors.value(v)) 1662 { 1663 //qDebug() << "Adding waypoint" << id(v); 1664 1665 if (dir == ParentToChild) 1666 { 1667 verticesLst.append(v); 1668 } 1669 else 1670 { 1671 verticesLst.prepend(v); 1672 } 1673 1674 // If a node is not reachable, it seems its entry in the predecessors map is itself 1675 // Avoid endless loop 1676 1677 if (predecessors.value(v) == v) 1678 { 1679 break; 1680 } 1681 } 1682 1683 return verticesLst; 1684 } 1685 1686 protected: 1687 1688 GraphContainer graph; 1689 MeaningOfDirection direction; 1690 }; 1691 1692 } // namespace Digikam 1693 1694 // Restore warnings 1695 #if !defined(Q_OS_DARWIN) && defined(Q_CC_GNU) 1696 # pragma GCC diagnostic pop 1697 #endif 1698 1699 #if defined(Q_CC_CLANG) 1700 # pragma clang diagnostic pop 1701 #endif 1702 1703 #endif // DIGIKAM_ITEM_HISTORY_GRAPH_BOOST_H