AiSD (4) - ADT GRAPH (lista sąsiedztwa)

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().

WPROWADZENIE

Typowe operacje dla ADT GRAPH.

konstruktor tworzący pusty graf skierowany lub nieskierowany;
odczyt liczby wierzchołków [v()];
odczyt liczby krawędzi [e()];
testowanie, czy graf jest skierowany [is_directed()];
wstawianie nowego wierzchołka [add_node(u) lub przez konstruktor];
usuwanie danego wierzchołka u wraz z krawędziami incydentnymi [del_node(u)]; w przypadku implementacji z macierzą sąsiedztwa wierzchołek faktycznie nie jest usuwany;
testowanie należenia wierzchołka u do grafu [has_node(u)];
wstawianie nowej krawędzi (u,v) [add_edge(u,v) lub dla krawędzi z wagą add_edge(u,v,weight)]; zwykle automatycznie wstawiane są też wierzchołki u i v, jeżeli wcześniej nie dodano ich do grafu;
usuwanie krawędzi (u,v) [del_edge(u,v)];
testowanie istnienia krawędzi (u,v) [has_edge(u,v) lub przez zerową wagę weight(u,v)];
odczyt wagi krawędzi weight(u,v) [domyślnie przyjmuje się wagę 1 (int lub float)];
iteracja po wierzchołkach grafu;
iteracja po krawędziach grafu;
iteracja po sąsiadach danego wierzchołka u;
czyszczenie grafu [clear()].

| Przykład grafu skierowanego i jego listy sąsiedztwa.
| Złożoność pamięciowa to zwykle O((n+m) log n) bitów.
| 1 --o 2   +---+
| o   / |   |   |   +---+   +---+    puste
| |  /  |   | 0 +--o| 1 +--o| 3 +--| łącze
| | o   o   |   |   +---+   +---+
| 0 --o 3   +---+
|           |   |   +---+
| n = 4     | 1 +--o| 2 +--|
| m = 5     |   |   +---+
|           +---+
|           |   |   +---+   +---+
|           | 2 +--o| 0 +--o| 3 +--|
|           |   |   +---+   +---+
|           +---+
|           |   |
|           | 3 +--|
|           |   |
|           +---+

| Przykład grafu nieskierowanego i jego listy sąsiedztwa.
| Złożoność pamięciowa to zwykle O((n+m) log n) bitów.
| 1---2   +---+
| | / |   |   |   +---+   +---+   +---+    puste
| 0---3   | 0 +--o| 1 +--o| 2 +--o| 3 +--| łącze
|         |   |   +---+   +---+   +---+
|         +---+
|         |   |   +---+   +---+
| n = 4   | 1 +--o| 0 +--o| 2 +--|
| m = 5   |   |   +---+   +---+
|         +---+
|         |   |   +---+   +---+   +---+
|         | 2 +--o| 0 +--o| 1 +--o| 3 +--|
|         |   |   +---+   +---+   +---+
|         +---+
|         |   |   +---+   +---+
|         | 3 +--o| 0 +--o| 2 +--|
|         |   |   +---+   +---+
|         +---+

ITERATORY

// Korzystanie z iteratorów w grafie.
// W grafie używamy std::map lub std::unordered_map.

// Przykładowe definicje grafów.
Graph<int> G; // lista sąsiedztwa, wierzchołki int, graf nieskierowany
Graph<char> G(true); // lista sąsiedztwa, wierzchołki char, graf skierowany
Graph<std::string> G; // lista sąsiedztwa, wierzchołki std::string, graf nieskierowany

// Dodawanie wierzchołków i krawędzi ...

for (auto n_it = G.node_begin(); n_it != G.node_end(); ++n_it) {
    print_node(*n_it); // NodeIterator
}
for (auto e_it = G.edge_begin(); e_it != G.edge_end(); ++e_it) {
    print_edge(*e_it); // EdgeIterator
}
// 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
}

class NodeIterator : public Iterator<T> { ... };
// w grafie używamy std::map lub std::unordered_map
NodeIterator node_begin() {
    return NodeIterator(this, this->adj_list.begin());
}
NodeIterator node_end() {
    return NodeIterator(this, this->adj_list.end());
}

class EdgeIterator : public Iterator<Edge<T>> { ... };
// w grafie używamy std::map lub std::unordered_map
EdgeIterator edge_begin() {
    return EdgeIterator(this);
}
EdgeIterator edge_end() {
    return EdgeIterator(this, this->adj_list.end(),
        this->adj_list.begin()->second.end()); // konwencja
}

class AdjacentIterator : public Iterator<T> { ... };
// w grafie używamy std::map lub std::unordered_map
AdjacentIterator adj_begin(T u) {
    auto pair_it = this->adj_list.find(u);
    return AdjacentIterator(this, pair_it, pair_it->second.begin());
}
AdjacentIterator adj_end(T u) {
    auto pair_it = this->adj_list.find(u);
    return AdjacentIterator(this, pair_it, pair_it->second.end());
}

ZADANIE 4.1 (GRAF BEZ WAG)

Przygotować implementację realizującą ADT GRAPH na bazie listy 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.

Wektor adj_list zawiera wektory/listy różnej długości. Wierzchołki grafu to liczby od 0 do n-1.

// graph.hpp
class Graph : public BaseGraph<int> { // wersja 5b
    bool directed; // czy graf jest skierowany
    std::vector< std::vector<int> > adj_list; // lista sąsiedztwa
public:
    // Powstaje wektor z 'n' pustymi wektorami.
    Graph(int n, bool directed=false) : directed(directed) {
        adj_list = std::vector< std::vector<int> >(n);
    }
    ~Graph() { clear(); }
    bool is_directed() const override { return directed; } // czy graf jest skierowany O(1)
    int v() const override { return adj_list.size(); } // liczba wierzchołków grafu O(1)
    int e() const override { // liczba krawędzi grafu O(n)
        int counter = 0;
        for (auto& vec : adj_list)
            counter += vec.size();
        return (directed ? counter : counter / 2);
    }
    int degree(int u) override {
        assert( !directed );
        return adj_list[u].size();
    }
    int indegree(int u) override; // liczba krawędzi wchodzących do u
    int outdegree(int u) override { return adj_list[u].size(); } // liczba krawędzi wychodzących z u
    void add_node(int u) override { assert((0 <= u) && (u < v())); } // tylko test zakresu
    void del_node(int u) override; // usuwanie krawedzi incydentnych
    bool has_node(int u) const override { return (0 <= u) && (u < v()); } // tylko test zakresu
    void add_edge(int u, int w, float weight=1.0) override; // wstawienie krawędzi (u,w)
    void add_edge(Edge<int> edge) override {
        add_edge(edge.source, edge.target, edge.weight);
    }
    void del_edge(int u, int w) override; // usunięcie krawędzi (u,w)
    void del_edge(Edge<int> edge) override {
        del_edge(edge.source, edge.target);
    }
    bool has_edge(int u, int w) const override; // test istnienia krawędzi (u,w)
    bool has_edge(Edge<int> edge) const override {
        return has_edge(edge.source, edge.target);
    }
    float weight(int u, int v) const override;
    float weight(Edge<int> edge) const override {
        return weight(edge.source, edge.target);
    }
    void clear() override { // usunięcie wszystkich krawędzi (wierzchołki zostają)
        // Zostawiamy adj_list z pustymi listami sąsiedztwa.
        for (auto& vec : adj_list)
            vec.clear();
    }
    void display() const override; // wypisywanie 'directed' i adj_list
};

// Inna możliwość to alokowana tablica z wektorami/listami różnej długości.
class Graph : public BaseGraph<int> { // wersja 5d
    int n;
    bool directed;
    std::vector<int> *adj_list;
public:
    Graph(int nn, bool directed=false) : n(nn), directed(directed) {
        adj_list = new std::vector<int> [n];
    }
    ~Graph() { clear(); delete [] adj_list; }
    bool is_directed() const override { return directed; }
    int v() const override { return n; } // liczba wierzchołków
    int e() const override { // liczba krawędzi
        int counter = 0;
        for (int u = 0; u < n; u++)
            counter += adj_list[u].size();
        return (directed ? counter : counter / 2);
    }

ZADANIE 4.2 (GRAF BEZ WAG)

Przygotować implementację realizującą ADT GRAPH na bazie listy sąsiedztwa dla grafu bez wag krawędzi. Będzie to klasa Graph (szablon) umieszczona w pliku graph.hpp. Uzupełnić plik graph.hpp, stworzyć funkcję main() i testy sprawdzające działanie interfejsu grafów.

Mapa ma klucze typu T (wierzchołki), a wartości to listy/wektory z wartościami typu T (listy sąsiadów).

// graph.hpp
template <typename T>
class Graph : public BaseGraph<T> { // wersja 5x
    bool directed;
    std::unordered_map<T, std::list<T> > adj_list; // lista sąsiedztwa
    //std::unordered_map<T, std::vector<T> > adj_list; // lista sąsiedztwa
public:
    Graph(bool d=false) : directed(d) {}
    ~Graph() { adj_list.clear(); }
    bool is_directed() const override { return directed; }
    int v() const override { return adj_list.size(); } // liczba wierzchołków
    int e() const override { // liczba krawędzi
        int counter = 0;
        for (auto& pair : adj_list)
            counter += pair.second.size();
        return (directed ? counter : counter / 2);
    }
    int degree(T u) override {
        assert( !directed );
        return adj_list[u].size();
    }
    int indegree(T u) override; // liczba krawędzi wchodzących do u
    int outdegree(T u) override { return adj_list[u].size(); } // liczba krawędzi wychodzących z u
    void add_node(T u) override { adj_list[u]; } // dodaj izolowany wierzchołek
    void del_node(T u) override;
    bool has_node(T u) const override;
    void add_edge(T u, T w, float weight=1.0) override; // wstawienie krawędzi (u,w)
    void add_edge(Edge<T> edge) override {
        add_edge(edge.source, edge.target, edge.weight);
    }
    void del_edge(T u, T w) override; // usunięcie krawędzi (u,w)
    void del_edge(Edge<T> edge) override {
        del_edge(edge.source, edge.target);
    }
    bool has_edge(T u, T w) const override; // test istnienia krawędzi
    bool has_edge(Edge<T> edge) const override {
        return has_edge(edge.source, edge.target);
    }
    float weight(T u, T w) const override; // waga krawędzi lub 0.0
    float weight(Edge<T> edge) const override {
        return weight(edge.source, edge.target);
    }
    void clear() override { adj_list.clear(); }
    void display() const override;
};

ZADANIE 4.3 (GRAF WAŻONY)

Przygotować implementację realizującą ADT GRAPH na bazie listy sąsiedztwa dla grafu z wagami krawędzi. Na liście sąsiedztwa powinny być przechowywane pary (wierzchołek końcowy krawędzi, waga krawędzi).

Inne rozwiązanie to przechowywanie na liście sąsiedztwa wskaźników do krawędzi (klasa Edge). Uzupełnić plik graph.hpp, stworzyć funkcję main() i testy sprawdzające działanie interfejsu grafów.

// graph.hpp
template <typename T>
class Graph { // wersja5c
    bool directed;
    std::unordered_map<T, std::list<Edge<T> *> > adj_list; // lista sąsiedztwa
    //std::unordered_map<T, std::vector<Edge<T> *> > adj_list; // lista sąsiedztwa
public:
    Graph(bool directed=false) : directed(directed) {}
    ~Graph() { clear(); } // trzeba zwolnić pamięć krawędzi
    bool is_directed() const override { return directed; }
    int v() const override { return adj_list.size(); } // liczba wierzchołków
    int e() const override { // liczba krawędzi
        int counter = 0;
        for (auto& pair : adj_list)
            counter += pair.second.size();
        return (directed ? counter : counter / 2);
    }
    int degree(T u) override {
        assert( !directed );
        return adj_list[u].size();
    }
    int indegree(T u) override; // liczba krawędzi wchodzących do u
    int outdegree(T u) override { return adj_list[u].size(); } // liczba krawędzi wychodzących z u
    void add_node(T u) override { adj_list[u]; } // dodaj izolowany wierzchołek
    void del_node(T u) override;
    bool has_node(T u) const override;
    void add_edge(T u, T w, float weight=1.0) override; // wstawienie krawędzi (u,w) z wagą
    void add_edge(Edge<T> edge) override {
        add_edge(edge.source, edge.target, edge.weight);
    }
    void del_edge(T u, T w) override; // usunięcie krawędzi (u,w)
    void del_edge(Edge<T> edge) override {
        del_edge(edge.source, edge.target);
    }
    bool has_edge(T u, T w) const override; // test istnienia krawędzi
    bool has_edge(Edge<T> edge) const override {
        return has_edge(edge.source, edge.target);
    }
    float weight(T u, T w) const override; // waga krawędzi lub 0.0
    float weight(Edge<T> edge) const override {
        return weight(edge.source, edge.target);
    }
    void clear() override; // trzeba zwolnić pamięć krawędzi
    void display() const override;
};

AiSD (index)