1052 Quiz#2 基於相鄰矩陣的有向圖表示方法

C++ 實習測試: 基於相鄰矩陣的有向圖表示方法 - Graph 類別

在這個測試裡, 我們把正課期中考時的 Graph 類別實際製作出來, 你需要在編譯器的協助下克服所有的語法問題。可以看書, 可以看講義, 可以 google, 可以線上查參考資料, 就是不要跟同學討論, 不要線上和別人討論, 不要繳交同學的 code, 對於下面的描述有疑問覺得有模稜兩可的請一定要提出問題, 不過請不要問這個為什麼 compile 不成功? 為什麼會當掉? 或是該怎麼寫? ...

在雲端運算/雲端儲存或是物聯網的環境中，我們可以運用上圖的有向圖 (Directed Graph) 作為端點以及連結架構的模型，以便運用一些演算法來計算流量或是動態地調配資源，資料檔案 data.txt 配合下面的Graph類別定義以及部份介面的實作, 可以在建構的時候由檔案串流中讀取資料，並且以下圖節點Vertex的單向串列建立相鄰矩陣 (Adjacency Matrix)，代表一個一般化有權重的有向圖

struct Vertex
{
    Vertex(): ID(0), weight(0), next(0) { }
    Vertex(int id, int weight)
        :ID(id), weight(weight), next(0) { }
    Vertex(const Vertex& src): ID(src.ID), weight(src.weight), next(0) { }
    ~Vertex() { delete next; }
    int ID;
    int weight;
    Vertex *next;
};

class Graph
{
public:
    Graph(ifstream &);
    Graph(const Graph &src);
    ~Graph();
    int getFirst(const int id, int *weight);
    int next(int *weight);
    void print(ostream &os);
private:
    void clone(const Graph &src);
    Vertex *m_listHeads;
    int m_curVertex;
    Vertex *m_iter;
    int m_nNodes;
    int m_nEdges;
};

Graph::Graph(ifstream &infile)
    : m_curVertex(0), m_iter(0)
{
    int i;
    infile >> m_nNodes;
    infile.ignore(80, '\n');

    infile >> m_nEdges;
    infile.ignore(80, '\n');

    m_listHeads = new Vertex[m_nNodes];
    for (i=0; i<m_nNodes; i++)
        m_listHeads[i].ID = i;

    int node1, node2, weight;
    Vertex *ptr;
    for (i=0; i<m_nEdges; i++)
    {
        infile >> node1 >> node2 >> weight;
        infile.ignore(80, '\n');
        ptr = &m_listHeads[node1];
        while (ptr->next!=0)
            ptr = ptr->next;
        ptr->next = new Vertex(node2, weight);
        m_listHeads[node1].weight++;
    }
}

Graph::~Graph()
{
    delete[] m_listHeads;
}

Graph::Graph(const Graph &src)
    : m_listHeads(0),
      m_curVertex(src.m_curVertex),
      m_iter(src.m_iter),
      m_nNodes(src.m_nNodes),
      m_nEdges(src.m_nEdges)
{
    clone(src);
}

void Graph::clone(const Graph &src)
{
    int i, j;
    Vertex *ptr, *ptrSrc;
    if (m_nNodes≤<=0)
        return;
    m_listHeads = new Vertex[m_nNodes];
    for (i=0; i<m_nNodes; i++)
    {
        m_listHeads[i].ID = i;
        m_listHeads[i].weight = src.m_listHeads[i].weight;
        ptrSrc = &src.m_listHeads[i];
        ptr = &m_listHeads[i];
        for (j=0; j<m_listHeads[i].weight; j++)
        {
            ptr->next = new Vertex(*(ptrSrc->next));
            ptrSrc = ptrSrc->next;
            ptr = ptr->next;
        }
    }
}

請根據下列要求完成這個類別：

先產生 VC 的專案, 把上面的程式碼放到適當的檔案裡, 下載 data.txt, 作出 main 函式與 unitTest 函式, 運用上面程式由串流中建構基礎的 Graph 類別, 編譯執行


1. 如果圖的架構常常需要調整, 允許刪除或是新增某些邊 (edge), 請設計並實作一個介面 void addEdge(const int node1, const int node2, int weight); 來新增一條類似 (0,4,3) 的邊
   
   
2. 請設計並實作一個介面 bool deleteEdge(const int node1, const int node2, int weight); 來刪除類似 (8,5,2) 的邊
   
   
3. 請實作一個 bool equal(const Graph&) const; 的介面來檢查兩個 graph 是不是完全一樣
   
   
4. 請替 Graph 類別撰寫一個設定運算子 (assignment operator, 請運用 private 的 clone 輔助函式)
   
   
5. 請撰寫單元測試程式碼, main() 裡面執行此測試, 單元測試主要測試上述建構元, 解構元, getFirst(), next() 介面, 新增刪除「邊」的介面, 存檔, 拷貝建構元, 以及設定運算子的功能, 請參考下面的註解設計

void Graph::unitTest() {
    cout << "Unit testing... " << endl;
    srand(time(0));
    {
        cout << "   [ctor, copy ctor, equal] started" << endl;

// 請測試Graph由檔案串流輸入的建構元
// 請測試Graph的拷貝建構元, 並且以assert及equal驗證拷貝的結果是正確的
// 請再一次測試Graph的拷貝建構元, 但是請運用new來產生新的Graph物件

        cout << "   [ctor, copy ctor, equal] tested" << endl;

        cout << "   [addEdge,deleteEdge] started" << endl;

//  data.txt 中的資料是 (0,1,5)->(0,3,3)->(0,4,3)->(0,5,2)
// 下面請用 addEdge(), deleteEdge(), equal(), assert() 來驗證在
// 串列最前面, 串列中間, 以及串列最尾巴新增一個邊都不會出錯
// 你也可以運用 deleteEdge() 回傳的 bool 值驗證某一條邊, 例如 (0,1,1)
// 並不存在

// 請考量 (0,1,1)

// 請考量 (0,2,1)

// 請考量 (0,6,7)

// 因為邊在串列中的順序是依照節點大小以及權重大小來排列的
// 請藉由 addEdge() 的先後順序來測試程式新增邊的時候是否有按照順序

        cout << "   [addEdge,deleteEdge] tested" << endl;

// 請測試輸出 Graph 物件到檔案串流, 再重新讀回來, 
// 與先前的 Graph 物件比對來驗證, 另外請直接驗證其中某些邊是否存在

        cout << "   [print(ostream&)] tested" << endl;

// 請測試 Graph 的設定運算子, 除了能夠完整的拷貝一個物件, 
// 想辦法確定有沒有 dangling pointer

        cout << "   [assignment] tested" << endl;

// 為了配合 Vertex 結構以及 Graph 物件的記憶體配置與釋放測試,
// 請新增一個全域的變數 gVertexCount 來紀錄配置了多少個 Vertex 結構, 請修改
//  Vertex 所有的建構元函式來遞增 gVertexCount, 請額外實作拷貝建構元函式來遞增 
// gVertexCount (因為下面的測試沒有用到 Vertex::operator==(), 所以沒有實作這個函式), 
// 請修改解構元函式來遞減 gVertexCount, 請運用 assert 來確保完整掌握記憶體的使用
// 你可以撰寫迴圈隨機配置/釋放大量的 Vertex 結構, 隨時掌握 Vertex 物件的數量
// 最後也應該要確保所有的 Vertex 結構(包含靜態配置和動態配置的)都釋放掉了

    }
    ...
    cout << "   [dtor] tested" << endl;

    cout << "Unit test completed" << endl;
}

考試時間: 160分鐘 (09:20 ~ 12:00 上傳時間截止)

後續:

前半學期最主要練習的是在 Bottom-up 程式設計中最基礎、也最重要的 類別封裝, 也許你心裡不斷地懷疑著: 不是說基礎嗎? 為什麼這麼複雜? 基礎和簡單不太一樣, 不要小看基礎, 萬丈高樓平地起, 就在這個基礎打下去的時候, 就已經預測得到它最後的高度了, 隨隨便便的基礎其實也就是常常需要打掉重練的原因, 沒有堅實的基礎, 真的不要去碰觸穩定的商用程式, 不要說製作, 連改都盡量不要去改它, 會出事的, 像是自己會走的機器人、自駕車、無人機、飛機上的自動駕駛、衛星上的控制系統、武器系統、...至於手機程式嘛...當掉重開就算了。也許你急著看到絢麗的界面, 想說都什麼時代了, 應該兩三行 code 就可以得到所有想要的功能, 應該都有現成的模組組合一下就好了, 如果真的是這樣, 你可以, 別人也可以, 大家都可以, 應該機器自己也可以吧, 咦!! 那你為什麼要來資訊系那麼辛苦做什麼?

接下去最直接的你可以運用這個類別寫一些圖的演算法, 例如 Prim 最小生成樹, Dijkstra 最短路徑等等, 此外需要練習的是越來越多物件之間的合作。