network.hpp

#ifndef NETWORK_H
#define NETWORK_H
 
#include <unordered_map>
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/exception.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/range/adaptor/filtered.hpp>
#include <boost/range/adaptor/transformed.hpp>
#include <boost/range/adaptor/reversed.hpp>
 
#include <features/Features.hpp>
#include <FeatureBuilder.hpp>
 
#include "HY_Features_Ids.hpp"
 
namespace network {
 
  const static int DEFAULT_LAYER_ID = 0;
 
  enum class SortOrder {
    Topological,
    TransposedDepthFirstPreorder
  };
  struct VertexProperty{
    std::string id;
  };
 
  template < typename OutputIterator >
  struct preorder_visitor : public boost::dfs_visitor<>
  {
      preorder_visitor(OutputIterator _iter) : m_iter(_iter) {}
 
      template < typename Edge, typename Graph >
      void back_edge(const Edge&, Graph&)
      {
          BOOST_THROW_EXCEPTION(boost::not_a_dag());
      }
 
      template < typename Vertex, typename Graph >
      void discover_vertex(const Vertex& u, Graph&)
      {
          *m_iter++ = u;
          //std::cerr << "vdiscover_vertex " << u << std::endl;
      }
 
      OutputIterator m_iter;
  };
 
  template < typename VertexListGraph, typename OutputIterator, typename P,
    typename T, typename R >
  void df_preorder_sort(VertexListGraph& g, OutputIterator result,
      const boost::bgl_named_params< P, T, R >& params)
  {
      typedef preorder_visitor< OutputIterator > PreOrderVisitor;
      depth_first_search(g, params.visitor(PreOrderVisitor(result)));
  }
 
  template < typename VertexListGraph, typename OutputIterator >
  void df_preorder_sort(VertexListGraph& g, OutputIterator result)
  {
      df_preorder_sort(
          g, result, boost::bgl_named_params< int, boost::buffer_param_t >(0)); // no additional named params
  }
 
  typedef boost::property<boost::vertex_index_t, std::size_t> IndexT;
  typedef boost::property<boost::vertex_name_t, std::string, IndexT> NodeT;
  typedef boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, NodeT> Graph;
  typedef std::vector< Graph::vertex_descriptor > NetworkIndexT;
  using IndexPair = std::pair< NetworkIndexT::const_iterator, NetworkIndexT::const_iterator>;
 
    class Network {
      public:
        Network() {}
 
        Network( geojson::GeoJSON fabric );
 
        Network( geojson::GeoJSON features, std::string* link_key);
 
        virtual ~Network(){}
 
        NetworkIndexT::const_reverse_iterator begin();
 
        NetworkIndexT::const_reverse_iterator end();
        
        auto filter(std::string type, SortOrder order = SortOrder::Topological) const
        {
          //todo need to worry about validating input???
          //if type isn't found as a prefix, this iterator range should be empty,
          //which is a reasonable semantic
          return get_sorted_index(order) | boost::adaptors::reversed
                        | boost::adaptors::transformed([this](int const& i) { return get_id(i); })
                        | boost::adaptors::filtered([type](std::string const& s) { 
                          //seperate the prefix from the numeric id
                          std::string id_type = s.substr(0, s.find(hy_features::identifiers::separator) );
                          //Allow subtypes, e.g. inx, tnx, cnx, to be pass the filter for a generic nexus type
                          if(type == hy_features::identifiers::nexus){
                            return hy_features::identifiers::isNexus(id_type);
                          }
                          //Allow subtypes, e.g. wb to be pass the filter for a generic catchment type
                          if(type == hy_features::identifiers::catchment){
                            return hy_features::identifiers::isCatchment(id_type);
                          }
                          //any other subtype filter gets only exact matches
                          return id_type == type; 
                        });
 
        }
 
        auto filter(std::string type, int target_layer, SortOrder order = SortOrder::Topological) const
        {
          //todo need to worry about valivdating input???
          //if type isn't found as a prefix, this iterator range should be empty,
          //which is a reasonable semantic
          return get_sorted_index(order) | boost::adaptors::reversed
                        | boost::adaptors::transformed([this](int const& i) { return get_id(i); })
                        | boost::adaptors::filtered([this,type,target_layer](std::string const& s) { 
                          //seperate the prefix from the numeric id
                          std::string id_type = s.substr(0, s.find(hy_features::identifiers::separator) );
 
                          bool type_matches;
 
                          if (type == hy_features::identifiers::nexus) type_matches = hy_features::identifiers::isNexus(id_type);
                          else if (type == hy_features::identifiers::catchment) type_matches = hy_features::identifiers::isCatchment(id_type);
                          else type_matches = (id_type == type);
 
                          if (!type_matches) return false;
 
                          auto iter = this->layer_map.find(s);
                          if (iter == this->layer_map.end()) return false;
 
                          auto const& layer = iter->second;
                          return layer == target_layer;
                        });
        }
        std::string get_id( Graph::vertex_descriptor idx) const;
 
        std::vector<std::string> get_origination_ids(const std::string& id);
 
        std::vector<std::string> get_destination_ids(const std::string& id);
 
        std::size_t size();
 
        IndexPair headwaters();
 
        IndexPair tailwaters();
 
        void print_network(){
          boost::dynamic_properties dp;
          dp.property("node_id", get(boost::vertex_name, this->graph));
          boost::write_graphviz_dp(std::cout, graph, dp);
        }
 
      protected:
 
      private:
 
        void init_indicies();
 
        NetworkIndexT topo_order;
 
        mutable NetworkIndexT tdfp_order;
 
        NetworkIndexT headwaters_idx;
        
        NetworkIndexT tailwaters_idx;
 
        //There are "classes" of tailwater to consider, "Free" "Coastal" "Internal" etc
        //Really the same is true for head waters in the "Free" and "Internal" sense where
        //there are interactions of boundary conditions
        //TODO Distributary network??? Has topological "wildcard"
        //Diffusive routing can assume DAG, Dynamic routing cannot
 
        Graph graph;
 
        std::unordered_map<std::string, Graph::vertex_descriptor> descriptor_map;
 
        std::unordered_map<std::string, long> layer_map;
        
        const NetworkIndexT& get_sorted_index(SortOrder order = SortOrder::Topological, bool cache = true) const;
 
    };
}
 
#endif //NETWORK_H