#include "graph_implement.h"
#include <QDebug>

AbstractGraph::~AbstractGraph(){}

void ALVex::visit(){
 if(visited)
 return;
 info->gVex->visit(true);
 visited = true;
}

void ALVex::access(const QString &hint){
 info->gVex->access(hint);
}

void ALArc::visit(){
 gArc->visit(true);
}

void ALArc::access(){
 gArc->access();
}

ALGraph::~ALGraph(){
 int i = vexList.size() - 1;
 while(i >= 0)
 DelVex(i--);
 vexList.clear();
}

void ALGraph::AddVex(MyGraphicsVexItem *gvex){
 ALVex newVex(gvex);
 vexList.push_back(newVex);
}

void ALGraph::AddVex(VexInfo *info){
 ALVex newVex(info);
 vexList.push_back(newVex);
}

void ALGraph::AddArc(MyGraphicsLineItem *garc, int weight){
 int strtVex = GetIdOf(garc->stVex());
 int endVex = GetIdOf(garc->edVex());

 ALArc *temp = vexList[strtVex].firstArc;
 ALArc *newArc = new ALArc(garc, endVex, temp);
 newArc->weight = weight;
 vexList[strtVex].firstArc = newArc;

 if(type == UDG){
 temp = vexList[endVex].firstArc;
 newArc = new ALArc(garc, strtVex, temp);
 vexList[endVex].firstArc = newArc;
 }
}

void ALGraph::DelVex(MyGraphicsVexItem *gvex){
 int vexID = GetIdOf(gvex);
 DelVex(vexID);
}

void ALGraph::DelVex(int vexID){
 //Delete out arc
 ALArc *curArc = vexList[vexID].firstArc;
 while(curArc != nullptr){
 ALArc *next = curArc->nextArc;
 delete curArc;
 curArc = next;
 }
 //Delete in arc and adjust arcs
 for(int i = 0; i < vexList.size(); i++){
 if(i == vexID) continue;
 ALArc *dummyHead = new ALArc(nullptr, 0, vexList[i].firstArc);
 ALArc *preArc = dummyHead;
 while(preArc->nextArc != nullptr){
 if(preArc->nextArc->eVexID == vexID){
 ALArc *next = preArc->nextArc;
 preArc->nextArc = next->nextArc;
 delete next;
 continue;
 }
 if(preArc->nextArc->eVexID > vexID)
 preArc->nextArc->eVexID--;
 preArc = preArc->nextArc;
 }
 vexList[i].firstArc = dummyHead->nextArc;
 delete dummyHead;
 }
 vexList.erase(vexList.begin() + vexID);
}

void ALGraph::DelArc(MyGraphicsLineItem *garc){
 int sVex = GetIdOf(garc->stVex());
 int eVex = GetIdOf(garc->edVex());
 DelArc(sVex, eVex);
}

void ALGraph::DelArc(int sVexID, int eVexID){
 //Delete sVex -> eVex
 if(vexList[sVexID].firstArc != nullptr){
 if(vexList[sVexID].firstArc->eVexID == eVexID){
 ALArc *awaitDel = vexList[sVexID].firstArc;
 vexList[sVexID].firstArc = awaitDel->nextArc;
 delete awaitDel;
 }
 else{
 ALArc *preArc = vexList[sVexID].firstArc;
 while(preArc->nextArc != nullptr && preArc->nextArc->eVexID != eVexID)
 preArc = preArc->nextArc;
 if(preArc->nextArc != nullptr){
 ALArc *awaitDel = preArc->nextArc;
 preArc->nextArc = awaitDel->nextArc;
 delete awaitDel;
 }
 }
 }
 //Delete eVex -> sVex
 if(type == UDG && vexList[eVexID].firstArc != nullptr){
 if(vexList[eVexID].firstArc->eVexID == sVexID){
 ALArc *awaitDel = vexList[eVexID].firstArc;
 vexList[eVexID].firstArc = awaitDel->nextArc;
 delete awaitDel;
 }
 else{
 ALArc *preArc = vexList[eVexID].firstArc;
 while(preArc->nextArc != nullptr && preArc->nextArc->eVexID != sVexID)
 preArc = preArc->nextArc;
 if(preArc->nextArc != nullptr){
 ALArc *awaitDel = preArc->nextArc;
 preArc->nextArc = awaitDel->nextArc;
 delete awaitDel;
 }
 }
 }
}

int ALGraph::GetIdOf(MyGraphicsVexItem *gvex){
 int i = 0;
 while(i < vexList.size() && !vexList[i].info->gVex->equalTo(gvex))
 i++;
 return i == vexList.size() ? -1 : i;
}

ALArc* ALGraph::FindArc(int sID, int eID){
 if(sID < 0 || sID >= vexList.size())
 return nullptr;
 ALArc *p = vexList[sID].firstArc;
 while(p != nullptr){
 if(p->eVexID == eID)
 return p;
 p = p->nextArc;
 }
 return nullptr;
}

void ALGraph::SetWeight(MyGraphicsLineItem *garc, int weight){
 int strtVex = GetIdOf(garc->stVex());
 int endVex = GetIdOf(garc->edVex());
 ALArc *p = vexList[strtVex].firstArc;
 while(p != nullptr){
 if(p->eVexID == endVex){
 p->weight = weight;
 p->gArc->setText(QString::asprintf("%d", weight));
 }
 p = p->nextArc;
 }
 if(type == UDG){
 p = vexList[endVex].firstArc;
 while(p != nullptr){
 if(p->eVexID == strtVex){
 p->weight = weight;
 }
 p = p->nextArc;
 }
 }
}

void ALGraph::ConvertType(int _type){
 if(_type == type) return;
 type = _type;
 if(type == UDG){
 for(int i = 0; i < vexList.size(); i++){
 ALArc *dummyHead = new ALArc(nullptr, i, vexList[i].firstArc);
 ALArc *pre = dummyHead;
 while(pre->nextArc != nullptr){
 if(pre->nextArc->eVexID == GetIdOf(pre->nextArc->gArc->edVex())){
 ALArc *temp = vexList[pre->nextArc->eVexID].firstArc;
 vexList[pre->nextArc->eVexID].firstArc = new ALArc(pre->nextArc->gArc, i, temp);
 pre->nextArc->gArc->setDirection(false);
 }
 pre = pre->nextArc;
 }
 delete dummyHead;
 }
 }
 else{
 for(int i = 0; i < vexList.size(); i++){
 ALArc *dummyHead = new ALArc(nullptr, i, vexList[i].firstArc);
 ALArc *pre = dummyHead;
 while(pre->nextArc != nullptr){
 if(pre->nextArc->eVexID != GetIdOf(pre->nextArc->gArc->edVex())){
 ALArc *temp = pre->nextArc;
 pre->nextArc = temp->nextArc;
 temp->gArc->setDirection(true);
 delete temp;
 continue;
 }
 pre = pre->nextArc;
 }
 vexList[i].firstArc = dummyHead->nextArc;
 delete dummyHead;
 }
 }
}

void ALGraph::ClearVisit(){
 for(int i = 0; i < vexList.size(); i++){
 vexList[i].visited = false;
 vexList[i].info->gVex->visit(false);
 }
}

void ALGraph::ResetDistance(){
 for(int i = 0; i < vexList.size(); i++){
 vexList[i].info->strtVexInfo = nullptr;
 vexList[i].info->distance = VexInfo::INF;
 vexList[i].info->preVexID = -1;
 vexList[i].info->gVex->access("", false);
 }
}

void ALGraph::DFS(int strtID, bool generateForest){
 if(strtID == -1)
 return;
 vector<int> awaitVexList;
 vector<ALArc*> awaitArcList;
 awaitVexList.push_back(strtID);
 while(awaitVexList.size() > 0){
 int nextVex = awaitVexList.back();
 ALArc *nextArc = awaitArcList.size() > 0 ? awaitArcList.back() : nullptr;
 awaitVexList.pop_back();
 if(nextArc)
 awaitArcList.pop_back();
 for(ALArc *p = vexList[nextVex].firstArc; p != nullptr; p = p->nextArc){
 if(vexList[p->eVexID].visited == false){
 awaitVexList.push_back(p->eVexID);
 awaitArcList.push_back(p);
 if(type == UDG && GetIdOf(p->gArc->edVex()) != p->eVexID)
 p->gArc->reverseDirection();
 }
 }
 if(nextArc && !vexList[nextArc->eVexID].visited)
 nextArc->visit();
 vexList[nextVex].visit();
 }
 if(generateForest){
 for(int i = 0; i < vexList.size(); i++){
 if(vexList[i].visited) continue;
 awaitVexList.clear();
 awaitArcList.clear();
 awaitVexList.push_back(i);
 while(awaitVexList.size() > 0){
 int nextVex = awaitVexList.back();
 ALArc *nextArc = awaitArcList.size() > 0 ? awaitArcList.back() : nullptr;
 awaitVexList.pop_back();
 if(nextArc)
 awaitArcList.pop_back();
 for(ALArc *p = vexList[nextVex].firstArc; p != nullptr; p = p->nextArc){
 if(vexList[p->eVexID].visited == false){
 awaitVexList.push_back(p->eVexID);
 awaitArcList.push_back(p);
 if(type == UDG && GetIdOf(p->gArc->edVex()) != p->eVexID)
 p->gArc->reverseDirection();
 }
 }
 if(nextArc && !vexList[nextArc->eVexID].visited)
 nextArc->visit();
 vexList[nextVex].visit();
 }
 }
 }
}

void ALGraph::BFS(int strtID, bool generateForest){
 if(strtID == -1)
 return;
 vector<int> awaitVexList;
 vector<ALArc*> awaitArcList;
 awaitVexList.push_back(strtID);
 while(awaitVexList.size() > 0){
 int nextVex = awaitVexList[0];
 ALArc *nextArc = awaitArcList.size() > 0 ? awaitArcList[0] : nullptr;
 awaitVexList.erase(awaitVexList.begin());
 if(nextArc)
 awaitArcList.erase(awaitArcList.begin());
 for(ALArc *p = vexList[nextVex].firstArc; p != nullptr; p = p->nextArc){
 if(vexList[p->eVexID].visited == false){
 awaitVexList.push_back(p->eVexID);
 awaitArcList.push_back(p);
 if(type == UDG && GetIdOf(p->gArc->edVex()) != p->eVexID)
 p->gArc->reverseDirection();
 }
 }
 if(nextArc && !vexList[nextArc->eVexID].visited)
 nextArc->visit();
 vexList[nextVex].visit();
 }
 if(generateForest){
 for(int i = 0; i < vexList.size(); i++){
 if(vexList[i].visited) continue;
 awaitVexList.clear();
 awaitArcList.clear();
 awaitVexList.push_back(i);
 while(awaitVexList.size() > 0){
 int nextVex = awaitVexList[0];
 ALArc *nextArc = awaitArcList.size() > 0 ? awaitArcList[0] : nullptr;
 awaitVexList.erase(awaitVexList.begin());
 if(nextArc)
 awaitArcList.erase(awaitArcList.begin());
 for(ALArc *p = vexList[nextVex].firstArc; p != nullptr; p = p->nextArc){
 if(vexList[p->eVexID].visited == false){
 awaitVexList.push_back(p->eVexID);
 awaitArcList.push_back(p);
 if(type == UDG && GetIdOf(p->gArc->edVex()) != p->eVexID)
 p->gArc->reverseDirection();
 }
 }
 if(nextArc && !vexList[nextArc->eVexID].visited)
 nextArc->visit();
 vexList[nextVex].visit();
 }
 }
 }
}

void ALGraph::Dijkstra(int strtID){
 //Clear previous result
 ClearVisit();
 ResetDistance();
 //Set start vex info to all vertexes
 for(int i = 0; i < vexList.size(); i++)
 vexList[i].info->strtVexInfo = vexList[strtID].info;
 //Start dijkstra
 vexList[strtID].info->distance = 0;
 vexList[strtID].access("strt");
 while(true){
 //Find next
 int minVexID = -1;
 for(int i = 0; i < vexList.size(); i++){
 if(vexList[i].visited || vexList[i].info->distance == VexInfo::INF)
 continue;
 if(minVexID == -1)
 minVexID = i;
 else if(vexList[i].info->distance < vexList[minVexID].info->distance)
 minVexID = i;
 }
 if(minVexID == -1)
 break;
 //Set visit to edge and vex
 ALArc *edge = FindArc(vexList[minVexID].info->preVexID, minVexID);
 if(edge){
 if(type == UDG && GetIdOf(edge->gArc->edVex()) != minVexID)
 edge->gArc->reverseDirection();
 edge->visit();
 }
 vexList[minVexID].visit();
 //Find adjacent
 for(ALArc *p = vexList[minVexID].firstArc; p != nullptr; p = p->nextArc){
 if(!vexList[p->eVexID].visited){
 if(GetIdOf(p->gArc->edVex()) != p->eVexID)
 p->gArc->reverseDirection();
 p->access();
 if(vexList[p->eVexID].info->distance == VexInfo::INF ||
 vexList[p->eVexID].info->distance > vexList[minVexID].info->distance + p->weight){
 vexList[p->eVexID].info->preVexID = minVexID;
 vexList[p->eVexID].info->distance = vexList[minVexID].info->distance + p->weight;
 vexList[p->eVexID].access(QString::asprintf("%d", vexList[p->eVexID].info->distance));
 }
 }
 }
 }
}

AMLGraph* ALGraph::ConvertToAML(){
 AMLGraph *converted = new AMLGraph(type);
 for(int i = 0; i < vexList.size(); i++){
 converted->AddVex(vexList[i].info);
 }
 for(int i = 0; i < vexList.size(); i++){
 ALArc *p = vexList[i].firstArc;
 while(p != nullptr){
 if(type == DG || (type == UDG && i == GetIdOf(p->gArc->edVex())))
 converted->AddArc(p->gArc, p->weight);
 p = p->nextArc;
 }
 }
 return converted;
}

/**************************************************************************************/

void AMLVex::visit(){
 if(visited)
 return;
 info->gVex->visit(true);
 visited = true;
}

void AMLVex::access(const QString &hint){
 info->gVex->access(hint);
}

void AMLArc::visit(){
 gArc->visit(true);
}

void AMLArc::access(){
 gArc->access();
}

AMLGraph::~AMLGraph(){
 int i = outVexList.size() - 1;
 while(i >= 0){
 DelVex(i--);
 }
 outVexList.clear();
 if(type == DG)
 inVexList.clear();
}

void AMLGraph::AddVex(MyGraphicsVexItem *gvex){
 AMLVex newVex(gvex);
 outVexList.push_back(newVex);

 if(type == DG){
 inVexList.push_back(newVex);
 }
}

void AMLGraph::AddVex(VexInfo *info){
 AMLVex newVex(info);
 outVexList.push_back(newVex);

 if(type == DG){
 inVexList.push_back(newVex);
 }
}

void AMLGraph::AddArc(MyGraphicsLineItem *garc, int weight){
 int strtVex = GetIdOf(garc->stVex());
 int endVex = GetIdOf(garc->edVex());

 AMLArc *nextOutArc = outVexList[strtVex].firstArc;
 AMLArc *nextInArc = type == DG ? inVexList[endVex].firstArc : outVexList[endVex].firstArc;
 AMLArc *newArc = new AMLArc(garc, strtVex, endVex, nextOutArc, nextInArc);
 newArc->weight = weight;
 outVexList[strtVex].firstArc = newArc;
 if(type == DG)
 inVexList[endVex].firstArc = newArc;
 else
 outVexList[endVex].firstArc = newArc;
}

void AMLGraph::DelVex(MyGraphicsVexItem *gvex){
 int vexID = GetIdOf(gvex);
 DelVex(vexID);
}

void AMLGraph::DelVex(int vexID){
 if(type == DG){
 //Delete out arc
 AMLArc *outArc = outVexList[vexID].firstArc;
 while(outArc != nullptr){
 AMLArc *dummyHead = new AMLArc(nullptr, 0, 0, nullptr, inVexList[outArc->inVexID].firstArc);
 AMLArc *preInArc = dummyHead;
 while(preInArc->nextInArc != nullptr){
 if(preInArc->nextInArc->outVexID == vexID){
 AMLArc *next = preInArc->nextInArc;
 preInArc->nextInArc = next->nextInArc;
 delete next;
 }
 else
 preInArc = preInArc->nextInArc;
 }
 inVexList[outArc->inVexID].firstArc = dummyHead->nextInArc;
 delete dummyHead;
 outArc = outArc->nextOutArc;
 }
 //Delete in arc and adjust ID
 for(int i = 0; i < outVexList.size(); i++){
 if(i == vexID) continue;
 AMLArc *dummyHead = new AMLArc(nullptr, 0, 0, outVexList[i].firstArc, nullptr);
 AMLArc *preOutArc = dummyHead;
 while(preOutArc->nextOutArc != nullptr){
 if(preOutArc->nextOutArc->inVexID == vexID){
 AMLArc *next = preOutArc->nextOutArc;
 preOutArc->nextOutArc = next->nextOutArc;
 delete next;
 continue;
 }
 if(preOutArc->nextOutArc->inVexID > vexID)
 preOutArc->nextOutArc->inVexID--;
 if(preOutArc->nextOutArc->outVexID > vexID)
 preOutArc->nextOutArc->outVexID--;
 preOutArc = preOutArc->nextOutArc;
 }
 outVexList[i].firstArc = dummyHead->nextOutArc;
 delete dummyHead;
 }
 outVexList.erase(outVexList.begin() + vexID);
 inVexList.erase(inVexList.begin() + vexID);
 }
 else{
 //Traverse all and adjust ID
 AMLArc *p = outVexList[vexID].firstArc;
 while(p != nullptr){
 if(p->outVexID == vexID){
 AMLArc *temp = p->nextOutArc;
 p->nextOutArc = nullptr;
 p = temp;
 }
 else{
 AMLArc *temp = p->nextInArc;
 p->nextInArc = nullptr;
 p = temp;
 }
 }
 outVexList[vexID].firstArc = nullptr;
 for(int i = 0; i < outVexList.size(); i++){
 if(i == vexID) continue;
 AMLArc *dummyHead = new AMLArc(nullptr, i, -1, outVexList[i].firstArc, nullptr);
 AMLArc *preArc = dummyHead;
 AMLArc *nextArc = preArc->nextOutArc;
 while(nextArc != nullptr){
 if(nextArc->inVexID == vexID || nextArc->outVexID == vexID){
 if(preArc->outVexID == i || preArc->outVexID == -i){
 if(nextArc->outVexID == i){
 preArc->nextOutArc = nextArc->nextOutArc;
 nextArc->nextOutArc = nullptr;
 delete nextArc;
 }
 else{
 preArc->nextOutArc = nextArc->nextInArc;
 nextArc->nextInArc = nullptr;
 delete nextArc;
 }
 }
 else{
 if(nextArc->outVexID == i){
 preArc->nextInArc = nextArc->nextOutArc;
 nextArc->nextOutArc = nullptr;
 delete nextArc;
 }
 else{
 preArc->nextInArc = nextArc->nextInArc;
 nextArc->nextInArc = nullptr;
 delete nextArc;
 }
 }
 nextArc = (preArc->outVexID == i || preArc->outVexID == -i) ? preArc->nextOutArc : preArc->nextInArc;
 continue;
 }
 if(preArc->inVexID > vexID)
 preArc->inVexID = - preArc->inVexID;
 else if(preArc->inVexID < 0)
 preArc->inVexID = - preArc->inVexID - 1;
 if(preArc->outVexID > vexID)
 preArc->outVexID = - preArc->outVexID;
 else if(preArc->outVexID < 0)
 preArc->outVexID = - preArc->outVexID - 1;
 preArc = nextArc;
 nextArc = (preArc->outVexID == i || preArc->outVexID == -i) ? preArc->nextOutArc : preArc->nextInArc;

 /********************************************************************************************/
 //Issue #1
 /*How this causes issue:
 * Example: when vexID is 1
 * preArc = nextArc => preArc: -3 -> -2
 * nextArc = ... => nextArc : 3 -> 1
 * Adjust pre Arc to => preArc: 2 -> 1
 * In next loop: nextArc->inVexID == 1 => judge if preArc->nextOutArc == 3 (in fact it is)
 * preArc->nextOutArc != 3 -> wrongly connect next out arc of 3 -> 1 to next out arc of 2 -> 1
 * which leads to wrong operations
 */

 //if(preArc->inVexID > vexID)
 // preArc->inVexID = - preArc->inVexID;
 //else if(preArc->inVexID < 0)
 // preArc->inVexID = - preArc->inVexID - 1;
 //if(preArc->outVexID > vexID)
 // preArc->outVexID = - preArc->outVexID;
 //else if(preArc->outVexID < 0)
 // preArc->outVexID = - preArc->outVexID - 1;

 /********************************************************************************************/

 }
 if(preArc->inVexID > vexID)
 preArc->inVexID = - preArc->inVexID;
 else if(preArc->inVexID < 0)
 preArc->inVexID = - preArc->inVexID - 1;
 if(preArc->outVexID > vexID)
 preArc->outVexID = - preArc->outVexID;
 else if(preArc->outVexID < 0)
 preArc->outVexID = - preArc->outVexID - 1;
 outVexList[i].firstArc = dummyHead->nextOutArc;
 delete dummyHead;
 }
 //Delete vexID
 outVexList.erase(outVexList.begin() + vexID);
 }
}

void AMLGraph::DelArc(MyGraphicsLineItem *garc){
 int sVex = GetIdOf(garc->stVex());
 int eVex = GetIdOf(garc->edVex());
 DelArc(sVex, eVex);
}

void AMLGraph::DelArc(int sVexID, int eVexID){
 if(type == DG){
 AMLArc *dummyHead;
 AMLArc *preArc;
 //Delete sVex -> eVex
 dummyHead = new AMLArc(nullptr, sVexID, -1, outVexList[sVexID].firstArc, nullptr);
 preArc = dummyHead;
 while(preArc->nextOutArc != nullptr){
 if(preArc->nextOutArc->inVexID == eVexID){
 preArc->nextOutArc = preArc->nextOutArc->nextOutArc;
 continue;
 }
 else
 preArc = preArc->nextOutArc;
 }
 outVexList[sVexID].firstArc = dummyHead->nextOutArc;
 delete dummyHead;
 //Delete eVex -> sVex
 dummyHead = new AMLArc(nullptr, -1, eVexID, nullptr, inVexList[eVexID].firstArc);
 preArc = dummyHead;
 while(preArc->nextInArc != nullptr){
 if(preArc->nextInArc->outVexID == sVexID){
 AMLArc *awaitDel = preArc->nextInArc;
 preArc->nextInArc = preArc->nextInArc->nextInArc;
 delete awaitDel;
 continue;
 }
 else
 preArc = preArc->nextInArc;
 }
 inVexList[eVexID].firstArc = dummyHead->nextInArc;
 delete dummyHead;
 }
 else{
 AMLArc *dummyHead;
 AMLArc *preArc;
 AMLArc *nextArc;
 //Delete sVex -> eVex
 dummyHead = new AMLArc(nullptr, sVexID, -1, outVexList[sVexID].firstArc, nullptr);
 preArc = dummyHead;
 nextArc = outVexList[sVexID].firstArc;
 while(nextArc != nullptr){
 if(nextArc->inVexID == eVexID || nextArc->outVexID == eVexID){
 if(preArc->outVexID == sVexID){
 if(nextArc->outVexID == sVexID){
 preArc->nextOutArc = nextArc->nextOutArc;
 nextArc->nextOutArc = nullptr;
 }
 else{
 preArc->nextOutArc = nextArc->nextInArc;
 nextArc->nextInArc = nullptr;
 }
 }
 else{
 if(nextArc->outVexID == sVexID){
 preArc->nextInArc = nextArc->nextOutArc;
 nextArc->nextOutArc = nullptr;
 }
 else{
 preArc->nextInArc = nextArc->nextInArc;
 nextArc->nextInArc = nullptr;
 }
 }
 nextArc = preArc->outVexID == sVexID ? preArc->nextOutArc : preArc->nextInArc;
 continue;
 }
 else{
 preArc = nextArc;
 nextArc = preArc->outVexID == sVexID ? preArc->nextOutArc : preArc->nextInArc;
 }
 }
 outVexList[sVexID].firstArc = dummyHead->nextOutArc;
 delete dummyHead;
 //Delete eVex -> sVex and release arc
 dummyHead = new AMLArc(nullptr, -1, eVexID, nullptr, outVexList[eVexID].firstArc);
 preArc = dummyHead;
 nextArc = outVexList[eVexID].firstArc;
 while(nextArc != nullptr){
 if(nextArc->inVexID == sVexID || nextArc->outVexID == sVexID){
 if(preArc->outVexID == eVexID){
 if(nextArc->outVexID == eVexID){
 preArc->nextOutArc = nextArc->nextOutArc;
 delete nextArc;
 }
 else{
 preArc->nextOutArc = nextArc->nextInArc;
 delete nextArc;
 }
 }
 else{
 if(nextArc->outVexID == eVexID){
 preArc->nextInArc = nextArc->nextOutArc;
 delete nextArc;
 }
 else{
 preArc->nextInArc = nextArc->nextInArc;
 delete nextArc;
 }
 }
 nextArc = preArc->outVexID == eVexID ? preArc->nextOutArc : preArc->nextInArc;
 continue;
 }
 else{
 preArc = nextArc;
 nextArc = preArc->outVexID == eVexID ? preArc->nextOutArc : preArc->nextInArc;
 }
 }
 outVexList[eVexID].firstArc = dummyHead->nextInArc;
 delete dummyHead;
 }
}

int AMLGraph::GetIdOf(MyGraphicsVexItem *gvex){
 int i = 0;
 while(i < outVexList.size() && outVexList[i].info->gVex != gvex)
 i++;
 return i == outVexList.size() ? -1 : i;
}

AMLArc* AMLGraph::FindArc(int strtID, int endID){
 if(strtID < 0 || strtID >= outVexList.size())
 return nullptr;
 AMLArc *p = outVexList[strtID].firstArc;
 while(p != nullptr){
 if(p->outVexID == endID || p->inVexID == endID)
 return p;
 p = p->outVexID == strtID ? p->nextOutArc : p->nextInArc;
 }
 return nullptr;
}

void AMLGraph::SetWeight(MyGraphicsLineItem *garc, int weight){
 int strtVex = GetIdOf(garc->stVex());
 int endVex = GetIdOf(garc->edVex());
 AMLArc *p = outVexList[strtVex].firstArc;
 while(p != nullptr){
 if(p->inVexID == endVex || p->outVexID == endVex){
 p->weight = weight;
 p->gArc->setText(QString::asprintf("%d", weight));
 }
 p = p->inVexID == strtVex ? p->nextInArc : p->nextOutArc;
 }
 if(type == DG){
 p = inVexList[endVex].firstArc;
 while(p != nullptr){
 if(p->inVexID == strtVex || p->outVexID == strtVex){
 p->weight = weight;
 p->gArc->setText(QString::asprintf("%d", weight));
 }
 p = p->inVexID == endVex ? p->nextInArc : p->nextOutArc;
 }
 }
}

void AMLGraph::ConvertType(int _type){
 if(_type == type) return;
 type = _type;
 if(type == UDG){
 for(int i = 0; i < inVexList.size(); i++){
 AMLArc *p = inVexList[i].firstArc;
 while(p != nullptr && p->nextInArc != nullptr){
 p->gArc->setDirection(false);
 p = p->nextInArc;
 }
 AMLArc *temp = outVexList[i].firstArc;
 if(p){
 outVexList[i].firstArc = inVexList[i].firstArc;
 p->nextInArc = temp;
 }
 while(temp != nullptr){
 temp->gArc->setDirection(false);
 temp = temp->nextOutArc;
 }
 }
 }
 else{
 inVexList.clear();
 inVexList.assign(outVexList.begin(), outVexList.end());
 for(int i = 0; i < inVexList.size(); i++)
 inVexList[i].firstArc = nullptr;
 for(int i = 0; i < outVexList.size(); i++){
 AMLArc *dummyHead = new AMLArc(nullptr, i, -1, outVexList[i].firstArc, nullptr);
 AMLArc *pre = dummyHead;
 AMLArc *next = outVexList[i].firstArc;
 while(next != nullptr){
 next->gArc->setDirection(true);
 if(next->outVexID != i){
 //A reversed edge
 pre->nextOutArc = next->nextInArc;
 AMLArc *temp = inVexList[next->inVexID].firstArc;
 inVexList[next->inVexID].firstArc = next;
 next->nextInArc = temp;
 next = pre->nextOutArc;
 continue;
 }
 pre = next;
 next = pre->nextOutArc;
 }
 outVexList[i].firstArc = dummyHead->nextOutArc;
 delete dummyHead;
 }
 }
}

void AMLGraph::ClearVisit(){
 for(int i = 0; i < outVexList.size(); i++){
 outVexList[i].visited = false;
 outVexList[i].info->gVex->visit(false);
 }
 if(type == DG)
 for(int i = 0; i < inVexList.size(); i++)
 inVexList[i].visited = false;
}

void AMLGraph::ResetDistance(){
 for(int i = 0; i < outVexList.size(); i++){
 outVexList[i].info->strtVexInfo = nullptr;
 outVexList[i].info->distance = VexInfo::INF;
 outVexList[i].info->preVexID = -1;
 outVexList[i].info->gVex->access("", false);
 }
 if(type == DG)
 for(int i = 0; i < outVexList.size(); i++){
 inVexList[i].info->strtVexInfo = nullptr;
 inVexList[i].info->distance = VexInfo::INF;
 inVexList[i].info->preVexID = -1;
 }
}

void AMLGraph::DFS(int strtID, bool generateForest){
 if(strtID == -1)
 return;
 vector<int> awaitVexList;
 vector<AMLArc*>awaitArcList;
 awaitVexList.push_back(strtID);
 while(awaitVexList.size() > 0){
 int nextVex = awaitVexList.back();
 AMLArc *nextArc = awaitArcList.size() > 0 ? awaitArcList.back() : nullptr;
 awaitVexList.pop_back();
 if(nextArc)
 awaitArcList.pop_back();
 for(AMLArc *p = outVexList[nextVex].firstArc; p != nullptr; p = p->outVexID == strtID ? p->nextOutArc : p->nextInArc){
 int endID = p->outVexID == nextVex ? p->inVexID : p->outVexID;
 if(outVexList[endID].visited == false){
 awaitVexList.push_back(endID);
 awaitArcList.push_back(p);
 if(type == UDG && GetIdOf(p->gArc->edVex()) != endID)
 p->gArc->reverseDirection();
 }
 }
 if(nextArc && !outVexList[nextVex].visited)
 nextArc->visit();
 outVexList[nextVex].visit();
 }
 if(generateForest){
 for(int i = 0; i < outVexList.size(); i++){
 if(outVexList[i].visited) continue;
 awaitVexList.clear();
 awaitArcList.clear();
 awaitVexList.push_back(i);
 while(awaitVexList.size() > 0){
 int nextVex = awaitVexList.back();
 AMLArc *nextArc = awaitArcList.size() > 0 ? awaitArcList.back() : nullptr;
 awaitVexList.pop_back();
 if(nextArc)
 awaitArcList.pop_back();
 for(AMLArc *p = outVexList[nextVex].firstArc; p != nullptr; p = p->outVexID == strtID ? p->nextOutArc : p->nextInArc){
 int endID = p->outVexID == nextVex ? p->inVexID : p->outVexID;
 if(outVexList[endID].visited == false){
 awaitVexList.push_back(endID);
 awaitArcList.push_back(p);
 if(type == UDG && GetIdOf(p->gArc->edVex()) != endID)
 p->gArc->reverseDirection();
 }
 }
 if(nextArc && !outVexList[nextVex].visited)
 nextArc->visit();
 outVexList[nextVex].visit();
 }
 }
 }
}

void AMLGraph::BFS(int strtID, bool generateForest){
 if(strtID == -1)
 return;
 vector<int> awaitVexList;
 vector<AMLArc*> awaitArcList;
 awaitVexList.push_back(strtID);
 while(awaitVexList.size() > 0){
 int nextVex = awaitVexList[0];
 AMLArc *nextArc = awaitArcList.size() > 0 ? awaitArcList[0] : nullptr;
 awaitVexList.erase(awaitVexList.begin());
 if(nextArc)
 awaitArcList.erase(awaitArcList.begin());
 for(AMLArc *p = outVexList[nextVex].firstArc; p != nullptr; p = p->outVexID == strtID ? p->nextOutArc : p->nextInArc){
 int endID = p->outVexID == nextVex ? p->inVexID : p->outVexID;
 if(outVexList[endID].visited == false){
 awaitVexList.push_back(endID);
 awaitArcList.push_back(p);
 if(type == UDG && GetIdOf(p->gArc->edVex()) != endID)
 p->gArc->reverseDirection();
 }
 }
 if(nextArc && !outVexList[nextVex].visited)
 nextArc->visit();
 outVexList[nextVex].visit();
 }
 if(generateForest){
 for(int i = 0; i < outVexList.size(); i++){
 if(outVexList[i].visited) continue;
 awaitVexList.clear();
 awaitArcList.clear();
 awaitVexList.push_back(i);
 while(awaitVexList.size() > 0){
 int nextVex = awaitVexList[0];
 AMLArc *nextArc = awaitArcList.size() > 0 ? awaitArcList[0] : nullptr;
 awaitVexList.erase(awaitVexList.begin());
 if(nextArc)
 awaitArcList.erase(awaitArcList.begin());
 for(AMLArc *p = outVexList[nextVex].firstArc; p != nullptr; p = p->outVexID == strtID ? p->nextOutArc : p->nextInArc){
 int endID = p->outVexID == nextVex ? p->inVexID : p->outVexID;
 if(outVexList[endID].visited == false){
 awaitVexList.push_back(endID);
 awaitArcList.push_back(p);
 if(type == UDG && GetIdOf(p->gArc->edVex()) != endID)
 p->gArc->reverseDirection();
 }
 }
 if(nextArc && !outVexList[nextVex].visited)
 nextArc->visit();
 outVexList[nextVex].visit();
 }
 }
 }
}

void AMLGraph::Dijkstra(int strtID){
 //Clear previous result
 ClearVisit();
 ResetDistance();
 //Set start vex info to all vertexes
 for(int i = 0; i < outVexList.size(); i++)
 outVexList[i].info->strtVexInfo = outVexList[strtID].info;
 //Start dijkstra
 outVexList[strtID].info->distance = 0;
 outVexList[strtID].access("strt");
 while(true){
 //Find next
 int minVexID = -1;
 for(int i = 0; i < outVexList.size(); i++){
 if(outVexList[i].visited || outVexList[i].info->distance == VexInfo::INF)
 continue;
 if(minVexID == -1)
 minVexID = i;
 else if(outVexList[i].info->distance < outVexList[minVexID].info->distance)
 minVexID = i;
 }
 if(minVexID == -1)
 break;
 //Set visit to edge and vex
 AMLArc *edge = FindArc(outVexList[minVexID].info->preVexID, minVexID);
 if(edge){
 if(type == UDG && GetIdOf(edge->gArc->edVex()) != minVexID)
 edge->gArc->reverseDirection();
 edge->visit();
 }
 outVexList[minVexID].visit();
 //Find adjacent
 for(AMLArc *p = outVexList[minVexID].firstArc; p != nullptr; p = p->outVexID == strtID ? p->nextOutArc : p->nextInArc){
 int endID = p->outVexID == minVexID ? p->inVexID : p->outVexID;
 if(!outVexList[endID].visited){
 if(GetIdOf(p->gArc->edVex()) != endID)
 p->gArc->reverseDirection();
 p->access();
 if(outVexList[endID].info->distance == VexInfo::INF ||
 outVexList[endID].info->distance > outVexList[minVexID].info->distance + p->weight){
 outVexList[endID].info->preVexID = minVexID;
 outVexList[endID].info->distance = outVexList[minVexID].info->distance + p->weight;
 outVexList[endID].access(QString::asprintf("%d", outVexList[endID].info->distance));
 }
 }
 }
 }
}

ALGraph* AMLGraph::ConvertToAL(){
 ALGraph *converted = new ALGraph(type);
 for(int i = 0; i < outVexList.size(); i++)
 converted->AddVex(outVexList[i].info);
 for(int i = 0; i < outVexList.size(); i++){
 AMLArc *p = outVexList[i].firstArc;
 while(p != nullptr){
 if(p->outVexID == i)
 converted->AddArc(p->gArc);
 p = p->outVexID == i ? p->nextOutArc : p->nextInArc;
 }
 }
 return converted;
}