基于C中一個(gè)行壓縮圖的簡(jiǎn)單實(shí)現(xiàn)代碼

2020-01-26 16:17:56

字體：大中小

供稿：網(wǎng)友

首先簡(jiǎn)單說一下什么是行壓縮圖，其實(shí)嚴(yán)格意義上應(yīng)該是行壓縮矩陣。正常情況下，矩陣是用二維數(shù)組簡(jiǎn)單存儲(chǔ)的，但是如果是稀疏矩陣，也就是零很多的時(shí)候，這樣比較浪費(fèi)空間。所以就有各種節(jié)省空間的存儲(chǔ)方式，三元組存儲(chǔ)就是其中一種。

什么是三元組呢？一個(gè)三元組就是(row,col,value)，這樣把所有不為零的值組成一個(gè)向量。這種存儲(chǔ)方式比二維數(shù)組節(jié)省了不少空間，當(dāng)然還可以進(jìn)一步節(jié)省，因?yàn)槿M里面row或者col重復(fù)存儲(chǔ)了，一行或者一列存一次就行了，按這種思路走下去就是行壓縮存儲(chǔ)了。

那具體什么是行壓縮存儲(chǔ)呢？行壓縮存儲(chǔ)的思想就是，把所有不為零的值按行訪問的順序組成一個(gè)向量，然后再把每一行值不為0的列的下標(biāo)存下來，這個(gè)兩個(gè)向量的大小和稀疏矩陣中不為0的值得個(gè)數(shù)相同，當(dāng)然要實(shí)現(xiàn)對(duì)行壓縮矩陣的訪問，還要把每一行的不為0的列的下標(biāo)在第二個(gè)向量中開始的位置存下來，有人把這個(gè)叫做指針。有了這三個(gè)向量就可以實(shí)現(xiàn)對(duì)矩陣實(shí)現(xiàn)高效的按行訪問了。行壓縮存儲(chǔ)比三元組優(yōu)秀的不僅是空間的壓縮，還有就是行訪問時(shí)的高效。三元組如果是有序的，可以二分查找來訪問一行，但是行壓縮存儲(chǔ)按行訪問時(shí)的時(shí)間復(fù)雜度是常數(shù)級(jí)的。大家可以參考下面這個(gè)行壓縮矩陣示意圖：

可能你會(huì)有疑問，你明明實(shí)現(xiàn)的行壓縮圖，怎么扯了這么多行壓縮矩陣呢？其實(shí)圖和矩陣是等價(jià)的，矩陣的一行可以看做是圖一個(gè)節(jié)點(diǎn)的出邊，矩陣的一列可以看做圖一個(gè)節(jié)點(diǎn)的入邊。當(dāng)然這里需要滿足兩個(gè)條件：第一個(gè)就是圖節(jié)點(diǎn)編號(hào)必須是從0或者1開始的連續(xù)數(shù)值（這個(gè)可以通過對(duì)圖的節(jié)點(diǎn)做一次映射解決），第二個(gè)就是圖必須至少是弱連通的（非連通圖可以拆成連圖片）。實(shí)現(xiàn)了稀疏矩陣的高效存儲(chǔ)訪問，也就實(shí)現(xiàn)了圖的高效存儲(chǔ)訪問。

下面來說一下，我的實(shí)現(xiàn)。我的實(shí)現(xiàn)跟經(jīng)典的行壓縮矩陣有兩個(gè)不同：第一個(gè)就是經(jīng)典的行壓縮矩陣沒有考慮一行全為0的情況，我對(duì)這種情況做了處理（之所以處理當(dāng)然不是因?yàn)槲覠o聊，而是因?yàn)橛羞@個(gè)需求）。第二個(gè)就是經(jīng)典的行壓縮圖對(duì)按列訪問比較慢（當(dāng)然是相對(duì)于按行訪問的速度而言），對(duì)行壓縮圖按列訪問時(shí)，時(shí)間復(fù)雜度是線性的。我也對(duì)這種情況做了處理。

這里簡(jiǎn)單說一下我的思路：

第一個(gè)問題，我是通過將所有指針默認(rèn)設(shè)為-1，即表示該行可能全為0，只有當(dāng)有非零值時(shí)才設(shè)置為其正確的指針。當(dāng)然訪問時(shí)也要做相應(yīng)的處理。

第二個(gè)問題，我是這樣解決的。我按列壓縮存儲(chǔ)的方式，存了一份每一列不為0的行下標(biāo)，以及每一列不為0的行下標(biāo)開始的位置。這樣我的實(shí)現(xiàn)中就多了兩個(gè)向量，浪費(fèi)了存儲(chǔ)空間，但是提高了按列訪問時(shí)的效率。

好了，talk is cheap，show me the code。下面是我的代碼（可能有錯(cuò)，我只做了簡(jiǎn)單的測(cè)試）

利用邊向量構(gòu)造壓縮圖

復(fù)制代碼代碼如下:

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

復(fù)制代碼代碼如下:

獲得一個(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;
}

這里訪問方式就跟按行訪問不一樣了，行訪問時(shí)，直接讀weight向量里面對(duì)應(yīng)的值就行了，這里不行，應(yīng)該weight向量是按行訪問順序存的。我的解決方法，獲取入節(jié)點(diǎn)，然后對(duì)整個(gè)節(jié)點(diǎn)對(duì)按行訪問獲得對(duì)應(yīng)值。這樣雖然繞了一下，但是對(duì)于稀疏圖來說，基本上也是常數(shù)級(jí)的。下面是getWeight的代碼

復(fù)制代碼代碼如下:

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

最后是對(duì)行或者列全0時(shí)的特殊處理，這里處理，體現(xiàn)在從指針向量獲取開始和結(jié)束位置的函數(shù)上

復(fù)制代碼代碼如下:

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

這里我只實(shí)現(xiàn)了兩個(gè)最簡(jiǎn)單的功能，獲取入邊和出邊。一方面是因?yàn)椋瑢?duì)于我做的東西，這兩個(gè)函數(shù)就夠了，另一方面，對(duì)于一個(gè)圖來說，有這兩個(gè)函數(shù)，其他函數(shù)都可以相應(yīng)實(shí)現(xiàn)。

上一篇：去掉vs2010中ipch文件和.sdf文件的解決方法

下一篇：C中實(shí)現(xiàn)矩陣乘法的一種高效的方法