Line data    Source code

       1           0 : // Distributed under the MIT License.
       2             : // See LICENSE.txt for details.
       3             : 
       4             : #pragma once
       5             : 
       6             : #include <brigand/brigand.hpp>
       7             : #include <type_traits>
       8             : 
       9             : #include "Utilities/Requires.hpp"
      10             : 
      11             : namespace brigand {
      12             : 
      13             : template <typename Source, typename Destination, typename Weight = int32_t<1>>
      14           0 : struct edge {
      15           0 :   using source = Source;
      16           0 :   using destination = Destination;
      17           0 :   using weight = Weight;
      18             : };
      19             : 
      20             : template <int Source, int Destination, int Weight = 1>
      21           0 : using edge_ = edge<int32_t<Source>, int32_t<Destination>, int32_t<Weight>>;
      22             : 
      23             : template <typename T>
      24           0 : struct get_source;
      25             : template <typename Source, typename Destination, typename Weight>
      26           0 : struct get_source<edge<Source, Destination, Weight>> {
      27           0 :   using type = Source;
      28             : };
      29             : 
      30             : template <typename T>
      31           0 : struct get_destination;
      32             : template <typename Source, typename Destination, typename Weight>
      33           0 : struct get_destination<edge<Source, Destination, Weight>> {
      34           0 :   using type = Destination;
      35             : };
      36             : 
      37             : template <typename T>
      38           0 : struct get_weight;
      39             : template <typename Source, typename Destination, typename Weight>
      40           0 : struct get_weight<edge<Source, Destination, Weight>> {
      41           0 :   using type = Weight;
      42             : };
      43             : 
      44             : template <typename State, typename Element>
      45           0 : struct add_unique_vertex;
      46             : 
      47             : template <typename State, typename Source, typename Destination,
      48             :           typename Weight>
      49           0 : struct add_unique_vertex<State, edge<Source, Destination, Weight>> {
      50           0 :   using source = typename if_<found<State, std::is_same<pin<Source>, _1>>,
      51             :                               list<>, list<Source>>::type;
      52           0 :   using destination =
      53             :       typename if_<found<State, std::is_same<pin<Destination>, _1>>, list<>,
      54             :                    list<Destination>>::type;
      55           0 :   using type = append<State, source, destination>;
      56             : };
      57             : 
      58             : template <class E, class S, class = std::nullptr_t>
      59           0 : struct has_source : std::false_type {};
      60             : template <class E, class S>
      61             : struct has_source<E, S, Requires<std::is_same<typename E::source, S>::value>>
      62             :     : std::true_type {};
      63             : 
      64             : template <class E, class D, class = void>
      65           0 : struct has_destination : std::false_type {};
      66             : template <class E, class D>
      67             : struct has_destination<
      68             :     E, D, Requires<std::is_same<typename E::destination, D>::value>>
      69             :     : std::true_type {};
      70             : 
      71             : template <class E, class S, class D>
      72           0 : struct has_source_and_destination : std::false_type {};
      73             : template <template <class...> class E, class S, class D, class W>
      74           0 : struct has_source_and_destination<E<S, D, W>, S, D> : std::true_type {};
      75             : 
      76             : template <class edgeList>
      77           0 : struct digraph;
      78             : 
      79             : namespace detail {
      80             : template <class Graph, class S, class D>
      81             : struct get_edge_impl;
      82             : template <class S, class D, class edgeList>
      83             : struct get_edge_impl<digraph<edgeList>, S, D> {
      84             :   using type = find<edgeList, has_source_and_destination<_1, pin<S>, pin<D>>>;
      85             : };
      86             : }  // namespace detail
      87             : 
      88             : namespace detail {
      89             : template <class Graph, class S, class D>
      90             : struct has_edge_impl;
      91             : template <class S, class D, class edgeList>
      92             : struct has_edge_impl<digraph<edgeList>, S, D>
      93             :     : found<edgeList, has_source_and_destination<_1, pin<S>, pin<D>>> {};
      94             : }  // namespace detail
      95             : 
      96             : template <class Graph>
      97           0 : struct outgoing_edges_impl;
      98             : template <class edgeList>
      99           0 : struct outgoing_edges_impl<digraph<edgeList>> {
     100           0 :   using type = typename digraph<edgeList>::adjacency_list;
     101             : };
     102             : 
     103             : template <class Graph>
     104           0 : struct ingoing_edges_impl;
     105             : template <class edgeList>
     106           0 : struct ingoing_edges_impl<digraph<edgeList>> {
     107           0 :   using type = typename digraph<edgeList>::ingoing_list;
     108             : };
     109             : 
     110             : // This is what we would like to do, but Intel cannot handle it...
     111             : template <class T, template <class...> class F, class... Es>
     112           0 : struct compute_adjacency_list;
     113             : template <template <class...> class VertexSeq, class... Vertices, class... Es,
     114             :           template <class...> class F>
     115           0 : struct compute_adjacency_list<VertexSeq<Vertices...>, F, Es...> {
     116           0 :   using type = brigand::list<
     117             :       brigand::filter<brigand::list<Es...>, F<brigand::_1, pin<Vertices>>>...>;
     118             : };
     119             : 
     120             : template <template <class...> class List, class... edges>
     121           0 : struct digraph<List<edges...>> {
     122             :  public:
     123           0 :   using edge_list = list<edges...>;
     124             :   static_assert(is_set<edge_list>::value,
     125             :                 "Cannot have repeated edges in a digraph");
     126           0 :   using unique_vertex_list =
     127             :       fold<edge_list, list<>, add_unique_vertex<_state, _element>>;
     128           0 :   using vertex_count = size<unique_vertex_list>;
     129           0 :   using edge_count = uint32_t<sizeof...(edges)>;
     130             : 
     131           0 :   using adjacency_list =
     132             :       compute_adjacency_list<unique_vertex_list, has_source, edges...>;
     133             : 
     134           0 :   using ingoing_list =
     135             :       compute_adjacency_list<unique_vertex_list, has_destination, edges...>;
     136             : 
     137             :   template <class E>
     138             :   static digraph<::brigand::remove<
     139             :       list<edges...>,
     140             :       detail::get_edge_impl<digraph<List<edges...>>, typename E::source,
     141             :                             typename E::destination>>>
     142           0 :       erase(brigand::type_<E>);
     143             : 
     144             :   template <class E>
     145             :   static digraph<push_back<
     146             :       remove<list<edges...>,
     147             :              detail::get_edge_impl<digraph<List<edges...>>, typename E::source,
     148             :                                    typename E::destination>>,
     149             :       E>>
     150           0 :       insert(::brigand::type_<E>);
     151             : };
     152             : 
     153             : namespace lazy {
     154             : template <class Graph, class S, class D>
     155           0 : using has_edge = ::brigand::detail::has_edge_impl<Graph, S, D>;
     156             : }  // namespace lazy
     157             : 
     158             : /*!
     159             :  * \ingroup UtilitiesGroup
     160             :  * \brief Check if a digraph has an edge with source `S` and destination `D`
     161             :  *
     162             :  *
     163             :  */
     164             : template <class Graph, class S, class D>
     165           1 : using has_edge = typename ::brigand::lazy::has_edge<Graph, S, D>::type;
     166             : 
     167             : namespace lazy {
     168             : template <class Graph, class S, class D>
     169           0 : using get_edge = ::brigand::detail::get_edge_impl<Graph, S, D>;
     170             : }  // namespace lazy
     171             : 
     172             : template <class Graph, class S, class D>
     173           0 : using get_edge = typename ::brigand::lazy::get_edge<Graph, S, D>;
     174             : 
     175             : template <class Graph, class Vertex>
     176           0 : using outgoing_edges = at<typename Graph::adjacency_list::type,
     177             :                           index_of<typename Graph::unique_vertex_list, Vertex>>;
     178             : 
     179             : template <class Graph, class Vertex>
     180           0 : using ingoing_edges = at<typename Graph::ingoing_list::type,
     181             :                          index_of<typename Graph::unique_vertex_list, Vertex>>;
     182             : 
     183             : template <class Graph>
     184           0 : using vertex_count = size<typename Graph::unique_vertex_list>;
     185             : 
     186             : template <class Graph>
     187           0 : using edge_count = size<typename Graph::edge_list>;
     188             : }  // namespace brigand