/*
 * buildGraph 利用邊向量 構(gòu)造壓縮圖
 * 對(duì)邊分別按第一個(gè)頂點(diǎn)、第二個(gè)頂點(diǎn)排序
 * 然后分別按行壓縮圖和列壓縮圖構(gòu)造行、列索引和指針
 * 全零行和全零列,指針置為-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);
    }

獲得一個(gè)節(jié)點(diǎn)的出邊
/*
 * getOutEdges 返回結(jié)點(diǎn)所有的出邊(即所有由結(jié)點(diǎn)指出的邊)
 *
 * @param node 要查找的結(jié)點(diǎn)
 *
 * @return 返回結(jié)點(diǎn)所有的出邊組成的向量
 */
@Override
public Vector<Edge> getOutEdges(int node) {
    Vector<Edge> res = new Vector<Edge>();
    int startIndex = getStartIndex(node, true);
    if (startIndex == -1) {
        // 沒有出邊的點(diǎn)
        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;
}

獲得一個(gè)節(jié)點(diǎn)的入邊
?
/*
 * getInEdges 獲取結(jié)點(diǎn)所有的入邊(即所有指向結(jié)點(diǎn)的邊)
 *
 * @param node 要查找的結(jié)點(diǎn)
 *
 * @return 返回所有由結(jié)點(diǎn)入邊組成的向量
 */
@Override
public Vector<Edge> getInEdges(int node) {
    Vector<Edge> res = new Vector<Edge>();
    int startIndex = getStartIndex(node, false);
    // 沒有入邊的點(diǎn)
    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;
}

/*
     * 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;
    }

/*
 * getStartIndex 獲取特定頂點(diǎn)的開始索引
 */
    private int getStartIndex(int node, boolean direction) {
        // true : out edge
        if (direction)
            return rowPtr.elementAt(node);
        else
            return colPtr.elementAt(node);
    }

　
?
/*
 * getEndIndex 獲取特定頂點(diǎn)的結(jié)束索引
 */
    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);
        }
    }