graph_metrics.hpp

Go to the documentation of this file.

//=======================================================================
// Copyright (c) 2013 Piotr Wygocki
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef PAAL_GRAPH_METRICS_HPP
#define PAAL_GRAPH_METRICS_HPP

#include "basic_metrics.hpp"

#include <boost/graph/johnson_all_pairs_shortest.hpp>
#include <boost/graph/floyd_warshall_shortest.hpp>
#include <boost/graph/adjacency_matrix.hpp>

namespace paal {
namespace data_structures {

namespace graph_type {
class sparse_tag;
class dense_tag;
class large_tag;
}

template <typename Graph> struct graph_metric_traits {
    //default graph_type
    using graph_tag_type = graph_type::sparse_tag;
};


template <typename graph_tag_type> struct graph_metric_filler_impl;

template <> struct graph_metric_filler_impl<graph_type::sparse_tag> {
    template <typename Graph, typename ResultMatrix>
    void fill_matrix(const Graph &g, ResultMatrix &rm) {
        boost::johnson_all_pairs_shortest_paths(g, rm);
    }
};

template <> struct graph_metric_filler_impl<graph_type::dense_tag> {
    template <typename Graph, typename ResultMatrix>
        void fill_matrix(const Graph &g, ResultMatrix &rm) {
        boost::floyd_warshall_all_pairs_shortest_paths(g, rm);
    }
};

// GENERIC
// GraphType could be sparse, dense, large ...
template <
    typename Graph, typename DistanceType,
    typename GraphType = typename graph_metric_traits<Graph>::graph_tag_type>
struct graph_metric : public array_metric<DistanceType>,
                      public graph_metric_filler_impl<
                          typename graph_metric_traits<Graph>::graph_tag_type> {
    typedef array_metric<DistanceType> GMBase;
    typedef graph_metric_filler_impl<
        typename graph_metric_traits<Graph>::graph_tag_type> GMFBase;

    graph_metric(const Graph &g) : GMBase(num_vertices(g)) {
        GMFBase::fill_matrix(g, GMBase::m_matrix);
    }
};

// TODO implement
template <typename Graph, typename DistanceType>
struct graph_metric<Graph, DistanceType, graph_type::large_tag> {
    graph_metric(const Graph &g) { assert(false); }
};

template <typename OutEdgeList, typename VertexList, typename Directed,
          typename VertexProperties, typename EdgeProperties,
          typename GraphProperties, typename EdgeList>
struct graph_metric_traits<
    boost::adjacency_list<OutEdgeList, VertexList, Directed, VertexProperties,
                          EdgeProperties, GraphProperties, EdgeList>> {
    typedef graph_type::sparse_tag graph_tag_type;
};

template <typename Directed, typename VertexProperty, typename EdgeProperty,
          typename GraphProperty, typename Allocator>
struct graph_metric_traits<boost::adjacency_matrix<
    Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>> {
    typedef graph_type::dense_tag graph_tag_type;
};

} 
} 

#endif // PAAL_GRAPH_METRICS_HPP