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:
#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
};
#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);
};
#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 :)