基于C中一个行压缩图的简单实现代码（2） Vector, return, null

yuyang911220

代码如下:
获得一个节点的出边
/*
* 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);
        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) {
        // trueut 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);
        }
    }
这里我只实现了两个最简单的功能，获取入边和出边。一方面是因为，对于我做的东西，这两个函数就够了，另一方面，对于一个图来说，有这两个函数，其他函数都可以相应实现。