Was wird benötigt, um BGL-Algorithmen auf bestehende Datenstrukturen anzuwenden (Kanten und Knoten als Vektor)?

Ich habe benutzerdefinierte Datenstrukturen wie folgt:

vector<myVertex *> my_vertices;
vector<myEdge *> my_edges;

Meine Klasse myEdge hat source()- und target()-Methoden, die myVertex* zurückgeben, also sollte sie so wie sie ist ziemlich fertig sein, richtig?

Was äußere Anpassung muss ich tun, um ein BGL-Diagramm mit meinen Containern zu verwenden? Ich bin mir bewusst, dass die Adapterbeispiele im docaber etwas Hilfe wäre sehr willkommen!

Ich interessiere mich für den reinen Basisgraphentyp adjacency_list und bin mir noch nicht sicher, welche Graphtraversalkonzepte ich benötige.

Was ich bisher über die Parameter adjacency_list verstanden habe:

adjacency_list<OutEdgeListS, VertexListS, DirectedS,
             VertexProperty, EdgeProperty, GraphProperty, EdgeListS>

• OutEdgeListS und VertexListS sind Selektoren für die Container, die verwendet werden, um die (1) Kantenliste für jeden der Scheitelpunkte und (2) die Scheitelpunktliste darzustellen. Diese Container halten als Elemente vertex_descriptor und edge_descriptor beziehungsweise. Mein Containertyp ist der einfache std::vector, also muss ich wohl keinen neuen Containertyp wie in example/container_gen.cpp erstellen. Ich muss einfach präzisieren, wahrscheinlich mit graph_traits, dass der Typ meiner Containerelemente Zeiger-auf-Objekt ist.
• VertexProperty und EdgeProperty sind als interner Massenspeicher für Zusatzinformationen, zB Farbetiketten, Kantengewichte… gedacht und bieten seit einigen Jahren das Bundled-Property-Feature.

Ich möchte, dass die Scheitelpunkt- und Kantendeskriptoren nicht standardmäßig Ganzzahlen sind, sondern Zeiger auf meine Objekte sind. Die BGL-Dokumentation weist ausdrücklich darauf hin, dass dies machbar ist in der 2002-Version des Buches12.1.2 :

Eine objektorientierte Graphimplementierung könnte Zeiger verwenden, um zugeordnete Scheitelpunktobjekte aufzuhäufen. Bei der Graph-Traits-Klasse werden diese Unterschiede durch den dem Vertex-Deskriptor zugeordneten Typ verborgen.

Obwohl es aus dem aktuellen 1.70-Online-Dokument verschwunden zu sein scheint.

Am liebsten würde ich so initialisieren:

MyGraph g(const& my_edges,const& my_vertices,
  undirected_tag, some_color, someweights, allow_parallel_edges_tag);

PS Ich bin nicht daran interessiert, Objektzeiger in der property_map zu füllen. Ich bin bereit, ‘default vecS’ nicht zu verwenden, einen std::vector, bei dem der Deskriptor eine ganze Zahl ist. Ich bin bereit, ein ‘benutzerdefiniertes vecS’ als std::vector von Objektzeigern zu verwenden; sowohl für OutEdgeList als auch für VertexList.

Bearbeiten: Dies ist genau die gleiche Frage wie die “1”. von diesem. Außer dass es nie beantwortet wurde … und die vorgeschlagene Lösung war für “2.”, mit property_map und teurem doppeltem Mapping :). Es scheint, dass die meisten Leute, nachdem sie stundenlang Hunderte von SO-Themen ausgegraben haben, die Verwendung von property_maps empfehlen, anstatt mit benutzerdefinierten Containern zu arbeiten. Die Leute neigen dazu, property_maps zu verwenden, um die tatsächlichen Knoten und Kanten zu speichern – ihre Objektzeiger, und lassen die vertex&edge_descriptors reine Standard-Integer-Indizes enthalten. Doch nach dem, was ich hier gelesen habe, gibt es “unter” vertex_descriptor eine interne Real-Index-Schicht, die verstärkt werden kann.

Als Kontext: Ich plane, dijkstra/johnson_all_pairs_shortest_paths (mit Vorgängerkarte und einem Besucher?) Und weiter optimal-dreyfus-wagner für Steinerbäume mit zu verwenden http://paal.mimuw.edu.pl/, eine Bibliothek auf dem bgl. So erstellen Sie einen SQL-Join-Solver für das dbms-erd-Tool pgmodeler https://github.com/pgmodeler/pgmodeler/pull/1232.

20.05.19: Antwort auf die Antwort von sehe

Tolle Information, das Klebstoffe alle Teile zusammen und brachte mich dazu, einige Kernpunkte wie Diagrammkonzepte nachzuholen. Ich habe gefragt, wie Adjazenzlisten mit benutzerdefinierten Datenstrukturen verwendet werden können, und Sie haben erklärt, wie ein vollständig benutzerdefiniertes Diagramm definiert wird.

Ich bin dabei, Kompromisse zwischen Ansätzen zu untersuchen:

1. behalte meine Datenstrukturen so wie sie sind und deine Lösung eines benutzerdefinierten Diagramms. Ich werde keine Zeit mit der Initialisierung verbringen, aber wahrscheinlich viel mehr Zeit damit, Out-Edges zu finden. Geringe Raumkomplexität, aber hohe Zeitkomplexität.
2. Gleicher Ansatz, aber refaktoriere meine Bibliothek, füge dedizierten Speicher hinzu, mit einem Vektor von einfallenden Kanten pro Vertex (als Klassenattribut von myVertex?). Out-Edge-Lookup in konstanter Zeit statt O(log(n)) mit (1) std::equal_range ? Wahrscheinlich die beste Option.
3. Verwenden Sie eine adjacency_list aber und haben Sie die Zeitkomplexitätsgarantien von bgl.
   • Instanziieren Sie eine Standard-Adjazenzliste, richten Sie eine Zwei-Wege-Zuordnung mit meinen Bibliothekscontainern ein / verwenden Sie gebündelte/interne Eigenschaften. Hohe Raumkomplexität; geringe Zeitkomplexität, aber nur für die bgl-Algorithmen wird die Initialisierung lang sein.
   • Möchten Sie auch erläutern, ob eine ordnungsgemäße OutEdgeList und VertexList die Verwendung der Adjacency-List-Klasse mit benutzerdefinierten Containern zu einer Option macht? Verweise auf diese Leisten beibehalten? Ich vermute an dieser Stelle, dass die Implementierung von adjacency_list möglicherweise nicht so flexibel ist.

Die Dokumentation für die Graph-Konzepte finden Sie bequem hier: https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/graph_concepts.html

Sie haben uns also nie gesagt, welche Algorithmen Sie verwenden möchten.

Lassen Sie mich also ein Beispiel herausgreifen: BFS. Die Dokumente sagen, es erfordert:

Ein gerichteter oder ungerichteter Graph. Der Diagrammtyp muss ein Modell von sein Knotenlistendiagramm und Inzidenzdiagramm.

Wenn Sie sich Ihre bereits vorhandenen Datenstrukturen ansehen, sieht es so aus, als ob Sie nur den Anwendungsfall der Vertex-Liste problemlos abdecken.

Die Kanten sind eher als Kantenliste implementiert. Es ist nicht möglich, das Inzidenzdiagramm aus der Kantenliste ohne Laufzeit- oder Speicheraufwand zu emulieren (das ist Mathematik, nichts mit Bibliotheks- oder Codequalität zu tun).

In Wirklichkeit ist es ziemlich wahrscheinlich, dass Sie Teile Ihrer bereits vorhandenen Datenstrukturen weggelassen haben, die für das Problem relevant sind, da die meisten Algorithmen nur für Vertex+Edge-Listen höchst suboptimal sind.

In der Praxis nehme ich an, dass Ihre Kantenliste wie eine klassische Adjazenzliste organisiert sein könnte (z. B. Sortieren nach Quellknoten, sodass Sie eine O (log (n)) -Suche nach Quellknoten haben KÖNNEN).

Für das Beispiel unten Ich gehe davon aus, dass dies der Fall ist. Denken Sie daran, wir sind nur Annäherung die Komplexitätsgarantien von Incidence Graph Concept:

Komplexität garantiert

Das source(), target()und out_edges() Funktionen müssen alle konstante Zeit sein. Das out_degree() Die Funktion muss in der Anzahl der Außenkanten linear sein.

Um diese Anforderungen tatsächlich zu erfüllen, benötigen Sie eine dedizierte Speicherung von Außenkanten pro Scheitelpunkt

Also, lass uns gehen:

Verspotten von YourLibrary

namespace YourLibrary {
    struct myVertex {
    };

    struct myEdge {
        myVertex* _s = nullptr;
        myVertex* _t = nullptr;

        myVertex* source() const { return _s; }
        myVertex* target() const { return _t; }
    };

    using Vertices = std::vector<myVertex *>;
    using Edges = std::vector<myEdge *>;
}

Erfüllung der Diagrammkonzepte

Sie wollten Verweise auf die bereits vorhandenen Datenstrukturen beibehalten:

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        Vertices& _vertices;
        Edges& _edges;

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  { }
    };
}

Jetzt werde ich nur die Liste der erforderlichen Merkmalstypen pro Konzept durchgehen:

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}

Öffnen Sie schließlich den Namensraum erneut, damit ADL diese Funktionen finden kann, die erforderlich sind, um die Kriterien “gültige Ausdrücke” zu erfüllen:

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }
}

Das wäre ungefähr funktionell entspricht einer adjacency_list mit a setS für den Vertex-Container.

Sehen Sie es Lebe auf Coliru

BFS läuft

Alles, was zusätzlich benötigt wird, sind die Argumente des Algorithmus. Sie benötigen sowohl die Farbkarte als auch die Vertexindexkarte. Dies ist völlig normal und wäre auch erforderlich, wenn Sie z adjacency_list<vecS, listS, directedS>.

Ich verstecke die Indexkarte in der MyGraph Wrapper und zeigen Sie die Farbkarte an, damit Sie Ihre Präferenz auswählen können:

Lebe auf Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/container/flat_map.hpp>
#include <algorithm>

namespace YourLibrary {
    struct myVertex {
    };

    struct myEdge {
        myVertex* _s = nullptr;
        myVertex* _t = nullptr;

        myVertex* source() const { return _s; }
        myVertex* target() const { return _t; }
    };

    using Vertices = std::vector<myVertex *>;
    using Edges = std::vector<myEdge *>;
}

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        using Index = boost::container::flat_map<Vertices::value_type, std::size_t>;

        Vertices& _vertices;
        Edges& _edges;
        Index _index;

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  {
            _index.reserve(vv.size());
            std::size_t i = 0;
            for(auto v : vv) { _index[v] = i++; }
        }
    };
}

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }

    // Due to BFD requiring the index_map
    auto get(boost::vertex_index_t, MyGraph const& g) {
        return boost::make_assoc_property_map(g._index);
    }
}

int main() {
    // I hate manual memory management, so let's own some objects
    auto a = std::make_unique<YourLibrary::myVertex>();
    auto b = std::make_unique<YourLibrary::myVertex>();
    auto c = std::make_unique<YourLibrary::myVertex>();
    auto ab = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{a.get(), b.get()});
    auto bc = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{b.get(), c.get()});

    // These were given in your question:
    YourLibrary::Vertices vv { a.get(), b.get(), c.get() };
    YourLibrary::Edges ee { ab.get(), bc.get() };

    // this is the glue required to fulfill the BGL concepts:
    Glue::MyGraph g(vv, ee);

    // this is showing that you can now BFS on it
    using V = boost::graph_traits<Glue::MyGraph>::vertex_descriptor;
    V start_vertex = a.get();
    std::map<V, boost::default_color_type> color_data;

    boost::breadth_first_search(g, start_vertex,
            boost::visitor(boost::default_bfs_visitor{})
            .color_map(boost::make_assoc_property_map(color_data)));
}

Fazit

Algorithmen haben Anforderungen, und solange Sie diese erfüllen, können Sie jede beliebige Datenstruktur verwenden.

In diesem Fall sollten Sie sich über die getroffenen Annahmen wirklich sicher sein und diese zu den hinzufügen MyGraph Konstrukteur:

assert(std::is_sorted(_edges.begin(), _edges.end(), EdgeOrder{}));