1
\$\begingroup\$

The vertices on the graph are numbers from 0 to |V| - 1 for convenience. I was thinking later to use a template wrapper for the graph.

Graph.h:

#pragma once
#include <unordered_set>
#include <vector>

class Graph
{
public:
    using size_type = std::size_t;
    using adj_list = std::unordered_set<size_type>;
private:
    std::vector<adj_list> list;
    size_type edges;
    void check_range(size_type) const;
public:
    using size_type = std::size_t;
    Graph(size_type v);
    ~Graph();

    void add_vertex();
    void add_edge(size_type, size_type);

    const adj_list& adj(size_type) const;
    Graph reverse() const;

    size_type E() const;
    size_type V() const;
};

Graph.cpp:

#include "Graph.h"

Graph::Graph(size_type v)
    : list(std::vector<adj_list>(v, std::unordered_set<size_type>())) {
}

Graph::~Graph() {
}

void Graph::add_vertex() {
    list.push_back(std::unordered_set<size_type>());
}

void Graph::add_edge(size_type v, size_type w) {
    check_range(v);
    check_range(w);

    list[v].insert(w);
    ++edges;
}

const typename Graph::adj_list & Graph::adj(size_type v) const {
    check_range(v);
    return list[v];
}

Graph Graph::reverse() const {
    Graph g(list.size());
    for (size_type v = 0, size = list.size(); v < size; ++v) {
        for (auto w : list[v]) {
            g.add_edge(w, v);
        }
    }
    return g;
}

void Graph::check_range(size_type v) const {
    if (v >= list.size()) {
        throw std::out_of_range("vertex out of range");
    }
}

typename Graph::size_type Graph::E() const {
    return edges;
}

typename Graph::size_type Graph::V() const {
    return list.size();
}

DFS.h:

#pragma once
#include "Graph.h"
#include <deque>
#include <stack>

class DFS
{
    enum vertex_state { on_stack, undiscovered, done };

    std::vector<vertex_state> vertices;
    std::deque<Graph::size_type> topo_sort;

public:
    using iterator = std::deque<Graph::size_type>::iterator;
    using reverse_iterator = std::deque<Graph::size_type>::reverse_iterator;

    DFS(const Graph&); 

    bool DFS_visit(const Graph& graph, Graph::size_type, std::stack<std::pair<Graph::size_type, bool>> &);

    bool DAG();

    iterator begin() { return topo_sort.begin(); }
    iterator end() { return topo_sort.end(); }

    reverse_iterator rbegin() { return topo_sort.rbegin(); }
    reverse_iterator rend() { return topo_sort.rend(); }

};

DFS.cpp:

#include "DFS.h"

DFS::DFS(const Graph& G) 
    : vertices(std::vector<vertex_state>(G.V(), undiscovered)),
      topo_sort(std::deque<Graph::size_type>()) {

    std::stack<std::pair<Graph::size_type, bool>> stack;
    for (auto v = 0; v < G.V(); ++v) {
        if (vertices[v] == undiscovered
               && !DFS_visit(G, v, stack)) {
            break;
        }
    }
    //while(v < G.V() && (marked(x) || DFS_visit(G, v++)))
} 

bool DFS::DFS_visit(const Graph& graph, Graph::size_type v, 
                                 std::stack<std::pair<Graph::size_type, bool>> &stack) {

    stack.push(std::make_pair(v, false));
    while (!stack.empty()) {         
        auto &current = stack.top();
        auto v        = current.first;

        if (current.second) {
            topo_sort.push_front(v);
            vertices[v] = done;     
        }
        else switch (vertices[v]) {

        case undiscovered:
            current.second = true;
            vertices[v]    = on_stack;
            for (auto w : graph.adj(v)) {
                stack.push(std::make_pair(w, false));
            }
            continue;

        case on_stack: 
            topo_sort.clear();
            return false;
        }
        stack.pop();
    }
    return true;
}


bool DFS::DAG() { 
    return !topo_sort.empty(); 
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.