// 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.