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 g.bcc ( 0 ); 0079 g.prim ( 0 ); 0080 g.pfs ( 0, PrimPU<char, int>() ); 0081 g.dijkstra ( 0 ); 0082 g.pfs ( 0, DijkPU<char, int>() ); 0083 return 0; 0084 }