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