有向图闭环检测值java代码实现
本文有向图闭环检测算法和实现由文章《如何检测节点网络中是否存在闭环之java实现》中的无向图闭环检测算法的基础上修改得到，其中修改点如下：
1.修改了数据结构，在原来无向图闭环检测算法的数据结构的基础上，增加了”isFrozen”和”isRoot”属性；其中”isFrozen”属性用于员无向图闭环检测算法中，在多父节点的场景下，由于相同的子节点要遍历两次而造成闭环检测判断的逻辑性错误，同时可以减少算法的开销，默认为false；”isRoot”属性用标识某一节点是否为根节点，默认为fasle。具体数据结构如下表：
| 属性名 | 值类型 |
| nodeName | String |
| curRelIndex | int |
| beforeNode | String |
| relList | List |
| isFrozen | boolean |
| isRoot | boolean |
2.修改了获取算法起始点的方法，将在无向图闭环算法中随机获取起始点的方式修改为符合有向图的特点的方式—–如果节点集合中有给定根节点，即集合中某个节点的”isFrozen”属性值为true,则选择该属性为根节点，事先给定根节点的方式有助于减少算法开销；若无给定根节点，则算法默认给定一个根节点，该根节点的元素为该集合中的所有的节点，这种方式增加算法的开销
3.修改了进入闭环检测方法的条件—-将count > 1 改为 count >= 1 ，其实在无向图中 count >= 1 也无妨。
4.修改了获取从一个节点的关系列表中获取下一节点索引的方法。取消掉了对节点关系列表中与上一节点相同的节点的过滤。
5.修改了back()方法，在back()中增加了对”isFrozen”属性的修改，修改规则是，当一个节点后退时，将改节点的”isFrozen”属性修改为”true”。
6.对traverse()做了一些修改，对调用head()和back()方法的判断中增加了一个判断条件—即若当前节点的isFrozen属性值为true，则后退，不再前进；因为若”isFrozen”属性的值为true，则说明该节点的所有子节点都已经遍历完，而且没有出现闭环的情况，所以可以不用再遍历。
源码如下：
/** * * 功能：判断有向图中是否存在闭环 * 作者：EugeneJao * @param nodeCollections * @return * @throws Exception */ public boolean isContainLoopInDigraph(Map> nodeCollections) throws Exception{ //用map的hash码计算，速度更快 Map visitedList = new HashMap (); /** * 初始化"起点 */ String startNode = getOriginInDigraph(nodeCollections); boolean containLoop = false ; /** * 初始化"视野" */ Map nodeName = new HashMap () ; nodeName.put("nextNode", startNode); nodeName.put("curNode", startNode); nodeName.put("beforeNode", startNode); int count = 0 ; /** * 如果当前不含有闭环，并且没有遍历完起点节点的所有分支则进入循环 */ while(!containLoop && !(nodeName.get("beforeNode").equals(nodeName.get("curNode")) && nodeName.get("nextNode") == null )){ nodeName = traverseInDigraph(nodeCollections, nodeName, visitedList); String tmpNextNode = nodeName.get("nextNode") ; if(count >= 1 && tmpNextNode != null){ containLoop = containSameNodeInDigraph(visitedList,tmpNextNode,nodeCollections); } count ++ ; } return containLoop; } /** * * 功能：再有向图中获取起始节点，即有向图根节点 * 作者：EugeneJao * @param nodeCollections * @return * @throws Exception */ @SuppressWarnings("rawtypes") private String getOriginInDigraph(Map > nodeCollections) throws Exception{ /** * 程序默认生成一个根节点 */ Map rootNode = new HashMap (); rootNode.put("nodeName", "rootNode"); rootNode.put("curRelIndex", -1); rootNode.put("beforeNode", "rootNode"); rootNode.put("isFrozen", false); rootNode.put("isRoot", true); List relList = new ArrayList (); Set keySet = nodeCollections.entrySet(); Iterator it = keySet.iterator() ; while(it.hasNext()){ Entry tmpSet = (Entry) it.next() ; String tmpKey = (String) tmpSet.getKey(); /** * 如果节点的isRoot属性值为true，则是根节点，直接返回该节点键名 * 否则，选取程序自动的方式生成根节点 */ if(!(nodeCollections.get(tmpKey).get("isRoot") instanceof Boolean)){ throw new Exception("节点"+ tmpKey + "参数isRoot类型错误,isRoot合法类型为布尔型,isRoot:" + nodeCollections.get(tmpKey).get("isRoot")); } boolean isRoot = (Boolean)nodeCollections.get(tmpKey).get("isRoot"); if(isRoot){ return tmpKey ; } /** * 默认根节点的子节点是节点结合中的所有节点 */ relList.add(tmpKey) ; } rootNode.put("relList", relList); nodeCollections.put("rootNode", rootNode);//将程序默认生成的根节点添加到节点集合中 return "rootNode" ; } /** * * 功能：在有向图中访问某个网络节点 * 作者：EugeneJao * @param nodeCollections * @param nodeName * @param visitedList * @return * @throws Exception */ private Map traverseInDigraph(Map > nodeCollections , Map nodeName , Map visitedList) throws Exception{ /** * 判断前进节点在网络中存不存在 */ if(nodeName.get("nextNode") != null){ if(!(nodeCollections.containsKey(nodeName.get("nextNode")))){ throw new Exception("节点网络构建异常,网络中不存在节点:" + nodeName); } } if(nodeName.get("curNode") == null || nodeName.get("beforeNode") == null){ throw new Exception("traverse()方法入参异常:curNode和beforeNode不能为空" + nodeName); } if(nodeName.get("nextNode") != null && nodeCollections.get(nodeName.get("nextNode"))== null ){ throw new Exception("节点"+ nodeName.get("nextNode") +"在节点集合中不存在"); } if(nodeName.get("nextNode") != null && !((nodeCollections.get(nodeName.get("nextNode")).get("isFrozen")) instanceof Boolean)){ throw new Exception("节点"+ nodeName.get("nextNode") +"参数类型异常:isFrozen合法类型为布尔类型，isFrozen:" + (nodeCollections.get(nodeName.get("nextNode")).get("isFrozen"))); } String nextNodeName = nodeName.get("nextNode") ; String curNodeName = nodeName.get("curNode") ; if( nextNodeName == null || (Boolean)nodeCollections.get(curNodeName).get("isFrozen")){ nodeName = backInDigraph(nodeCollections, nodeName); }else{ nodeName = headInDigraph(nodeCollections, nodeName, visitedList); } /** * 如果不是起始"视野"，但是nextNode和curNode相同的， * 说明在一个节点上可能存在包含自身的关系，这样的数据是异常数据 * 顺序不可调整至调用head()和back()的语句前面 */ if(nodeName.get("curNode").equals(nodeName.get("nextNode")) && !nodeName.get("curNode").equals(nodeName.get("beforeNode"))){ int curRelIndex = (Integer) nodeCollections.get(nodeName.get("curNode")).get("curRelIndex") ; throw new Exception("节点参数异常:节点" + nodeName.get("curNode")+ "的关系节点不能包含自身，在relList的第"+ (curRelIndex + 1)+"元素上"); } return nodeName ; } /** * * 功能：在有向图中前进至下一个节点 * 作者：EugeneJao * @param nodeCollections * @param nodeName * @param visitedList * @return */ @SuppressWarnings("unchecked") private Map headInDigraph(Map > nodeCollections , Map nodeName , Map visitedList){ String curNodeName = nodeName.get("nextNode") ; //传入参数的nextNode在本方法中即是当前节点 String beforeNodeName = nodeName.get("curNode") ;//传入参数的curNode在本方法中即是前一节点 Map curNode = nodeCollections.get(curNodeName); List relList = (List ) curNode.get("relList") ; curNode.put("beforeNode",beforeNodeName) ;//传入参数的beforeNode在本方法中即是当前节点 int curRelIndex = getNextNodeIndexInDigraph(curNode); /** * 获取下一个前进的目标节点名称,当curRelIndex等于relList的长度时， * 说明当前节点的所有关系节点都遍历完了,已无节点可以前进，只能后退 */ String nextNodeName = null ; if(curRelIndex < relList.size()){ nextNodeName = relList.get(curRelIndex) ; } /** * 更新当前节点信息 */ curNode.put("curRelIndex", curRelIndex);//不能调整顺序值调用getNextNodeIndex()方法后面 nodeCollections.put(curNodeName, curNode); /** * 更新nodeName信息 */ nodeName.put("nextNode", nextNodeName); nodeName.put("curNode", curNodeName); nodeName.put("beforeNode", beforeNodeName); /** * 更新visitedList信息 */ visitedList.put(curNodeName,null) ; return nodeName; } /** * * 功能：在无向图中后退至之前的节点 * 作者：EugeneJao * @param nodeCollections * @param nodeName * @return */ private Map backInDigraph(Map > nodeCollections , Map nodeName){ /** * 节点后退，说明遍历完当前节点的所有子孙节点后，依然没有闭环 * 所以先更新当前节点信息的isFroze字段为true * 在多个父节点的情况下，通过isFrozen字段来区分之前通过另一父节点对改节点的遍历 * 同时也通过这个属性介绍算法运算的复杂度 */ String curNodeName = nodeName.get("curNode"); Map curNode = nodeCollections.get(curNodeName); curNode.put("isFrozen", true); /** * 更新完Frozen属性后，做后退操作 */ curNodeName = nodeName.get("beforeNode") ; //传入参数的beforeNode在后退操作中即是当前节点 curNode = nodeCollections.get(curNodeName); List relList = (List ) curNode.get("relList") ; String beforeNodeName = (String) curNode.get("beforeNode"); /** * 先更新当前节点beforeNode信息，因为后面要用 */ curNode.put("beforeNode", beforeNodeName);//不能调整顺序值调用getNextNodeIndex()方法后面 int curRelIndex = getNextNodeIndexInDigraph(curNode); /** * 获取下一个前进的目标节点名称,当curRelIndex等于relList的长度时， * 说明当前节点的所有关系节点都遍历完了,已无节点可以前进，只能后退 */ String nextNodeName = null ; if(curRelIndex < relList.size()){ nextNodeName = relList.get(curRelIndex) ; } /** * 更新当前节点信息 */ curNode.put("curRelIndex", curRelIndex);//不能调整顺序值调用getNextNodeIndex()方法前面 nodeCollections.put(curNodeName, curNode); /** * 更新nodeName信息 */ nodeName.put("nextNode", nextNodeName); nodeName.put("curNode", curNodeName); nodeName.put("beforeNode",beforeNodeName) ; return nodeName; } /** * * 功能：检测有向图中是否存在环路 * 作者：EugeneJao * @param visitedList * @param curNodeName * @return */ private boolean containSameNodeInDigraph(Map visitedList,String curNodeName,Map > nodeCollections){ Map curNode = (Map ) nodeCollections.get(curNodeName); boolean isFrozen = (Boolean) curNode.get("isFrozen"); /** * 如果visitedList中存在当前节点，并且当前节点的isFrozen属性不为true * 则说明存在闭环 */ if(visitedList.containsKey(curNodeName) && !isFrozen){ return true ; } return false; } /** * * 功能：在有向图中获取下一节点名称在relList里的索引值 * 作者：EugeneJao * @param curNode * @return */ @SuppressWarnings("unchecked") private int getNextNodeIndexInDigraph(Map curNode){ List relList = (List ) curNode.get("relList") ; int curRelIndex = (Integer) curNode.get("curRelIndex") ; String beforeNodeName = (String) curNode.get("beforeNode"); curRelIndex ++ ; /** * 如果curRelIndex大于relList的大小 * 则说明当前节点的关系节点全都遍历过了,curRelIndex赋值为relList的大小， * 即说明当前节点的关系节点全都遍历过了，不能前进了，只能后退 */ if(curRelIndex > relList.size()){ curRelIndex = relList.size() ; } return curRelIndex ; }
测试代码如下：
public static void main(String [] args) throws Exception{
Map> nodeCollections = new HashMap>() ;
Map node_1 = new HashMap() ;
String nodeName_1 = "1" ;
List relList_1 = new ArrayList() ;
relList_1.add("2");
relList_1.add("3");
int curRelIndex_1 = -1 ;
String beforeNode_1 = null ;
node_1.put("nodeName", nodeName_1) ;
node_1.put("curRelIndex", curRelIndex_1) ;
node_1.put("beforeNode", beforeNode_1) ;
node_1.put("relList", relList_1) ;
node_1.put("isFrozen", false);
node_1.put("isRoot", true);
Map node_2 = new HashMap() ;
String nodeName_2 = "2" ;
List relList_2 = new ArrayList() ;
relList_2.add("4");
int curRelIndex_2 = -1 ;
String beforeNode_2 = null ;
node_2.put("nodeName", nodeName_2) ;
node_2.put("curRelIndex", curRelIndex_2) ;
node_2.put("beforeNode", beforeNode_2) ;
node_2.put("relList", relList_2) ;
node_2.put("isFrozen", false);
node_2.put("isRoot", false);
Map node_3 = new HashMap() ;
String nodeName_3 = "3" ;
List relList_3 = new ArrayList() ;
relList_3.add("4");
int curRelIndex_3 = -1 ;
String beforeNode_3 = null ;
node_3.put("nodeName", nodeName_3) ;
node_3.put("curRelIndex", curRelIndex_3) ;
node_3.put("beforeNode", beforeNode_3) ;
node_3.put("relList", relList_3) ;
node_3.put("isFrozen", false);
node_3.put("isRoot", false);
Map node_4 = new HashMap() ;
String nodeName_4 = "4" ;
List relList_4 = new ArrayList() ;
relList_4.add("5");
relList_4.add("6");
int curRelIndex_4 = -1 ;
String beforeNode_4 = null ;
node_4.put("nodeName", nodeName_4) ;
node_4.put("curRelIndex", curRelIndex_4) ;
node_4.put("beforeNode", beforeNode_4) ;
node_4.put("relList", relList_4) ;
node_4.put("isFrozen", false);
node_4.put("isRoot", false);
Map node_5 = new HashMap() ;
String nodeName_5 = "5" ;
List relList_5 = new ArrayList() ;
int curRelIndex_5 = -1 ;
String beforeNode_5 = null ;
node_5.put("nodeName", nodeName_5) ;
node_5.put("curRelIndex", curRelIndex_5) ;
node_5.put("beforeNode", beforeNode_5) ;
node_5.put("relList", relList_5) ;
node_5.put("isFrozen", false);
node_5.put("isRoot", false);
Map node_6 = new HashMap() ;
String nodeName_6 = "6" ;
List relList_6 = new ArrayList() ;
relList_6.add("7");
int curRelIndex_6 = -1 ;
String beforeNode_6 = null ;
node_6.put("nodeName", nodeName_6) ;
node_6.put("curRelIndex", curRelIndex_6) ;
node_6.put("beforeNode", beforeNode_6) ;
node_6.put("relList", relList_6) ;
node_6.put("isFrozen", false);
node_6.put("isRoot", false);
Map node_7 = new HashMap() ;
String nodeName_7 = "7" ;
List relList_7 = new ArrayList() ;
relList_7.add("6");
int curRelIndex_7 = -1 ;
String beforeNode_7 = null ;
node_7.put("nodeName", nodeName_7) ;
node_7.put("curRelIndex", curRelIndex_7) ;
node_7.put("beforeNode", beforeNode_7) ;
node_7.put("relList", relList_7) ;
node_7.put("isFrozen", false);
node_7.put("isRoot", false);
nodeCollections.put("1",node_1 );
nodeCollections.put("2",node_2 );
nodeCollections.put("3",node_3 );
nodeCollections.put("4",node_4 );
nodeCollections.put("5",node_5 );
nodeCollections.put("6",node_6 );
nodeCollections.put("7",node_7 );
GraphAnalysis analysis = new GraphAnalysis() ;
long start = System.currentTimeMillis();
/*boolean result = analysis.isContainLoop(nodeCollections);*/
boolean result = analysis.isContainLoopInDigraph(nodeCollections);
long end = System.currentTimeMillis();
System.out.println(result);
System.out.println("耗时:" + (end - start) );
}