C語言最短路徑和矩陣乘法.
#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;
} 本文由用戶 kycb6387 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！