Reprezentacja grafu :: 4programmers.net

wazxse5

2018-01-13T20:33:36+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: Kraków
Postów: 95

0

Cześć!
Mam za zadanie napisać program który będzie miał możliwość implementacji różnych algorytmów grafowych, ewentualnie potem dorobię do tego jakiś gui.
Zacząłem od zdefiniowania klasy grafu. I tu pojawia się moje pytanie. W jaki sposób najlepiej reprezentować graf, jak powinna wyglądać klasa grafu?
Chcę by obejmowała ona różne rodzaje grafów; skierowanie, nieskierowanie, wielokrawędziowe, z wagami, z pętlami, w ogóle żeby była jak najszersza.
Zdefiniowałem klasy grafu, wierzchołka i krawędzi. Na razie mam tyle:

Kopiuj

#include <vector>
#include "Edge.h"
#include "Vertex.h"

class Graph {
private:
    int size;
    bool directed;

    // tablica wierzchołków
    std::vector<Vertex> vertices;
    // tablica krawędzi
    std::vector<Edge> edges;
    // macierz sąsiedztwa, dwuwymiarowa tablica zbiorów krawędzi
    std::vector<std::vector<std::vector<Edge*>>> matrix;

public:
    //CONSTRUCTORS AND GENERATORS
    Graph(int size, bool directed);
    void init();

    // GETTERS, SETTERS AND PRINTERS
    int getSize() const;
    void setSize(int size);
    bool isDirected() const;
    void setDirected(bool directed);

    void printSimpleAsMatrix();

    // ALGORITHMS
};

Kopiuj

#include <string>

class Vertex {
private:
    int id;
    std::string name;

    int weight;
    int color;

public:
    // CONSTRUCTORS
    Vertex(int id, std::string name);

    // GETTERS, SETTERS AND PRINTERS
    int getId() const;
    std::string getName() const;
    void setName(std::string name);
    int getWeight() const;
    void setWeight(int weight);
    int getColor() const;
    void setColor(int color);
};

Kopiuj

#include "Vertex.h"

class Edge {
private:
    int id;
    bool directed;
    int length;

    Vertex* startVertex = nullptr;
    Vertex* endVertex = nullptr;

public:
    // CONSTRUCTORS
    Edge(bool directed, int length);
    Edge(bool directed, int length, Vertex *startVertex, Vertex *endVertex);

    // GETTERS AND SETTERS
    int getId() const;
    bool isDirected() const;
    void setDirected(bool directed);
    int getLength() const;
    void setLength(int length);
    Vertex *getStartVertex() const;
    void setStartVertex(Vertex *startVertex);
    Vertex *getEndVertex() const;
    void setEndVertex(Vertex *endVertex);
};

Lepiej reprezentować graf jako dwa zbiory (wierzchołków i krawędzi) i tworzyć macierz sąsiedztwa w funkcjach w których jej potrzebuję?
Czy może lepiej trzymać tę macierz cały czas, ale czy nie jest to zbędna redundancja?
Czy to dobrze że używam tu vector, czy może inny kontener będzie lepszy?
Krawędź ma pamiętać swoje wierzchołki, lepiej robić to poprzez wskaźnik na Vertex czy po prostu id?

Bardzo proszę też o ogólne rady co do kodu :)

koszalek-opalek

2018-01-16T00:36:16+01:00

Rejestracja: dni
Ostatnio: dni

0

wazxse5 napisał(a):

Cześć!
Mam za zadanie napisać program który będzie miał możliwość implementacji różnych algorytmów grafowych, ewentualnie potem dorobię do tego jakiś gui.
Zacząłem od zdefiniowania klasy grafu. I tu pojawia się moje pytanie. W jaki sposób najlepiej reprezentować graf, jak powinna wyglądać klasa grafu?
Chcę by obejmowała ona różne rodzaje grafów; skierowanie, nieskierowanie, wielokrawędziowe, z wagami, z pętlami, w ogóle żeby była jak najszersza.

Eh, to będzie kłopot, bo silnie zależy reprezentacja od konkretnego algorytmu ORAZ rodzaju/właściwości grafu reprezentowanego...

Klasy Vertex i Edge zbyt skomplikowane jak dla mnie -- chcesz tam wrzucić od razu wszystkie właściwości, a potem się okaże, że i tak za mało... Przcież nie wszędzie będzie potrzebny kolor czy długość krawędzi... Może jakieś szablony albo dziedziczenie?

Lepiej reprezentować graf jako dwa zbiory (wierzchołków i krawędzi) i tworzyć macierz sąsiedztwa w funkcjach w których jej potrzebuję?
Czy może lepiej trzymać tę macierz cały czas, ale czy nie jest to zbędna redundancja?

A czy macierz sąsiedztwa będzie zawsze potrzebna? Dla grafów rzadkich (większość pewnie jest takich w praktyce), to straszna strata miejsca, lepiej jakieś listy sąsiedztwa, czy coś...

Czy to dobrze że używam tu vector, czy może inny kontener będzie lepszy?

Ja bym pomyślał o mapie.

Krawędź ma pamiętać swoje wierzchołki, lepiej robić to poprzez wskaźnik na Vertex czy po prostu id?

Ja zwykle robię id. Ale znowu -- zależy od konkretnego zastosowania...

koszalek-opalek

2018-01-16T11:06:06+01:00

Rejestracja: dni
Ostatnio: dni

0

Spróbuj coś podobnego może do mojego przykładu:

Kopiuj

#include <vector>
#include <map>

using VertexID = int;

template<typename V, typename E>
// V i E mogą być całkiem dowolnymi typami (struktury, klasy, wskaźniki, ...)
// opisującymi zawartość odpowiednio węzła i krawędzi
class Graph {
private:
    std::vector<V> vertices;
    std::map<std::pair<VertexID, VertexID>, E> edges;
    // dla multigrqafu może się przydać multimap
    // a jesli Ci nie potrzeba uporządkowania
    // to unordered_map lub unordered_multimap
public:
    VertexID how_many_vertices() {
        return vertices.size();
    }
    VertexID how_many_edges() {
        return edges.size();
    }
    VertexID add_vertex(V v) {
        vertices.push_back(v);
        return how_many_vertices()-1;
    }
    void add_edge(VertexID vi1, VertexID vi2, E e) {
        edges[{vi1, vi2}] = e;
    }
    void add_undirected_edge(VertexID vi1, VertexID vi2, E e) {
        edges[{vi1, vi2}] = e;
        edges[{vi2, vi1}] = e;
    }
    bool is_edge(VertexID vi1, VertexID vi2) {
        return edges.count({vi1, vi2}) != 0;
    }
    E get_edge(VertexID vi1, VertexID vi2) {
        return edges[{vi1, vi2}];
    }
    V get_vertex(VertexID vi) {
        return vertices[vi];
    }
    template<typename F>
    void for_each_vertex(F f) { // f to funktor (?) przyjmujący
                                // dwa argumenty typów: VertexID, V
        VertexID vi = 0;
        for(auto & v : vertices) {
            f(vi, v);
            ++vi;
        }
    }
    template<typename F>
    void for_each_edge(F f) { // f to funktor (?) przyjmujący
                              // trzy argumenty typów: VertexID, VertexID, E
        for(auto & e : edges) {
            f(e.first.first, e.first.second, e.second);
        }
    }
};

#include <string>
#include <iostream>

int main() {
    using namespace std;

    Graph<string, string> g;

    VertexID v_kot = g.add_vertex("kot");
    VertexID v_slon = g.add_vertex("słoń");
    VertexID v_mysz = g.add_vertex("mysz");
    VertexID v_pies = g.add_vertex("pies");

    g.add_edge(v_kot, v_pies, "kot boi się psa");
    g.add_undirected_edge(v_slon, v_mysz, "słoń boi się myszy i odwrotnie");
    g.add_edge(v_mysz, v_kot, "mysz boi się kota");
    g.add_edge(v_mysz, v_pies, "mysz boi się psa");
    g.add_edge(v_mysz, v_mysz, "mysz to się nawet boi sama siebie...");

    g.for_each_vertex(
        [](VertexID i, string opis){
            cout << i << ": " << opis << endl;
        });

    g.for_each_edge(
        [](VertexID i, VertexID j, string opis){
            cout << i << " -> " << j << ": " << opis << endl;
        });

    g.for_each_edge(
        [&](VertexID i, VertexID j, string opis){
            cout << g.get_vertex(i) << " -> " << g.get_vertex(j) << ": " << opis << endl;
        });
}