0001 #include "Graph_test.h"
0002 
0003 template <typename Tv, typename Te> //生成由v个顶点、e条边构成的随机图
0004 void randomGraph(GraphMatrix<Tv, Te>& g, Rank n, Rank e) { //assert: 0 < e(e-1) <= v
0005    while ((g.n < n) || (g.e < e)) { //随机测试
0006       if (g.n < n) { //顶点
0007          if (dice((Rank) 100) < 65) { //65%概率插入顶点
0008             Tv vertex = (Tv) ('A' + dice((Rank) 26));
0009             g.insert(vertex);
0010          } else { //35%概率删除顶点
0011             if (1 > g.n) continue;
0012             int v = dice(g.n);
0013             Tv x = g.remove(v);
0014          }
0015       }
0016       if ((1 < g.n) && (g.e < e)) { //边
0017          if (dice((Rank) 100) < 65) { //65%概率插入边
0018             int v = dice(g.n), j = dice(g.n); Te e = dice(n*3);
0019             if (g.exists(v, j)) {
0020             } else {
0021                g.insert(e, e, v, j);
0022             }
0023          } else { //35%概率删除边
0024             int v = dice(g.n), j = dice(g.n);
0025             if (g.exists(v, j)) {
0026                Te e = g.remove(v, j);
0027             } else {
0028             }
0029          }
0030       }
0031    }
0032    for (Rank v = 0; v < n; v++) g.vertex(v) = 'A' + (Tv) v;
0033 }
0034 
0035 void importGraph(GraphMatrix<char, int>& g) { //从命令行（文件重定向）中导入图
0036    int n; scanf("%d\n", &n);
0037    for (int v = 0; v < n; v++) { //插入n个顶点
0038       char vertex; scanf("%c", &vertex);
0039       g.insert(vertex);
0040    }
0041    for (int v = 0; v < n; v++)
0042       for (int j = 0; j < n; j++) { //插入边
0043          int edge; scanf("%d", &edge);
0044          if (!edge) continue;
0045          g.insert(edge, edge, v, j);
0046       }
0047 }
0048 
0049 int main(int argc, char* argv[]) { //图结构的统一测试
0050    if (2 > argc) { printf("Usage: %s -random <n> <e> | -import <n> <e> < <path>\a\a\n", argv[0]); return -1; }
0051    //-import < ..\..\_input\graph.prim.0009+0028.txt  ..\..\_output\Graph_Matrix\graph.prim.0009+0028.txt
0052    //-random 67 543 > ..\..\_output\Graph_Matrix\graph.random.0067+0543.txt
0053    srand(31415926); //srand((uint32_t) time(nullptr)); //随机种子
0054    GraphMatrix<char, int> g;
0055    if (!strcmp("-random", argv[1]))
0056       randomGraph<char, int>(g, atoi(argv[2]), atoi(argv[3])); //顶点以字符编号，边为整数权重
0057    else if (!strcmp("-import", argv[1]))
0058       importGraph(g); //从命令行（文件重定向）中导入图
0059    else return -1;
0060    g.bfs(0);
0061    g.pfs(0, BfsPU<char, int>());
0062    g.dfs(0);
0063    g.pfs(0, DfsPU<char, int>());
0064    Stack<char> ts = g.tSort(0);
0065    g.bcc(0);
0066    g.prim(0);
0067    g.pfs(0, PrimPU<char, int>());
0068    g.dijk(0);
0069    g.pfs(0, DijkPU<char, int>());
0070    return 0;
0071 }