Design einer Klasse für Graphen



  • Hallöchen,
    ich schreibe gerade aus Spaß und zur Übung eine Klasse für Graphen.
    Dazu verwende ich eine Adjazenzliste, d.h. zu jedem Knoten speichere ich eine Liste von Kanten.

    Das ganze ist mit Templates realisiert, sodass jede Kante Kanteninformationen vom Typ Edge_Data und jeder Knoten Knoteninformationen vom Typ Vertex_Data hat. Dadurch müsste man eine große Flexibilität erreichen.

    Grob skizziert sieht die Klasse Graph jetzt wie folgt aus:

    template <typename Edge_Data, typename Vertex_Data>
    class Graph
    {
    public:
        class Vertex;
        class Edge;
    
    private:
        std::vector<Vertex> node;
    
    public:
    
        ///Datenstrukturen zur Repräsentierung von Kanten und Knoten
    
        class Edge
        {
        public:
                                            Edge(std::string start,
                                                 std::string finish,
                                                 std::string name,
                                                 std::shared_ptr<Edge_Data> data 
                                                 =Edge_Data{}));
    
            const Vertex&                   start_vertex() const;
            const Vertex&                   finish_vertex() const;
    
            const Edge_Data&                get_data() const;
            Edge_Data&                      get_data();
    
            //...
    
        private:
            std::string                     name;
            const Vertex&                   start;      //Anfangsknoten
            const Vertex&                   finish;    //Endknoten
            std::shared_ptr<Edge_Data>      data;       //Bei einem ungerichteten Graphen teilen sich zwei Kanten eine Kanteninformation
        };
    
        class Vertex
        {
        public:
                                            Vertex(std::string name, Vertex_Data  
                                            data = Vertex_Data{});
    
            const Vertex_Data&              get_data() const;
            Vertex_Data&                    get_data();
    
            const Edge&                     get_edge(const std::string& finish) 
                                            const;
    
            Edge&                           get_edge(const std::string& finish);
    
            const std::list<Edge>&          get_adjacent_edges() const;
            std::list<Edge>                 get_adjacent_edges();
    
            //...
    
        private:
            std::string                     name;
            Vertex_Data                     data;
            std::list<Edge>                 adjacency_list;     
        };
    
        Graph(std::initializer_list<Vertex>, std::initializer_list<Edge>,bool directed = true);
    
        //Zugrif auf Kanten
        //...
    
        //Zugriff auf Knoten
        //...
    };
    

    Jetzt ergeben sich einige Probleme, für die ich auf nach langem Nachdenken keine elegante Lösung gefunden habe...

    1. Bei einem ungerichteten Graphen werden Kanten doppekt gespeichert, also (u, v) und (v, u) beispielsweise. Jetzt sollen Änderungen aber konsistent seien, deshalb sind die Kanteninformationen als shared_ptr gespeichert. Lieber wäre es mir aber, wenn die Kantenobjekte gleich wären. Da dachte ich anfangs an eine list von shared_ptr, aber ich würde halt lieber keine list von shared_ptr als Adjazenzliste zurückgeben wollen...

    2. Eine Kante speichert eine Konstante Referenz auf die beiden Endknoten. Eine Kante kann also allein anhand von Knotennamen nicht rausfinden, wo der Knoten gespeichert ist, bzw. ob es ihn überhaupt gibt. Ein Graph lässt sich also nicht durch einen Konstruktor erstellen wie er im Code geschrieben ist...
    Was ich will, ist einen Graphen durch die folgende Syntax beispielsweise initialisieren zu können:

    Graph<int, int> G{{"a", "b", "c"}, {{"a", "b", "Kante_a_b", 10}, {"b", "c", "Kante_b_c", -5}};
    

    Eine Möglichkeit wäre es jetzt den Graph Konstruktor so zu verändern, dass statt Vertex alle möglichen Weisen einen Vertex zu konstruieren als Parameter verwendet wird und das gleiche für Edge. Also so ungefähr:

    Graph(std::initializer_list<std::pair<std::string, Vertex_Data>> Vertex_List,
    std::initializer_list<std::pair<std::pair<std::string, std::string>, Edge_Data>> Edge_List);
    

    Wirklich elegant ist das nicht, und bei mehreren Arten einen Vertex bzw. eine Edge zu konstruieren muss der Graph Konstruktor auch entsprechend häufig überladen werden. Und wenn die Art und Weise wie eine Kante konstruiert wird, geändert wird, muss man wieder auch alle abhängigen Graph Konstruktoren anpassen.

    Ich hoffe der Text war jetzt nicht zu lang und unverständlich...
    Gruß und vielen Dank schon mal
    Paul

    PS: Über andere Anmerkungen zum Design oder dem bisschen Code oder anderer Kritik freue ich mich ausdrücklich, da ich in meinem Bekanntenkreis keinen einzigen Programmierer habe, und ich mich somit quasi nicht mit anderen darüber austauschen kann...



  • Hoi,

    Ein paar Anregungen könntest du dir bei folgenden Bibliotheken holen.
    Die sind alle open-source. Insbesondere das Speichern der Daten beim Knoten wird überall anders gelöst.

    lemon graph library https://lemon.cs.elte.hu/trac/lemon
    boost graph library http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/index.html
    boost parallel grapg library http://www.boost.org/doc/libs/1_56_0/libs/graph_parallel/doc/html/mpi_bsp_process_group.html

    Viele Grüße



  • Danke, ich schau es mir mal an und gucke ob es mir weiterhilft...
    Gruß
    Paul



  • Ich habe mir die Boost Graphenbibliothek mal angeschaut, und ein paar Dinge übernommen:

    enum class Direction
    {
        UNDIRECTED,     //ungerichteter Graph
        DIRECTED,       //gerichteter Graph, der zu jedem Knoten nur ausgehende Kanten speicher
        BIDIRECTIONAL  //gerichteter Graph, der zusaätzlich zu jedem Knoten die eingehenden Kanten speichert
    };
    
    /** Edge_Data:      gibt die Art der Kanteninformationen an
        Vertex_Data:    gibt die Art der Knoteninformationen an
        Edge_ID: gibt   die Art der Kennzeichnung einer Kante an    (üblicherweise eine Zahl, oder ein String)
        Vertex_ID:      gibt die Art der Kennzeichnung eines Knotens an  (üblicherweise eine Zahl oder ein String)
    **/
    template<typename Edge_Data, typename Vertex_Data, typename Edge_ID, typename Vertex_ID>
    class adjacency_list
    {
    private:
        class Edge;
        class Vertex;
    
    public:
    
        //Knoten werden in einer Hashmap gespeichert
        using const_vertex_iterator = typename std::unordered_map<Vertex_ID, Vertex>::const_iterator;
        using vertex_iterator = typename std::unordered_map<Vertex_ID, Vertex>::iterator;
        //Kanten werden in einer Liste gespeichert
        using const_edge_iterator = typename std::list<Edge>::const_iterator;
        using edge_iterator = typename std::list<Edge>::iterator;
    
        //Default Konstruktor
        adjacency_list(Direction d = Direction::DIRECTED);
        //Den Graphen aus gegebenen Knoten und Kanten erstellen
        adjacency_list(std::initializer_list<Vertex_ID> vertex, std::pair<std::pair<Vertex_ID, Vertex_ID>, Edge_Data> edge = {}, Direction d = Direction::DIRECTED);
        //Den Graphen nur aus gegebenen Kanten erstellen, dabei werden die Knoten aus der Kantenliste hergeleitet
        adjacency_list(std::pair<std::pair<Vertex_ID, Vertex_ID>, Edge_Data> edge, Direction d = Direction::DIRECTED);
    
        void add_vertex(Vertex_ID id, Vertex_Data data = Vertex_Data{});
    
        void add_egde(Vertex_ID start, Vertex_ID finnish, Edge_Data data = Edge_Data{});
    
        //Entfernt alle Kanten (start, finnish) in einem gerichteten und bidirektionalen Graphen,
        //und alle Kanten zwischen den beiden Knoten aus einem ungerichteten Graphen
        void remove_edge(Vertex_ID start, Vertex_ID finnish);
    
        void remove_edge(Edge_ID e);    //Entfernt die Kante es aus dem Graphen
    
        //Zugriff auf die Knoten
        bool find(const Vertex_ID& v) const;
    
        std::pair<vertex_iterator, vertex_iterator> get_vertices();
        std::pair<const_vertex_iterator, const_vertex_iterator> get_vertices() const;
    
        const Vertex_Data& get_vertex_data(const Vertex_ID& v) const;
        void set_vertex_data(const Vertex_ID& v, Vertex_Data data);
    
        //Zugriff auf die Kanten
        bool find(const Edge_ID& e) const;
    
        std::pair<edge_iterator, edge_iterator> get_adjacent_edges(Vertex_ID v);
        std::pair<const_edge_iterator, const_edge_iterator> get_adjacent_edges(Vertex_ID v) const;
    
        void set_edge_data(const Edge_ID& e, Edge_Data data);
        //Die Kanteninformation aller Kanten zwischen den angegebenen Knoten ändern
        void set_edge_data(const Vertex_ID& start, const Vertex_ID& finish, Edge_Data data);
    
        const Edge_Data& get_edge_data(const Edge_ID& e);
    
        //Die Kantengewichte aller Kanten zwischen den angegebenen Knoten zurückgeben
        std::vector<const Edge_Data&> get_edge_data(const Vertex_ID& start, const Vertex_ID& finish);
    
    private:
        std::unordered_map<Vertex_ID, Vertex> vertex_table;
    
    };
    

    Das müsste doch für Algorithmen wie Dijkstra oder Bellman-Ford ausreichen, oder?

    Spannend fände ich es auch mal damit Flussnetzwerke zu bauen und den Ford-Fulkerson Algorithmus zu implementieren...

    Eine Sache gibt es aber noch, die noch nicht gelöst ist (wahrscheinlich gibt es noch mehr, nur sehe ich die gerade nicht 🙂 ):
    Bei einem bidirektionalen Graphen sollte man Zugriff auf die Out-Edges und auf die In-Edges eines Knotens haben, und bei gerichteten und ungerichteten Graphen nur auf die Out-Edges (wobei beim ungerichteten Graphen Out-Edges = In-Edges..).
    Wie setze ich das am besten in das schon geschriebene Interface um?

    Gruß
    Paul


Anmelden zum Antworten