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

Lesezeit: 13 Minuten

Benutzer-Avatar
AIZweifel

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.

  • Möchten Sie dies mithilfe von #include auf ein bestimmtes minimal reproduzierbares Beispiel eingrenzen? Ich kann es anfassen. Ich kenne die allgemeinen Grundsätze. Warten Sie … dieser Link, von dem Sie sagten, dass er nie beantwortet wurde, hat eine akzeptierte Antwort mit Upvotes.

    – Kenny Ostrom

    18. Mai 2019 um 21:34 Uhr


  • Guter Ablauf mit den Antworten. 1. Die Kosten für die Zeitkomplexität sind möglicherweise nicht allzu hoch. Es hängt von der Skalierung und Verteilung ab (log (N) ist ziemlich schnell, WENN Ihre Kanten tatsächlich geordnet sind. Es wäre nicht schwer, einen kleinen Lookup-Cache im Glue-Wrapper-Konstruktor hinzuzufügen (MyGraph).

    – sehen

    20. Mai 2019 um 14:53 Uhr

  • Ich stimme zu, dass 2. wahrscheinlich optimal und konzeptionell am saubersten ist (es erfordert BGL-spezifischen Code, wäre aber unaufdringlich, sodass die enge Kopplung vermieden wird).

    – sehen

    20. Mai 2019 um 14:53 Uhr

  • 3. [ad 1st bullet] Simplist, wenn Sie das Diagramm nicht oft ändern und die Zuordnungen beibehalten müssen, scheint der geringste Code / die geringste Versorgung mit BGL-Magie zu sein. Sie werden am besten in der Lage sein, z. B. vorhandene Arbeit auf StackOverflow zu nutzen

    – sehen

    20. Mai 2019 um 14:57 Uhr

  • 3. [ad 2nd bullet] Ich stimme zu, dass es nicht flexibel genug sein wird. Ich denke, unabhängig davon, wie Sie es drehen, wird adjacency_list davon ausgehen, dass es den Out-Edge-List-Container erstellen kann (also Referenzen sind out) und selbst wenn Sie es dazu bringen, einen “gefälschten Container-Wrapper” zu verwenden, um tatsächlich auf Ihre Scheitelpunktliste zu verweisen würde wahrscheinlich gegen einige Annahmen in der Bibliothek verstoßen. Ich denke, per Definition haben Graph-Modelle eine Wertsemantik in BGL). Ist es nicht wert?

    – sehen

    20. Mai 2019 um 14:57 Uhr

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{}));

  • Entschuldigung, in der schmutzigen Änderungsgeschichte dieses Beitrags habe ich den Kontext unten und etwas spät hinzugefügt. Danke für die ausführliche Antwort, anpackendes Lesen.

    – AIDzweifel

    19. Mai 2019 um 0:11 Uhr

  • Da Stackoverflow jetzt wirklich von Threads im Forumsstil abrät … Ich habe meiner ursprünglichen Frage meine Reaktion auf Ihre großartige Antwort angehängt.

    – AIDzweifel

    19. Mai 2019 um 23:42 Uhr

  • Ja. Ich denke, das hat es nicht wirklich gelöst. Ich ging aber mit und kommentierte Punkt für Punkt. In Zukunft und im Interesse zukünftiger Besucher, die nach Antworten suchen, können Sie eine neue Frage stellen. Das ist /mehr Arbeit/ und es ist schwieriger, die Frage sinnvoll zu stellen, aber zumindest lässt es uns über das Gesamtbild und den Wert der Fragen für die breite Öffentlichkeit nachdenken 🙂 Cheers

    – sehen

    20. Mai 2019 um 14:59 Uhr


  • Danke für diese ausführliche Antwort, sie war sehr hilfreich für mein Verständnis. Eine Sache, die ich immer noch versuche zu verstehen, ist, warum dieses Beispiel nicht mit Funktionen wie funktioniert boost::out_edges? Es scheint, als müsste es seitdem funktionieren Glue::MyGraph modelliert das IncidenceGraph-Konzept, aber ich erhalte Typabzugsfehler boost::out_edges(start_vertex, g); — vielleicht übersehe ich etwas Offensichtliches?

    – Bosmacen

    23. Februar 2021 um 20:14 Uhr


  • Fragte.

    – Bosmacen

    24. Februar 2021 um 13:38 Uhr

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

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy