#include"DijkstraSP.h"

#include"TopoLongestPath.h"

#include"BellmanFordSP.h"

int main(){

EdgeWeightedDigraph* G = new EdgeWeightedDigraph("./data/tinyEWD.txt"); //tinyDAG无环有向图

//基础测试

cout<<G->getE()<<endl;

cout<<G->getV()<<endl;

cout<<G->degree(0)<<endl;

//Dijkstra shortest path测试

cout<<endl;

int startV=0;

int endV = 6;

DijkstraSP* dSP = new DijkstraSP(G,startV);

dSP->getSP(G,startV);

cout<<"hasPathTo endVertex="<<endV<<" is "<<(bool)dSP->hasPathTo(endV)<<endl;

double totalW=0.0;

for(DiEdge e:dSP->pathTo(endV)){

cout<<e.from()<<"-"<<e.to()<<" "<<e.getWeight()<<endl;

totalW += e.getWeight();

}

cout<<"from 0 to 6, shortestpath="<<totalW<<endl;

cout<<endl;

//无环图 LongestPath测试

startV=5;

endV = 2;

G = new EdgeWeightedDigraph("./data/tinyEWDAG.txt");

TopoLP* topoLP = new TopoLP(G);

topoLP->getTopoLP(G,startV);

totalW=0.0;

for(DiEdge e:topoLP->pathTo(endV)){

cout<<e.from()<<"-"<<e.to()<<" "<<e.getWeight()<<endl;

totalW += e.getWeight();

}

cout<<"from 5 to 2, longestpath="<<totalW<<endl;

//思考:

//应用: 限制优先级问题

//idea: 将限制条件转化为有向图 P431 => 加权有向图最长路径

//一般性问题 Bellman-Ford

//不存在权重值之和为负的还 有向图

cout<<endl;

startV=0;

endV = 3;

G = new EdgeWeightedDigraph("./data/tinyEWDnc.txt");

BellmanSP* bSP = new BellmanSP(G);

bSP->getBellmanSP(G,startV);

totalW=0.0;

for(DiEdge e:bSP->pathTo(endV)){

cout<<e.from()<<"-"<<e.to()<<" "<<e.getWeight()<<endl;

totalW += e.getWeight();

}

cout<<"from 0 to 1, longestpath="<<totalW<<endl;

//思考:

//金融套汇问题 ==》 转化为寻找负权重之和的环 P444

}