AiSD (index)

AiSD (16) - algorytmy grafowe

OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie

WPROWADZENIE

ADT GRAPH implementuje pojęcie grafu z teorii grafów. Graf G=(V,E) składa się ze skończonego zbioru wierzchołków V i skończonego zbioru krawędzi E łączących pary wierzchołków. Grafy (krawędzie) mogą być skierowane lub nieskierowane. Wierzchołki i krawędzie mogą mieć zdefiniowane dodatkowe atrybuty (waga, kolor, etykieta, itp.). Oznaczenia n=|V|, m=|E|.

Typowe operacje dla ADT GRAPH są następujące:

• konstruktor tworzący pusty graf skierowany lub nieskierowany.
• odczyt liczby wierzchołków,
• odczyt liczby krawędzi,
• dodanie wierzchołka,
• usunięcie wierzchołka,
• testowanie, czy graf zawiera wierzchołek,
• dodanie krawędzi,
• usunięcie krawędzi,
• testowanie, czy graf zawiera krawędź,
• iterowanie po wszystkich wierzchołkach grafu,
• iterowanie po wszystkich krawędziach grafu,
• iterowanie po wszystkich sąsiadach danego grafu (lub po krawędziach wychodzących),
• czyszczenie grafu.

Typowe reprezentacje grafu.

• Lista sąsiedztwa (ang. adjacency list). Pamięć O(n+m).
• Macierz sąsiedztwa (ang. adjacency matrix). Pamięć O(n^2). Tutaj zwykle wierzchołki są liczbami całkowitymi numerującymi wiersze/kolumny macierzy. Zwykle przyjmuje się, że wierzchołki grafu są utworzone i nie będą usuwane.
• Macierz incydencji (ang. incidence matrix). Pamięć O(n m).
• Lista krawędzi. Pamięć O(m).

Propozycja interfejsu grafu bez wag z wierzchołkami typu int. Przyjmujemy, że utworzenie grafu oznacza jednocześnie utworzenie wierzchołków. Metoda del_node() usuwa jedynie krawędzie połączone z danym wierzchołkiem.

class Graph {
    bool directed;
    // reszta zależy od implementacji
public:
    Graph(int size, bool directed=false); // wierzchołki od 0 do size-1
    ~Graph();
    Graph(const Graph& other); // copy constructor
    Graph(Graph&& other);  // move constructor
    Graph& operator=(const Graph& other); // copy assignment operator, return *this
    Graph& operator=(Graph&& other); // move assignment operator, return *this
    bool is_directed() const { return directed; }
    int getV() const; // zwraca liczbę wierzchołków
    int getE() const; // zwraca liczbę krawędzi
    bool add_node(int v); // tylko test v
    bool has_node(int v); // tylko test v
    void del_node(int v); // usuwa krawędzie połączone z v
    void add_edge(int u, int v);
    bool has_edge(int u, int v);
    void del_edge(int u, int v);
    void clear(); // usuwa wszystkie krawędzie
    void visit(int v); // można np. wypisać wierzchołek v
    void dfs(int v); // v to wierzchołek startowy
    void bfs(int v); // v to wierzchołek startowy
    friend std::ostream& operator<<(std::ostream&, const Graph&);
};
// Zwykle potrzebne są jeszcze 3 iteratory:
// (1) iteracja po wierzchołkach,
// (2) iteracja po krawędziach,
// (2) iteracja po sąsiadach danego wierzchołka v.

ZADANIE 16.1

https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/index.html

Zapoznać się z The Boost Graph Library (BGL). Stworzyć przypadkowy graf nieskierowany ważony spójny. Znaleźć minimalne drzewo rozpinające grafu za pomocą algorytmu Prima lub Kruskala.

ZADANIE 16.2

http://graphblas.org/

Zapoznać się z projektem GraphBLAS, który definiuje API dla algorytmów grafowych.

ZADANIE 16.3

https://github.com/ufkapano/graphs-dict

Zapoznać się z pakietem graphtheory w języku Python.

AiSD (index)