*****************************************************************************
*                    PROGRAM: COORD                                         *
*                                                                           *
*                    Author:  Andrej Mrvar                                  *
*                             Faculty of Social Sciences                    *
*                             University of Ljubljana                       *
*                             E-mail: andrej.mrvar@uni-lj.si                *
*                             july 1994 - januar 1995                       * 
*****************************************************************************

   Program automatically finds suitable locations for vertices of given graph,
   so that there are as little as possible crossings of edges. 
   First, greedy algorithm is used (adding vertices sequentially on possible
   positions so that as little as possible crossings are produced),
   second, this solution is optimized (if we wish) - using interchanges
   of vertices and movings of vertices to other, free positions.
   
   Input to program: 

   1. File with network definition (format is explained in instructions 
      for using program DRAW).
     
   2. File with permutation of vertices that specifies order in which 
      vertices will be selected. 
      RC program can be used to get a suitable permutation.
        For example core or degree partition of given network 
        (mirror of this permutation must be made to get the most important 
        vertices in the top). It is clever to put the vertices with 
        the highest degree in the middle of the picture, others around.
      Identity or random permutation can also be generated.
      Dimension of matrix and dimension of permutation must be the same!
     
   3. File with possible positions (ASCII file produced by program itself).
      Program uses only feasible positions that are specified.
      Two diferrent shapes of positions can be generated:
      NET - rectangular net of points x by y 
            (number of points in x and in y direction must be specified)
      CONCENTRIC CIRCLES - with given distance (arc) between vertices on same 
                           circle (dimension of space is 10000*10000).
      Select positions that are the most suitable for given network.
      Program is also able to read given positions from network file.
      (positions for vertices computed already before)

  4. File with permutation of positions.
     Sometimes is better to use positions in some other order
     instead from first to the last in order in which points were generated.
     Example : If net is selected - it is usually better to select points in
               random order than first use points from first, then 
               points from second row...
     RC program can be used again to get suitable permutation,
     random permutation can also be generated.
     The dimension of this permutation can be smaller (or equal) than 
     number of vertices in positions file. If dimension is smaller
     not specified points will be filled as identity permutation.
    
  5. File with fixed vertices' list. First vertex specified will be
     placed to the first (permuted) location, second to the second position
     and so on. These vertices will not be moved during optimisation -
     they will stay on these places.

  6. - if NO CONTROL is selected, vertices are put on positions                    
       without checking crossings of links (the fastest method).
     - if CONTROL is selected, number of positions that will be checked 
       when new vertex is added must be specified (the higher is the number 
       the better solution is obtained but it takes also more time...)
       If CONTROL is selected, local optimisation can be used after the 
       greedy algorithm is completed.
  
   7. At last ASCII file [.NET] must be specified where the result 
      (graph definition with coordinates of vertices) will be written.

    Result of algorithm (picture) can be seen with program DRAW.