diff --git a/core/libs/database/history/itemhistorygraph.cpp b/core/libs/database/history/itemhistorygraph.cpp index bda45d318b..686de7e153 100644 --- a/core/libs/database/history/itemhistorygraph.cpp +++ b/core/libs/database/history/itemhistorygraph.cpp @@ -1,899 +1,899 @@ /* ============================================================ * * This file is a part of digiKam project * https://www.digikam.org * * Date : 2010-10-23 * Description : Graph data class for image history * * Copyright (C) 2010-2011 by Marcel Wiesweg * * This program is free software; you can redistribute it * and/or modify it under the terms of the GNU General * Public License as published by the Free Software Foundation; * either version 2, or (at your option) * any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * ============================================================ */ #include "itemhistorygraph.h" // Local includes #include "digikam_debug.h" #include "dimagehistory.h" #include "itemscanner.h" #include "itemhistorygraphdata.h" namespace Digikam { class Q_DECL_HIDDEN ItemHistoryGraphDataSharedNull : public QSharedDataPointer { public: ItemHistoryGraphDataSharedNull() : QSharedDataPointer(new ItemHistoryGraphData) { } }; Q_GLOBAL_STATIC(ItemHistoryGraphDataSharedNull, imageHistoryGraphDataSharedNull) // ----------------------------------------------------------------------------------------------- ItemInfo HistoryVertexProperties::firstItemInfo() const { if (infos.isEmpty()) { return ItemInfo(); } return infos.first(); } bool HistoryVertexProperties::markedAs(HistoryImageId::Type type) const { if (referredImages.isEmpty()) { return false; } foreach (const HistoryImageId& ref, referredImages) { if (ref.m_type == type) { return true; } } return false; } bool HistoryVertexProperties::alwaysMarkedAs(HistoryImageId::Type type) const { if (referredImages.isEmpty()) { return false; } foreach (const HistoryImageId& ref, referredImages) { if (ref.m_type != type) { return false; } } return true; } bool HistoryVertexProperties::operator==(const QString& id) const { return uuid == id; } bool HistoryVertexProperties::operator==(const ItemInfo& info) const { return infos.contains(info); } bool HistoryVertexProperties::operator==(qlonglong id) const { foreach (const ItemInfo& info, infos) { if (info.id() == id) { return true; } } return false; } bool HistoryVertexProperties::operator==(const HistoryImageId& other) const { if (!uuid.isEmpty() && !other.m_uuid.isEmpty()) { return (uuid == other.m_uuid); } foreach (const HistoryImageId& id, referredImages) { if (ItemScanner::sameReferredImage(id, other)) { //qCDebug(DIGIKAM_DATABASE_LOG) << id << "is the same as" << other; return true; } } return false; } HistoryVertexProperties& HistoryVertexProperties::operator+=(const QString& id) { if (!uuid.isNull() && id.isNull()) { uuid = id; } return *this; } HistoryVertexProperties& HistoryVertexProperties::operator+=(const ItemInfo& info) { if (!info.isNull() && !infos.contains(info)) { infos << info; if (uuid.isNull()) { uuid = info.uuid(); } } return *this; } HistoryVertexProperties& HistoryVertexProperties::operator+=(const HistoryImageId& id) { if (id.isValid() && !referredImages.contains(id)) { referredImages << id; if (uuid.isNull() && !id.m_uuid.isEmpty()) { uuid = id.m_uuid; } } return *this; } QDebug operator<<(QDebug dbg, const HistoryVertexProperties& props) { foreach (const ItemInfo& info, props.infos) { dbg.space() << info.id(); } return dbg; } QDebug operator<<(QDebug dbg, const HistoryImageId& id) { dbg.nospace() << " { "; dbg.nospace() << id.m_uuid; dbg.space() << id.m_type; dbg.space() << id.m_fileName; dbg.space() << id.m_filePath; dbg.space() << id.m_creationDate; dbg.space() << id.m_uniqueHash; dbg.space() << id.m_fileSize; dbg.space() << id.m_originalUUID; dbg.nospace() << " } "; return dbg; } // ----------------------------------------------------------------------------------------------- HistoryEdgeProperties& HistoryEdgeProperties::operator+=(const FilterAction& action) { actions << action; return *this; } // ----------------------------------------------------------------------------------------------- HistoryGraph::Vertex ItemHistoryGraphData::addVertex(const QList& imageIds) { if (imageIds.isEmpty()) { return Vertex(); } Vertex v = addVertex(imageIds.first()); if (imageIds.size() > 1) { applyProperties(v, QList(), imageIds); } return v; } HistoryGraph::Vertex ItemHistoryGraphData::addVertex(const HistoryImageId& imageId) { if (!imageId.isValid()) { return Vertex(); } Vertex v; QList infos; //qCDebug(DIGIKAM_DATABASE_LOG) << "Adding vertex" << imageId.m_uuid.left(6) << imageId.fileName(); // find by HistoryImageId (most notably, by UUID) v = findVertexByProperties(imageId); //qCDebug(DIGIKAM_DATABASE_LOG) << "Found by properties:" << (v.isNull() ? -1 : int(v)); if (v.isNull()) { // Resolve HistoryImageId, find by ItemInfo foreach (const qlonglong& id, ItemScanner::resolveHistoryImageId(imageId)) { ItemInfo info(id); //qCDebug(DIGIKAM_DATABASE_LOG) << "Found info id:" << info.id(); infos << info; v = findVertexByProperties(info); } } applyProperties(v, infos, QList() << imageId); //qCDebug(DIGIKAM_DATABASE_LOG) << "Returning vertex" << v; return v; } HistoryGraph::Vertex ItemHistoryGraphData::addVertex(qlonglong id) { return addVertex(ItemInfo(id)); } HistoryGraph::Vertex ItemHistoryGraphData::addVertex(const ItemInfo& info) { Vertex v; QString uuid; HistoryImageId id; // Simply find by image id v = findVertexByProperties(info); //qCDebug(DIGIKAM_DATABASE_LOG) << "Find by id" << info.id() << ": found" << v.isNull(); if (v.isNull()) { // Find by contents uuid = info.uuid(); if (!uuid.isNull()) { v = findVertexByProperties(uuid); } //qCDebug(DIGIKAM_DATABASE_LOG) << "Find by uuid" << uuid << ": found" << v.isNull(); if (v.isNull()) { id = info.historyImageId(); v = findVertexByProperties(id); //qCDebug(DIGIKAM_DATABASE_LOG) << "Find by h-i-m" << ": found" << v.isNull(); } // Need to add new vertex. Do this through the method which will resolve the history id if (v.isNull()) { v = addVertex(id); } } applyProperties(v, QList() << info, QList() << id); //qCDebug(DIGIKAM_DATABASE_LOG) << "Returning vertex" << v << properties(v).infos.size(); return v; } HistoryGraph::Vertex ItemHistoryGraphData::addVertexScanned(qlonglong id) { // short version where we do not read information about id from an ItemInfo Vertex v = findVertexByProperties(id); applyProperties(v, QList() << ItemInfo(id), QList()); return v; } void ItemHistoryGraphData::applyProperties(Vertex& v, const QList& infos, const QList& ids) { // if needed, add a new vertex; or retrieve properties to add possibly new entries if (v.isNull()) { v = HistoryGraph::addVertex(); } HistoryVertexProperties& props = properties(v); // adjust properties foreach (const ItemInfo& info, infos) { props += info; } foreach (const HistoryImageId& id, ids) { props += id; } } int ItemHistoryGraphData::removeNextUnresolvedVertex(int index) { QList vs = vertices(); for ( ; index < vs.size() ; ++index) { Vertex& v = vs[index]; const HistoryVertexProperties& props = properties(v); if (props.infos.isEmpty()) { foreach (const HistoryGraph::Edge& upperEdge, edges(v, HistoryGraph::EdgesToRoot)) { foreach (const HistoryGraph::Edge& lowerEdge, edges(v, HistoryGraph::EdgesToLeaf)) { HistoryEdgeProperties combinedProps; combinedProps.actions += properties(upperEdge).actions; combinedProps.actions += properties(lowerEdge).actions; HistoryGraph::Edge connection = addEdge(source(lowerEdge), target(upperEdge)); setProperties(connection, combinedProps); } } remove(v); return index; } } return index; } QHash ItemHistoryGraphData::categorize() const { QHash types; foreach (const Vertex& v, vertices()) { const HistoryVertexProperties& props = properties(v); HistoryImageId::Types type; if (props.alwaysMarkedAs(HistoryImageId::Source)) { type |= HistoryImageId::Source; } else if (isLeaf(v)) { // Leaf: Assume current version type |= HistoryImageId::Current; } else if (isRoot(v)) { // Root: Assume original if at least once marked as such if (props.markedAs(HistoryImageId::Original)) { type |= HistoryImageId::Original; } } else { type = HistoryImageId::Intermediate; } /* * There is one situation which cannot be deduced from the graph structure: * When there is a derived image, but the parent image shall be kept as visible "Current". * In this case, the ExplicitBranch flag can be set on the next action. */ if (!(type & HistoryImageId::Current) && hasEdges(v, EdgesToLeaf)) { // We check if all immediate actions set the ExplicitBranch flag bool allBranches = true; foreach (const Edge& e, edges(v, EdgesToLeaf)) { - const HistoryEdgeProperties& props = properties(e); + const HistoryEdgeProperties& props2 = properties(e); - if (props.actions.isEmpty()) + if (props2.actions.isEmpty()) { continue; // unclear situation, ignore } - if (!(props.actions.first().flags() & FilterAction::ExplicitBranch)) + if (!(props2.actions.first().flags() & FilterAction::ExplicitBranch)) { allBranches = false; break; } } if (allBranches) { type |= HistoryImageId::Current; } } types[v] = type; } return types; } // ----------------------------------------------------------------------------------------------- ItemHistoryGraph::ItemHistoryGraph() : d(*imageHistoryGraphDataSharedNull) { } ItemHistoryGraph::ItemHistoryGraph(const ItemHistoryGraph& other) : d(other.d) { } ItemHistoryGraph::~ItemHistoryGraph() { } ItemHistoryGraph& ItemHistoryGraph::operator=(const ItemHistoryGraph& other) { d = other.d; return *this; } bool ItemHistoryGraph::isNull() const { return (d == *imageHistoryGraphDataSharedNull); } bool ItemHistoryGraph::isEmpty() const { return d->isEmpty(); } bool ItemHistoryGraph::isSingleVertex() const { return (d->vertexCount() == 1); } bool ItemHistoryGraph::hasEdges() const { return d->hasEdges(); } ItemHistoryGraphData& ItemHistoryGraph::data() { return *d; } const ItemHistoryGraphData& ItemHistoryGraph::data() const { return *d; } void ItemHistoryGraph::clear() { *d = HistoryGraph(); } ItemHistoryGraph ItemHistoryGraph::fromInfo(const ItemInfo& info, HistoryLoadingMode loadingMode, ProcessingMode processingMode) { ItemHistoryGraph graph; if (loadingMode & LoadRelationCloud) { graph.addRelations(info.relationCloud()); } if (loadingMode & LoadSubjectHistory) { graph.addHistory(info.imageHistory(), info); } if (loadingMode & LoadLeavesHistory) { foreach (const ItemInfo& leaf, graph.leafImages()) { if (leaf != info) { graph.addHistory(leaf.imageHistory(), leaf); } } } if (processingMode == PrepareForDisplay) { graph.prepareForDisplay(info); } return graph; } void ItemHistoryGraph::addHistory(const DImageHistory& givenHistory, const ItemInfo& historySubject) { addHistory(givenHistory, historySubject.historyImageId()); } void ItemHistoryGraph::addHistory(const DImageHistory& givenHistory, const HistoryImageId& subjectId) { // append the subject to its history DImageHistory history = givenHistory; if (subjectId.isValid()) { history << subjectId; } d->addHistory(history); } void ItemHistoryGraph::addScannedHistory(const DImageHistory& history, qlonglong historySubjectId) { d->addHistory(history, historySubjectId); } void ItemHistoryGraphData::addHistory(const DImageHistory& history, qlonglong extraCurrent) { if (history.isEmpty()) { return; } HistoryGraph::Vertex last; HistoryEdgeProperties edgeProps; foreach (const DImageHistory::Entry& entry, history.entries()) { if (!last.isNull()) { edgeProps += entry.action; } HistoryGraph::Vertex v; if (!entry.referredImages.isEmpty()) { v = addVertex(entry.referredImages); } if (!v.isNull()) { if (!last.isNull()) { if (v != last) { HistoryGraph::Edge e = addEdge(v, last); setProperties(e, edgeProps); edgeProps = HistoryEdgeProperties(); } else { qCWarning(DIGIKAM_DATABASE_LOG) << "Broken history: Same file referred by different entries. Refusing to add a loop."; } } last = v; } } if (extraCurrent) { HistoryGraph::Vertex v = addVertexScanned(extraCurrent); if (!v.isNull() && !last.isNull() && (v != last)) { HistoryGraph::Edge e = addEdge(v, last); setProperties(e, edgeProps); } } } void ItemHistoryGraph::addRelations(const QList >& pairs) { HistoryGraph::Vertex v1, v2; typedef QPair IdPair; foreach (const IdPair& pair, pairs) { if ((pair.first < 1) || (pair.second < 1)) { continue; } if (pair.first == pair.second) { qCWarning(DIGIKAM_DATABASE_LOG) << "Broken relations cloud: Refusing to add a loop."; } v1 = d->addVertex(pair.first); v2 = d->addVertex(pair.second); //qCDebug(DIGIKAM_DATABASE_LOG) << "Adding" << v1 << "->" << v2; d->addEdge(v1, v2); } } void ItemHistoryGraph::reduceEdges() { if (d->vertexCount() <= 1) { return; } QList removedEgdes; HistoryGraph reduction = d->transitiveReduction(&removedEgdes); if (reduction.isEmpty()) { return; // reduction failed, not a DAG } foreach (const HistoryGraph::Edge& e, removedEgdes) { if (!d->properties(e).actions.isEmpty()) { // TODO: conflict resolution qCDebug(DIGIKAM_DATABASE_LOG) << "Conflicting history information: Edge removed by transitiveReduction is not empty."; } } *d = reduction; } bool ItemHistoryGraph::hasUnresolvedEntries() const { foreach (const HistoryGraph::Vertex& v, d->vertices()) { if (d->properties(v).infos.isEmpty()) { return true; } } return false; } void ItemHistoryGraph::dropUnresolvedEntries() { // Remove nodes which could not be resolved into image infos // The problem is that with each removable, the vertex list is invalidated, // so we cannot do one loop over d->vertices for (int i = 0 ; i < d->vertexCount() ; ) { i = d->removeNextUnresolvedVertex(i); } } void ItemHistoryGraph::sortForInfo(const ItemInfo& subject) { // Remove nodes which could not be resolved into image infos QList toRemove; foreach (const HistoryGraph::Vertex& v, d->vertices()) { HistoryVertexProperties& props = d->properties(v); ItemScanner::sortByProximity(props.infos, subject); } } void ItemHistoryGraph::prepareForDisplay(const ItemInfo& subject) { reduceEdges(); dropUnresolvedEntries(); sortForInfo(subject); } QList > ItemHistoryGraph::relationCloud() const { QList > pairs; ItemHistoryGraphData closure = ItemHistoryGraphData(d->transitiveClosure()); QList edges = closure.edgePairs(); foreach (const HistoryGraph::VertexPair& edge, edges) { foreach (const ItemInfo& source, closure.properties(edge.first).infos) { foreach (const ItemInfo& target, closure.properties(edge.second).infos) { pairs << QPair(source.id(), target.id()); } } } return pairs; } QPair, QList > ItemHistoryGraph::relationCloudParallel() const { QList subjects, objects; ItemHistoryGraphData closure = ItemHistoryGraphData(d->transitiveClosure()); QList edges = closure.edgePairs(); foreach (const HistoryGraph::VertexPair& edge, edges) { foreach (const ItemInfo& source, closure.properties(edge.first).infos) { foreach (const ItemInfo& target, closure.properties(edge.second).infos) { subjects << source.id(); objects << target.id(); } } } return qMakePair(subjects, objects); } QList ItemHistoryGraph::allImages() const { return d->toInfoList(d->vertices()); } QList ItemHistoryGraph::allImageIds() const { QList ids; foreach (const HistoryGraph::Vertex& v, d->vertices()) { foreach (const ItemInfo& info, d->properties(v).infos) { ids << info.id(); } } return ids; } QList ItemHistoryGraph::rootImages() const { return d->toInfoList(d->roots()); } QList ItemHistoryGraph::leafImages() const { return d->toInfoList(d->leaves()); } QHash ItemHistoryGraph::categorize() const { QHash vertexType = d->categorize(); QHash types; foreach (const HistoryGraph::Vertex& v, d->vertices()) { const HistoryVertexProperties& props = d->properties(v); if (props.infos.isEmpty()) { continue; } HistoryImageId::Types type = vertexType.value(v); foreach (const ItemInfo& info, props.infos) { types[info] = type; } } return types; } static QString toString(const HistoryVertexProperties& props) { QString s = QLatin1String("Ids: "); QStringList ids; foreach (const ItemInfo& info, props.infos) { ids << QString::number(info.id()); } if (props.uuid.isEmpty()) { if (ids.size() == 1) { return QLatin1String("Id: ") + ids.first(); } else { return QLatin1String("Ids: (") + ids.join(QLatin1String(",")) + QLatin1Char(')'); } } else { if (ids.size() == 1) { return QLatin1String("Id: ") + ids.first() + QLatin1String(" UUID: ") + props.uuid.left(6) + QLatin1String("..."); } else { return QLatin1String("Ids: (") + ids.join(QLatin1String(",")) + QLatin1String(") UUID: ") + props.uuid.left(6) + QLatin1String("..."); } } } QDebug operator<<(QDebug dbg, const ItemHistoryGraph& g) { if (g.data().isEmpty()) { dbg << "(Empty graph)"; return dbg; } QList vertices = g.data().topologicalSort(); if (vertices.isEmpty()) { vertices = g.data().vertices(); dbg << "Not-a-DAG-Graph with" << vertices.size() << "vertices:" << endl; } else { dbg << "Graph with" << vertices.size() << "vertices:" << endl; } foreach (const HistoryGraph::Vertex& target, vertices) { QString targetString = toString(g.data().properties(target)); QStringList sourceVertexTexts; foreach (const HistoryGraph::Vertex& source, g.data().adjacentVertices(target, HistoryGraph::InboundEdges)) { sourceVertexTexts << toString(g.data().properties(source)); } if (!sourceVertexTexts.isEmpty()) { dbg.nospace() << QLatin1String("{ ") + targetString + QLatin1String(" } ") + QLatin1String("-> { ") + sourceVertexTexts.join(QLatin1String(" }, { ")) + QLatin1String(" }") << endl; } else if (g.data().outDegree(target) == 0) { dbg.nospace() << QLatin1String("Unconnected: { ") + targetString + QLatin1String(" }") << endl; } } return dbg; } } // namespace Digikam diff --git a/core/libs/database/history/itemhistorygraph.h b/core/libs/database/history/itemhistorygraph.h index 9e7e3b27d1..0ccd7902c3 100644 --- a/core/libs/database/history/itemhistorygraph.h +++ b/core/libs/database/history/itemhistorygraph.h @@ -1,194 +1,196 @@ /* ============================================================ * * This file is a part of digiKam project * https://www.digikam.org * * Date : 2010-10-23 * Description : Graph data class for item history * * Copyright (C) 2010-2011 by Marcel Wiesweg * * This program is free software; you can redistribute it * and/or modify it under the terms of the GNU General * Public License as published by the Free Software Foundation; * either version 2, or (at your option) * any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * ============================================================ */ #ifndef DIGIKAM_ITEM_HISTORY_GRAPH_H #define DIGIKAM_ITEM_HISTORY_GRAPH_H // Qt includes #include #include #include // Local includes #include "iteminfo.h" #include "historyimageid.h" #include "digikam_export.h" namespace Digikam { class ItemHistoryGraphData; class DImageHistory; class DIGIKAM_DATABASE_EXPORT ItemHistoryGraph { public: ItemHistoryGraph(); ItemHistoryGraph(const ItemHistoryGraph& other); ~ItemHistoryGraph(); ItemHistoryGraph& operator=(const ItemHistoryGraph& other); bool isNull() const; bool isEmpty() const; bool isSingleVertex() const; /** * Returns if the graph contains any edges. Because loops are not allowed, * this also means (!isEmpty() && !isSingleVertex()). */ bool hasEdges() const; ItemHistoryGraphData& data(); const ItemHistoryGraphData& data() const; enum HistoryLoadingFlag { /// Load the relation cloud to the graph. Will give all edges, but no further info LoadRelationCloud = 1 << 0, /// Will load the DImageHistory of the given subject LoadSubjectHistory = 1 << 1, /// Will load the DImageHistory of all leave vertices of the graph LoadLeavesHistory = 1 << 2, LoadAll = LoadRelationCloud | LoadSubjectHistory | LoadLeavesHistory }; Q_DECLARE_FLAGS(HistoryLoadingMode, HistoryLoadingFlag) enum ProcessingMode { NoProcessing, PrepareForDisplay }; /** * Convenience: Reads all available history for the given info from the database * and returns the created graph. * Depending on mode, the graph will be preparedForDisplay(). * If no history is recorded and no relations found, a single-vertex graph is returned. */ static ItemHistoryGraph fromInfo(const ItemInfo& info, HistoryLoadingMode loadingMode = LoadAll, ProcessingMode processingMode = PrepareForDisplay); /** * Add the given history. * The optionally given info or id is used as the "current" image of the history. * If you read a history from a file's metadata or the database, you shall give the * relevant subject. */ void addHistory(const DImageHistory& history, const ItemInfo& historySubject = ItemInfo()); void addHistory(const DImageHistory& history, const HistoryImageId& historySubject = HistoryImageId()); /** * This is very similar to addHistory. The only difference is that * no attempt is made to retrieve an ItemInfo for the historySubjectId. * Can be useful in the context of scanning */ void addScannedHistory(const DImageHistory& history, qlonglong historySubjectId); /** * Add images and their relations from the given pairs. * Each pair (a,b) means "a is derived from b". */ void addRelations(const QList >& pairs); - /** Clears this graph. */ + /** + * Clears this graph. + */ void clear(); /** * Remove edges which provide only duplicate information * (performs a transitive reduction). * Especially call this when addRelations() was used. */ void reduceEdges(); /** * Returns true if for any entry no ItemInfo could be located. */ bool hasUnresolvedEntries() const; /** * Remove all vertices from the graph for which no existing ItemInfo * could be found in the database */ void dropUnresolvedEntries(); /** * Sort vertex information prioritizing for the given vertex */ void sortForInfo(const ItemInfo& subject); /** * Combines reduceEdges(), dropOrphans() and sortForInfo() */ void prepareForDisplay(const ItemInfo& subject); /** * Returns all possible relations between images in this graph, * the edges of the transitive closure. * The first variant returns (1,2),(3,4),(6,8), the second (1,3,6)(2,4,8). */ QList > relationCloud() const; QPair, QList > relationCloudParallel() const; /** * Returns image infos / ids from all vertices in this graph */ QList allImages() const; QList allImageIds() const; /** * Returns image infos / ids from all root vertices in this graph, * i.e. vertices with no precedent history. */ QList rootImages() const; /** * Returns image infos / ids from all leaf vertices in this graph, * i.e. vertices with no subsequent history. */ QList leafImages() const; /** * Attempts at a categorization of all images in the graph * into the types defined by HistoryImageId. * The type will be invalid if no decision can be made due to conflicting data. */ QHash categorize() const; private: QSharedDataPointer d; }; QDebug DIGIKAM_DATABASE_EXPORT operator<<(QDebug dbg, const ItemHistoryGraph& g); } // namespace Digikam Q_DECLARE_OPERATORS_FOR_FLAGS(Digikam::ItemHistoryGraph::HistoryLoadingMode) #endif // DIGIKAM_ITEM_HISTORY_GRAPH_H diff --git a/core/libs/database/history/itemhistorygraph_boost.h b/core/libs/database/history/itemhistorygraph_boost.h index 5837f425bc..a98a315783 100644 --- a/core/libs/database/history/itemhistorygraph_boost.h +++ b/core/libs/database/history/itemhistorygraph_boost.h @@ -1,1644 +1,1650 @@ /* ============================================================ * * This file is a part of digiKam project * https://www.digikam.org * * Date : 2010-10-22 * Description : Boost Graph Library: a graph class * * Copyright (C) 2010-2011 by Marcel Wiesweg * * This program is free software; you can redistribute it * and/or modify it under the terms of the GNU General * Public License as published by the Free Software Foundation; * either version 2, or (at your option) * any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * ============================================================ */ #ifndef DIGIKAM_ITEM_HISTORY_GRAPH_BOOST_H #define DIGIKAM_ITEM_HISTORY_GRAPH_BOOST_H // To include pragma directives for MSVC #include "digikam_config.h" // Pragma directives to reduce warnings from Boost header files. #if !defined(Q_OS_DARWIN) && defined(Q_CC_GNU) # pragma GCC diagnostic push # pragma GCC diagnostic ignored "-Wunused-local-typedefs" #endif #if defined(Q_OS_DARWIN) && defined(Q_CC_CLANG) # pragma clang diagnostic push # pragma clang diagnostic ignored "-Wundef" # pragma clang diagnostic ignored "-Wunused-parameter" # pragma clang diagnostic ignored "-Wcast-align" # pragma clang diagnostic ignored "-Wunused-local-typedef" #endif // Boost includes // Prohibit boost using deprecated header files #define BOOST_NO_HASH // C++ includes #include #include // Boost library includes #include #include #include #include #include #include #include #include #include #include #include // Local includes #include "digikam_debug.h" #include "digikam_export.h" -/** Install custom property ids, out-of-namespace */ +/** + * Install custom property ids, out-of-namespace + */ enum vertex_properties_t { vertex_properties }; enum edge_properties_t { edge_properties }; namespace boost { BOOST_INSTALL_PROPERTY(vertex, properties); BOOST_INSTALL_PROPERTY(edge, properties); } namespace Digikam { /** * Adds the necessary typedefs so that associative_property_map * accepts a QMap, and it can be used as a Boost Property Map */ template class QMapForAdaptors : public QMap { public: typedef Key key_type; typedef Value data_type; typedef typename std::pair value_type; QMapForAdaptors() { } }; /** * Each edge is directed: "vertex1 -> vertex2". * This direction has a meaning with methods such as * roots() or leaves(). */ enum MeaningOfDirection { /// Edges are directed from a parent to its child ParentToChild, /// Edges are direct from a child to its parent ChildToParent }; /** * The graph base class template */ template class DIGIKAM_DATABASE_EXPORT Graph { public: typedef boost::adjacency_list< - boost::vecS, /// Standard storage. listS was desirable, but many algorithms work only with vecS + boost::vecS, ///< Standard storage. listS was desirable, but many algorithms work only with vecS boost::vecS, - boost::bidirectionalS, /// directed graph + boost::bidirectionalS, ///< directed graph boost::property >, - boost::property /// One property for each edge: EdgeProperties + boost::property ///< One property for each edge: EdgeProperties > GraphContainer; /** * a bunch of graph-specific typedefs that make the long boost types manageable */ typedef typename boost::graph_traits graph_traits; typedef typename graph_traits::vertex_descriptor vertex_t; typedef typename graph_traits::edge_descriptor edge_t; typedef typename graph_traits::vertex_iterator vertex_iter; typedef typename graph_traits::edge_iterator edge_iter; typedef typename graph_traits::adjacency_iterator adjacency_iter; typedef typename graph_traits::out_edge_iterator out_edge_iter; typedef typename graph_traits::in_edge_iterator in_edge_iter; typedef typename boost::inv_adjacency_iterator_generator::type inv_adjacency_iter; typedef typename graph_traits::degree_size_type degree_t; typedef std::pair adjacency_vertex_range_t; typedef std::pair inv_adjacency_vertex_range_t; typedef std::pair out_edge_range_t; typedef std::pair vertex_range_t; typedef std::pair edge_range_t; typedef typename boost::property_map::type vertex_index_map_t; typedef typename boost::property_map::const_type const_vertex_index_map_t; typedef typename boost::property_map::type vertex_property_map_t; typedef typename boost::property_map::const_type const_vertex_property_map_t; typedef typename boost::property_map::type edge_property_map_t; typedef typename boost::property_map::const_type const_edge_property_map_t; /** * These two classes provide source-compatible wrappers for the vertex and edge descriptors, * providing default construction to null and the isNull() method. */ class Vertex { public: Vertex() : v(graph_traits::null_vertex()) { } // cppcheck-suppress noExplicitConstructor Vertex(const vertex_t& v) // krazy:exclude=explicit : v(v) { } Vertex& operator=(const vertex_t& other) { v = other; return *this; } operator const vertex_t&() const { return v; } operator vertex_t&() { return v; } bool operator==(const vertex_t& other) const { return v == other; } bool isNull() const { return v == graph_traits::null_vertex(); } protected: vertex_t v; }; class Edge { public: Edge() : null(true) { } // cppcheck-suppress noExplicitConstructor Edge(const edge_t& e) // krazy:exclude=explicit : e(e), null(false) { } Edge& operator=(const edge_t& other) { e = other; null = false; return *this; } operator const edge_t&() const { return e; } operator edge_t&() { return e; } const edge_t& toEdge() const { return e; } edge_t& toEdge() { return e; } bool operator==(const edge_t& other) const { return e == other; } bool isNull() const { return null; } protected: edge_t e; // there is not null_edge, we must emulate it bool null; }; public: typedef QPair VertexPair; typedef QPair EdgePair; typedef QMapForAdaptors VertexVertexMap; typedef QMapForAdaptors VertexIntMap; typedef boost::associative_property_map VertexVertexMapAdaptor; typedef boost::associative_property_map VertexIntMapAdaptor; public: explicit Graph(MeaningOfDirection direction = ParentToChild) : direction(direction) { } Graph(const Graph& g) : graph(g.graph), direction(g.direction) { } virtual ~Graph() { } Graph& operator=(const Graph& other) { graph = other.graph; direction = other.direction; return *this; } MeaningOfDirection meaningOfDirection() const { return direction; } void clear() { graph.clear(); } Vertex addVertex() { Vertex v = boost::add_vertex(graph); return v; } Vertex addVertex(const VertexProperties& properties) { Vertex v = addVertex(); setProperties(v, properties); return v; } void remove(const Vertex& v) { if (v.isNull()) { return; } boost::clear_vertex(v, graph); boost::remove_vertex(v, graph); } Edge addEdge(const Vertex& v1, const Vertex& v2) { Edge e = edge(v1, v2); if (e.isNull()) { e = boost::add_edge(v1, v2, graph).first; } return e; } Edge edge(const Vertex& v1, const Vertex& v2) const { std::pair pair = boost::edge(v1, v2, graph); if (pair.second) { return pair.first; } return Edge(); } bool hasEdge(const Vertex& v1, const Vertex& v2) const { return boost::edge(v1, v2, graph).second; } /// Does not care for direction bool isConnected(const Vertex& v1, const Vertex& v2) const { if (boost::edge(v1, v2, graph).second) { return true; } if (boost::edge(v2, v1, graph).second) { return true; } return false; } void setProperties(const Vertex& v, const VertexProperties& props) { boost::put(vertex_properties, graph, v, props); } const VertexProperties& properties(const Vertex& v) const { return boost::get(vertex_properties, graph, v); } VertexProperties& properties(const Vertex& v) { return boost::get(vertex_properties, graph, v); } void setProperties(const Edge& e, const EdgeProperties& props) { boost::put(edge_properties, graph, e, props); } template Vertex findVertexByProperties(const T& value) const { vertex_range_t range = boost::vertices(graph); for (vertex_iter it = range.first; it != range.second; ++it) { const VertexProperties& props = properties(*it); // must implement operator==(const T&) if (props == value) { return *it; } } return Vertex(); } EdgeProperties properties(const Vertex& v1, const Vertex& v2) const { Edge e = edge(v1, v2); if (e.isNull()) { return EdgeProperties(); } return properties(e); } const EdgeProperties& properties(const Edge& e) const { return boost::get(edge_properties, graph, e); } EdgeProperties& properties(const Edge& e) { return boost::get(edge_properties, graph, e); } /** * Accessing vertices and egdes */ const GraphContainer& getGraph() const { return graph; } QList vertices() const { return toVertexList(boost::vertices(graph)); } enum AdjacencyFlags { OutboundEdges = 1 << 0, InboundEdges = 1 << 1, /// These resolve to one of the flags above, depending on MeaningOfDirection EdgesToLeaf = 1 << 2, EdgesToRoot = 1 << 3, AllEdges = InboundEdges | OutboundEdges }; QList adjacentVertices(const Vertex& v, AdjacencyFlags flags = AllEdges) const { if (flags & EdgesToLeaf) { flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? OutboundEdges : InboundEdges)); } if (flags & EdgesToRoot) { flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? InboundEdges : OutboundEdges)); } QList verticesLst; if (flags & OutboundEdges) { verticesLst << toVertexList(boost::adjacent_vertices(v, graph)); } if (flags & InboundEdges) { verticesLst << toVertexList(boost::inv_adjacent_vertices(v, graph)); } return verticesLst; } // for "hasAdjacentVertices", simply use hasEdges(v, flags) int vertexCount() const { return boost::num_vertices(graph); } bool isEmpty() const { return isEmptyRange(boost::vertices(graph)); } int outDegree(const Vertex& v) const { return boost::out_degree(v, graph); } int inDegree(const Vertex& v) const { return boost::in_degree(v, graph); } bool isRoot(const Vertex& v) const { return !hasEdges(v, EdgesToRoot); } bool isLeaf(const Vertex& v) const { return !hasEdges(v, EdgesToLeaf); } Vertex source(const Edge& e) const { return boost::source(e.toEdge(), graph); } Vertex target(const Edge& e) const { return boost::target(e.toEdge(), graph); } QList edges(const Vertex& v, AdjacencyFlags flags = AllEdges) const { if (flags & EdgesToLeaf) { flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? OutboundEdges : InboundEdges)); } if (flags & EdgesToRoot) { flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? InboundEdges : OutboundEdges)); } QList es; if (flags & OutboundEdges) { es << toEdgeList(boost::out_edges(v, graph)); } if (flags & InboundEdges) { es << toEdgeList(boost::in_edges(v, graph)); } return es; } int edgeCount() const { return boost::num_edges(graph); } bool hasEdges(const Vertex& v, AdjacencyFlags flags = AllEdges) const { if (flags & EdgesToLeaf) { flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? OutboundEdges : InboundEdges)); } if (flags & EdgesToRoot) { flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? InboundEdges : OutboundEdges)); } if (flags & OutboundEdges) { if (!isEmptyRange(boost::out_edges(v, graph))) { return true; } } if (flags & InboundEdges) { if (!isEmptyRange(boost::in_edges(v, graph))) { return true; } } return false; } bool hasEdges() const { return !isEmptyRange(boost::edges(graph)); } QList edges() const { return toEdgeList(boost::edges(graph)); } QList edgePairs() const { QList pairs; edge_range_t range = boost::edges(graph); for (edge_iter it = range.first ; it != range.second ; ++it) { pairs << VertexPair(boost::source(*it, graph), boost::target(*it, graph)); } return pairs; } /* ---- Algorithms ---- */ /** * Returns the vertex ids of this graph, in topological order. */ QList topologicalSort() const { std::list verticesLst; try { boost::topological_sort(graph, std::back_inserter(verticesLst)); } catch (boost::bad_graph& e) { qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); return QList(); } typedef typename std::list::iterator vertex_list_iter; return toVertexList(std::pair(verticesLst.begin(), verticesLst.end())); } enum GraphCopyFlags { CopyVertexProperties = 1 << 0, CopyEdgeProperties = 1 << 1, CopyAllProperties = CopyVertexProperties | CopyEdgeProperties }; /** * Returns a copy of this graph with all edges added to form the transitive closure */ Graph transitiveClosure(GraphCopyFlags flags = CopyAllProperties) const { // make_iterator_property_map: // 1. The second parameter, our verteX_index map, converts the key (Vertex) into an index // 2. The index is used to store the value (Vertex) in the first argument, which is our vector std::vector copiedVertices(vertexCount(), Vertex()); Graph closure; try { boost::transitive_closure(graph, closure.graph, orig_to_copy(make_iterator_property_map(copiedVertices.begin(), get(boost::vertex_index, graph))) ); } catch (boost::bad_graph& e) { qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); return Graph(); } copyProperties(closure, flags, copiedVertices); return closure; } /** * Returns a copy of this graph, with edges removed so that the transitive reduction is formed. * Optionally, a list of edges of this graph that have been removed in the returned graph is given. */ Graph transitiveReduction(QList* removedEdges = 0, GraphCopyFlags flags = CopyAllProperties) const { std::vector copiedVertices(vertexCount(), Vertex()); Graph reduction; // named parameters is not implemented try { boost::transitive_reduction(graph, reduction.graph, make_iterator_property_map(copiedVertices.begin(), get(boost::vertex_index, graph)), get(boost::vertex_index, graph)); } catch (boost::bad_graph& e) { qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); return Graph(); } copyProperties(reduction, flags, copiedVertices); if (removedEdges) { *removedEdges = edgeDifference(reduction, copiedVertices); } return reduction; } /** * Returns all roots, i.e. vertices with no parents. * Takes the graph direction into account. */ QList roots() const { return findZeroDegree(direction == ParentToChild ? true : false); } /** * Returns all roots of vertex v. Subset of roots(). * I case any leaves have roots that are not roots of v, * they will not be contained in this list. */ QList rootsOf(const Vertex& v) const { return findZeroDegreeFrom(v, direction == ParentToChild ? true : false); } /** * Returns all leaves, i.e. vertices with no children * Takes the graph direction into account. */ QList leaves() const { return findZeroDegree(direction == ParentToChild ? false : true); } QList leavesFrom(const Vertex& v) const { return findZeroDegreeFrom(v, direction == ParentToChild ? false : true); } template static bool alwaysFalse(const T&, const T&) { return false; } /** * Returns the longest path through the graph, starting from a vertex in roots(), * ending on a vertex in leaves(), and passing vertex v. * The returned list is given in that order, root - v - leave. * If there is more than one candidate for root or leave, lessThan is used to determine the first candidate. */ QList longestPathTouching(const Vertex& v) const { return longestPathTouching(v, alwaysFalse); } template QList longestPathTouching(const Vertex& v, LessThan lessThan) const { if (v.isNull()) { return QList(); } QList fromRoot; QList toLeave; Path path; path.longestPath(boost::make_reverse_graph(graph), v); QList rootCandidates = mostRemoteNodes(path.distances); if (!rootCandidates.isEmpty()) { std::stable_sort(rootCandidates.begin(), rootCandidates.end(), lessThan); Vertex root = rootCandidates.first(); fromRoot << listPath(root, v, path.predecessors, ChildToParent); } path.longestPath(graph, v); QList leaveCandidates = mostRemoteNodes(path.distances); if (!leaveCandidates.isEmpty()) { std::stable_sort(leaveCandidates.begin(), leaveCandidates.end(), lessThan); Vertex leave = leaveCandidates.first(); toLeave << listPath(leave, v, path.predecessors); } if (direction == ParentToChild) { return fromRoot << v << toLeave; } else { return toLeave << v << fromRoot; } } /** * Returns the shortestPath between id1 and id2. * If s2 is not reachable from s1, the path is searched from s2 to s1. * The returned list always starts with s1, contains the intermediate vertices, and ends with s2. * If no path is available, an empty list is returned. */ QList shortestPath(const Vertex& v1, const Vertex& v2) const { if (v1.isNull() || v2.isNull()) { return QList(); } QList verticesLst; Path path; path.shortestPath(graph, v1); if (path.isReachable(v2)) { verticesLst = listPath(v2, v1, path.predecessors, ChildToParent); verticesLst.prepend(v1); } else { // assume inverted parameters path.shortestPath(graph, v2); if (path.isReachable(v1)) { verticesLst = listPath(v1, v2, path.predecessors); verticesLst.append(v2); } } return verticesLst; } /** * Returns the shortest distances from Vertex to all vertices in the graph. * If the value is -1, a vertex is not reachable from v. */ QMap shortestDistancesFrom(const Vertex& v) const { Path path; if (direction == ParentToChild) { path.shortestPath(graph, v); } else { path.shortestPath(boost::make_reverse_graph(graph), v); } // change 2147483647 to -1 typename QMap::iterator it; for (it = path.distances.begin() ; it != path.distances.end() ; ++it) { if (it.value() == std::numeric_limits::max()) it.value() = -1; } return path.distances; } enum ReturnOrder { BreadthFirstOrder, DepthFirstOrder }; /** * For a vertex v reachable from a vertex root, * returns, in depth-first or breadth-first order, all vertices dominated by v * starting from root. */ QList verticesDominatedBy(const Vertex& v, const Vertex& root, ReturnOrder order = BreadthFirstOrder) const { if (v.isNull() || isEmpty()) { return QList(); } GraphSearch search; if (order == BreadthFirstOrder) { search.breadthFirstSearch(graph, root, direction == ChildToParent); } else { search.depthFirstSearch(graph, root, direction == ChildToParent); } return verticesDominatedBy(v, root, search.vertices); } /** * For a vertex v reachable from a vertex root all vertices dominated by v starting from root. * The returned list is in depth-first order, using root as starting point, and * when discovering a vertex, sorting the adjacent vertices with the given lessThan. */ template QList verticesDominatedByDepthFirstSorted(const Vertex& v, const Vertex& root, LessThan lessThan) const { return verticesDominatedBy(v, root, verticesDepthFirstSorted(root, lessThan)); } /** * For a vertex v reachable from a vertex root returns * all vertices dominated by v starting from root. * The order is the same as in the given, sorted list of all vertices in this graph * (or all vertices expected to be returned. The returned list is the intersection * of the dominated vertices and presortedVertices, in order of presortedVertices) */ QList verticesDominatedBy(const Vertex& v, const Vertex& root, const QList presortedVertices) const { if (v.isNull() || isEmpty()) { return QList(); } DominatorTree tree; tree.enter(graph, root, direction); QList dominatedTree = treeFromPredecessors(v, tree.predecessors); - // remove all vertices from the DFS of v that are not in the dominated tree + /// remove all vertices from the DFS of v that are not in the dominated tree QList orderedTree; foreach (const Vertex& v, presortedVertices) { if (dominatedTree.contains(v)) { orderedTree << v; } } return orderedTree; } /** * Orders all vertices of the graph in a breadth-first manner. * A single vertex is taken as reference to distinguish main root and side paths. * Otherwise the first root is taken as reference. */ QList verticesBreadthFirst(const Vertex& givenRef = Vertex()) const { if (isEmpty()) { return QList(); } Vertex ref(givenRef); if (ref.isNull()) ref = roots().first(); QList verticesLst; verticesLst << rootsOf(ref); if (verticesLst.size() == vertexCount()) return verticesLst; GraphSearch search; search.breadthFirstSearch(graph, verticesLst.first(), direction == ChildToParent); QList bfs = search.verticesLst; foreach (const Vertex& v, verticesLst) { bfs.removeOne(v); } verticesLst << bfs; if (verticesLst.size() == vertexCount()) return verticesLst; - // sort in any so far unreachable nodes + /// sort in any so far unreachable nodes vertex_range_t range = boost::vertices(graph); for (vertex_iter it = range.first ; it != range.second ; ++it) { if (!verticesLst.contains(*it)) { GraphSearch childSearch; childSearch.breadthFirstSearch(graph, *it, direction == ChildToParent); QList childBfs = childSearch.vertices; QList toInsert; // any item reachable from *it should come after it int minIndex = verticesLst.size(); foreach (const Vertex& c, childBfs) { int foundAt = verticesLst.indexOf(c); if (foundAt == -1) { toInsert << c; } else { minIndex = qMin(foundAt, minIndex); } } foreach (const Vertex& c, toInsert) { verticesLst.insert(minIndex++, c); } } } return verticesLst; } /** * Orders all vertices of the graph in a depth-first manner. * When discovering a vertex, the adjacent vertices are sorted with the given lessThan. * A single vertex is taken as starting point. * If null, the first root is taken as reference. */ template QList verticesDepthFirstSorted(const Vertex& givenRef, LessThan lessThan) const { if (isEmpty()) { return QList(); } Vertex ref(givenRef); if (ref.isNull()) ref = roots().first(); QList verticesLst; verticesLst = rootsOf(ref); if (verticesLst.size() == vertexCount() || verticesLst.isEmpty()) return verticesLst; GraphSearch search; search.depthFirstSearchSorted(graph, verticesLst.first(), direction == ChildToParent, lessThan); QList dfs = search.vertices; foreach (const Vertex& v, verticesLst) { dfs.removeOne(v); } verticesLst << dfs; return search.vertices; } protected: QList treeFromPredecessors(const Vertex& v, const VertexVertexMap& predecessors) const { QList verticesLst; verticesLst << v; treeFromPredecessorsRecursive(v, verticesLst, predecessors); return verticesLst; } void treeFromPredecessorsRecursive(const Vertex& v, QList& vertices, const VertexVertexMap& predecessors) const { QList children = predecessors.keys(v); vertices << children; foreach (const Vertex& child, children) { treeFromPredecessorsRecursive(child, vertices, predecessors); } } /** * Returns a list of vertex ids of vertices in the given range */ template static QList toList(const range_t& range) { typedef typename range_t::first_type iterator_t; QList list; for (iterator_t it = range.first ; it != range.second ; ++it) { list << *it; } return list; } template static QList toVertexList(const range_t& range) { return toList(range); } template static QList toEdgeList(const range_t& range) { return toList(range); } template static bool isEmptyRange(const range_t& range) { return range.first == range.second; } /** * According to the given flags and based on the map, * copies vertex and edge properties from this to the other graph */ void copyProperties(Graph& other, GraphCopyFlags flags, const std::vector& copiedVertices) const { other.direction = direction; if (flags & CopyVertexProperties) { vertex_index_map_t indexMap = boost::get(boost::vertex_index, graph); vertex_range_t range = boost::vertices(graph); for (vertex_iter it = range.first ; it != range.second ; ++it) { Vertex copiedVertex = copiedVertices[boost::get(indexMap, *it)]; if (copiedVertex.isNull()) { continue; } other.setProperties(copiedVertex, properties(*it)); } } if (flags & CopyEdgeProperties) { vertex_index_map_t indexMap = boost::get(boost::vertex_index, graph); edge_range_t range = boost::edges(graph); for (edge_iter it = range.first ; it != range.second ; ++it) { Vertex s = boost::source(*it, graph); Vertex t = boost::target(*it, graph); Vertex copiedS = copiedVertices[boost::get(indexMap, s)]; Vertex copiedT = copiedVertices[boost::get(indexMap, t)]; if (copiedS.isNull() || copiedT.isNull()) { continue; } Edge copiedEdge = other.edge(copiedS, copiedT); if (!copiedEdge.isNull()) { other.setProperties(copiedEdge, properties(s, t)); } } } } /** * Returns a list of edges of this graph that have been removed in other. * copiedVertices maps the vertices of this graph to other. */ QList edgeDifference(const Graph& other, const std::vector& copiedVertices) const { QList removed; vertex_index_map_t indexMap = boost::get(boost::vertex_index, graph); edge_range_t range = boost::edges(graph); for (edge_iter it = range.first ; it != range.second ; ++it) { Vertex s = boost::source(*it, graph); Vertex t = boost::target(*it, graph); Vertex copiedS = copiedVertices[boost::get(indexMap, s)]; Vertex copiedT = copiedVertices[boost::get(indexMap, t)]; if (copiedS.isNull() || copiedT.isNull()) { continue; } Edge copiedEdge = other.edge(copiedS, copiedT); if (copiedEdge.isNull()) { removed << *it; } } return removed; } /** * Finds vertex ids of all vertices with zero in- our out-degree. */ QList findZeroDegree(bool inOrOut) const { QList verticesLst; vertex_range_t range = boost::vertices(graph); for (vertex_iter it = range.first ; it != range.second ; ++it) { if ( (inOrOut ? in_degree(*it, graph) : out_degree(*it, graph)) == 0) { verticesLst << *it; } } return verticesLst; } QList findZeroDegreeFrom(const Vertex& v, bool inOrOut) const { bool invertGraph = (direction == ChildToParent); if (!inOrOut) invertGraph = !invertGraph; GraphSearch search; search.breadthFirstSearch(graph, v, invertGraph); QList verticesLst; foreach (const Vertex& candidate, search.vertices) { if ( (inOrOut ? in_degree(candidate, graph) : out_degree(candidate, graph)) == 0) { verticesLst << candidate; } } return verticesLst; } /** * Helper class to find paths through the graph. * Call one of the methods and then read the maps. */ class Path { public: template void shortestPath(const GraphType& graph, const Vertex& v) { int weight = 1; try { boost::dag_shortest_paths(graph, v, - // we provide a constant weight of 1 + /// we provide a constant weight of 1 weight_map(boost::ref_property_map::edge_descriptor,int>(weight)). - // Store distance and predecessors in QMaps, wrapped to serve as property maps + /// Store distance and predecessors in QMaps, wrapped to serve as property maps distance_map(VertexIntMapAdaptor(distances)). predecessor_map(VertexVertexMapAdaptor(predecessors)) ); } catch (boost::bad_graph& e) { qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); } } template void longestPath(const GraphType& graph, const Vertex& v) { int weight = 1; try { boost::dag_shortest_paths(graph, v, - // we provide a constant weight of 1 + /// we provide a constant weight of 1 weight_map(boost::ref_property_map::edge_descriptor,int>(weight)). - // Invert the default compare method: With greater, we get the longest path + /// Invert the default compare method: With greater, we get the longest path distance_compare(std::greater()). - // will be returned if a node is unreachable + /// will be returned if a node is unreachable distance_inf(-1). - // Store distance and predecessors in QMaps, wrapped to serve as property maps + /// Store distance and predecessors in QMaps, wrapped to serve as property maps distance_map(VertexIntMapAdaptor(distances)). predecessor_map(VertexVertexMapAdaptor(predecessors)) ); } catch (boost::bad_graph& e) { qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); } } bool isReachable(const Vertex& v) const { return predecessors.value(v, v) != v; } VertexVertexMap predecessors; VertexIntMap distances; }; class DominatorTree { public: template void enter(const GraphType& graph, const Vertex& v, MeaningOfDirection direction = ParentToChild) { try { if (direction == ParentToChild) { boost::lengauer_tarjan_dominator_tree(graph, v, VertexVertexMapAdaptor(predecessors)); } else boost::lengauer_tarjan_dominator_tree(boost::make_reverse_graph(graph), v, VertexVertexMapAdaptor(predecessors)); } catch (boost::bad_graph& e) { qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); } } VertexVertexMap predecessors; }; class GraphSearch { public: template void depthFirstSearch(const GraphType& graph, const Vertex& v, bool invertGraph) { // remember that the visitor is passed by value DepthFirstSearchVisitor vis(this); try { if (invertGraph) { boost::depth_first_search(boost::make_reverse_graph(graph), visitor(vis).root_vertex(v)); } else { boost::depth_first_search(graph, visitor(vis).root_vertex(v)); } } catch (boost::bad_graph& e) { qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); } } template void depthFirstSearchSorted(const GraphType& graph, const Vertex& v, bool invertGraph, LessThan lessThan) { // remember that the visitor is passed by value DepthFirstSearchVisitor vis(this); std::vector color_vec(boost::num_vertices(graph), boost::white_color); try { if (invertGraph) { depth_first_search_sorted(boost::make_reverse_graph(graph), v, vis, make_iterator_property_map(color_vec.begin(), get(boost::vertex_index, graph)), lessThan); } else { depth_first_search_sorted(graph, v, vis, make_iterator_property_map(color_vec.begin(), get(boost::vertex_index, graph)), lessThan); } } catch (boost::bad_graph& e) { qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); } } template void breadthFirstSearch(const GraphType& graph, const Vertex& v, bool invertGraph) { BreadthFirstSearchVisitor vis(this); try { if (invertGraph) { boost::breadth_first_search(boost::make_reverse_graph(graph), v, visitor(vis)); } else { boost::breadth_first_search(graph, v, visitor(vis)); } } catch (boost::bad_graph& e) { qCDebug(DIGIKAM_DATABASE_LOG) << e.what(); } } class CommonVisitor { protected: explicit CommonVisitor(GraphSearch* const q) : q(q) { } void record(const Vertex& v) const { q->vertices << v; } GraphSearch* const q; }; class DepthFirstSearchVisitor : public boost::default_dfs_visitor, public CommonVisitor { public: explicit DepthFirstSearchVisitor(GraphSearch* const q) : CommonVisitor(q) { } template void discover_vertex(VertexType u, const GraphType&) const { this->record(u); } }; class BreadthFirstSearchVisitor : public boost::default_bfs_visitor, public CommonVisitor { public: explicit BreadthFirstSearchVisitor(GraphSearch* const q) : CommonVisitor(q) { } template void discover_vertex(VertexType u, const GraphType&) const { this->record(u); } }; QList vertices; protected: template class lessThanMapEdgeToTarget { typedef typename boost::graph_traits::edge_descriptor edge_descriptor; public: lessThanMapEdgeToTarget(const GraphType& g, VertexLessThan vertexLessThan) : g(g), vertexLessThan(vertexLessThan) { } bool operator()(const edge_descriptor& a, const edge_descriptor& b) { return vertexLessThan(boost::target(a, g), boost::target(b, g)); } public: const GraphType& g; VertexLessThan vertexLessThan; }; - // This is boost's simple, old, recursive DFS algorithm adapted with lessThan + /// This is boost's simple, old, recursive DFS algorithm adapted with lessThan template void depth_first_search_sorted(const IncidenceGraph& g, Vertex u, DFSVisitor& vis, ColorMap color, LessThan lessThan) { //typedef std::pair > VertexInfo; typedef typename boost::graph_traits::edge_descriptor edge_descriptor; QList outEdges; //std::vector stack; boost::put(color, u, boost::gray_color); vis.discover_vertex(u, g); outEdges = toList(boost::out_edges(u, g)); - // Sort edges. The lessThan we have takes vertices, so we use a lessThan which - // maps the given edges to their targets, and calls our vertex lessThan. + /** + * Sort edges. The lessThan we have takes vertices, so we use a lessThan which + * maps the given edges to their targets, and calls our vertex lessThan. + */ std::sort(outEdges.begin(), outEdges.end(), lessThanMapEdgeToTarget(g, lessThan)); foreach (const edge_descriptor& e, outEdges) { Vertex v = boost::target(e, g); vis.examine_edge(e, g); boost::default_color_type v_color = boost::get(color, v); if (v_color == boost::white_color) { vis.tree_edge(e, g); depth_first_search_sorted(g, v, vis, color, lessThan); } else if (v_color == boost::gray_color) { vis.back_edge(e, g); } else { vis.forward_or_cross_edge(e, g); } } put(color, u, boost::black_color); vis.finish_vertex(u, g); } }; - /** Get the list of vertices with the largest value in the given distance map */ + /** + * Get the list of vertices with the largest value in the given distance map + */ QList mostRemoteNodes(const VertexIntMap& distances) const { typename VertexIntMap::const_iterator it; int maxDist = 1; QList candidates; for (it = distances.begin() ; it != distances.end() ; ++it) { if (it.value() > maxDist) { maxDist = it.value(); //qDebug() << "Increasing maxDist to" << maxDist; candidates.clear(); } if (it.value() >= maxDist) { //qDebug() << "Adding candidate" << id(it.key()) << "at distance" << maxDist; candidates << it.key(); } /* if (it.value() == -1) qDebug() << id(it.key()) << "unreachable"; else qDebug() << "Distance to" << id(it.key()) << "is" << it.value(); */ } return candidates; } /** * Get a list of vertex ids for the path from root to target, using the given predecessors. * Depending on MeaningOfDirection, the ids are listed inverted, from target to root. */ QList listPath(const Vertex& root, const Vertex& target, const VertexVertexMap& predecessors, MeaningOfDirection dir = ParentToChild) const { QList verticesLst; for (Vertex v = root ; v != target ; v = predecessors.value(v)) { //qDebug() << "Adding waypoint" << id(v); if (dir == ParentToChild) { verticesLst.append(v); } else { verticesLst.prepend(v); } // If a node is not reachable, it seems its entry in the predecessors map is itself // Avoid endless loop if (predecessors.value(v) == v) { break; } } return verticesLst; } protected: GraphContainer graph; MeaningOfDirection direction; }; } // namespace Digikam // Restore warnings #if !defined(Q_OS_DARWIN) && defined(Q_CC_GNU) # pragma GCC diagnostic pop #endif #if defined(Q_OS_DARWIN) && defined(Q_CC_CLANG) # pragma clang diagnostic pop #endif #endif // DIGIKAM_ITEM_HISTORY_GRAPH_BOOST_H diff --git a/core/libs/database/history/itemhistorygraphmodel.h b/core/libs/database/history/itemhistorygraphmodel.h index b0b1453f55..62a832c8b1 100644 --- a/core/libs/database/history/itemhistorygraphmodel.h +++ b/core/libs/database/history/itemhistorygraphmodel.h @@ -1,132 +1,134 @@ /* ============================================================ * * This file is a part of digiKam project * https://www.digikam.org * * Date : 2010-10-27 * Description : Model to an ItemHistoryGraph * * Copyright (C) 2010-2011 by Marcel Wiesweg * * This program is free software; you can redistribute it * and/or modify it under the terms of the GNU General * Public License as published by the Free Software Foundation; * either version 2, or (at your option) * any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * ============================================================ */ #ifndef DIGIKAM_ITEM_HISTORY_GRAPH_MODEL_H #define DIGIKAM_ITEM_HISTORY_GRAPH_MODEL_H // Qt includes #include // Local includes #include "dragdropimplementations.h" #include "itemhistorygraph.h" #include "digikam_export.h" namespace Digikam { class ItemHistoryGraph; class ItemInfo; class ItemListModel; class FilterAction; class DIGIKAM_DATABASE_EXPORT ItemHistoryGraphModel : public QAbstractItemModel, public DragDropModelImplementation { Q_OBJECT public: enum Mode { ImagesListMode, ImagesTreeMode, CombinedTreeMode }; enum ExtraRoles { IsImageItemRole = Qt::UserRole + 1000, IsFilterActionItemRole = Qt::UserRole + 1001, IsHeaderItemRole = Qt::UserRole + 1002, IsCategoryItemRole = Qt::UserRole + 1003, IsSeparatorItemRole = Qt::UserRole + 1004, IsSubjectImageRole = Qt::UserRole + 1010, FilterActionRole = Qt::UserRole + 1020 }; public: explicit ItemHistoryGraphModel(QObject* const parent = nullptr); ~ItemHistoryGraphModel(); void setMode(Mode mode); Mode mode() const; /** * Set the history subject and the history graph. * Per default, the subject's history graph is read. */ void setHistory(const ItemInfo& subject, const ItemHistoryGraph& graph = ItemHistoryGraph()); ItemInfo subject() const; bool isImage(const QModelIndex& index) const; bool hasImage(const ItemInfo& info); ItemInfo imageInfo(const QModelIndex& index) const; /// Note: There may be multiple indexes for an info. The index found first is returned. QModelIndex indexForInfo(const ItemInfo& info) const; bool isFilterAction(const QModelIndex& index) const; FilterAction filterAction(const QModelIndex& index) const; + ///@{ // QAbstractItemModel implementation virtual QVariant headerData(int section, Qt::Orientation orientation, int role = Qt::DisplayRole) const override; virtual int rowCount(const QModelIndex& parent = QModelIndex()) const override; virtual int columnCount(const QModelIndex& parent = QModelIndex()) const override; virtual Qt::ItemFlags flags(const QModelIndex& index) const override; virtual bool hasChildren(const QModelIndex& parent = QModelIndex()) const override; virtual QModelIndex index(int row, int column, const QModelIndex& parent = QModelIndex()) const override; virtual QModelIndex parent(const QModelIndex& index) const override; virtual QVariant data(const QModelIndex& index, int role = Qt::DisplayRole) const override; virtual bool setData(const QModelIndex& index, const QVariant& value, int role) override; + ///@} DECLARE_MODEL_DRAG_DROP_METHODS /** * Returns an internal image model used for entries representing images. * Note: Set a thumbnail thread on this model if you need thumbnails. */ ItemListModel* imageModel() const; /** * If the given index is represented by the internal image model, * return the image model's index. * Otherwise an invalid index is returned. */ QModelIndex imageModelIndex(const QModelIndex& index) const; private: class Private; Private* const d; }; } // namespace Digikam #endif // DIGIKAM_ITEM_HISTORY_GRAPH_MODEL_H