lion137
2018-11-28 00:08

TDD in C++

Ciąg dalszy, po tam jakiś teoretycznych próbkach, napisałem coś bardziej praktycznego:): ADT geneyczny graf w C++. Niestety założenia uczyniły interfejs tłustym, jak tłusty bankowy kocur:); przytaczam klasę w całości:

/*
 * template class Graph ADT (undirected)
 */

template <class T>
class Graph {

    int V;
    int E;  
    std::unordered_map<T, std::forward_list<T>> adj;
    std::vector<T> vert;

    void construct(int _V){
        V = _V;
        E = 0;
        count = 0;
        std::forward_list<T> a;
        T el;
        for (int i = 0; i < V; i++){
            vert.push_back(el);
        }
    }

    public:

    std::unordered_map<T, bool> marked;
    int count;  // #connected components

    Graph(int _V) {
        construct(_V);
    }

    Graph(std::string fname){
        std::ifstream in(fname);
        int a, e;
        in >> a;
        in >> e;
        construct(a);
        T ver;
        std::forward_list<T> a_list;
        for (int i = 0; i < V; i++){
            in >> ver;
            vert[i] = ver;
            marked[ver] = false;
            adj[ver] = a_list;
        }
        T v, w;
        for (int i = 0; i < e; i++){
            in >> v >> w;
            add_edge(v, w); 
        }
    }

    ~Graph() {}

    int vertices() {return V;}  // num of vertices
    int edges() {return E;}     // num of edges
    T const& vertex(int v) {return vert[v];} // vertex v

    void add_edge(T _elem_v, T _elem_w){
        adj[_elem_v].push_front(_elem_w);
        adj[_elem_w].push_front(_elem_v);
        E++;
    }

    std::forward_list<T> const& adjacent(T v){
        return adj[v];
    } 

    // helper functions
    bool is_marked(T v){
        return marked[v];
    }

    void print_graph(){
        std::cout << V << " vertices, " << E << " edges"<<"\n";
            for (auto x: adj){
                std::cout << x.first << ": ";
                for (auto it = x.second.begin(); it != x.second.end(); ++it){
                    std::cout << *it << " ";
                } 
                std::cout<< "\n";
            } 
            std::cout << '\n';
    }       
};

Jak widać sporo dodatkowych struktur, jak marked, czy vert, ale za to upraszczamy kod klienta, może być umieszczony w oddzielnym module czy przestrzeni nazw (nie potrzebuje dodatkowych klas, ale coś za coś, paskudna mutowalność grafu:/). Np., sprawdzanie czy spójny(przy założeniu, że mamy działający dfs), może wyglądać tak:

template <class T>
bool is_connected(Graph<T>& g, T v){
    dfs(g, v);
    if (g.count == g.vertices()) return true;
    else return false;
}

Będa updaty:)
Podziękowania dla:

viader

czemu są jednoliterowe nazwy zmiennych? coś to upraszcza? mi się czyta przez to źle ten kod ;_;

lion137

Hm... Czemu te same, które konkretnie? Starałem się tam gdzie mowa o wierzchołkach lub krawędziach używac podobnych zmiennych.

grzesiek51114

Skoro już się czepiamy to czemu przekazujesz argumenty przez wartość? Graph(std::string fname), void add_edge(T _elem_v, T _elem_w) Chyba, że jest to celowe, tak z ciekawości po prostu pytam.

Pijak

Gnwno kod, ale zawsze można się pochwalić.

lion137

Bardzo dziękujemy za merytoryczny komentarz:-)