最短経路と行列乗算
10494 ワード
#include <iostream>
#include <stdexcept>
#include <vector>
#include <algorithm>
#include <memory>
#include <map>namespace{
enum:int{
MAXVALUE = 9999
};
}template<typename T>
class Node{
private:
T key_;
public:
typedef T key_type;
// .
template<typename Ty>
Node(const Ty& key);
// .
template<typename Ty>
Node(const Node<Ty>& otherNode_);
// .
template<typename Ty>
Node(Node<Ty>&& otherNode_);
// .
Node() = default;
// .
~Node();
template<typename Ty>
Node<Ty>& operator*()const;
//== .
template<typename Ty>
friend bool operator==(const Node<Ty>& first_, const Node<Ty>& second_);
//< .
template<typename Ty>
friend bool operator<(const Node<Ty>& first_, const Node<Ty>& second_);
// .
const Node<T>& operator=(const Node<T>& otherNode_);// .
//<< .
template<typename Ty>
friend std::ostream& operator<<(std::ostream& os, const Node<Ty>& node_);
// .
template<typename Ty>
void operator=(Node<Ty>&& otherNode_);
};template<typename T>
template<typename Ty>
Node<T>::Node(const Ty& key)
:key_(key)
{
//std::cout<<"constructor function."<<std::endl;
}template<typename T>
template<typename Ty>
Node<T>::Node(const Node<Ty>& otherNode_)
:key_(otherNode_.key_)
{
std::cout<<"copy for constructor"<<std::endl;
}template<typename T>
Node<T>::~Node()
{
//
}template<typename Ty>
bool operator==(const Node<Ty>& first_, const Node<Ty>& second_)
{
return (first_.key_ == second_.key_) ? true : false;
}template<typename T>
const Node<T>& Node<T>::operator=(const Node<T>& otherNode_) // .
{
this->key_ = otherNode_.key_;
std::cout<<"copy function"<<std::endl;
}template<typename T>
template<typename Ty>
Node<Ty>& Node<T>::operator*()const
{
return *this;
}template<typename Ty>
bool operator<(const Node<Ty>& first_, const Node<Ty>& second_)
{
//std::cout<<"<"<<std::endl;
return (first_.key_ < second_.key_) ? true : false;
}template<typename Ty>
std::ostream& operator<<(std::ostream& os, const Node<Ty>& node_)
{
os<<node_.key_<<std::endl;
return os;
}template<typename T>
template<typename Ty>
void Node<T>::operator=(Node<Ty>&& otherNode_)
{
std::cout<<"operator move"<<std::endl;
this->key_ = otherNode_.key_;
}template<typename T>
class Map{
private:
//class in class.
class Compare{
public:
template<typename Ty>
bool operator()(const Node<Ty>& first_, const Node<Ty>& second_);
};
//class in class.
class Container{
public:
template<typename Ty>
bool operator()(Map<Ty>* temp_map, typename Map<Ty>::cv_iter currentIter_first, typename Map<Ty>::v_iter currentIter_second);
};
std::map<Node<T>, std::map<Node<T>, int>> graph_; //
static std::map<Node<T>, std::vector<Node<T>>> adjList_;
std::map<Node<T>, std::map<Node<T>, int>> temp_graph_;
unsigned int nodeNumber_;
typename Map<T>::Graph extend_shortest_paths();
const int& min(const int& first_, const int& second_);
public:
typedef std::map<Node<T>, std::map<Node<T>, int>> Graph;
using v_iter = typename std::vector<Node<T>>::const_iterator;// .
using cv_iter = typename std::map<Node<T>, std::vector<Node<T>>>::const_iterator;
template<typename Ty>
using cmm_iter = typename std::map<Node<Ty>, std::map<Node<Ty>, int>>::const_iterator;// .
template<typename Ty>
using cm_iter = typename std::map<Node<Ty>, int>::const_iterator;
template<typename Ty, unsigned int N>
Map(const Ty (&edge)[N][3]);
~Map();
Map()=default;
void slow_all_pairs_shortest_paths();
void print();
};template<typename T>
std::map<Node<T>, std::vector<Node<T>>> Map<T>::adjList_;template<typename T>
template<typename Ty, unsigned int N>
Map<T>::Map(const Ty (&edges)[N][3])
:nodeNumber_(N)
{
if(N == 0){
throw std::runtime_error(std::string("there is nothing in graph"));
}
for(int i =0; i<N; ++i){ // 。
Node<Ty> first_(edges[i][0]);
Node<Ty> second_(edges[i][2]);
this->graph_[first_][second_] = edges[i][1];
//this->temp_graph_[first_][second_] = ::MAXVALUE;
this->adjList_[first_].push_back(second_); // ： A vector .
//std::cout<<"first: "<<first_<<std::endl;
//std::cout<<"second: "<<second_<<std::endl;
}
cv_iter iter_first = this->adjList_.cbegin();
for(; iter_first != this->adjList_.cend(); ++iter_first){
v_iter iter_second = this->adjList_[iter_first->first].cbegin();
for(; iter_second != this->adjList_[iter_first->first].cend(); ++iter_second){
std::cout<<"iter_first: "<<iter_first->first<<std::endl;
std::cout<<"iter_second: "<<*iter_second<<std::endl;
}
}
}template<typename T>
typename Map<T>::Graph Map<T>::extend_shortest_paths()
{
Container jundge_;
cv_iter first_ = this->adjList_.cbegin();
Graph l_graph_;
for(; first_ != this->adjList_.cend(); ++first_){
//std::cout<<"first_->first"<<first_->first<<std::endl;
v_iter second_ = this->adjList_[first_->first].cbegin();
for(; second_ != this->adjList_[first_->first].cend(); ++second_){
//std::cout<<"second_: "<< *second_ <<std::endl;
l_graph_[first_->first][*second_] = ::MAXVALUE;
cv_iter third_ = this->adjList_.cbegin();
for(; third_ != this->adjList_.cend(); ++third_){
bool boolean = jundge_(this, third_, second_);
if(boolean == false){
continue;
}
std::cout<<"first_:"<<(first_->first)<<std::endl;
std::cout<<"second_: "<<*second_<<std::endl;
std::cout<<"third_: "<<third_->first<<std::endl;
l_graph_[first_->first][*second_] = this->min(l_graph_[first_->first][*second_], this->temp_graph_[first_->first][third_->first]+this->graph_[third_->first][*second_]);
}
}
}
return l_graph_;
}template<typename T>
void Map<T>::slow_all_pairs_shortest_paths()
{
for(int i=1; i<this->nodeNumber_; ++i){
this->temp_graph_ = this->extend_shortest_paths();
}
}template<typename T>
template<typename Ty>
bool Map<T>::Compare::operator()(const Node<Ty>& first_, const Node<Ty>& second_)
{
return first_ < second_ ? true : false;
}template<typename T>
const int& Map<T>::min(const int& first_, const int& second_)
{
return (first_ < second_) ? first_ : second_;
}template<typename T>
template<typename Ty>
bool Map<T>::Container::operator()(Map<Ty>* temp_map, typename Map<Ty>::cv_iter currentIter_first, typename Map<Ty>::v_iter currentIter_second)
{
if(temp_map->adjList_[currentIter_first->first].empty()){
return false;
}else{
typename Map<Ty>::v_iter first_ = temp_map->adjList_[currentIter_first->first].cbegin();
typename Map<Ty>::v_iter second_ = temp_map->adjList_[currentIter_first->first].cend();
typename Map<Ty>::v_iter third_;
third_=std::find_if(first_, second_, [currentIter_second](const Node<Ty>& temp_)->bool { return (temp_ == *currentIter_second) ? true : false; });
if(third_ == second_){
return false;
}else{
return true;
}
}
}template<typename T>
void Map<T>::print()
{
if(this->temp_graph_.empty()){
std::cout<<"there is nothing/n"<<std::endl;
return;
}else{
cmm_iter<T> begin = this->temp_graph_.cbegin();
for(; begin != this->temp_graph_.cend(); ++begin){
Node<T> temp_node = begin->first;
cm_iter<T> begin_ = this->temp_graph_[temp_node].cbegin();
for(; begin_ != this->temp_graph_[temp_node].cend(); ++begin_){
std::cout<< (begin->first) <<"<->"<<begin_->second<<"<->"<<begin_->first<<std::endl;
}
}
}
}template<typename T>
Map<T>::~Map()
{
if(!this->graph_.empty()){
this->graph_.clear();
}
if(!this->adjList_.empty()){
this->adjList_.clear();
}
if(!this->temp_graph_.empty()){
this->temp_graph_.clear();
}
}int main()
{
/*Node<int> one_(20);
Node<int> two_(30);
Node<int> three_;
three_ = one_;
one_ = two_;
std::cout<<one_;
three_ = std::move(one_);
std::cout<<std::boolalpha<< (one_<two_ )<<std::endl;*/
int graph[9][3]={
{1, 3, 2},//node--weighting--node.
{1, 8, 3},
{1, -4, 5},
{2, 7, 5},
{2, 1, 4},
{3, 4, 2},
{4, 2, 1},
{4, -5, 3},
{5, 6, 4}
};
Map<int> myGraph(graph);
myGraph.slow_all_pairs_shortest_paths();
myGraph.print();
return 0;
}