OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie
Ogólne zalecenia do przesyłanych programów.
(1) Katalog z programem powinien zawierać Makefile i pliki źródłowe.
(2) Program powinien kompilować się poleceniem make.
(3) Nie używać deklaracji using namespace std;.
(4) Zalecane są testy automatyczne z assert().
Dla grafu G=(V,E) przyjmujemy oznaczenia: n=|V|, m=|E|.
V(G) to zbiór wierzchołków, E(G) to zbiór krawędzi.
Macierz sąsiedztwa A ma wymiar n × n.
A[u][v] = 0 oznacza brak krawędzi (u,v).
A[u][v] = 1 oznacza istnienie krawędzi (u,v).
Dla grafu nieskierowanego macierz A jest symetryczna,
A[u][v] = A[v][u].
Można powiedzieć, że jedna krawędź nieskierowana (u,v) jest wewnętrznie
zapisywana jako dwie krawędzie skierowane (u,v) oraz (v,u).
Dla grafu ważonego wagę krawędzi zapisujemy
w elemencie A[u][v] = weight(u,v).
Waga nie może być równa zero, bo zero oznacza brak krawędzi.
Dla grafów prostych zawsze A[u][u] = 0 (brak pętli).
Jeżeli dopuszczamy możliwość istnienia pętli (ang. loop)
w grafie, czyli opisujemy multigraf,
to pętlę przy wierzchołku u zaznaczamy jako A[u][u] = 1.
Przy każdym wierzchołku może być najwyżej jedna pętla,
bo w macierzy A przechowjemy tylko 0/1.
Dla multigrafu ważonego można zapisać A[u][u] = weight(u,u),
ale tylko jeżeli każdy wierzchołek ma co najwyżej jedną pętlę ważoną.
Typowe operacje dla ADT GRAPH.
| Przykład grafu skierowanego i jego macierzy sąsiedztwa. | 1 --o 2 +---+---+---+---+---+ | o / | |r\c| 0 | 1 | 2 | 3 | | | / | +---+---+---+---+---+ | | o o | 0 | 0 | 1 | 0 | 1 | złożoność pamięciowa to O(n^2) bitów | 0 --o 3 +---+---+---+---+---+ | | 1 | 0 | 0 | 1 | 0 | outdegree(0) = 2, indegree(0) = 1, | n = 4 +---+---+---+---+---+ outdegree(1) = 1, indegree(1) = 1, | m = 5 | 2 | 1 | 0 | 0 | 1 | outdegree(2) = 2, indegree(2) = 1, | +---+---+---+---+---+ outdegree(3) = 0, indegree(3) = 2, | | 3 | 0 | 0 | 0 | 0 | \sum_v outdegree(v) = \sum_v indegree(v) = m | +---+---+---+---+---+
| Przykład grafu nieskierowanego i jego macierzy sąsiedztwa. | 1---2 +---+---+---+---+---+ | | / | |r\c| 0 | 1 | 2 | 3 | macierz jest symetryczna | 0---3 +---+---+---+---+---+ | | 0 | 0 | 1 | 1 | 1 | złożoność pamięciowa to O(n^2) bitów | n = 4 +---+---+---+---+---+ | m = 5 | 1 | 1 | 0 | 1 | 0 | degree(1) = degree(3) = 2, | +---+---+---+---+---+ degree(0) = degree(2) = 3, | | 2 | 1 | 1 | 0 | 1 | \sum_v degree(v) = 2 m | +---+---+---+---+---+ | | 3 | 1 | 0 | 1 | 0 | | +---+---+---+---+---+
Krawędzie grafu są reprezentowane przez klasę Edge<T>. To jest szablon, w którym wierzchołki grafu są typu T, a wagi krawędzi typu float. Domyślna waga krawędzi wynosi 1.0.
// edge.hpp
template<typename T>
class Edge {
public:
T source;
T target;
float weight;
Edge(T s, T t, float w=1.0) : source(s), target(t), weight(w) {}
~Edge() {} // destruktor
Edge(const Edge& edge) : source(edge.source), target(edge.target),
weight(edge.weight) {} // copy-constructor
// Operator negacji bitowej, ale tu pasuje.
Edge operator~() const { return Edge(target, source, weight); }
Edge& operator=(const Edge& other); // return *this;
friend std::ostream& operator<<(std::ostream& os, const Edge& edge);
bool operator==(const Edge& edge);
bool operator!=(const Edge& edge);
};
// basegraph.hpp
template <typename T>
class BaseGraph { // abstract class
public:
BaseGraph() {}
~BaseGraph() {}
virtual bool is_directed() const = 0;
virtual int v() const = 0; // liczba wierzcholkow
virtual int e() const = 0; // liczba krawedzi
virtual int degree(T u) = 0; // problem z const dla operator[]
virtual int indegree(T u) = 0; // stopień wejściowy
virtual int outdegree(T u) = 0; // stopień wyjściowy
virtual void add_node(T u) = 0;
virtual void del_node(T u) = 0;
virtual bool has_node(T u) const = 0;
virtual void add_edge(T u, T w, float weight=1.0) = 0;
virtual void add_edge(Edge<T> edge) = 0;
virtual void del_edge(T u, T w) = 0;
virtual void del_edge(Edge<T> edge) = 0;
virtual bool has_edge(T u, T w) const = 0;
virtual bool has_edge(Edge<T> edge) const = 0;
virtual float weight(T u, T w) const = 0;
virtual float weight(Edge<T> edge) const = 0;
virtual void clear() = 0;
virtual void display() const = 0;
};
Istnieje wzorzec projektowy Iterator, który może być zrealizowany na wiele sposobów.
// Korzystanie z iteratorów po kontenerze w STL.
// begin(), end() dla zwykłych iteratorów;
// cbegin(), cend() dla iteratorów z gwarancją niezmienności kontenera;
// rbegin(), rend() dla iteratorów odwrotnych;
// crbegin(), crend() dla iteratorów odwrotnych z gwarancją niezmienności kontenera;
for (auto it = container.begin(); it != container.end(); ++it)
print(*it);
// Inny spotykany interfejs iteratorów.
auto it = container.create_iterator();
for (it.first(); !it.is_done(); it.next())
print(it.current());
// Korzystanie z iteratorów w grafie.
Graph G(7); // macierz sąsiedztwa, n = 7, graf nieskierowany
Graph G(7,true); // macierz sąsiedztwa, n = 7, graf skierowany
// Dodawanie krawędzi ...
for (auto n_it = G.node_begin(); n_it != G.node_end(); ++n_it) {
print_node(*n_it); // NodeIterator, *n_it jest typu int
}
for (auto e_it = G.edge_begin(); e_it != G.edge_end(); ++e_it) {
print_edge(*e_it); // EdgeIterator, *e_it jest typu Edge<int>
}
// Niech 'node' oznacza pewien wierzchołek grafu.
for (auto a_it = G.adj_begin(node); a_it != G.adj_end(node); ++a_it) {
print_node(*a_it); // AdjacentIterator, *a_it jest typu int
}
class NodeIterator : public Iterator<int> { ... };
NodeIterator node_begin() { return NodeIterator(this, 0); } // lub bez zera
NodeIterator node_end() { return NodeIterator(this, v()); }
class EdgeIterator : public Iterator<Edge<int>> { ... };
EdgeIterator edge_begin() { return EdgeIterator(this); }
EdgeIterator edge_end() { return EdgeIterator(this, v(), v()); } // konwencja
class AdjacentIterator : public Iterator<int> { ... };
AdjacentIterator adj_begin(int r) { return AdjacentIterator(this, r); }
AdjacentIterator adj_end(int r) { return AdjacentIterator(this, r, v()); }
// iterator.hpp
template <typename T>
class Iterator { // abstract class
public:
Iterator() {}
~Iterator() {}
// Sa problemy w dziedziczeniu tych funkcji.
//virtual Iterator& operator=(const Iterator& other) = 0; // tego się nie robi
//virtual Iterator& operator++() = 0;
//virtual Iterator operator++(int) = 0;
//virtual bool operator==(const Iterator& other) = 0;
//virtual bool operator!=(const Iterator& other) = 0;
virtual T operator*() const = 0; // działa
};
Przygotować implementację realizującą ADT GRAPH na bazie macierzy sąsiedztwa dla grafu bez wag krawędzi. Będzie to klasa Graph umieszczona w pliku graph.hpp. Uzupełnić plik graph.hpp, stworzyć funkcję main() i testy sprawdzające działanie interfejsu grafów.
W kilku metodach zamiast podawania dwóch argumentów int (u,w) można zaimplementować dodatkowo korzystanie z jednego argumentu typu Edge<int>.
Wierzchołki grafu to liczby od 0 do n-1.
// graph.hpp
class Graph : public BaseGraph<int> { // wersja 6x
bool directed; // czy graf jest skierowany
std::vector< std::vector<int> > adj_matrix; // macierz sąsiedztwa
public:
// Tu jest alokowana pamięć na macierz kwadratową nxn
// i następuje wypełnianie macierzy zerami.
Graph(int n, bool directed=false) : directed(directed) {
adj_matrix = std::vector< std::vector<int> >(n, std::vector<int>(n, 0));
}
~Graph() { clear(); }
bool is_directed() const override { return directed; } // czy graf jest skierowany O(1)
int v() const override { return adj_matrix.size(); } // liczba wierzchołków grafu O(1)
int e() const override { // liczba krawędzi grafu, O(n^2) time
int counter = 0;
for (int u = 0; u < v(); u++)
for (int w = 0; w < v(); w++)
counter += adj_matrix[u][w]; // sumujemy 0 i 1
return (directed ? counter : counter / 2);
}
int degree(int u) override; // liczba sąsiadów (tylko graf nieskierowany
int indegree(int u) override; // liczba krawędzi wchodzących do u
int outdegree(int u) override; // liczba krawędzi wychodzących z u
void add_node(int u) override {
assert( 0 <= u && u < v() );
}
void del_node(int u) override { // tylko usuwamy krawędzie incydentne
for (int w = 0; w < v(); w++) {
adj_matrix[u][w] = 0;
adj_matrix[w][u] = 0;
}
}
bool has_node(int u) const override {
return (0 <= u && u < v());
}
void add_edge(int u, int w, float weight=1.0) override; // wstawienie krawędzi (u,w)
void add_edge(Edge<int> edge) override;
void del_edge(int u, int w) override; // usunięcie krawędzi (u,w)
void del_edge(Edge<int> edge) override;
bool has_edge(int u, int w) const override { // test istnienia krawędzi
return adj_matrix[u][w] == 1;
}
bool has_edge(Edge<int> edge) const override {
return adj_matrix[edge.source][edge.target] == 1;
}
float weight(int u, int w) const override {
return adj_matrix[u][w];
}
float weight(Edge<int> edge) const override {
return adj_matrix[edge.source][edge.target];
}
void clear() override; // usunięcie wszystkich krawędzi O(n^2)
void display() const override; // wypisywanie 'directed' i adj_matrix
};
Przygotować implementację realizującą ADT GRAPH na bazie macierzy sąsiedztwa dla grafu z wagami krawędzi. W macierzy sąsiedztwa zamiast 1/0 powinny być przechowywane wagi krawędzi (int lub float), przy czym wagi muszą być różne od zera. Takie podejście nie jest dobre, jeżeli w danym problemie mamy krawędzie z zerowymi wagami, np. tak jest w sieciach przepływowych.
Inne rozwiązanie to przechowywanie w macierzy sąsiedztwa wskaźników do krawędzi (klasa Edge). Wskaźnik nullptr oznacza brak krawędzi. To rozwiązanie pozwala na przechowywanie w krawędziach innych danych niż dowolne wagi (również zerowe), np. etykiet tekstowych.
// graph.hpp
class Graph : public BaseGraph<int> { // wersja 7x
bool directed;
// Adjacency matrix to store graph edges.
std::vector<std::vector<Edge<int> *> > adj_matrix;
public:
Graph(int n, bool directed=false) : directed(directed) {
adj_matrix = std::vector< std::vector<Edge<int> *> >(
n, std::vector<Edge<int> *>(n, nullptr));
}
~Graph() { clear(); } // trzeba zwolnić pamięć krawędzi
bool is_directed() const override { return directed; }
int v() const override { return adj_matrix.size(); }
int e() const override;
int degree(int u) override; // stopień wierzchołka
int indegree(int u) override;
int outdegree(int u) override;
void add_node(int u) override;
void del_node(int u) override;
bool has_node(int u) const override;
void add_edge(int u, int w, float weight=1.0); // dodanie krawędzi (u,w)
void add_edge(Edge<int> edge) override;
void del_edge(int u, int w); // usunięcie krawędzi (u,w)
void del_edge(Edge<int> edge) override;
bool has_edge(int u, int w) const override { // test istnienia krawędzi
return adj_matrix[u][w] != nullptr;
}
bool has_edge(Edge<int> edge) const override {
return adj_matrix[edge.source][edge.target] != nullptr;
}
float weight(int u, int w) const override; // waga krawędzi lub 0.0
float weight(Edge<int> edge) const override;
void clear() override; // usunięcie wszystkich krawędzi O(n^2)
void display() const override;
};
W obu poprzenich zadaniach zamiast korzystania z std::vector można rozważyć korzystanie z alokowanej tablicy wskaźników do alokowanych wierszy macierzy.
int n; // trzeba zapisać rozmiar tablic int **adj_matrix; // grafy bez wag Edge<int> ***adj_matrix; // grafy ważone