一个行压缩图的简单实现

首先简单说一下什么是行压缩图,其实严格意义上应该是行压缩矩阵。正常情况下,矩阵是用二维数组简单存储的,但是如果是稀疏矩阵,也就是零很多的时候,这样比较浪费空间。所以就有各种节省空间的存储方式,三元组存储就是其中一种。

什么是三元组呢?一个三元组就是(row,col,value),这样把所有不为零的值组成一个向量。这种存储方式比二维数组节省了不少空间,当然还可以进一步节省,因为三元组里面row或者col重复存储了,一行或者一列存一次就行了,按这种思路走下去就是行压缩存储了。

那具体什么是行压缩存储呢?行压缩存储的思想就是,把所有不为零的值按行访问的顺序组成一个向量,然后再把每一行值不为0的列的下标存下来,这个两个向量的大小和稀疏矩阵中不为0的值得个数相同,当然要实现对行压缩矩阵的访问,还要把每一行的不为0的列的下标在第二个向量中开始的位置存下来,有人把这个叫做指针。有了这三个向量就可以实现对矩阵实现高效的按行访问了。行压缩存储比三元组优秀的不仅是空间的压缩,还有就是行访问时的高效。三元组如果是有序的,可以二分查找来访问一行,但是行压缩存储按行访问时的时间复杂度是常数级的。 大家可以参考下面这个行压缩矩阵示意图:

可能你会有疑问,你明明实现的行压缩图,怎么扯了这么多行压缩矩阵呢?其实图和矩阵是等价的,矩阵的一行可以看做是图一个节点的出边,矩阵的一列可以看做图一个节点的入边。当然这里需要满足两个条件:第一个就是图节点编号必须是从0或者1开始的连续数值(这个可以通过对图的节点做一次映射解决),第二个就是图必须至少是弱连通的(非连通图可以拆成连图片)。实现了稀疏矩阵的高效存储访问,也就实现了图的高效存储访问。

下面来说一下,我的实现。我的实现跟经典的行压缩矩阵有两个不同:第一个就是经典的行压缩矩阵没有考虑一行全为0的情况,我对这种情况做了处理(之所以处理当然不是因为我无聊,而是因为有这个需求)。第二个就是经典的行压缩图对按列访问比较慢(当然是相对于按行访问的速度而言),对行压缩图按列访问时,时间复杂度是线性的。我也对这种情况做了处理。

这里简单说一下我的思路:

第一个问题,我是通过将所有指针默认设为-1,即表示该行可能全为0,只有当有非零值时才设置为其正确的指针。当然访问时也要做相应的处理。

第二个问题,我是这样解决的。我按列压缩存储的方式,存了一份每一列不为0的行下标,以及每一列不为0的行下标开始的位置。这样我的实现中就多了两个向量,浪费了存储空间,但是提高了按列访问时的效率。

好了,talk is cheap,show me the code。下面是我的代码(可能有错,我只做了简单的测试)

利用边向量构造压缩图

/*
* buildGraph 利用边向量 构造压缩图
* 对边分别按第一个顶点、第二个顶点排序
* 然后分别按行压缩图和列压缩图构造行、列索引和指针
* 全零行和全零列,指针置为-1
*/
private void buildGraph(Vector<Edge> edges) {
int edgeSize = edges.size();
weight
= new Vector<Float>(edgeSize);
rowIndex
= new Vector<Integer>(edgeSize);
rowPtr
= new Vector<Integer>(nodeCount + 1);
colIndex
= new Vector<Integer>(edgeSize);
colPtr
= new Vector<Integer>(nodeCount + 1);
// set default value as -1
for (int i = 0; i < nodeCount; ++i) {
rowPtr.add(
-1);
colPtr.add(
-1);
}
rowPtr.add(edges.size());
colPtr.add(edges.size());

// sort the edge based on first node
EdgeBasedOnFirstNodeComparator cmp = new EdgeBasedOnFirstNodeComparator();
Collections.sort(edges, cmp);
// build row index and pointer
int curNode = edges.elementAt(0).getFirstNode();
int curPtr = 0;
for (int i = 0; i < edgeSize; ++i) {
Edge e
= edges.elementAt(i);
// System.out.println("curNode" + curNode + "firstNode: "
// + e.getFirstNode());
weight.add(e.getWeight());
rowIndex.add(e.getSecondNode());
if (curNode != e.getFirstNode()) {
rowPtr.set(curNode, curPtr);
curNode
= e.getFirstNode();
curPtr
= i;
}

}
rowPtr.set(curNode, curPtr);
// sort the edge based on second node
EdgeBasedOnSecondNodeComparator cmp2 = new EdgeBasedOnSecondNodeComparator();
Collections.sort(edges, cmp2);
// build column index and pointer
curNode = edges.elementAt(0).getSecondNode();
curPtr
= 0;
for (int i = 0; i < edgeSize; ++i) {
Edge e
= edges.elementAt(i);
colIndex.add(e.getFirstNode());
if (curNode != e.getSecondNode()) {
colPtr.set(curNode, curPtr);
curNode
= e.getSecondNode();
curPtr
= i;
}

}
colPtr.set(curNode, curPtr);
}

获得一个节点的出边

/*
* getOutEdges 返回结点所有的出边(即所有由结点指出的边)
*
* @param node 要查找的结点
*
* @return 返回结点所有的出边组成的向量
*/
@Override
public Vector<Edge> getOutEdges(int node) {
Vector<Edge> res = new Vector<Edge>();
int startIndex = getStartIndex(node, true);
if (startIndex == -1) {
// 没有出边的点
return null;
}
int endIndex = getEndIndex(node, true);
float value;
Edge e;
int outNode;
for (int index = startIndex; index < endIndex; ++index) {
value = weight.elementAt(index);
outNode = rowIndex.elementAt(index);
e = new Edge(node, outNode, value);
res.add(e);
}
return res;
}

获得一个节点的入边

/*
* getInEdges 获取结点所有的入边(即所有指向结点的边)
*
* @param node 要查找的结点
*
* @return 返回所有由结点入边组成的向量
*/
@Override
public Vector<Edge> getInEdges(int node) {
Vector<Edge> res = new Vector<Edge>();
int startIndex = getStartIndex(node, false);
// 没有入边的点
if (startIndex == -1) {
return null;
}
int endIndex = getEndIndex(node, false);
float value;
Edge e;
int inNode;
for (int index = startIndex; index < endIndex; ++index) {
inNode = colIndex.elementAt(index);
value = getWeight(inNode, node);
e = new Edge(inNode, node, value);
res.add(e);
}
return res;
}

这里访问方式就跟按行访问不一样了,行访问时,直接读weight向量里面对应的值就行了,这里不行,应该weight向量是按行访问顺序存的。我的解决方法,获取入节点,然后对整个节点对按行访问获得对应值。这样虽然绕了一下,但是对于稀疏图来说,基本上也是常数级的。下面是getWeight的代码

/*
* getWeight 获得特定边的weight
*/
private float getWeight(int row, int col) {
int startIndex = getStartIndex(row, true);
int endIndex = getEndIndex(row, true);
for (int i = startIndex; i < endIndex; ++i) {
if (rowIndex.elementAt(i) == col)
return weight.elementAt(i);
}
return 0;
}

最后是对行或者列全0时的特殊处理,这里处理,体现在从指针向量获取开始和结束位置的函数上

/*
* getStartIndex 获取特定顶点的开始索引
*/
private int getStartIndex(int node, boolean direction) {
// true : out edge
if (direction)
return rowPtr.elementAt(node);
else
return colPtr.elementAt(node);
}

 

/*
* getEndIndex 获取特定顶点的结束索引
*/
private int getEndIndex(int node, boolean direction) {
// true:out edge
if (direction) {
int i = 1;
while ((node + i) < nodeCount) {
if (rowPtr.elementAt(node + i) != -1)
return rowPtr.elementAt(node + i);
else
++i;
}
return rowPtr.elementAt(nodeCount);
} else {
int i = 1;
while ((node + i) < nodeCount) {
if (colPtr.elementAt(node + i) != -1)
return colPtr.elementAt(node + i);
else
++i;
}
return colPtr.elementAt(nodeCount);
}
}

  

这里我只实现了两个最简单的功能,获取入边和出边。一方面是因为,对于我做的东西,这两个函数就够了,另一方面,对于一个图来说,有这两个函数,其他函数都可以相应实现。好吧,最后我再说一句,我这是抛砖引玉,实在简陋。其实C++ boost库里面有一个实现很好的行压缩图,只是有点复杂,有兴趣的可以去看一下 http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/compressed_sparse_row.html

 

 

本文链接



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量