/*
* Classical: Graph.cpp
*
* @version $Id: Graph.cpp ,GCC 4.5.0 2010/09/20 19:38:35 $
*
* @author Liangyi Fan.
*
* Revisions:
*
* Revision 1.1 2010/09/20 21:38:35 Liangyi Fan.
* Initial revision
*
*/
#include "Graph.h"
/**
* add the edge of the GraphMatrix, set the corresponding position in Matrix to 1;
*
* @param edgeBegin the number use to express the begin node;
*
* @param edgeEnd the number use to express the end node;
*
*/
void Graph::addEdge(int edgeBegin, int edgeEnd){
if(adjGraphMatrix[edgeBegin][edgeEnd]!=1 || adjGraphMatrix[edgeEnd][edgeBegin]!=1){
adjGraphMatrix[edgeBegin][edgeEnd]=1;
//adjGraphMatrix[edgeEnd][edgeBegin]=1;
}
}
/**
* use DFS search algorithm to search the Graph and
* print out the node which visit in sequence
*
* @param GraphMatrix The innerExpression string;
*
* @param startPoint the first point which we use to start to search;
*
*/
void Graph::bfs_Search(int GraphMatrix[][16], int startPoint){
queue<int> myQueue;
queue<int> visitPath;
int i,node;
int visit[16];
memset(visit, 0, sizeof(visit));
myQueue.push(startPoint);
while(!myQueue.empty()){
node = myQueue.front();
myQueue.pop();
if(visit[node]) continue;
visit[node] = 1;
visitPath.push(node);
for(i =0; i<16; i++){
if(GraphMatrix[node][i]==1)
myQueue.push(i);
}
}
Graph p_Graph ;
//print out the search path;
cout<<"The visit sequence of this file is: "<<endl;
for(int k =0;k<16;k++){
cout<<p_Graph.NumberToChar(visitPath)<<" ";
visitPath.pop();
}
}
/**
* transfer the input node of char into Number which use to express in Matrix;
*
* @param node The char name of node;
*
* @return the number we use to express for node;
*/
int Graph::changeIntoNumber(char node){
int nodeNum ;
switch (node){
case 'A':
nodeNum = 0; break;
case 'B':
nodeNum = 1; break;
case 'C':
nodeNum = 2; break;
case 'D':
nodeNum = 3; break;
case 'E':
nodeNum = 4; break;
case 'F':
nodeNum = 5; break;
case 'G':
nodeNum = 6; break;
case 'H':
nodeNum = 7; break;
case 'I':
nodeNum = 8; break;
case 'J':
nodeNum = 9; break;
case 'K':
nodeNum = 10; break;
case 'L':
nodeNum = 11; break;
case 'M':
nodeNum = 12; break;
case 'N':
nodeNum = 13; break;
case 'O':
nodeNum = 14; break;
case 'P':
nodeNum = 15; break;
case ' ':
nodeNum = -1; break;
case '\0':
nodeNum = -2; break;
case ':':
nodeNum = -1; break;
default :
nodeNum = -1; break;
}
return nodeNum;
}
/**
* transfer the number in matrix into corresponding char node;
*
* @param visitPath the input visitPath;
*
* @return the char value of the input visit
*/
char Graph::NumberToChar(queue<int> visitPath){
char nodeChar;
switch (visitPath.front()){
case 0:
nodeChar = 'A';break;
case 1:
nodeChar = 'B';break;
case 2:
nodeChar = 'C';break;
case 3:
nodeChar = 'D';break;
case 4:
nodeChar = 'E';break;
case 5:
nodeChar = 'F';break;
case 6:
nodeChar = 'G';break;
case 7:
nodeChar = 'H';break;
case 8:
nodeChar = 'I';break;
case 9:
nodeChar = 'J';break;
case 10:
nodeChar = 'K';break;
case 11:
nodeChar = 'L';break;
case 12:
nodeChar = 'M';break;
case 13:
nodeChar = 'N';break;
case 14:
nodeChar = 'O';break;
case 15:
nodeChar = 'P';break;
default: break;
}
return nodeChar;
}
