8063591569

Listing 2.1: Implementacja struktury Graph<V,E>

01    template <class V, class E> struct Graph {

// Typ krawędzi (Ed) dziedziczy po typie zawierającym dodatkowe informacje // związane z krawędzią (E). Zawiera on również pole v, określające numer // wierzchołka, do którego prowadzi krawędź. Zaimplementowany konstruktor // pozwala na skrócenie zapisu wielu funkcji korzystających ze struktury grafu.

02    struct Ed : E {

03    int v;

04    Ed(E p, int w) : E(p), v(w) { }

05    };

// Typ wierzchołka (Ve) dziedziczy po typie zawierającym dodatkowe informacje //z nim związane (V) oraz po wektorze krawędzi. To drugie dziedziczenie może // wydawać się na pierwszy rzut oka stosunkowo dziwne, lecz jest ono przydatne -// umożliwia łatwe iterowanie po wszystkich krawędziach wychodzących z // wierzchołka v: FOREACH(it, g[v])

06    struct Ve : V, vector<Ed> { };

// Wektor wierzchołków w grafie

07    vector<Ve> g;

// Konstruktor grafu - przyjmuje jako parametr liczbę wierzchołków

08    Graph (int n = 0) : g(n) { }

// Funkcja dodająca do grafu nową krawędź skierowaną z wierzchołka b do e,

// zawierającą dodatkowe informacje określone przez zmienną d.

09    void EdgeD(int b, int e, E d = E()) {

10    g[b].PB(Ed(d, e));

n }

// Funkcja dodająca do grafu nową krawędź nieskierowaną, łączącą wierzchołki // b i e oraz zawierającą dodatkowe informacje określone przez zmienną // d. Krawędź nieskierowana jest reprezentowana przez dwie krawędzie // skierowane - jedną prowadzącą z wierzchołka b do wierzchołka e, oraz // drugą z wierzchołka e do b. Struktura E w grafach nieskierowanych // musi dodatkowo zawierać element int rev. Dla danej krawędzi skierowanej // (b,e), pole to przechowuje pozycję krawędzi (e,b) na liście incydencji // wierzchołka e. Dzięki temu, dla dowolnej krawędzi w grafie w czasie stałym // można znaleźć krawędź o przeciwnym zwrocie.

12    void EdgeU(int b, int e, E d = E()) {

13    Ed eg(d, e);

14    eg.rev = SIZE(g[e]) + (b == e);

15    g[b].PB(eg);

16    eg.rev = SIZE(g[eg.v = b]) - 1;

17    g[e].PB(eg);

18    }

m};_

W kolejnych rozdziałach dotyczących teorii grafów, przedstawione zostaną implementacje różnych algorytmów wykorzystujących strukturę Graph<V,E>. Wszystkie funkcje realizujące te algorytmy są metodami grafu, a co za tym idzie, ich treść musi zostać umieszczona w obrębie struktury Graph<V,E>. Faktu tego w dalszej części książki nie będziemy więcej przywoływać — zdajemy się na dobrą pamięć czytelnika.