基于十字链表储存大型路网Java实现

行文目录

• 1 十字链表
• • 1.1 基本概念
  • • 1.1.1 邻接表与逆邻接表
    • 1.1.2 十字链表
  • 1.2 基本操作
• 2 十字链表java实现
• • 2.1 结点定义
  • 2.2 边的定义
  • 2.3 网络的定义
  • 2.4 路网加载
  • 2.5 解释说明

1 十字链表

1.1 基本概念

十字链表是一种综合了邻接表和逆邻接表的一种链式储存结构。邻接表是图的标准表示方法，先简单介绍邻接表，再介绍十字链表。

1.1.1 邻接表与逆邻接表

邻接表主要是为了节省稀疏图的储存空间，采用链表的方式进行图的存储。邻接表主要是反映顶点出度的情况，逆邻接表主要是反映入度情况。举个例子。

其中，其邻接表表示为（节点结构为：顶点编号、权值、下一个节点位置）：

其中，其逆邻接表表示为：

由上面两张图片可以看出，领接表与逆邻接表主要是出度与入度的差别。

1.1.2 十字链表

为什么已经有邻接表了还需要介绍十字链表呢？原因就是对于出度和入度，邻接表不能兼得。在大型路网中，计算从A点出发，前往最近的K个点用邻接表很容易计算，但是基于邻接表计算从其他节点出发，到达A点最近的K个节点就不好计算了。原因就是出度和入度不能兼得。为了解决在有向图中的相关问题，在大型路网中可以基于十字链表进行图算法设计。

以下部分是对相关blog的总结，侵删（传送门1，传送门2）。图片主要源于书籍（大话数据结构）。

顶点结构

• firstin、firstout 分别指向入边表、出边表中的第一个结点

边结构

• tailvex、headvex分别指弧起点（即弧尾）、弧终点（即弧头）在顶点表中的下标。
• headlink是指入边表指针域，指向终点相同的下一条边（即弧头相同，所以命名为headlink）
• taillink是指出边表指针域，指向起点相同的下一条边（即弧尾相同，所以命名为taillink）

网络表示

看完上面的介绍，初学者的我表示：…，都是些啥哟?

后来稍微有点理解了之后我会这样子介绍十字链表。

当然，我画的图并不严谨，只是我是这么理解的。在表示网络时，我们先设置一个点集，每个Node对象中存在两个属性，其中adjacentLinks存储该点的后继边，也就是领接表中的出度；predecessorLinks存储该点的前继边，也就是逆邻接表的入度。这是不是很容易理解了？一个节点无非就只有这两种属性，从这个节点出来的边和进来的边。所以说，十字链表关注的重点是顶点（一家之言，欢迎指正）。

1.2 基本操作

作为一个网络结构。一般需要有的功能是：

• 增加节点
• 增加一条边
• 删除节点
• 删除一条边
• 属性统计（网络节点数、边数、节点出度、入度、节点是否包含邻接边）

具体操作看代码吧

2 十字链表java实现

2.1 结点定义

package Graph;import java.util.HashMap;
import SSP.*;public class NetNode {private int m_nodeID;private HashMap<Integer, NetLink> m_pAdjacentLinkset;private HashMap<Integer, NetLink> m_pPredecessorLinks;private Label label;public NetNode(int iNodeID, HashMap<Integer, NetLink> pAdjacentLinkset, HashMap<Integer, NetLink> pPredecessorLinks)throws Exception{if (iNodeID < 0){ throw new Exception("NetNode encounter an error." + "nodeID should large than 0: " + iNodeID); }if (pAdjacentLinkset == null || pPredecessorLinks == null){ throw new Exception("NetNode encounter an error." + "pAdjacentLinkset and pPredecessorLinks should not be null"); }m_nodeID = iNodeID;m_pAdjacentLinkset = pAdjacentLinkset;m_pPredecessorLinks = pPredecessorLinks;label = null;}public NetNode(int iNodeID){m_nodeID = iNodeID;m_pAdjacentLinkset = new HashMap<>();;m_pPredecessorLinks = new HashMap<>();label = null;}public int NodeID(){return m_nodeID;}public int AdjacentLinkCount(){return m_pAdjacentLinkset.size();}public Label getLabel(){return this.label;}public void setLabel(Label newLabel) {this.label = newLabel;}public HashMap<Integer, NetLink> AdjacentLinks(){return m_pAdjacentLinkset;}public HashMap<Integer, NetLink> PredecessorLinks(){return m_pPredecessorLinks;}public Boolean hasAdjacentLink(Integer iHeadNodeID){return m_pAdjacentLinkset.containsKey(iHeadNodeID);}public NetLink GetAdjacentLink(Integer iHeadNodeID){try{return m_pAdjacentLinkset.get(iHeadNodeID);}catch (Exception e){System.out.println("NetNode encounter an error." + "node " + m_nodeID + " does not contain any adjacent node:" + iHeadNodeID);}return m_pAdjacentLinkset.get(iHeadNodeID);}public void AddAdjacentLink(NetLink pAdjacentLink){m_pAdjacentLinkset.put(pAdjacentLink.headNodeID, pAdjacentLink);}public void RemoveAdjacentLink(Integer iHeadNodeID){if (m_pAdjacentLinkset.containsKey(iHeadNodeID)){m_pAdjacentLinkset.remove(iHeadNodeID);}}public void Release(){m_pAdjacentLinkset.clear();m_pPredecessorLinks.clear();}public void AddPredecessorLink(NetLink pPredecessorLink) throws Exception{if (pPredecessorLink == null){ throw new Exception("NetNode encounter an error." + "pPredecessorLink should not be null"); }m_pPredecessorLinks.put(pPredecessorLink.tailNodeID, pPredecessorLink);}public void RemovePredecessorLink(int iTailNodeID) throws Exception{if (m_pPredecessorLinks.containsKey(iTailNodeID)){m_pPredecessorLinks.remove(iTailNodeID);}else{throw new Exception("NetNode encounter an error.input tail node does not exist:");}}
}

2.2 边的定义

package Graph;public class NetLink {public NetNode headNode;public NetNode tailNode;public double linkCost;public int headNodeID;public int tailNodeID;public int linkID;public NetLink(NetNode pTailNode, NetNode pHeadNode, double pLinkCost, int plinkID){this.headNode = pHeadNode;this.tailNode = pTailNode;this.linkCost = pLinkCost;this.headNodeID = pHeadNode.NodeID();this.tailNodeID = pTailNode.NodeID();this.linkID = plinkID;}
}

2.3 网络的定义

package Graph;
import java.util.*;public class Network {public HashMap<Integer, NetNode> m_pNodesets;public Network() {m_pNodesets = new HashMap<>();}public Boolean isNodeExists(int iNodeID){return m_pNodesets.containsKey(iNodeID);}public NetNode GetNetNode(int iNodeID) throws Exception{try{return m_pNodesets.get(iNodeID);}catch (Exception ex){throw new Exception("Network.GetNetNode() encounter an error." + ex.getStackTrace());}}public Boolean isLinkExists(int iTailNodeID, int iHeadNodeID) throws Exception{if (!this.isNodeExists(iTailNodeID)){return false;}NetNode pTailNode = this.GetNetNode(iTailNodeID);if (!pTailNode.hasAdjacentLink(iHeadNodeID)){return false;}return true;}public NetLink GetNetLink(int iTailNodeID, int iHeadNodeID) throws Exception{try{NetNode pTailNode = this.GetNetNode(iTailNodeID);return pTailNode.GetAdjacentLink(iHeadNodeID);}catch (Exception ex){throw new Exception("Network.GetNetLink() encounter an error.");}}public void AddNode(int iNodeID, NetNode pNetNode) throws Exception{if (iNodeID < 0){throw new Exception("Network encounter an error." + "nodeID should not be negative: " + iNodeID);}if (this.isNodeExists(iNodeID)){throw new Exception("Network encounter an error." + "input node is alread in the network: " + iNodeID);}if (pNetNode == null){throw new Exception("Network encounter an error." + "input pNetNode should not be null");}m_pNodesets.put(iNodeID, pNetNode);}public void RemoveNode(int iNodeID) throws Exception{if (m_pNodesets.containsKey(iNodeID)){m_pNodesets.remove(iNodeID);}else{throw new Exception("Network.RemoveNode() encounter an error." + "Node " + iNodeID + " is not in the network.");}}
}

2.4 路网加载

package SSP;import java.io.BufferedReader;
import java.io.FileReader;import Graph.NetLink;
import Graph.NetNode;
import Graph.Network;public class NetworkLoader {private BufferedReader reader;public Network loadNet(String path) throws Exception {Network pNetwork = new Network();//File inFile = new File(path);String inString ="";try {//reader = new BufferedReader(new FileReader("C:\\Users\\hhhSir\\Desktop\\Network.csv"));reader = new BufferedReader(new FileReader(path));reader.readLine();NetNode pTailNode;NetNode pHeadNode;NetLink pNetLink;while((inString=reader.readLine())!=null) {String item[] = inString.split(",");int fromNodeID = new Integer(item[0]);int toNodeID = new Integer(item[1]);int objectID = new Integer(item[2]);double linkCost = new Double(item[3]);if(!pNetwork.isNodeExists(fromNodeID)) {pTailNode = new NetNode(fromNodeID);//pNetwork.m_pNodesets.put(fromNodeID, pTailNode);pNetwork.AddNode(fromNodeID, pTailNode);}else {pTailNode = pNetwork.GetNetNode(fromNodeID);}if(!pNetwork.isNodeExists(toNodeID)) {pHeadNode = new NetNode(toNodeID);//pNetwork.m_pNodesets.put(toNodeID, pHeadNode);pNetwork.AddNode(toNodeID, pHeadNode);}else {pHeadNode = pNetwork.GetNetNode(toNodeID);}if(!pTailNode.hasAdjacentLink(toNodeID)) {pNetLink = new NetLink(pTailNode, pHeadNode, linkCost, objectID);pTailNode.AddAdjacentLink(pNetLink);}else {throw new Exception("pTailNode exists the adjacentLink, the link exists"); }if(!pHeadNode.PredecessorLinks().containsKey(fromNodeID)) {pHeadNode.AddPredecessorLink(pNetLink);}else {throw new Exception("pHeadNode exists the PredecessorLink, the link exists");}}}catch(Exception e) {e.printStackTrace();}return pNetwork;}
}

2.5 解释说明

其中上面用到了一个label类，也是自己定义的，主要是为了计算最短距离溯源用的，先贴个代码，后续有时间写一点最短路径的算法。

package SSP;import Graph.*;public class Label {public NetNode pAssociatedNode;public double iPathCost;  //pathCostpublic NetLink pLink;public Label pPrevious;public Label(NetNode pNode, double pathCost, NetLink link, Label previous) {this.pAssociatedNode = pNode;this.iPathCost = pathCost;this.pLink = link;this.pPrevious = previous;}public Label(NetNode pNode) {this.pAssociatedNode = pNode;this.iPathCost = 0;this.pLink = null;this.pPrevious = null;}//扩展下一个节点public Label ExpandAcylic(NetLink pLink) {NetNode pNode = pLink.headNode;//判断扩展的节点是不是在路径中if(this.isNodeInPath(pNode.NodeID())) {return null;}else {//生成新的labeldouble newPathCost = this.iPathCost+pLink.linkCost;return new Label(pNode, newPathCost, pLink, this);//return null;}}public Boolean isNodeInPath(int iNodeID) {if(iNodeID==pAssociatedNode.NodeID()) {return true;}Label pLabel = this;while(pLabel!=null) {if(pLabel.pAssociatedNode.NodeID()==iNodeID) {return true;}pLabel = pLabel.pPrevious;}return false;}
}

该demo的用例是一个Network.csv的文件，文件格式为：

分别是起点、终点、对应边编号、对应边长度四个字段。测试数据如下所示，是厦门市厦门岛路网数据。

链接：https://pan.baidu.com/s/1WgWl-w5xDGSFNnL5iJ_pbA
提取码：py6k

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！