package zhongXing;
import java.util.*;
import java.util.Map.Entry;
import java.io.*;
public class choosePath {
/*
* @splitString 二维的String类型的数组，用于存储split(" ")切割后，返回的Sting类型的数组
* @colOfDatas 用于记录数据的行数
* @setOfVetixInGraph 用于存储图中的节点
* @mapOfVetixToNum 用于把节点和节点编号一一对应，节点编号从0开始
* @valueOfEdge 权值矩阵， 用于快速获取边的权值
*
*
*
* */
private static String startNode;
private static String endNode;
private static ArrayList arrayListOfChoosedPath=new ArrayList();
private static ArrayList arrayListOfMustThoughNode=new ArrayList();
private static ArrayList arrayListOfMustThoughEdge=new ArrayList();
private static ArrayList arrayListOfCanNotThoughEdge=new ArrayList();
private static int needOfNode;
public static void main(String[] args) throws IOException {
//sumCol变量用于记录数据集中边的数量
int sumCol=0;
BufferedReader bfr2 = new BufferedReader(new FileReader(
"C://Users//Administrator//Desktop//text//case.txt"));
bfr2.readLine();
bfr2.readLine();
while(!bfr2.readLine().equals("")){
sumCol++;
}
System.out.println("tempcol="+sumCol);
String tempMustThoughNode=null;
while(!(tempMustThoughNode=bfr2.readLine()).equals("")){
System.out.println(tempMustThoughNode);
arrayListOfMustThoughNode.add(tempMustThoughNode);
}
while(!(tempMustThoughNode=bfr2.readLine()).equals("")){
System.out.println(tempMustThoughNode);
arrayListOfMustThoughEdge.add(tempMustThoughNode.split(" ")[0]);
arrayListOfMustThoughEdge.add(tempMustThoughNode.split(" ")[1]);
}
while((tempMustThoughNode=bfr2.readLine())!=null){
System.out.println(tempMustThoughNode);
arrayListOfCanNotThoughEdge.add(tempMustThoughNode.split(" ")[0]);
arrayListOfCanNotThoughEdge.add(tempMustThoughNode.split(" ")[1]);
}
bfr2.close();
BufferedReader bfr = new BufferedReader(new FileReader(
"C://Users//Administrator//Desktop//text//case.txt"));
String [] info=bfr.readLine().split(" ");
startNode=info[1];
endNode=info[2];
needOfNode=Integer.parseInt(info[3]);
//定义一个二维的String类型的数组，用于存储split(" ")切割后，返回的Sting类型的数组
String[][] splitString = new String[sumCol][2];
//colOfDatas变量用于记录数据的行数
int colOfDatas = 0;
//临时变量，记录每次读取到的一行String
String flagOfReadLineString = null;
bfr.readLine();
//while循环用于把读取到的一行String用split(" ")切割后的一维String数组的地址给二维数组splitString的第一维
while (!(flagOfReadLineString = bfr.readLine()).equals("")) {
splitString[colOfDatas++] = flagOfReadLineString.split(" ");
}
//打印输出数据集的行数
System.out.println("colOfDatas=" + sumCol);
System.out.println("splitString.length="+splitString.length);
// setOfVetixInGraph用于存储图中的节点（利用Set中元素不重复的特点，依次把边的两端的节点往Set集合中添加，实现数据集中节点的获取及存储）
Set<String> setOfVetixInGraph = new TreeSet<String>();
for (int i = 0; i < splitString.length; i++) {
setOfVetixInGraph.add(splitString[i][0]);
setOfVetixInGraph.add(splitString[i][1]);
}
System.out.println("这个数据集中一个有" + setOfVetixInGraph.size() + "个节点");
// 定义Map集合mapOfVetixToNum，用于把节点和节点编号一一对应，节点编号从0开始
//原理是：利用依次遍历上面的setOfVetixInGraph中的元素，同时用节点编号来对应标识
Map<String, Integer> mapOfVetixToNum = new TreeMap<String, Integer>();
Iterator<String> it = setOfVetixInGraph.iterator();
String flagOfVetixToNum = null;
//labelOfVetix，用于标注节点的编号
int labelOfVetix = 0;
while (it.hasNext()) {
flagOfVetixToNum = it.next();
mapOfVetixToNum.put(flagOfVetixToNum, labelOfVetix++);
}
//把节点和节点标号对应起来的集合打印出来
System.out.println("mapOfVetixToNum)=" + mapOfVetixToNum);
// 还需要定义一个权值矩阵，valueOfEdge用于快速获取边的权值
int[][] valueOfEdge = new int[setOfVetixInGraph.size()][setOfVetixInGraph.size()];
for (int i = 0; i < splitString.length; i++) {
valueOfEdge[mapOfVetixToNum.get(splitString[i][0])][mapOfVetixToNum
.get(splitString[i][1])] = Integer
.parseInt(splitString[i][2]);
}
// //用于打印权值矩阵
// for (int i = 0; i < valueOfEdge.length; i++) {
// System.out.println("valueOfEdge==" + Arrays.toString(valueOfEdge[i]));
//
// }
// setOfNeighborVetix存储每一个节点的直接相连的节点的集合 mapOfVetixToNerghborvetixset用于让节点和直连节点集合一一对应起来
Set<String> setOfNeighborVetix;
Map<String, ArrayList<String>> mapOfVetixToNerghborvetixset = new TreeMap<String, ArrayList<String>>();
ArrayList<String> arrayList;
for (String s : setOfVetixInGraph) {
setOfNeighborVetix = new TreeSet<String>();
for (int i = 0; i < splitString.length; i++) {
if (s.equals(splitString[i][0])) {
setOfNeighborVetix.add(splitString[i][1]);
} else if (s.equals(splitString[i][1])) {
setOfNeighborVetix.add(splitString[i][0]);
}
}
Object[] string = setOfNeighborVetix.toArray();
arrayList = new ArrayList<String>();
for (int i = 0; i < setOfNeighborVetix.size(); i++) {
arrayList.add((String) string[i]);
}
mapOfVetixToNerghborvetixset.put(s, arrayList);
}
Node node = new Node();
node.setRelationNodes(mapOfVetixToNerghborvetixset);
Paths path = new Paths();
boolean flag1 = path.getPaths(node, startNode, null, startNode, endNode);
// System.out.println("flag1=" + flag1);
ArrayList sers = path.getPathStore();
//存储节点数不大于11个的路径集合
ArrayList afterChoosePath=new ArrayList();
int num = sers.size();
System.out.println("一共存储了" + num + "条路径");
int countNum = 0;
Stack tempStack ;
String tempString;
for (int i = 0; i < num; i++) {
//tempStack用于记录，返回的ArrayList中的第i个元素，即，存储第i条路径的集合
tempStack = (Stack) sers.get(i);
//如果这条路径中的节点个数小于11，并且，这条路径中包含节点"N7"和"N12"，（即，满足节点个数和必过节点的需求）
if(tempStack.size() <= needOfNode && tempStack.contains("N7") && tempStack.contains("N12")&& tempStack.contains("N4")&& tempStack.contains("N2")&& tempStack.contains("N13")&& tempStack.contains("N14")){
//用于判断必须要经过的边是否满足需求
if(((tempStack.indexOf("N2")-tempStack.indexOf("N4"))==1||(tempStack.indexOf("N2")-tempStack.indexOf("N4"))==-1)&&((tempStack.indexOf("N14")-tempStack.indexOf("N13"))==1||(tempStack.indexOf("N14")-tempStack.indexOf("N13"))==-1)&&
((tempStack.indexOf("N11")==-1)||(tempStack.indexOf("N12")==-1)||(((tempStack.indexOf("N11")-tempStack.indexOf("N12"))!=-1))&&((tempStack.indexOf("N12")-tempStack.indexOf("N11"))!=-1))){
afterChoosePath.add(tempStack);
countNum++;
}
// System.out.println(sers.get(i));
}
}
System.out.println("路径中经过节点少于"+needOfNode+"个的路径共有" + countNum + "条");
//用于遍历选择出来的stack中的元素，通过计算每条路径上边的权值总和，选出权值最小的那一条路径
//定义一个Map用于记录每条路径的总权值，用于排序选择
Map storeValueOfPath = new HashMap();
// System.out.println("afterChoosePath="+afterChoosePath);
// System.out.println("afterChoosePath.size()="+afterChoosePath.size());
for(int i = 0 ; i < afterChoosePath.size();i++){
Stack o = (Stack)afterChoosePath.get(i);
int sum=0;
for(int j = 0 ; j < o.size()-1 ; j ++){
sum+=valueOfEdge[mapOfVetixToNum.get(o.get(j))][mapOfVetixToNum.get(o.get(j+1))];
}
storeValueOfPath.put(o, sum);
}
System.out.println("storeValueOfPath="+storeValueOfPath);
//============================================================================
arrayListOfChoosedPath.add("S");
arrayListOfChoosedPath.add("N2");
arrayListOfChoosedPath.add("N4");
arrayListOfChoosedPath.add("N5");
arrayListOfChoosedPath.add("N12");
arrayListOfChoosedPath.add("N6");
arrayListOfChoosedPath.add("N7");
arrayListOfChoosedPath.add("N8");
arrayListOfChoosedPath.add("N14");
arrayListOfChoosedPath.add("N13");
arrayListOfChoosedPath.add("E");
System.out.println("arrayListOfChoosedPath:"+arrayListOfChoosedPath);
System.out.println("arrayListOfMustThoughNode:"+arrayListOfMustThoughNode);
System.out.println("arrayListOfMustThoughEdge:"+arrayListOfMustThoughEdge);
System.out.println("arrayListOfCanNotThoughEdge:"+arrayListOfCanNotThoughEdge);
BufferedReader bfr1 = new BufferedReader(new FileReader(
"C://Users//Administrator//Desktop//text//case.txt"));
BufferedWriter bfw = new BufferedWriter(new FileWriter("C://Users//Administrator//Desktop//text//final11.net"));
//定义一个二维的String类型的数组，用于存储split(" ")切割后，返回的Sting类型的数组
String[][] splitString1 = new String[82][2];
//colOfDatas变量用于记录数据的行数
int colOfDatas1 = 0;
//临时变量，记录每次读取到的一行String
String flagOfReadLineString1 = null;
String flagOfReadLineString2 = null;
Iterator it1 = mapOfVetixToNum.entrySet().iterator();
//写入*Vertices
bfw.write("*Vertices "+setOfVetixInGraph.size());
//换行
bfw.newLine();
while(it1.hasNext()){
Object en = it1.next();
//((int)((Entry)(en)).getValue()) 获取到的是节点对应的 编号，这个编号是从0开始的
//((int)((Entry)(en)).getValue())+1 目的是让编号从1开始，从而适应Pajek软件的数据输入格式
//如果是必须经过的节点就显示为Green，如果是开始节点或者终止节点就显示为Yellow，选择出来的路径上的节点显示为Black,其余的节点全部显示为CornflowerBlue;
if(arrayListOfMustThoughNode.contains(((Entry)(en)).getKey().toString())){
bfw.write((((int)((Entry)(en)).getValue())+1)+" "+"\""+((Entry)(en)).getKey().toString()+"\""+" ic Green");
}else
if(startNode.equals(((Entry)(en)).getKey().toString())||endNode.equals(((Entry)(en)).getKey().toString())){
bfw.write((((int)((Entry)(en)).getValue())+1)+" "+"\""+((Entry)(en)).getKey().toString()+"\""+" ic Yellow");
}else
if(arrayListOfChoosedPath.contains(((Entry)(en)).getKey().toString())){
bfw.write((((int)((Entry)(en)).getValue())+1)+" "+"\""+((Entry)(en)).getKey().toString()+"\""+" ic Black");
}else{
//\是格式转换符
bfw.write((((int)((Entry)(en)).getValue())+1)+" "+"\""+((Entry)(en)).getKey().toString()+"\""+" ic CornflowerBlue");
}
bfw.newLine();
}
//输入*Edges
bfw.write("*Edges");
//换行
bfw.newLine();
bfr1.readLine();
bfr1.readLine();
//while循环用于把读取到的一行String用split(" ")切割后的一维String数组的地址给二维数组splitString的第一维
while (!(flagOfReadLineString1 = bfr1.readLine()).equals("")) {
String temp0 = flagOfReadLineString1.split(" ")[0] ;
String temp1 = flagOfReadLineString1.split(" ")[1] ;
//必过的边显示为 Green，选择出来的路径上的边显示为Black，不能经过的边显示为Red，其余边无色
if(arrayListOfMustThoughEdge.contains(temp0)&&arrayListOfMustThoughEdge.contains(temp1)&&((arrayListOfMustThoughEdge.indexOf(temp0)/2)==(arrayListOfMustThoughEdge.indexOf(temp1)/2))){
bfw.write((mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[0])+1)+" "+(mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[1])+1)+" "+flagOfReadLineString1.split(" ")[2]+" c Green");
}else
if(arrayListOfCanNotThoughEdge.contains(temp0)&&arrayListOfCanNotThoughEdge.contains(temp1)&&((arrayListOfCanNotThoughEdge.indexOf(temp0)/2)==(arrayListOfCanNotThoughEdge.indexOf(temp1)/2))){
bfw.write((mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[0])+1)+" "+(mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[1])+1)+" "+flagOfReadLineString1.split(" ")[2]+" c Red");
}else
if(arrayListOfChoosedPath.contains(temp0)&&arrayListOfChoosedPath.contains(temp1)&&(((arrayListOfChoosedPath.indexOf(temp0)-arrayListOfChoosedPath.indexOf(temp1))==1)||((arrayListOfChoosedPath.indexOf(temp0)-arrayListOfChoosedPath.indexOf(temp1))==-1))){
bfw.write((mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[0])+1)+" "+(mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[1])+1)+" "+flagOfReadLineString1.split(" ")[2]+" c Black");
}else{
bfw.write((mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[0])+1)+" "+(mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[1])+1)+" "+flagOfReadLineString1.split(" ")[2]);
}
//mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[0])获取的是第一列节点对应的编号，是个字符串类型，mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[1])获取的是第二列节点对应的编号，是个字符串类型，这些编号是从零开始的，
//mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[0])+1，mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[0])+1，这里加一的目的是为了适应Pajek软件的数据输入格式
// bfw.write((mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[0])+1)+" "+(mapOfVetixToNum.get(flagOfReadLineString1.split(" ")[1])+1)+" "+flagOfReadLineString1.split(" ")[2]);
bfw.newLine();
}
bfw.flush();
bfw.close();
bfr.close();
//============================================================================
}
}
class Paths {
private Stack stack = new Stack();;/* 临时保存路径节点的栈 */
private ArrayList sers = new ArrayList();/* 存储路径的集合 */
private StringBuilder sb = new StringBuilder();
private Set set = new HashSet();
//返回，把生成的，存储着路径的，ArrayList集合
public ArrayList getPathStore() {
// System.out.println("sers=="+sers);
return sers;
}
public boolean isNodeInStack(String node)/* 判断节点是否在栈中 */
{
Iterator it = stack.iterator();
while (it.hasNext()) {
String node1 = (String) it.next();
if (node.equals(node1))
return true;
}
return false;
}
public void showAndSavePath()/* 此时栈中的节点组成一条所求路径，转储并打印输出 */
{
// System.out.println("stack=="+stack);
// System.out.println("stack.toArray="+stack.toString());
// Object[] o=stack.toArray();
// String[] str=new String[o.length];
// for (int i = 0; i < o.length; i++) {
// str[i]= (String) o[i];
// }
// sb.append(stack);
Stack stack1 = (Stack) stack.clone();
// System.out.println("stack1="+stack1);
sers.add(stack1); /* 转储 */
// return sers;
// System.out.println("\n");
// System.out.println("sers="+sers);
}
/* 寻找路径的方法 */
public boolean getPaths(Node Node1, String cNode, String pNode,
String sNode, String eNode)
/*
* cNode表示当前的起始节点currentNode，pNode表示当前起始节点的上一节点previousNode，
* sNode表示最初的起始节点startNode，eNode表示终点endNode
*/
{
// System.out.println("getre=="+Node1.getRelationNodes());
String nNode = null;
if (cNode!=null && pNode!=null && cNode.equals(pNode))
return false;/* 如果符合条件判断说明出现环路，不能再顺着该路径继续寻路，返回false */
if (cNode!=null) {
int i = 0;
stack.push(cNode);/* 起始节点入栈 */
if (cNode.equals(eNode))/* 如果该起始节点就是终点，说明找到一条路径 */
{
showAndSavePath();/* 转储并打印输出该路径，返回true */
return true;
} else/* 如果不是,继续寻路 */
{
// System.out.println("cNode="+cNode);
// System.out.println("i="+i);
// System.out.println("get(1)====="+Node1.getRelationNodes().get(cNode));
// System.out.println("get(cNode)="+Node1.getRelationNodes().get(cNode).get(i));
nNode = Node1.getRelationNodes().get(cNode).get(i);/* 从与当前起始节点cNode有连接关系的节点集中按顺序遍历得到一个节点作为下一次递归寻路时的起始节点 */
while (nNode!=null) {
// System.out.println("pNode="+pNode);
// System.out.println("nNode="+nNode);
// System.out.println("sNode="+sNode);
// System.out.println("pNode="+pNode);
if ((pNode!=null)
&& ((nNode.equals(sNode)) || (nNode.equals(pNode)) || isNodeInStack(nNode)))/*
* 如果nNode是最初的起始节点或者nNode就是cNode的上一节点或者nNode已经在栈中
* ，
* 说明产生环路
* ,
* 应重新在与当前起始节点有连接关系的节点集中寻找nNode
*/
{
i++;
if (i >= Node1.getRelationNodes().get(cNode).size())
nNode = null;
else
nNode = Node1.getRelationNodes().get(cNode).get(i);
continue;
}
/* 以nNode为新的起始节点，当前起始节点cNode为上一节点，递归调用寻路方法 */
if (getPaths(Node1, nNode, cNode, sNode, eNode))/* 递归调用 */
{
stack.pop();/* 如果找到一条路径，则弹出栈顶节点 */
}
i++;/* 继续在与cNode有连接关系的节点集中测试nNode */
if (i >= Node1.getRelationNodes().get(cNode).size())
nNode = null;
else
nNode = Node1.getRelationNodes().get(cNode).get(i);
}
stack.pop();/* 当遍历完所有与cNode有连接关系的节点后，说明在以cNode为起始节点到终点的路径已经全部找到 */
return false;
}
} else
return false;
}
}
class Node/* 表示一个节点以及和这个节点相连的所有节点 */
{
public String name = null;
private Map<String, ArrayList<String>> relationNodes = new TreeMap<String, ArrayList<String>>();
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Map<String, ArrayList<String>> getRelationNodes() {
return relationNodes;
}
public void setRelationNodes(Map<String, ArrayList<String>> relationNodes) {
this.relationNodes = relationNodes;
}
}
