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