INSTALL

*******************************************************************************
*                                                                             *
*                         MINIMUM CYCLE BASIS                                 *
*                                                                             *
*                          UNIX INSTALLATION                                  *
*                                                                             *
*******************************************************************************


In this file I use <LEP> to denote the path name where you have
extracted the LEP packet. Default is the directory <LEDA>/LEPS right
below the LEDA main directory. If you have extracted the MCB
package in that directory the directory <LEP>/mcb (here I use the name 
mcb for the directory, but it might be something like mcb-0.1 based on 
the version of the package) should contain the following files and 
subdirectories:

README                    information about the LEP
INSTALL                   this file
FIXES                     bug fixes since last release
Makefile                  make script
make.config               make configuration settings
configure                 configuration command
doc/                      user manual
incl/                     include directory
src/                      source files
test/ 		          test programs
demo/                     demo programs
confdir/		  build system


1. CONFIGURATION
----------------

   a)  Go to the directory <LEP>/mcb

   b)  Type: configure

       where <cc> is the name (or command) of your C++ compiler
       and the optional second parameter defines the path where
       the needed LEDA package is installed 

       
   c)  For deviations from the default retype configure with
       additional information:
       
       Example: CXX=g++ LEDAROOT=/Somepath/LEDA/ configure

       The configure script, accepts a number of additional parameters

       --disable-checking     Disable the check of any preconditions and invariants
                              This is dangerous for general code, use it only for 
			      doing measurements of running times.
       --enable-debug-output  Enable the debugging output of the algorithms.
       --enable-stats-output  Enable the statistic output of the algorithms.

       Use ./configure --help to see all available options.

   d)  In case configure fails, try changing to <LEP>/mcb/confdir and 
       running make. Then go back to <LEP>/mcb and retry the configure script.

1.1 NOTE FOR LEDA VERSION 5.0 OR LATER
--------------------------------------
Starting from version 5.0, LEDA has a different include structure, which might 
prevent the LEP from beeing compiled.

The configure script on unix platforms compiles the code with the flag
LEDA_GE_V5 in case LEDA-5.0 or newer is detected.

For older code there is another alternative, to set HEADER_COMPAT to yes
when calling configure.
Execute configure as:

LEDAROOT=/path/to/LEDA/5.0 <other options> HEADER_COMPAT=yes configure

and the old style include structure will be compiled as well.

2. COMPILING
-------------

   Now just type "make"


3. INSTALLATION 
----------------

a) Header Files
  
   All LEDA header files are contained in "<LEDA>/incl/LEDA".
   All LEP header files are contained in "<LEP>/mcb/incl"

   You can also copy the include files into one of the global
   include directories, e.g.:

   AT&T CC:  cp -r <LEP>/mcb/incl /usr/include/CC

   GNU g++:  cp -r <LEP>/mcb/incl /usr/local/lib/g++-include     

   Or you can use the -I flag of the compiler as described below:

   CC (g++) -I<LEDA>/incl -I<LEP>/mcb/incl \
            -L<LEDA> ...

   If you have access to the LEDA installation tree and you extracted
   the LEP mcb inside the directory <LEDA>/LEPS you can copy
   the header files to the default include path 

   <LEDA>/incl/LEP/mcb

   by the command

	make lepintegrate

   After this you can compile programs which use LEDA and the LEP
   by the simpler command:

   CC (g++) -I<LEDA>/incl -L<LEDA> ...


4. Template Makefile
--------------------

After compiling the LEP you can find in LEP/mcb/doc/makefiles a template
makefile for compiling programs using the same flags. 

Simply copy the makefile to the directory containing your source. 
You must then open the makefile and change two things: a) the variable
PROGS must contain the names of the programs that you want to build, 
b) the makefile has to include the file make.config located in the 
root directory of the LEP.

Details are also contained inside the makefile.


5. DOCUMENTATION
----------------

   You can grab the documentation from the www server where you obtained 
   this package.


*******************************************************************************
*                                                                             *
*                          Minimum Cycle Basis                                *
*                                                                             *
*                          WINDOWS INSTALLATION                               *
*                                                                             *
*******************************************************************************


6. WINDOWS - BORLAND C++ BCC32 (STATIC)
---------------------------------------

The LEP can be compiled for use with the LEDA and Borland bcc32
compiler. LEDA must be compiled as static.

a) install LEDA with static variables, set LEDAROOT=path to leda
   The LEDAROOT directory should contains some or all of these files

	libL.lib      basic library
  	libG.lib      graph library
  	libP.lib      d2-geo library
  	libD3.lib     d3-geo library
  	libGeoW.lib   GeoWin library
  	libW.lib      window library

b) Setting the Environment Variables for Borland C++:

    * Make sure that the directory of bcc32.exe is contained in your path. bcc32.exe is 
	  located in the \bin directory of your compiler, 
	  e.g., in c:\borland\bcc55\bin
    * Make sure that there is a file bcc32.cfg in the \bin directory of your compiler 
	  which sets the compiler options for the include and lib paths to the correct 
	  directories. On the author's machine this means adding the lines
      -I"c:\borland\bcc55\include"
      -L"c:\borland\bcc55\lib"
      to bcc32.cfg.
    * Make sure that there is a file ilink32.cfg in the \bin directory of your compiler which 
	  sets the linker options for the lib path to the correct directory. On the author's 
	  machine this means adding the line
      -L"c:\borland\bcc55\lib" -L"c:\borland\bcc55\lib\PSDK"
      to ilink32.cfg.

c) Go to the <LEP>/mcb directory and execute make_bcc_static.bat
   To clean the sources run 
   
   make allclean

   or simply

   make clean

d) To compile your program use something like

   bcc32 -P -I<LEP>/mcb/incl -I%LEDAROOT%/incl \
            -L<LEP>/mcb -L%LEDAROOT% \
			libg.lib libl.lib libmcb.lib yoursource.c ...

7. WINDOWS - BORLAND C++ BCC32 (DYNAMIC)
----------------------------------------

The LEP can be compiled for use with the LEDA and Borland bcc32
compiler. LEDA must be as dynamic library (dll).

a) install LEDA and set LEDAROOT=path to leda
   The LEDAROOT directory should contain the following files

	leda.dll
	leda.lib
	libGeoW.lib

   Add to the PATH variable the LEDAROOT path, so that the leda.dll can 
   be found, or copy leda.dll to some other appropriate path.

b) Setting the Environment Variables for Borland C++:

    * Make sure that the directory of bcc32.exe is contained in your path. bcc32.exe is 
	  located in the \bin directory of your compiler, 
	  e.g., in c:\borland\bcc55\bin
    * Make sure that there is a file bcc32.cfg in the \bin directory of your compiler 
	  which sets the compiler options for the include and lib paths to the correct 
	  directories. On the author's machine this means adding the lines
      -I"c:\borland\bcc55\include"
      -L"c:\borland\bcc55\lib"
      to bcc32.cfg.
    * Make sure that there is a file ilink32.cfg in the \bin directory of your compiler which 
	  sets the linker options for the lib path to the correct directory. On the author's 
	  machine this means adding the line
      -L"c:\borland\bcc55\lib" -L"c:\borland\bcc55\lib\PSDK"
      to ilink32.cfg.

c) Go to the <LEP>/mcb directory and execute make_bcc_dll.bat
   To clean the sources run 
   
   make allclean

   or simply

   make clean

d) To compile your program use something like

   bcc32 -P -DLEDA_DLL -I<LEP>/mcb/incl -I%LEDAROOT%/incl \
         -L<LEP>/mcb -L%LEDAROOT% \
	  leda.lib libmcb.lib yoursource.c

8. WINDOWS - MICROSOFT VISUAL STUDIO .NET (STATIC)
--------------------------------------------------

The LEP can be compiled for use with the LEDA and Microsoft Visual
Studio .NET. LEDA must be compiled as static.

a) install LEDA with static variables, set LEDAROOT=path to leda
   The LEDAROOT directory should contains at least one of the following
   library sets:

   - libl_ml.lib, libg_ml.lib, libp_ml.lib, libw_ml.lib, libgeow_ml.lib, libd3_ml.lib
   - libl_mld.lib, libg_mld.lib, libp_mld.lib, libw_mld.lib, libgeow_mld.lib, libd3_mld.lib
   - libl_md.lib, libg_md.lib, libp_md.lib, libw_md.lib, libgeow_md.lib, libd3_md.lib
   - libl_mdd.lib, libg_mdd.lib, libp_mdd.lib, libw_mdd.lib, libgeow_mdd.lib, libd3_mdd.lib
   - libl_mt.lib, libg_mt.lib, libp_mt.lib, libw_mt.lib, libgeow_mt.lib, libd3_mt.lib
   - libl_mtd.lib, libg_mtd.lib, libp_mtd.lib, libw_mtd.lib, libgeow_mtd.lib, libd3_mtd.lib
   
b) Setting the Environment Variables for Visual Studio .NET:

    * The compiler cl.exe and the linker link.exe require that the environment variables
      PATH, INCLUDE, and LIB have been set properly.

      When Visual C++ was installed, setup created a batch file, VSVARS32.BAT, containing 
      commands to modify PATH, LIB, and INCLUDE. Run VSVARS32.BAT at the command prompt before 
      you compile your application program. VSVARS32.BAT is located in the \bin subdirectory 
      of your compiler installation, 
      e.g., c: \programs \microsoft visual studio .NET\Vc7 \bin.

      To compile programs together with LEDA, the environment variables PATH, LIB, and 
      INCLUDE must additionally contain the corresponding LEDA directories.

c) Go to the <LEP>/mcb directory and execute make_msc_static.bat. This script accepts
   two arguments. The first argument is one of the following:

   ml, mld, md, mdd, mt, mtd, default.

   This option corresponds to the appropriate choice that was made when LEDA
   was build. The option default means to use the compiler's default choice.

   The second option has again the same values. It is used in order to force the 
   build scripts to assume that leda's libraries are named like libg_xx.lib.

   Examples: 
   ---------

   make_msc_static ml		: Assume LEDA was compiled with ml option and libraries are 
   				  named like libl_ml.lib, etc.
   make_msc_static mt default	: Assume LEDA was compiled with mt option and libraries are
   				  named like libl.lib, etc.
   make_msc_static mdd xx	: Assume LEDA was compiled with mdd option and libraries are
   				  named like libl_xx.lib, etc.

   To compile something in the demo directory, change there and use nmake.

   To clean the sources run 
   
   nmake allclean

   or simply

   nmake clean

d) To compile your program use something like

   cl <option> -nologo -EHsc -TP -I<LEP>/mcb/incl -I%LEDAROOT%/incl \
      libg_xx.lib libl_xx.lib ... libmcb.lib yoursource.c

   Possible values for <option> are "-ML", "-MLd", "-MD", "-MDd", "-MT" and "-MTd".
   You have to use the LEDA libraries that correspond to the chosen <option>, e.g., with
   option "-MD" you must use libl_md, libg_md, etc. Using another set of libraries with 
   "-MD" could lead to serious linker errors.

   The option -TP is necessary if the C++ source code files have extension .c. If your 
   files have extension .cpp  this option is not necessary.

9. WINDOWS - MICROSOFT VISUAL .NET 2003 (DYNAMIC)
-------------------------------------------------

The LEP can be compiled for use with the LEDA and Microsoft Visual Studio .NET. 
LEDA must be compiled as dynamic.

a) install LEDA, set LEDAROOT=path to leda
   The LEDAROOT directory should contains at least one of the following
   library sets:

   - leda_ml.dll, leda_ml.lib, libGeoW_ml.lib
   - leda_mld.dll, leda_mld.lib, libGeoW_mld.lib
   - leda_md.dll, leda_md.lib, libGeoW_md.lib
   - leda_mdd.dll, leda_mdd.lib, libGeoW_mdd.lib
   - leda_mt.dll, leda_mt.lib, libGeoW_mt.lib
   - leda_mtd.dll, leda_mtd.lib, libGeoW_mtd.lib
   
b) Setting the Environment Variables for Visual Studio .NET:

    * The compiler cl.exe and the linker link.exe require that the environment variables
      PATH, INCLUDE, and LIB have been set properly.

      When Visual C++ was installed, setup created a batch file, VSVARS32.BAT, containing 
      commands to modify PATH, LIB, and INCLUDE. Run VSVARS32.BAT at the command prompt before 
      you compile your application program. VSVARS32.BAT is located in the \bin subdirectory 
      of your compiler installation, 
      e.g., c: \programs \microsoft visual studio .NET\Vc7 \bin.

      To compile programs together with LEDA, the environment variables PATH, LIB, and 
      INCLUDE must additionally contain the corresponding LEDA directories.

c) Go to the <LEP>/mcb directory and execute make_msc_dll.bat. This script accepts
   two arguments. The first argument is one of the following:

   ml, mld, md, mdd, mt, mtd, default.

   This option corresponds to the appropriate choice that was made when LEDA
   was build. The option default means to use the compiler's default choice.

   The second option has again the same values. It is used in order to force the 
   build scripts to assume that leda's libraries are named like leda_xx.lib.

   Examples: 
   ---------

   make_msc_dll ml		: Assume LEDA was compiled with ml option and libraries are 
   				  named like leda_ml.lib, leda_ml.dll, etc.
   make_msc_dll mt default	: Assume LEDA was compiled with mt option and libraries are
   				  named like leda.lib, leda.dll, etc.
   make_msc_dll mdd xx		: Assume LEDA was compiled with mdd option and libraries are
   				  named like leda_xx.lib, leda_xx.dll, etc.

   To compile something in the demo directory, change there and use nmake.

   To clean the sources run 
   
   nmake allclean

   or simply

   nmake clean

d) To compile your program use something like

   cl <option> -nologo -DLEDA_DLL -EHsc -TP -I<LEP>/mcb/incl -I%LEDAROOT%/incl \
      leda_xx.lib libmcb.lib yoursource.c

   Possible values for <option> are "-ML", "-MLd", "-MD", "-MDd", "-MT" and "-MTd".
   You have to use the LEDA libraries that correspond to the chosen <option>, e.g., with
   option "-MD" you must use leda_md.lib, etc. Using another set of libraries with 
   "-MD" could lead to serious linker errors.

   The option -TP is necessary if the C++ source code files have extension .c. If your 
   files have extension .cpp  this option is not necessary.

Note that in order for the system to find the leda_xx.dll file of LEDA, the leda_xx.dll 
must reside in a directory which is in the PATH environmental library.

10. Optimization Options and Configuration - IMPORTANT
------------------------------------------------------

10.1 GCC and LEDA
-----------------

If you are using GCC version 3.4 or newer in combination with LEDA 5.0.1 
or older do not use the code with the following optimization flags

-fschedule-insns
-fschedule-insns2

at the author's PC, the resulting code contains a memory leak.
This is due to incompatibility between GCC and LEDA's memory manager.

Note that the flags -O2 and -O3 use these optimization flags
and therefore the flags -fno-schedule-insns and -fno-schedule-insns2
must also be used. The configure script automatically enables these
if required.

Moreover, when using GCC 4.x and LEDA do not use strict aliasing, again
in the author's machine unpredictable results occur. The configure script
automatically enables the option -fno-strict-aliasing if this scenario is
detected.

10.2 Checking Disabled
----------------------

The configure script offers a flag 

--disable-checking

which compiles the LEP, with any internal check disabled
by adding the flag -DLEDA_CHECKING_OFF, the same flag
that LEDA uses to disable any preconditions' or invariants'
checking.

Note that no check is performed in such a case. 

10.3 Configuration Flags
------------------------

All configuration flags are contained in the header file config.h .