2
\$\begingroup\$

I'm looking for suggestions on how to improve the usage of modern C++ features with this simple graph search algorithm, particularly with regard to the use of STL containers and lambda expressions.

Note: I am using an implementation of BFS that can be obtained from DFS by replacing the stack with a queue.

#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <iostream>
#include <algorithm>

template <typename Key>
class Graph {
public:
    Graph(std::ostream& stream = std::cout) : _stream(stream) {}
    void add_edge(const Key& v1, const Key& v2) { _adjacency_list.insert( {v1, v2} ); }
    void DFS_rec(const Key& v) const;
    void DFS(const Key& v) const;
    void BFS(const Key& v) const;
    void print_adjacency() const;
private:
    std::ostream& _stream;
    typedef std::pair<Key,Key> edge;
    std::unordered_multimap<Key,Key> _adjacency_list;
    void DFS_helper(const Key& v, std::unordered_set<Key>& visited) const;
};

// RecursiveDFS(v):
// if v is unmarked:
//     mark v
//     for each edge vw:
//         RecursiveDFS(w)

template <typename Key>
void Graph<Key>::DFS_rec(const Key& v) const
{
    std::unordered_set<Key> visited;
    DFS_helper(v, visited);
}

template <typename Key>
void Graph<Key>::DFS_helper(const Key& v, std::unordered_set<Key>& visited) const
{
    visited.insert(v);
    _stream << v << " ";
    const auto adjacent_edges = _adjacency_list.equal_range(v);
    const auto explore = [&] (const edge& e) { if (visited.find(e.second) == visited.end()) DFS_helper(e.second, visited); };
    std::for_each(adjacent_edges.first, adjacent_edges.second, explore);
}

// see p. 6 of http://jeffe.cs.illinois.edu/teaching/algorithms/notes/18-graphs.pdf
// DFS(v):
// S.push(v)
// while S is not empty:
//     u = S.pop()
//     if u is unmarked:
//         mark u
//         for each edge uw:
//             S.push(w)

template <typename Key>
void Graph<Key>::DFS(const Key& v) const
{
    std::unordered_set<Key> visited;
    std::deque<Key> S;
    S.push_back(v);
    while(S.size() > 0)
    {
        const auto& u = S.back();
        S.pop_back();
        const bool unvisited = visited.find(u) == visited.end();
        if (unvisited)
        {
            visited.insert(u); _stream << u << " ";
            const auto& adjacent_edges = _adjacency_list.equal_range(u);
            std::for_each(adjacent_edges.first, adjacent_edges.second, [&](const edge& e) { S.push_back(e.second); });
        }
    }
}

// BFS(v):
// Q.enqueue(v)
// while Q is not empty:
//     u = Q.dequeue()
//     if u is unmarked:
//         mark u
//         for each edge uw:
//             Q.enqueue(w)


template <typename Key>
void Graph<Key>::BFS(const Key& v) const
{
    std::unordered_set<Key> visited;
    std::deque<Key> Q;
    Q.push_back(v);
    while(Q.size() > 0)
    {
        const auto& u = Q.front();
        Q.pop_front();
        const bool unvisited = visited.find(u) == visited.end();
        if (unvisited)
        {
            visited.insert(u); _stream << u << " ";
            const auto& adjacent_edges = _adjacency_list.equal_range(u);
            std::for_each(adjacent_edges.first, adjacent_edges.second, [&](const edge& e) { Q.push_back(e.second); });
        }
    }
}

template <typename Key>
void Graph<Key>::print_adjacency() const
{
    auto it = _adjacency_list.begin();
    while(it != _adjacency_list.end())
    {
        _stream << it->first << ": ";
        auto range = _adjacency_list.equal_range(it->first);
        std::for_each(range.first, range.second, [&](const edge& e) { _stream << e.second << " "; ++it; });
        _stream << "\n";

    }
}


int main()
{
    Graph<std::string> g;
    g.add_edge("a","b"); g.add_edge("b","c"); g.add_edge("c","d");
    g.add_edge("b","a"); g.add_edge("c","b"); g.add_edge("d","c");
    g.add_edge("c","e"); g.add_edge("e","f"); g.add_edge("b","f");
    g.add_edge("e","c"); g.add_edge("f","e"); g.add_edge("f","b");
    g.add_edge("f","g"); g.add_edge("a","g");
    g.add_edge("g","f"); g.add_edge("g","a");
    std::cout << "Printing the adjacency list:\n";
    g.print_adjacency();
    std::cout << "Performing BFS exploration starting at vertex a:\n";
    g.BFS("a");
    std::cout << "\nPerforming DFS exploration starting at vertex a:\n";
    g.DFS("a");
    std::cout << "\n";
    g.DFS_rec("a");
    std::cout << "\n";
}
\$\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.