Graph.hpp

Go to the documentation of this file.

#pragma once
#include <vector>
#include <queue>
#include <set>
#include <iomanip> 
 
 
namespace mackey {
 
    template<typename _node, typename _edge, template<typename ...> typename container_t, typename ...Args>
    class Neighborhood {
    public:
        typedef _node node_t; 
        typedef _edge edge_t; 
        template<typename ... Argshere>
        void insert(node_t end, Argshere&&... args);
        void reserve(size_t n);
        struct const_iterator {
            auto operator ++()->const_iterator&;
            auto node() const->node_t;  
            auto edge() const->const edge_t&;
            bool operator!=(const_iterator other) const;
            const_iterator() = default;
        private:
            typedef typename container_t<std::pair<node_t, edge_t>, Args...>::const_iterator iter_t;
            const_iterator(iter_t it);
            iter_t it;
            friend class Neighborhood;
        };
        auto begin() const->const_iterator; 
        auto end() const->const_iterator;   
    private:
        container_t<std::pair<node_t, edge_t>, Args...> edges;
    };
 
    template<typename _neighborhood>
    class Graph {
    public:
        typedef _neighborhood neighborhood_t;           
        typedef typename neighborhood_t::edge_t edge_t; 
        typedef typename neighborhood_t::node_t node_t; 
        Graph() = default;
        size_t number_of_nodes() const;
 
        template<typename ... Args>
        void draw_edge(node_t start, node_t end, Args&&... args);
 
        void reserve_edges_for_node(size_t num, node_t node);
 
        template<typename T>
        void reserve_edges_per_node(const T& v);
 
        void reserve_nodes(size_t n);
 
        void adjoin_nodes(size_t new_number_of_nodes);
 
        auto neighbors(node_t node) const -> const neighborhood_t&;
 
        std::function<std::string(node_t)> node_names;
 
        void print_name_labels(std::ostream& os) const;
    private:
        std::vector<neighborhood_t> neighborhoods;
    };
    
    template<typename graph_t, typename policy_t>
    class ShortestPaths {
    public:
        typedef typename graph_t::node_t node_t;                                
        typedef typename graph_t::neighborhood_t::const_iterator edge_iter_t;   
 
        void print_path(std::ostream& os, node_t i) const;
 
        std::vector<std::vector<edge_iter_t>> paths;
 
        std::vector<node_t> root_per_path;
 
        void compute_with_root(node_t new_root);
 
        bool disconnected(node_t) const;
 
    protected:
        ShortestPaths(const graph_t& G);
 
        const graph_t& G;
 
        std::vector<size_t> distance_policy;
 
        std::vector<std::pair<node_t, edge_iter_t>> previous;
 
        node_t root;
 
    private:
        void print_path_minimal(std::ostream& os, node_t i, std::set<node_t>& nodes_printed) const;
        void print_path_minimal(std::ostream& os, node_t i) const;
        void compute_distance();
        void compute_paths();
        template<typename _graph, typename _pol>
        friend std::ostream& operator<<(std::ostream&, const ShortestPaths<_graph, _pol>&);
    };
 
    //Prints graph in .dot format with named nodes if provided
    template<typename neighborhood_t>
    std::ostream& operator<<(std::ostream& os, const Graph<neighborhood_t>& G);
 
    //Prints graph in .dot format with named nodes if provided
    template<typename graph_t, typename policy_t>
    std::ostream& operator<<(std::ostream& os, const ShortestPaths<graph_t, policy_t>& D);
 
}
#include "impl/Graph.ipp"