H
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
