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