代码如下:
/*
* buildGraph 利用边向量 构造压缩图
* 对边分别按第一个顶点、第二个顶点排序
* 然后分别按行压缩图和列压缩图构造行、列索引和指针
* 全零行和全零列,指针置为-1
*/
private void buildGraph(VectorEdge edges) {
int edgeSize = edges.size();
weight = new VectorFloat(edgeSize);
rowIndex = new VectorInteger(edgeSize);
rowPtr = new VectorInteger(nodeCount + 1);
colIndex = new VectorInteger(edgeSize);
colPtr = new VectorInteger(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 VectorEdge getOutEdges(int node) {
VectorEdge res = new VectorEdge();
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 VectorEdge getInEdges(int node) {
VectorEdge res = new VectorEdge();
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);
if(startIndex==-1)
return 0;
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);
}
}
这里我只实现了两个最简单的功能,获取入边和出边。一方面是因为,对于我做的东西,这两个函数就够了,另一方面,对于一个图来说,有这两个函数,其他函数都可以相应实现。