C语言最短路径和矩阵乘法.
2018-07-20 来源：open-open
#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:
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>
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 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 Compare{
public:
template<typename Ty>
bool operator()(const Node<Ty>& first_, const Node<Ty>& second_);
};
//template<typename Ty>
//typedef Graph std::map<Node<Ty>, std::map<Node<Ty>, int>>; //不能用typedef只能用using.
class Container{
public:
template<typename Ty>
bool operator()(typename Map<Ty>::cv_iter currentIter_, std::shared_ptr<Node<Ty>> currentNode_);
};
std::map<Node<T>, std::map<Node<T>, int>> graph_; //该边的加权值可以为负
std::map<Node<T>, std::vector<Node<T>>> adjList_;
std::map<Node<T>, std::map<Node<T>, int>> temp_graph_;
unsigned int nodeNumber_;
template<typename Ty>
typename Map<Ty>::Graph extend_shortest_paths(std::shared_ptr< typename Map<Ty>::Graph > g);
const int& min(const int& first_, const int& second_);
public:
template<typename Ty>
using Graph = std::map<Node<Ty>, std::map<Node<Ty>, int>>;//类型别名.
template<typename Ty>
using v_iter = typename std::vector<Node<Ty>>::const_iterator;//类型别名.
template<typename Ty>
using cv_iter = typename std::map<Node<Ty>, std::vector<Node<Ty>>>::const_iterator;
template<typename Ty>
using cmm_iter = typename std::map<Node<Ty>, 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();
};
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中.
}
}
template<typename T>
template<typename Ty>
typename Map<Ty>::Graph Map<T>::extend_shortest_paths(std::shared_ptr< typename Map<Ty>::Graph > g)
{
typename Map<Ty>::Container jundge_;
typename Map<Ty>::cv_iter first_ = this->adjList_.cbegin();
typename Map<Ty>::v_iter second_ = this->adjList_[first_->first].cbegin();
typename Map<Ty>::Graph temp_graph_;
for(; first_ != this->adjList_.cend(); ++first_){
for(; second_ != this->adjList_[first_->first].cend(); ++second_){
temp_graph_[first_->first][*second_] = ::MAXVALUE;
typename Map<Ty>::v_iter third_ = this->adjList_[first_->first].cbegin();
for(; third_ != this->adjList_[first_->first].cend(); ++third_){
bool boolean = jundge(third_, std::make_shared<Node<Ty>> (*second_));
if(boolean == false){
continue;
}
temp_graph_[first_][second_] = this->min(temp_graph_[first_][second_], (*g)[first_][third_]+this->graph_[third_][second_]);
}
}
}
return (*g);
}
template<typename T>
void Map<T>::slow_all_pairs_shortest_paths()
{
Map<T>::Graph<T> L(this->graph_);
for(int i=1; i<this->nodeNumber_; ++i){
L = this->extended_shortest_paths(std::make_shared< Map<T>::Graph<T> > (this->graph_));
}
}
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()(typename Map<Ty>::cv_iter currentIter_, std::shared_ptr<Node<Ty>> currentNode_)
{
if(Map<Ty>::adjList_[*currentNode_].empty()){
return false;
}else{
typename Map<Ty>::v_iter first_ = Map<Ty>::adjList_[*currentNode_].cbegin();
typename Map<Ty>::v_iter second_ = Map<Ty>::adjList_[*currentNode_].cend();
typename Map<Ty>::v_iter third_;
third_=std::find_if(first_, second_, [currentNode_](const Node<Ty>& temp_)->bool { return (temp_ == *currentNode_) ? true : false; });
if(third_ == second_){
return false;
}else{
return true;
}
}
}
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;
return 0;
}
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。
最新资讯
热门推荐