[Data Structure] 支援任意型態的 Graph 實作

在我之前的文章裡，提到 Graph 可用 Adjacency Matrix 或 Adjacency Lists 表示。
在這裡要討論的，是採用 C++ 物件導向建立 Graph 類別，讓此 Graph 內的 Node 支援任意型態的物件，並讓此 Graph 物件可當作有向或無向圖，且 Edge 可以分配權重，或設為無權重，也可將 Edge 用任意物件表示。

在此採用動態陣列儲存 Node 的資訊。不採用靜態的陣列來描述 Graph 有什麼優點呢？由於靜態陣列的大小是事先預定的，通常我們無法確切知道要處理的資料量到底有多大，因此為 Graph 採用動態新增 Node 的方式，是比較實際的作法。Graph 的 Class 實作方法很多，我通常將 Adjacency Lists 改為用動態指標陣列維護，並新增 function 來操作它們。

我習慣 Template 的編寫方式，讓 Graph 可以支援各種型態的資料：

template <
   typename T,
   typename Edge = double
   >
class MyGraph
{
   // ...
};

T 用來表示要存到 Node 裡的物件類別，使用此 Graph 時，任意型態 T 都可當作此 Graph 的中的 Node。Edge 的預設型態是 double，代表預設 Graph 的每條邊用浮點數來設定權重，當然，也可用其他型態來當作 Edge，這是 Template 的好處。

Graph 的物件實作很簡單。在 Class 內定義以下 private 成員，就完成基本的 Graph 架構：

list<T*> node_list;
vector<vector<unsigned long> > neighbor_vec;
vector<vector<E*> > edge_vec;

node_list 內存著指標，每個指標指向 Graph 內每個 Node。
用 list 儲存 Node，而不用 vector 的原因，在於用迴圈走訪 Graph 中的 Node 時，如果經常一邊走訪一邊刪除 Node，此時 list 的 remove 函式較方便：

int node_index = 0;
for(list<T*>::iterator it = node_list.begin(); it != node_list.end(); it++)
{
      if(some_condition)  delete *it;
      *it = NULL;
      node_index++;
}
node_list.remove((T*)NULL);

而 neighbor_vec 存著每個 Node 相鄰的其他 Node 的 index。
假如第 0 個 Node（簡稱 Node_0）有 3 個鄰居，則這 3 個鄰居的 index 即存在 neighbor_vec[0][0]、neighbor_vec[0][1] 跟 neighbor_vec[0][2] 內。
於是第 m 個 Node 的第 n 個鄰居的 index 為 neighbor_vec[m][n]。

而 edge_vec 存有每個 Node 關聯到的 Edge 指標，假如 Node_0 關聯到兩條 Edge，則 edge_vec[0][0] 和 edge_vec[0][1] 內就會儲存指向這兩個 Edge 的指標。
如上述程式碼所表示的，我們可以用 iterator 走訪 Graph。我們也可以輕易透過 index 的對應關係，來刪除 Node 並回收沒被用到的記憶體空間。

完整的 Graph 通常俱備以下功能：

1. 測試是否沒有任何 Node，即 Graph 是否為空。
2. 回傳 Node 數目。
3. 回傳 Edge 數目。
4. 清空 Graph。
5. 查詢某 Edge 是否存在。
6. 加入 Node。
7. 加入 Edge。
8. 刪除 Node。
9. 刪除 Edge。
10. 訪問特定的 Node。
11. 訪問特定 Node 的鄰居。

加入這些功能的成員函式之後，就完成一個容易使用的 Graph 物件實作。

Reference
Horowitz, E., Sahni, S., & Mehta D. (Eds.). (2006). Fundamental Of Data Structures in C++ (2nd ed.). New Jersey USA: Silicon Press.