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, int n, int 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 i = dice ( g.n ); 0019 Tv v = g.remove ( i ); 0020 } 0021 } 0022 if ( ( 1 < g.n ) && ( g.e < e ) ) { //边 0023 if ( dice ( 100 ) < 65 ) { //65%概率插入边 0024 int i = dice ( g.n ), j = dice ( g.n ); Te e = dice ( ( Te ) 3 * n ); 0025 if ( g.exists ( i, j ) ) { 0026 } else { 0027 g.insert ( e, e, i, j ); 0028 } 0029 } else { //35%概率删除边 0030 int i = dice ( g.n ), j = dice ( g.n ); 0031 if ( g.exists ( i, j ) ) { 0032 Te e = g.remove ( i, j ); 0033 } else { 0034 } 0035 } 0036 } 0037 } 0038 for ( int i = 0; i < n; i++ ) g.vertex ( i ) = 'A' + i; 0039 } 0040 0041 /****************************************************************************************** 0042 * 从命令行(文件重定向)中导入图 0043 ******************************************************************************************/ 0044 void importGraph ( GraphMatrix<char, int> & g ) { 0045 int n; scanf ( "%d\n", &n ); 0046 for ( int i = 0; i < n; i++ ) { //插入v个顶点 0047 char vertex; scanf ( "%c", &vertex ); 0048 g.insert ( vertex ); 0049 } 0050 for ( int i = 0; i < n; i++ ) 0051 for ( int j = 0; j < n; j++ ) { //插入边 0052 int edge; scanf ( "%d", &edge ); 0053 if ( 0 > edge ) continue; 0054 g.insert ( edge, edge, i, 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 13 29 > ..\..\_output\Graph_Matrix\graph.random.0013+0029.001.txt 0065 // -random 57 219 > ..\..\_output\Graph_Matrix\graph.random.0057+0219.001.txt 0066 srand ( ( unsigned int ) time ( NULL ) ); 0067 //srand( 7654321 ); 0068 GraphMatrix<char, int> g; 0069 if ( !strcmp ( "-random", argv[1] ) ) 0070 randomGraph<char, int> ( g, atoi ( argv[2] ), atoi ( argv[3] ) ); //顶点以字符编号,边为整数权重 0071 else if ( !strcmp ( "-import", argv[1] ) ) 0072 importGraph ( g ); //从命令行(文件重定向)中导入图 0073 else return -1; 0074 g.bfs ( 0 ); 0075 g.pfs ( 0, BfsPU<char, int>() ); 0076 g.dfs ( 0 ); 0077 g.pfs ( 0, DfsPU<char, int>() ); 0078 Stack<char>* ts = g.tSort ( 0 ); 0079 g.bcc ( 0 ); 0080 g.prim ( 0 ); 0081 g.pfs ( 0, PrimPU<char, int>() ); 0082 g.dijkstra ( 0 ); 0083 g.pfs ( 0, DijkstraPU<char, int>() ); 0084 return 0; 0085 }