文件列表:

results\Res_C1\res.cimi.g1.txt (1171, 2003-01-07)
results\Res_C1\res.cimi.g2.txt (1210, 2003-01-08)
results\Res_C1\res.cimi.g3.txt (1183, 2003-01-07)
results\Res_C1\res.cimi.g4.txt (1180, 2003-01-07)
results\Res_C1\res.cimi.g5.txt (1182, 2003-01-07)
results\Res_C1\res.cimi.g6.txt (1192, 2003-01-07)
results\traces\res.g.18.txt (307, 2003-01-16)
results\Res_GT\res.g1.txt (1179, 2003-01-07)
results\Res_GT\res.g10.txt (1193, 2003-01-07)
results\Res_GT\res.g11.txt (1195, 2003-01-07)
results\Res_GT\res.g12.txt (1221, 2003-01-07)
results\Res_GT\res.g13.txt (733, 2003-01-08)
results\Res_GT\res.g14.txt (734, 2003-01-07)
results\Res_GT\res.g15.txt (733, 2003-01-07)
results\Res_GT\res.g16.txt (734, 2003-01-07)
results\Res_GT\res.g17.txt (733, 2003-01-05)
results\Res_GT\res.g18.txt (734, 2003-01-05)
results\Res_GT\res.g19.txt (734, 2003-01-07)
results\Res_GT\res.g2.txt (1184, 2003-01-08)
results\Res_GT\res.g3.txt (66, 2003-01-07)
results\Res_GT\res.g4.txt (1160, 2003-01-07)
results\Res_GT\res.g5.txt (1170, 2003-01-07)
results\Res_GT\res.g6.txt (1173, 2003-01-07)
results\Res_GT\res.g7.txt (1172, 2003-01-07)
results\Res_GT\res.g8.txt (66, 2003-01-07)
results\Res_GT\res.g9.txt (1163, 2003-01-07)
results\Res_C1\res.rg.100.1.txt (1249, 2003-01-06)
results\Res_C1\res.rg.100.2.txt (1248, 2003-01-04)
results\Res_C1\res.rg.100.3.txt (1244, 2003-01-04)
results\Res_C1\res.rg.100.4.txt (1243, 2003-01-06)
results\traces\res.rg.100.5.txt (314, 2003-01-16)
results\Res_C1\res.rg.100.5.txt (1249, 2003-01-06)
results\Res_C1\res.rg.150.1.txt (738, 2003-01-08)
results\Res_C1\res.rg.150.2.txt (737, 2003-01-08)
results\Res_C1\res.rg.150.3.txt (738, 2003-01-08)
results\Res_C1\res.rg.150.4.txt (738, 2003-01-09)
results\Res_C1\res.rg.150.5.txt (739, 2003-01-09)
results\Res_C1\res.rg.200.1.txt (739, 2003-01-05)
... ...

// The SA algorithm for maximum planar subgraph problem, 2003 // University of Tampere, Finland // Department of Computer and Information Sciences // Corresponding author: Timo Poranen, tp@cs.uta.fi This simulated annealing algorithm (SA) is based on the manuscript "A simple randomized algorithm for determining maximum planar subgraphs" Author: Timo Poranen, e-mail: tp@cs.uta.fi WWW-page of this work: http://www.cs.uta.fi/~tp/max_planar/ ************* You may use these source codes freely for research and testing purposes. If you test different parameters for the cooling process and find out that they are better than the parameters used in our tests, please inform the author by email! ************ ---------------------------------- A graph is \textsl{planar} if it admits a plane drawing where no two distinct edges intersect, otherwise the graph is \textsl{non-planar}. Let $G=(V,E)$ be a graph without loops and parallel edges. If a graph $G'=(V,E')$ is a planar subgraph of $G$ such that every graph $G''$ obtained from $G'$ by adding an edge from $E \setminus E'$ is non-planar, then $G'$ is called a \textsl{maximal planar subgraph} of $G$. Let $G'=(V,E')$ be a maximal planar subgraph of $G$. If there is no planar subgraph $G''=(V,E'')$ of $G$ with $\mid E'' \mid > \mid E' \mid$, then $G'$ is a \textsl{maximum planar subgraph}. A maximal planar subgraph is maximal in the sense of that adding edges is not possible and the maximum planar subgraph is maximal with respect to the cardinality of its edge set. This readme file contains information for the simulated annealing algorithm for maximum planar subgraph problem FILES and COMPILATION ---------------------------------- After unpacking the original mpsa.tar.gz file, you should have following files and directories: README.txt this file Makefile makefile for compilation max_planar.cpp main file & main loop sa_graph.h sa_graph's header file sa_graph.cpp initialization etc. sa_alg.cpp simulated annealing algorithm graphs/data directory for graphs used in our experimental tests. You can download graphs from their original location: http://www.research.att.com/~mgcr/data/index.html results/ result files from our test runs result/traces sample trace files The implementation of the SA algorithm is originally written in C++ programming language for computer running under Linux Mandrake $8.1$. It uses LEDA 4.3 (commercial version) for planarity test. Check that your $LEDAROOT is set correctly (See LEDA's manual) if you have problems in compliations You can compile it with the GCC compiler just typing make After compilation you should have the following new files a.out //executable file max_planar.o sa_alg.o sa_graph.o BUGS ------------------------ If you find any bugs, please let the author know. USAGE ---------------------------------- Download first test graphs from http://www.research.att.com/~mgcr/data/index.html To see how SA works, try: ./a.out 1 res.txt -e -sa -f graphs/data/g1.dat * Now SA algorithm reads graph g1.dat from directorey graphs/data/ and performs one execution of SA algorithm using empty set initialization. Results are saved to file "res.txt". SA algorithm's parameters are read from file "sa_parameters.txt" (build in property of SA). Or, if you are not able to download test graphs, you may try to create a random graph with 30 vertices and 100 edges: ./a.out 1 res.txt -e -sa -r 30 100 * Now SA creates a random graph with 30 vertices and 100 edges. Result is written to file "res.txt". Graph is not saved. If you write ./a.out without parameters or with incorrect parameters, you get instructions: --------- Usage: a.out REPEATS RESULT_FILE INI_SOL ALGORITHM_TYPE GRAPH_SOURCE_TYPE [PARAMETERS] REPEATS number of repeats of the algorithm RESULT_FILE file where results are written -e empty set initialization -sa simulated annealing algorithm -f FILENAME graph is read from file. File in edge-list format -fgml FILENAME graph is read from file. File in gml format -r V E [TARGET] random graph with V vertices and E edges graph is saved to filename TARGET in gml-format -t trace.txt a trace file trace.txt is written Examples: ./a.out 20 results/res.txt -e -sa -f graphs/data/g5.dat ./a.out 1 res.txt -e -sa -f graphs/data/g1.dat ./a.out 1 res.txt -e -sa -r 80 350 graphs/data/mygraph.gml ./a.out 1 results/res.txt -e -sa -f graphs/data/g19.dat -t results/trace.txt Notice that the order of parameters matters! -------- The REPEATS is the number of separate runs, RESULT_FILE is file where results and other information is stored. INI_SOL is the method of initialization (only emplyset initialization , "-e", implemented) ALGORITHM_TYPE is the algorithm for optimizing initial solution. Only simulated annealing algorithm (-sa) is now implemented. GRAPH_SOURCE: For random graphs, use -r V E to construct a random graph with V vertices and E edges. Random graph is saved to file if a target file is gives. You can also read graph from file (in gml format) with parameter -f FILENAME of -fgml FILENAME (for graphs in gml-format,. Note that if given RESULT_FILE already exists, it will be overwritten. PARAMETER FILE ---------------------------------- Parameter file contains different parameters for SA algorithm. You can change the initial and frozen temperatures, cooling ratio and equilibrium detection rate. Also the type of initial solution can be changed. Here is the example parameter file "sa_parameters.txt" ----------------------- t0 0.3 t1 0.2 alpha 0.999 innerloop 5 ---------------------- Inner loop sizes: // innerloop 0 - vertices // 1 - 2*vertices // 2 - vertices*vertices // 3 - vertices*vertices*0.5 // 4 - edges/2 // 5 - edges // 6 - 2*edges In our experimental test we used the parameters above. Probably there exists better parameters for different classes of graphs. Do not change parameters between multiple runs (when the number of runs is given as a command line parameter). Parameters are always read from file between distinct runs! STOPPING CRITERION ------------------------------------------- When temperature is <=t1, algorithm ends. If the size of planar subgraph is equal to the Euler lower bound, algorithm terminates. TODO & POSSIBLE IMPROVEMENTS & FUTURE PLANS ------------------------------------------- * Dynamic planarity test implementation will make the algorithm run faster (planarity test: O(n), dynamic planarity test: (amortized) log(n)). * It is possible that using bettter initial solution than "empty set" better approximations can be achieved * If you dont like printings during the execution of SA, comment them from the source code and compile the program again.

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：