diff --git a/core/libs/database/imagehistory/imagehistorygraph.cpp b/core/libs/database/imagehistory/imagehistorygraph.cpp index 70f8ce018b..9a86649dc1 100644 --- a/core/libs/database/imagehistory/imagehistorygraph.cpp +++ b/core/libs/database/imagehistory/imagehistorygraph.cpp @@ -1,883 +1,891 @@ /* ============================================================ * * This file is a part of digiKam project * http://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 "imagehistorygraph.h" // Local includes #include "digikam_debug.h" #include "dimagehistory.h" #include "imagescanner.h" #include "imagehistorygraphdata.h" namespace Digikam { -// ----------------------------------------------------------------------------------------------- - class Q_DECL_HIDDEN ImageHistoryGraphDataSharedNull : public QSharedDataPointer { public: - ImageHistoryGraphDataSharedNull() : QSharedDataPointer(new ImageHistoryGraphData) {} + ImageHistoryGraphDataSharedNull() : QSharedDataPointer(new ImageHistoryGraphData) + { + } }; Q_GLOBAL_STATIC(ImageHistoryGraphDataSharedNull, imageHistoryGraphDataSharedNull) // ----------------------------------------------------------------------------------------------- ImageInfo HistoryVertexProperties::firstImageInfo() const { if (infos.isEmpty()) { return ImageInfo(); } return infos.first(); } bool HistoryVertexProperties::markedAs(HistoryImageId::Type type) const { if (referredImages.isEmpty()) { return false; } - foreach(const HistoryImageId& ref, referredImages) + 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) + 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 ImageInfo& info) const { return infos.contains(info); } bool HistoryVertexProperties::operator==(qlonglong id) const { - foreach(const ImageInfo& info, infos) + foreach (const ImageInfo& 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) + foreach (const HistoryImageId& id, referredImages) { if (ImageScanner::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 ImageInfo& 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 ImageInfo& info, props.infos) + foreach (const ImageInfo& 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 ImageHistoryGraphData::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 ImageHistoryGraphData::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 UUID // 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 ImageInfo - foreach(const qlonglong& id, ImageScanner::resolveHistoryImageId(imageId)) + foreach (const qlonglong& id, ImageScanner::resolveHistoryImageId(imageId)) { ImageInfo info(id); //qCDebug(DIGIKAM_DATABASE_LOG) << "Found info id:" << info.id(); infos << info; if (v.isNull()) { v = findVertexByProperties(info); } } } applyProperties(v, infos, QList() << imageId); //qCDebug(DIGIKAM_DATABASE_LOG) << "Returning vertex" << v; return v; } HistoryGraph::Vertex ImageHistoryGraphData::addVertex(qlonglong id) { return addVertex(ImageInfo(id)); } HistoryGraph::Vertex ImageHistoryGraphData::addVertex(const ImageInfo& 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 ImageHistoryGraphData::addVertexScanned(qlonglong id) { // short version where we do not read information about id from an ImageInfo Vertex v = findVertexByProperties(id); applyProperties(v, QList() << ImageInfo(id), QList()); + return v; } -void ImageHistoryGraphData::applyProperties(Vertex& v, const QList& infos, const QList& ids) +void ImageHistoryGraphData::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 ImageInfo& info, infos) + foreach (const ImageInfo& info, infos) { props += info; } - foreach(const HistoryImageId& id, ids) + foreach (const HistoryImageId& id, ids) { props += id; } } int ImageHistoryGraphData::removeNextUnresolvedVertex(int index) { QList vs = vertices(); - for (; index ImageHistoryGraphData::categorize() const { QHash types; - foreach(const Vertex& v, vertices()) + 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)) + foreach (const Edge& e, edges(v, EdgesToLeaf)) { const HistoryEdgeProperties& props = properties(e); if (props.actions.isEmpty()) { continue; // unclear situation, ignore } // See bug 277502 if ((props.actions.first().flags() & FilterAction::ExplicitBranch)) { allBranches = false; break; } } if (allBranches) { type |= HistoryImageId::Current; } } types[v] = type; } return types; } // ----------------------------------------------------------------------------------------------- ImageHistoryGraph::ImageHistoryGraph() : d(*imageHistoryGraphDataSharedNull) { } ImageHistoryGraph::ImageHistoryGraph(const ImageHistoryGraph& other) : d(other.d) { } ImageHistoryGraph::~ImageHistoryGraph() { } ImageHistoryGraph& ImageHistoryGraph::operator=(const ImageHistoryGraph& other) { d = other.d; return *this; } bool ImageHistoryGraph::isNull() const { return d == *imageHistoryGraphDataSharedNull; } bool ImageHistoryGraph::isEmpty() const { return d->isEmpty(); } bool ImageHistoryGraph::isSingleVertex() const { return d->vertexCount() == 1; } bool ImageHistoryGraph::hasEdges() const { return d->hasEdges(); } ImageHistoryGraphData& ImageHistoryGraph::data() { return *d; } const ImageHistoryGraphData& ImageHistoryGraph::data() const { return *d; } void ImageHistoryGraph::clear() { *d = HistoryGraph(); } ImageHistoryGraph ImageHistoryGraph::fromInfo(const ImageInfo& info, HistoryLoadingMode loadingMode, ProcessingMode processingMode) { ImageHistoryGraph graph; if (loadingMode & LoadRelationCloud) { graph.addRelations(info.relationCloud()); } if (loadingMode & LoadSubjectHistory) { graph.addHistory(info.imageHistory(), info); } if (loadingMode & LoadLeavesHistory) { - foreach(const ImageInfo& leaf, graph.leafImages()) + foreach (const ImageInfo& leaf, graph.leafImages()) { if (leaf != info) { graph.addHistory(leaf.imageHistory(), leaf); } } } if (processingMode == PrepareForDisplay) { graph.prepareForDisplay(info); } return graph; } void ImageHistoryGraph::addHistory(const DImageHistory& givenHistory, const ImageInfo& historySubject) { addHistory(givenHistory, historySubject.historyImageId()); } void ImageHistoryGraph::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 ImageHistoryGraph::addScannedHistory(const DImageHistory& history, qlonglong historySubjectId) { d->addHistory(history, historySubjectId); } void ImageHistoryGraphData::addHistory(const DImageHistory& history, qlonglong extraCurrent/*=0*/) { if (history.isEmpty()) { return; } HistoryGraph::Vertex last; HistoryEdgeProperties edgeProps; - foreach(const DImageHistory::Entry& entry, history.entries()) + 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 ImageHistoryGraph::addRelations(const QList >& pairs) { HistoryGraph::Vertex v1, v2; typedef QPair IdPair; - foreach(const IdPair& pair, pairs) + 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 ImageHistoryGraph::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) + 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 ImageHistoryGraph::hasUnresolvedEntries() const { - foreach(const HistoryGraph::Vertex& v, d->vertices()) + foreach (const HistoryGraph::Vertex& v, d->vertices()) { if (d->properties(v).infos.isEmpty()) { return true; } } return false; } void ImageHistoryGraph::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; ivertexCount(); ) { i = d->removeNextUnresolvedVertex(i); } } void ImageHistoryGraph::sortForInfo(const ImageInfo& 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); ImageScanner::sortByProximity(props.infos, subject); } } void ImageHistoryGraph::prepareForDisplay(const ImageInfo& subject) { reduceEdges(); dropUnresolvedEntries(); sortForInfo(subject); } QList > ImageHistoryGraph::relationCloud() const { QList > pairs; - ImageHistoryGraphData closure = d->transitiveClosure(); + ImageHistoryGraphData closure = ImageHistoryGraphData(d->transitiveClosure()); QList edges = closure.edgePairs(); - foreach(const HistoryGraph::VertexPair& edge, edges) + foreach (const HistoryGraph::VertexPair& edge, edges) { - foreach(const ImageInfo& source, closure.properties(edge.first).infos) + foreach (const ImageInfo& source, closure.properties(edge.first).infos) { - foreach(const ImageInfo& target, closure.properties(edge.second).infos) + foreach (const ImageInfo& target, closure.properties(edge.second).infos) { pairs << QPair(source.id(), target.id()); } } } return pairs; } QPair, QList > ImageHistoryGraph::relationCloudParallel() const { QList subjects, objects; - ImageHistoryGraphData closure = d->transitiveClosure(); + ImageHistoryGraphData closure = ImageHistoryGraphData(d->transitiveClosure()); QList edges = closure.edgePairs(); - foreach(const HistoryGraph::VertexPair& edge, edges) + foreach (const HistoryGraph::VertexPair& edge, edges) { - foreach(const ImageInfo& source, closure.properties(edge.first).infos) + foreach (const ImageInfo& source, closure.properties(edge.first).infos) { - foreach(const ImageInfo& target, closure.properties(edge.second).infos) + foreach (const ImageInfo& target, closure.properties(edge.second).infos) { subjects << source.id(); objects << target.id(); } } } return qMakePair(subjects, objects); } QList ImageHistoryGraph::allImages() const { return d->toInfoList(d->vertices()); } QList ImageHistoryGraph::allImageIds() const { QList ids; - foreach(const HistoryGraph::Vertex& v, d->vertices()) + foreach (const HistoryGraph::Vertex& v, d->vertices()) { - foreach(const ImageInfo& info, d->properties(v).infos) + foreach (const ImageInfo& info, d->properties(v).infos) { ids << info.id(); } } return ids; } QList ImageHistoryGraph::rootImages() const { return d->toInfoList(d->roots()); } QList ImageHistoryGraph::leafImages() const { return d->toInfoList(d->leaves()); } QHash ImageHistoryGraph::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 ImageInfo& info, props.infos) { types[info] = type; } } return types; } static QString toString(const HistoryVertexProperties& props) { QString s; s = QLatin1String("Ids: "); QStringList ids; foreach(const ImageInfo& 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 ImageHistoryGraph& 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/imagehistory/imagehistorygraph_boost.h b/core/libs/database/imagehistory/imagehistorygraph_boost.h index 5320e4be41..5119df46ec 100644 --- a/core/libs/database/imagehistory/imagehistorygraph_boost.h +++ b/core/libs/database/imagehistory/imagehistorygraph_boost.h @@ -1,1599 +1,1640 @@ /* ============================================================ * * This file is a part of digiKam project * http://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_IMAGE_HISTORY_GRAPH_BOOST_H #define DIGIKAM_IMAGE_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" /** 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 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 { - /** - * Each edge is directed: "vertex1 -> vertex2". - * This direction has a meaning with methods such as - * roots() or leaves(). - */ - /// 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 Graph { public: typedef boost::adjacency_list< boost::vecS, /// Standard storage. listS was desirable, but many algorithms work only with vecS boost::vecS, boost::bidirectionalS, /// directed graph boost::property >, 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()) { } 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) { } 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) + : 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 */ + /** + * 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)); + flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? OutboundEdges + : InboundEdges)); } if (flags & EdgesToRoot) { - flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? InboundEdges : OutboundEdges)); + flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? InboundEdges + : OutboundEdges)); } QList vertices; if (flags & OutboundEdges) { vertices << toVertexList(boost::adjacent_vertices(v, graph)); } if (flags & InboundEdges) { vertices << toVertexList(boost::inv_adjacent_vertices(v, graph)); } return vertices; } // 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)); + flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? OutboundEdges + : InboundEdges)); } if (flags & EdgesToRoot) { - flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? InboundEdges : OutboundEdges)); + 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)); + flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? OutboundEdges + : InboundEdges)); } if (flags & EdgesToRoot) { - flags = (AdjacencyFlags)(flags | (direction == ParentToChild ? InboundEdges : OutboundEdges)); + 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) + 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 vertices; try { boost::topological_sort(graph, std::back_inserter(vertices)); } 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(vertices.begin(), vertices.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; } + 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 vertices; Path path; path.shortestPath(graph, v1); if (path.isReachable(v2)) { vertices = listPath(v2, v1, path.predecessors, ChildToParent); vertices.prepend(v1); } else { // assume inverted parameters path.shortestPath(graph, v2); if (path.isReachable(v1)) { vertices = listPath(v1, v2, path.predecessors); vertices.append(v2); } } return vertices; } /** * 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 { QList vertices; 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) + 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 + 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 + 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 + 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 QList orderedTree; - foreach(const Vertex& v, presortedVertices) + 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 vertices; vertices << rootsOf(ref); if (vertices.size() == vertexCount()) return vertices; GraphSearch search; search.breadthFirstSearch(graph, vertices.first(), direction == ChildToParent); QList bfs = search.vertices; - foreach(const Vertex& v, vertices) + foreach (const Vertex& v, vertices) { bfs.removeOne(v); } vertices << bfs; if (vertices.size() == vertexCount()) return vertices; // sort in any so far unreachable nodes vertex_range_t range = boost::vertices(graph); - for (vertex_iter it = range.first; it != range.second; ++it) + for (vertex_iter it = range.first ; it != range.second ; ++it) { if (!vertices.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 = vertices.size(); - foreach(const Vertex& c, childBfs) + foreach (const Vertex& c, childBfs) { int foundAt = vertices.indexOf(c); if (foundAt == -1) { toInsert << c; } else { minIndex = qMin(foundAt, minIndex); } } - foreach(const Vertex& c, toInsert) + foreach (const Vertex& c, toInsert) { vertices.insert(minIndex++, c); } } } return vertices; } /** * 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 vertices; vertices = rootsOf(ref); if (vertices.size() == vertexCount() || vertices.isEmpty()) return vertices; GraphSearch search; search.depthFirstSearchSorted(graph, vertices.first(), direction == ChildToParent, lessThan); QList dfs = search.vertices; - foreach(const Vertex& v, vertices) + foreach (const Vertex& v, vertices) { dfs.removeOne(v); } vertices << dfs; return search.vertices; } protected: QList treeFromPredecessors(const Vertex& v, const VertexVertexMap& predecessors) const { QList vertices; vertices << v; treeFromPredecessorsRecursive(v, vertices, predecessors); + return vertices; } - void treeFromPredecessorsRecursive(const Vertex& v, QList& vertices, const VertexVertexMap& predecessors) const + void treeFromPredecessorsRecursive(const Vertex& v, + QList& vertices, + const VertexVertexMap& predecessors) const { QList children = predecessors.keys(v); vertices << children; - foreach(const Vertex& child, 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) + 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); + vertex_range_t range = boost::vertices(graph); - for (vertex_iter it = range.first; it != range.second; ++it) + 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) + 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) + 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 vertices; vertex_range_t range = boost::vertices(graph); - for (vertex_iter it = range.first; it != range.second; ++it) + for (vertex_iter it = range.first ; it != range.second ; ++it) { if ( (inOrOut ? in_degree(*it, graph) : out_degree(*it, graph)) == 0) { vertices << *it; } } return vertices; } QList findZeroDegreeFrom(const Vertex& v, bool inOrOut) const { bool invertGraph = (direction == ChildToParent); if (!inOrOut) invertGraph = !invertGraph; GraphSearch search; search.breadthFirstSearch(graph, v, invertGraph); QList vertices; - foreach(const Vertex& candidate, search.vertices) + foreach (const Vertex& candidate, search.vertices) { - if ( (inOrOut ? in_degree(candidate, graph) : out_degree(candidate, graph)) == 0) + if ( (inOrOut ? in_degree(candidate, graph) + : out_degree(candidate, graph)) == 0) { vertices << candidate; } } return vertices; } - /** * 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 weight_map(boost::ref_property_map::edge_descriptor,int>(weight)). // 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 weight_map(boost::ref_property_map::edge_descriptor,int>(weight)). // Invert the default compare method: With greater, we get the longest path distance_compare(std::greater()). // will be returned if a node is unreachable distance_inf(-1). // 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* q) : q(q) {} + 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 + class DepthFirstSearchVisitor : public boost::default_dfs_visitor, + public CommonVisitor { public: - explicit DepthFirstSearchVisitor(GraphSearch* q) : CommonVisitor(q) {} + 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* q) : CommonVisitor(q) {} + 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) { } - const GraphType& 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 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. - std::sort(outEdges.begin(), outEdges.end(), lessThanMapEdgeToTarget(g, lessThan)); + std::sort(outEdges.begin(), + outEdges.end(), + lessThanMapEdgeToTarget(g, lessThan)); - foreach(const edge_descriptor& e, outEdges) + foreach (const edge_descriptor& e, outEdges) { - Vertex v = boost::target(e, g); + 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 */ QList mostRemoteNodes(const VertexIntMap& distances) const { typename VertexIntMap::const_iterator it; int maxDist = 1; QList candidates; - for (it = distances.begin(); it != distances.end(); ++it) + 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 listPath(const Vertex& root, + const Vertex& target, + const VertexVertexMap& predecessors, + MeaningOfDirection dir = ParentToChild) const { QList vertices; - for (Vertex v = root; v != target; v = predecessors.value(v)) + for (Vertex v = root ; v != target ; v = predecessors.value(v)) { //qDebug() << "Adding waypoint" << id(v); if (dir == ParentToChild) { vertices.append(v); } else { vertices.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 vertices; } 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_IMAGE_HISTORY_GRAPH_BOOST_H diff --git a/core/libs/database/imagehistory/imagehistorygraphdata.h b/core/libs/database/imagehistory/imagehistorygraphdata.h index df7cb4b9b7..013718e9ac 100644 --- a/core/libs/database/imagehistory/imagehistorygraphdata.h +++ b/core/libs/database/imagehistory/imagehistorygraphdata.h @@ -1,155 +1,155 @@ /* ============================================================ * * This file is a part of digiKam project * http://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. * * ============================================================ */ #ifndef DIGIKAM_IMAGE_HISTORY_GRAPH_DATA_H #define DIGIKAM_IMAGE_HISTORY_GRAPH_DATA_H // Qt includes #include // Local includes #include "filteraction.h" #include "historyimageid.h" #include "imagehistorygraph_boost.h" namespace Digikam { class ImageInfo; +/** + * Every vertex has one associated object of this class + * + * All entries in a vertex refer to _identical_ images. + * There can be multiple referred images in a history entry. + * Each single HistoryImageId can resolve into none, one, + * or multiple ImageInfos. + * So there is no mapping between the two fields here. + * + * If an image is created from multiple source images (panorama etc.), + * there will be one vertex per source image! + */ class HistoryVertexProperties { public: - /** - * Every vertex has one associated object of this class - * - * All entries in a vertex refer to _identical_ images. - * There can be multiple referred images in a history entry. - * Each single HistoryImageId can resolve into none, one, - * or multiple ImageInfos. - * So there is no mapping between the two fields here. - * - * If an image is created from multiple source images (panorama etc.), - * there will be one vertex per source image! - */ - - QString uuid; - QList referredImages; - QList infos; - ImageInfo firstImageInfo() const; bool markedAs(HistoryImageId::Type) const; bool alwaysMarkedAs(HistoryImageId::Type) const; bool operator==(const QString& uuid) const; bool operator==(const ImageInfo& info) const; bool operator==(qlonglong id) const; bool operator==(const HistoryImageId& info) const; HistoryVertexProperties& operator+=(const QString& uuid); HistoryVertexProperties& operator+=(const ImageInfo& info); HistoryVertexProperties& operator+=(const HistoryImageId& info); + +public: + + QString uuid; + QList referredImages; + QList infos; }; QDebug operator<<(QDebug dbg, const HistoryVertexProperties& props); QDebug operator<<(QDebug dbg, const HistoryImageId& id); // ------------------------------------------------------------------------------ +/** + * Every edge has one associated object of this class. + * + * For two vertices v1, v2 with and edge e, v1 -> v2, + * describes the actions necessary to create v2 from v2: + * v1 -> actions[0] -> ... -> actions[n] = v2. + */ class HistoryEdgeProperties { public: - /** - * Every edge has one associated object of this class. - * - * For two vertices v1, v2 with and edge e, v1 -> v2, - * describes the actions necessary to create v2 from v2: - * v1 -> actions[0] -> ... -> actions[n] = v2. - */ - QList actions; HistoryEdgeProperties& operator+=(const FilterAction& action); }; typedef Graph HistoryGraph; // ------------------------------------------------------------------------------ class ImageHistoryGraphData : public HistoryGraph, public QSharedData { public: ImageHistoryGraphData() - : HistoryGraph(ChildToParent) + : HistoryGraph(ChildToParent) { } - ImageHistoryGraphData(const HistoryGraph& g) // krazy:exclude=explicit - : HistoryGraph(g) + explicit ImageHistoryGraphData(const HistoryGraph& g) + : HistoryGraph(g) { } ImageHistoryGraphData& operator=(const HistoryGraph& g) { HistoryGraph::operator=(g); return *this; } Vertex addVertex(const HistoryImageId& id); Vertex addVertex(const QList& imageIds); Vertex addVertex(qlonglong id); Vertex addVertexScanned(qlonglong id); Vertex addVertex(const ImageInfo& info); void addHistory(const DImageHistory& givenHistory, qlonglong extraCurrent = 0); int removeNextUnresolvedVertex(int begin); inline QList toInfoList(const QList& vertices) const { QList infos; - foreach(const HistoryGraph::Vertex& v, vertices) + foreach (const HistoryGraph::Vertex& v, vertices) { infos << properties(v).infos; } return infos; } QHash categorize() const; protected: void applyProperties(Vertex& v, const QList& infos, const QList& ids); }; } // namespace Digikam #endif // DIGIKAM_IMAGE_HISTORY_GRAPH_DATA_H