/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* IGraph library. Copyright (C) 2007-2012 Gabor Csardi 334 Harvard street, Cambridge, MA 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include "config.h" #include "igraph_centrality.h" #include "igraph_components.h" #include "igraph_constants.h" #include "igraph_constructors.h" #include "igraph_datatype.h" #include "igraph_error.h" #include "igraph_glpk_support.h" #include "igraph_interface.h" #include "igraph_memory.h" #include "igraph_structural.h" #include "igraph_types.h" #include /* #define SUGIYAMA_DEBUG */ #ifdef _MSC_VER /* MSVC does not support variadic macros */ #include static void debug(const char* fmt, ...) { va_list args; va_start(args, fmt); #ifdef SUGIYAMA_DEBUG vfprintf(stderr, fmt, args); #endif va_end(args); } #else #ifdef SUGIYAMA_DEBUG #define debug(...) fprintf(stderr, __VA_ARGS__) #else #define debug(...) #endif #endif /* MSVC uses __forceinline instead of inline */ #ifdef _MSC_VER #define INLINE __forceinline #else #define INLINE inline #endif /* * Implementation of the Sugiyama layout algorithm as described in: * * [1] K. Sugiyama, S. Tagawa and M. Toda, "Methods for Visual Understanding of * Hierarchical Systems". IEEE Transactions on Systems, Man and Cybernetics * 11(2):109-125, 1981. * * The layering (if not given in advance) is calculated by ... TODO * * [2] TODO * * The X coordinates of nodes within a layer are calculated using the method of * Brandes & Köpf: * * [3] U. Brandes and B. Köpf, "Fast and Simple Horizontal Coordinate * Assignment". In: Lecture Notes in Computer Science 2265:31-44, 2002. * * Layer compaction is done according to: * * [4] N.S. Nikolov and A. Tarassov, "Graph layering by promotion of nodes". * Journal of Discrete Applied Mathematics, special issue: IV ALIO/EURO * workshop on applied combinatorial optimization, 154(5). * * The steps of the algorithm are as follows: * * 1. Cycle removal by finding an approximately minimal feedback arc set * and reversing the direction of edges in the set. Algorithms for * finding minimal feedback arc sets are as follows: * * - Find a cycle and find its minimum weight edge. Decrease the weight * of all the edges by w. Remove those edges whose weight became zero. * Repeat until there are no cycles. Re-introduce removed edges in * decreasing order of weights, ensuring that no cycles are created. * * - Order the vertices somehow and remove edges which point backwards * in the ordering. Eades et al proposed the following procedure: * * 1. Iteratively remove sinks and prepend them to a vertex sequence * s2. * * 2. Iteratively remove sources and append them to a vertex sequence * s1. * * 3. Choose a vertex u s.t. the difference between the number of * rightward arcs and the number of leftward arcs is the largest, * remove u and append it to s1. Goto step 1 if there are still * more vertices. * * 4. Concatenate s1 with s2. * * This algorithm is known to produce feedback arc sets at most the * size of m/2 - n/6, where m is the number of edges. Further * improvements are possible in step 3 which bring down the size of * the set to at most m/4 for cubic directed graphs, see Eades (1995). * * - For undirected graphs, find a maximum weight spanning tree and * remove all the edges not in the spanning tree. For directed graphs, * find minimal cuts iteratively and remove edges pointing from A to * B or from B to A in the cut, depending on which one is smaller. Yes, * this is time-consuming. * * 2. Assigning vertices to layers according to [2]. * * 3. Extracting weakly connected components. The remaining steps are * executed for each component. * * 4. Compacting the layering using the method of [4]. TODO * Steps 2-4 are performed only when no layering is given in advance. * * 5. Adding dummy nodes to ensure that each edge spans at most one layer * only. * * 6. Finding an optimal ordering of vertices within a layer using the * Sugiyama framework [1]. * * 7. Assigning horizontal coordinates to each vertex using [3]. * * 8. ??? * * 9. Profit! */ /** * Data structure to store a layering of the graph. */ typedef struct { igraph_vector_ptr_t layers; } igraph_i_layering_t; /** * Initializes a layering. */ int igraph_i_layering_init(igraph_i_layering_t* layering, const igraph_vector_t* membership) { long int i, n, num_layers; if (igraph_vector_size(membership) == 0) { num_layers = 0; } else { num_layers = (long int) igraph_vector_max(membership) + 1; } IGRAPH_CHECK(igraph_vector_ptr_init(&layering->layers, num_layers)); IGRAPH_FINALLY(igraph_vector_ptr_destroy_all, &layering->layers); for (i = 0; i < num_layers; i++) { igraph_vector_t* vec = igraph_Calloc(1, igraph_vector_t); IGRAPH_VECTOR_INIT_FINALLY(vec, 0); VECTOR(layering->layers)[i] = vec; IGRAPH_FINALLY_CLEAN(1); } IGRAPH_VECTOR_PTR_SET_ITEM_DESTRUCTOR(&layering->layers, igraph_vector_destroy); n = igraph_vector_size(membership); for (i = 0; i < n; i++) { long int l = (long int) VECTOR(*membership)[i]; igraph_vector_t* vec = VECTOR(layering->layers)[l]; IGRAPH_CHECK(igraph_vector_push_back(vec, i)); } IGRAPH_FINALLY_CLEAN(1); return IGRAPH_SUCCESS; } /** * Destroys a layering. */ void igraph_i_layering_destroy(igraph_i_layering_t* layering) { igraph_vector_ptr_destroy_all(&layering->layers); } /** * Returns the number of layers in a layering. */ int igraph_i_layering_num_layers(const igraph_i_layering_t* layering) { return (int) igraph_vector_ptr_size(&layering->layers); } /** * Returns the list of vertices in a given layer */ igraph_vector_t* igraph_i_layering_get(const igraph_i_layering_t* layering, long int index) { return (igraph_vector_t*)VECTOR(layering->layers)[index]; } /** * Forward declarations */ static int igraph_i_layout_sugiyama_place_nodes_vertically(const igraph_t* graph, const igraph_vector_t* weights, igraph_vector_t* membership); static int igraph_i_layout_sugiyama_order_nodes_horizontally(const igraph_t* graph, igraph_matrix_t* layout, const igraph_i_layering_t* layering, long int maxiter); static int igraph_i_layout_sugiyama_place_nodes_horizontally(const igraph_t* graph, igraph_matrix_t* layout, const igraph_i_layering_t* layering, igraph_real_t hgap, igraph_integer_t no_of_real_nodes); /** * Calculated the median of four numbers (not necessarily sorted). */ static INLINE igraph_real_t igraph_i_median_4(igraph_real_t x1, igraph_real_t x2, igraph_real_t x3, igraph_real_t x4) { igraph_real_t arr[4] = { x1, x2, x3, x4 }; igraph_vector_t vec; igraph_vector_view(&vec, arr, 4); igraph_vector_sort(&vec); return (arr[1] + arr[2]) / 2.0; } /** * \ingroup layout * \function igraph_layout_sugiyama * \brief Sugiyama layout algorithm for layered directed acyclic graphs. * * * This layout algorithm is designed for directed acyclic graphs where each * vertex is assigned to a layer. Layers are indexed from zero, and vertices * of the same layer will be placed on the same horizontal line. The X coordinates * of vertices within each layer are decided by the heuristic proposed by * Sugiyama et al to minimize edge crossings. * * * You can also try to lay out undirected graphs, graphs containing cycles, or * graphs without an a priori layered assignment with this algorithm. igraph * will try to eliminate cycles and assign vertices to layers, but there is no * guarantee on the quality of the layout in such cases. * * * The Sugiyama layout may introduce "bends" on the edges in order to obtain a * visually more pleasing layout. This is achieved by adding dummy nodes to * edges spanning more than one layer. The resulting layout assigns coordinates * not only to the nodes of the original graph but also to the dummy nodes. * The layout algorithm will also return the extended graph with the dummy nodes. * An edge in the original graph may either be mapped to a single edge in the * extended graph or a \em path that starts and ends in the original * source and target vertex and passes through multiple dummy vertices. In * such cases, the user may also request the mapping of the edges of the extended * graph back to the edges of the original graph. * * * For more details, see K. Sugiyama, S. Tagawa and M. Toda, "Methods for Visual * Understanding of Hierarchical Systems". IEEE Transactions on Systems, Man and * Cybernetics 11(2):109-125, 1981. * * \param graph Pointer to an initialized graph object. * \param res Pointer to an initialized matrix object. This will contain * the result and will be resized as needed. The first |V| rows * of the layout will contain the coordinates of the original graph, * the remaining rows contain the positions of the dummy nodes. * Therefore, you can use the result both with \p graph or with * \p extended_graph. * \param extended_graph Pointer to an uninitialized graph object or \c NULL. * The extended graph with the added dummy nodes will be * returned here. In this graph, each edge points downwards * to lower layers, spans exactly one layer and the first * |V| vertices coincide with the vertices of the * original graph. * \param extd_to_orig_eids Pointer to a vector or \c NULL. If not \c NULL, the * mapping from the edge IDs of the extended graph back * to the edge IDs of the original graph will be stored * here. * \param layers The layer index for each vertex or \c NULL if the layers should * be determined automatically by igraph. * \param hgap The preferred minimum horizontal gap between vertices in the same * layer. * \param vgap The distance between layers. * \param maxiter Maximum number of iterations in the crossing minimization stage. * 100 is a reasonable default; if you feel that you have too * many edge crossings, increase this. * \param weights Weights of the edges. These are used only if the graph contains * cycles; igraph will tend to reverse edges with smaller * weights when breaking the cycles. */ int igraph_layout_sugiyama(const igraph_t *graph, igraph_matrix_t *res, igraph_t *extd_graph, igraph_vector_t *extd_to_orig_eids, const igraph_vector_t* layers, igraph_real_t hgap, igraph_real_t vgap, long int maxiter, const igraph_vector_t *weights) { long int i, j, k, l, m, nei; long int no_of_nodes = (long int)igraph_vcount(graph); long int comp_idx; long int next_extd_vertex_id = no_of_nodes; igraph_bool_t directed = igraph_is_directed(graph); igraph_integer_t no_of_components; /* number of components of the original graph */ igraph_vector_t membership; /* components of the original graph */ igraph_vector_t extd_edgelist; /* edge list of the extended graph */ igraph_vector_t layers_own; /* layer indices after having eliminated empty layers */ igraph_real_t dx = 0, dx2 = 0; /* displacement of the current component on the X axis */ igraph_vector_t layer_to_y; /* mapping from layer indices to final Y coordinates */ if (layers && igraph_vector_size(layers) != no_of_nodes) { IGRAPH_ERROR("layer vector too short or too long", IGRAPH_EINVAL); } if (extd_graph != 0) { IGRAPH_VECTOR_INIT_FINALLY(&extd_edgelist, 0); if (extd_to_orig_eids != 0) { igraph_vector_clear(extd_to_orig_eids); } } IGRAPH_CHECK(igraph_matrix_resize(res, no_of_nodes, 2)); IGRAPH_VECTOR_INIT_FINALLY(&membership, 0); IGRAPH_VECTOR_INIT_FINALLY(&layer_to_y, 0); /* 1. Find a feedback arc set if we don't have a layering yet. If we do have * a layering, we can leave all the edges as is as they will be re-oriented * to point downwards only anyway. */ if (layers == 0) { IGRAPH_VECTOR_INIT_FINALLY(&layers_own, no_of_nodes); IGRAPH_CHECK(igraph_i_layout_sugiyama_place_nodes_vertically( graph, weights, &layers_own)); } else { IGRAPH_CHECK(igraph_vector_copy(&layers_own, layers)); IGRAPH_FINALLY(igraph_vector_destroy, &layers_own); } /* Normalize layering, eliminate empty layers */ if (no_of_nodes > 0) { igraph_vector_t inds; IGRAPH_VECTOR_INIT_FINALLY(&inds, 0); IGRAPH_CHECK((int) igraph_vector_qsort_ind(&layers_own, &inds, 0)); j = -1; dx = VECTOR(layers_own)[(long int)VECTOR(inds)[0]] - 1; for (i = 0; i < no_of_nodes; i++) { k = (long int)VECTOR(inds)[i]; if (VECTOR(layers_own)[k] > dx) { /* New layer starts here */ dx = VECTOR(layers_own)[k]; j++; IGRAPH_CHECK(igraph_vector_push_back(&layer_to_y, dx * vgap)); } VECTOR(layers_own)[k] = j; } igraph_vector_destroy(&inds); IGRAPH_FINALLY_CLEAN(1); } /* 2. Find the connected components. */ IGRAPH_CHECK(igraph_clusters(graph, &membership, 0, &no_of_components, IGRAPH_WEAK)); /* 3. For each component... */ dx = 0; for (comp_idx = 0; comp_idx < no_of_components; comp_idx++) { /* Extract the edges of the comp_idx'th component and add dummy nodes for edges * spanning more than one layer. */ long int component_size, next_new_vertex_id; igraph_vector_t old2new_vertex_ids; igraph_vector_t new2old_vertex_ids; igraph_vector_t new_layers; igraph_vector_t edgelist; igraph_vector_t neis; IGRAPH_VECTOR_INIT_FINALLY(&edgelist, 0); IGRAPH_VECTOR_INIT_FINALLY(&neis, 0); IGRAPH_VECTOR_INIT_FINALLY(&new2old_vertex_ids, no_of_nodes); IGRAPH_VECTOR_INIT_FINALLY(&old2new_vertex_ids, no_of_nodes); IGRAPH_VECTOR_INIT_FINALLY(&new_layers, 0); igraph_vector_fill(&old2new_vertex_ids, -1); /* Construct a mapping from the old vertex ids to the new ones */ for (i = 0, next_new_vertex_id = 0; i < no_of_nodes; i++) { if (VECTOR(membership)[i] == comp_idx) { IGRAPH_CHECK(igraph_vector_push_back(&new_layers, VECTOR(layers_own)[i])); VECTOR(new2old_vertex_ids)[next_new_vertex_id] = i; VECTOR(old2new_vertex_ids)[i] = next_new_vertex_id; next_new_vertex_id++; } } component_size = next_new_vertex_id; /* Construct a proper layering of the component in new_graph where each edge * points downwards and spans exactly one layer. */ for (i = 0; i < no_of_nodes; i++) { if (VECTOR(membership)[i] != comp_idx) { continue; } /* Okay, this vertex is in the component we are considering. * Add the neighbors of this vertex, excluding loops */ IGRAPH_CHECK(igraph_incident(graph, &neis, (igraph_integer_t) i, IGRAPH_OUT)); j = igraph_vector_size(&neis); for (k = 0; k < j; k++) { long int eid = (long int) VECTOR(neis)[k]; if (directed) { nei = IGRAPH_TO(graph, eid); } else { nei = IGRAPH_OTHER(graph, eid, i); if (nei < i) { /* to avoid considering edges twice */ continue; } } if (VECTOR(layers_own)[i] == VECTOR(layers_own)[nei]) { /* Edge goes within the same layer, we don't need this in the * layered graph, but we need it in the extended graph */ if (extd_graph != 0) { IGRAPH_CHECK(igraph_vector_push_back(&extd_edgelist, i)); IGRAPH_CHECK(igraph_vector_push_back(&extd_edgelist, nei)); if (extd_to_orig_eids != 0) { IGRAPH_CHECK(igraph_vector_push_back(extd_to_orig_eids, eid)); } } } else if (VECTOR(layers_own)[i] > VECTOR(layers_own)[nei]) { /* Edge goes upwards, we have to flip it */ IGRAPH_CHECK(igraph_vector_push_back(&edgelist, VECTOR(old2new_vertex_ids)[nei])); for (l = (long int) VECTOR(layers_own)[nei] + 1; l < VECTOR(layers_own)[i]; l++) { IGRAPH_CHECK(igraph_vector_push_back(&new_layers, l)); IGRAPH_CHECK(igraph_vector_push_back(&edgelist, next_new_vertex_id)); IGRAPH_CHECK(igraph_vector_push_back(&edgelist, next_new_vertex_id++)); } IGRAPH_CHECK(igraph_vector_push_back(&edgelist, VECTOR(old2new_vertex_ids)[i])); /* Also add the edge to the extended graph if needed, but this time * with the proper orientation */ if (extd_graph != 0) { IGRAPH_CHECK(igraph_vector_push_back(&extd_edgelist, i)); next_extd_vertex_id += VECTOR(layers_own)[i] - VECTOR(layers_own)[nei] - 1; for (l = (long int) VECTOR(layers_own)[i] - 1, m = 1; l > VECTOR(layers_own)[nei]; l--, m++) { IGRAPH_CHECK(igraph_vector_push_back(&extd_edgelist, next_extd_vertex_id - m)); IGRAPH_CHECK(igraph_vector_push_back(&extd_edgelist, next_extd_vertex_id - m)); if (extd_to_orig_eids != 0) { IGRAPH_CHECK(igraph_vector_push_back(extd_to_orig_eids, eid)); } } IGRAPH_CHECK(igraph_vector_push_back(&extd_edgelist, nei)); if (extd_to_orig_eids != 0) { IGRAPH_CHECK(igraph_vector_push_back(extd_to_orig_eids, eid)); } } } else { /* Edge goes downwards */ IGRAPH_CHECK(igraph_vector_push_back(&edgelist, VECTOR(old2new_vertex_ids)[i])); for (l = (long int) VECTOR(layers_own)[i] + 1; l < VECTOR(layers_own)[nei]; l++) { IGRAPH_CHECK(igraph_vector_push_back(&new_layers, l)); IGRAPH_CHECK(igraph_vector_push_back(&edgelist, next_new_vertex_id)); IGRAPH_CHECK(igraph_vector_push_back(&edgelist, next_new_vertex_id++)); } IGRAPH_CHECK(igraph_vector_push_back(&edgelist, VECTOR(old2new_vertex_ids)[nei])); /* Also add the edge to the extended graph */ if (extd_graph != 0) { IGRAPH_CHECK(igraph_vector_push_back(&extd_edgelist, i)); for (l = (long int) VECTOR(layers_own)[i] + 1; l < VECTOR(layers_own)[nei]; l++) { IGRAPH_CHECK(igraph_vector_push_back(&extd_edgelist, next_extd_vertex_id)); IGRAPH_CHECK(igraph_vector_push_back(&extd_edgelist, next_extd_vertex_id++)); if (extd_to_orig_eids != 0) { IGRAPH_CHECK(igraph_vector_push_back(extd_to_orig_eids, eid)); } } IGRAPH_CHECK(igraph_vector_push_back(&extd_edgelist, nei)); if (extd_to_orig_eids != 0) { IGRAPH_CHECK(igraph_vector_push_back(extd_to_orig_eids, eid)); } } } } } /* At this point, we have the subgraph with the dummy nodes and * edges, so we can run Sugiyama's algorithm on it. */ { igraph_matrix_t layout; igraph_i_layering_t layering; igraph_t subgraph; IGRAPH_CHECK(igraph_matrix_init(&layout, next_new_vertex_id, 2)); IGRAPH_FINALLY(igraph_matrix_destroy, &layout); IGRAPH_CHECK(igraph_create(&subgraph, &edgelist, (igraph_integer_t) next_new_vertex_id, 1)); IGRAPH_FINALLY(igraph_destroy, &subgraph); /* igraph_vector_print(&edgelist); igraph_vector_print(&new_layers); */ /* Assign the vertical coordinates */ for (i = 0; i < next_new_vertex_id; i++) { MATRIX(layout, i, 1) = VECTOR(new_layers)[i]; } /* Create a layering */ IGRAPH_CHECK(igraph_i_layering_init(&layering, &new_layers)); IGRAPH_FINALLY(igraph_i_layering_destroy, &layering); /* Find the order in which the nodes within a layer should be placed */ IGRAPH_CHECK(igraph_i_layout_sugiyama_order_nodes_horizontally(&subgraph, &layout, &layering, maxiter)); /* Assign the horizontal coordinates. This is according to the algorithm * of Brandes & Köpf */ IGRAPH_CHECK(igraph_i_layout_sugiyama_place_nodes_horizontally(&subgraph, &layout, &layering, hgap, (igraph_integer_t) component_size)); /* Re-assign rows into the result matrix, and at the same time, */ /* adjust dx so that the next component does not overlap this one */ j = next_new_vertex_id - component_size; k = igraph_matrix_nrow(res); IGRAPH_CHECK(igraph_matrix_add_rows(res, j)); dx2 = dx; for (i = 0; i < component_size; i++) { l = (long int)VECTOR(new2old_vertex_ids)[i]; MATRIX(*res, l, 0) = MATRIX(layout, i, 0) + dx; MATRIX(*res, l, 1) = VECTOR(layer_to_y)[(long)MATRIX(layout, i, 1)]; if (dx2 < MATRIX(*res, l, 0)) { dx2 = MATRIX(*res, l, 0); } } for (i = component_size; i < next_new_vertex_id; i++) { MATRIX(*res, k, 0) = MATRIX(layout, i, 0) + dx; MATRIX(*res, k, 1) = VECTOR(layer_to_y)[(long)MATRIX(layout, i, 1)]; if (dx2 < MATRIX(*res, k, 0)) { dx2 = MATRIX(*res, k, 0); } k++; } dx = dx2 + hgap; igraph_destroy(&subgraph); igraph_i_layering_destroy(&layering); igraph_matrix_destroy(&layout); IGRAPH_FINALLY_CLEAN(3); } igraph_vector_destroy(&new_layers); igraph_vector_destroy(&old2new_vertex_ids); igraph_vector_destroy(&new2old_vertex_ids); igraph_vector_destroy(&edgelist); igraph_vector_destroy(&neis); IGRAPH_FINALLY_CLEAN(5); } igraph_vector_destroy(&layers_own); igraph_vector_destroy(&layer_to_y); igraph_vector_destroy(&membership); IGRAPH_FINALLY_CLEAN(3); if (extd_graph != 0) { IGRAPH_CHECK(igraph_create(extd_graph, &extd_edgelist, (igraph_integer_t) next_extd_vertex_id, igraph_is_directed(graph))); igraph_vector_destroy(&extd_edgelist); IGRAPH_FINALLY_CLEAN(1); } return IGRAPH_SUCCESS; } static int igraph_i_layout_sugiyama_place_nodes_vertically(const igraph_t* graph, const igraph_vector_t* weights, igraph_vector_t* membership) { long int no_of_nodes = igraph_vcount(graph); long int no_of_edges = igraph_ecount(graph); IGRAPH_CHECK(igraph_vector_resize(membership, no_of_nodes)); if (no_of_edges == 0) { igraph_vector_fill(membership, 0); return IGRAPH_SUCCESS; } #ifdef HAVE_GLPK if (igraph_is_directed(graph) && no_of_nodes <= 1000) { /* Network simplex algorithm of Gansner et al, using the original linear * programming formulation */ long int i, j; igraph_vector_t outdegs, indegs, feedback_edges; glp_prob *ip; glp_smcp parm; /* Allocate storage and create the problem */ ip = glp_create_prob(); IGRAPH_FINALLY(glp_delete_prob, ip); IGRAPH_VECTOR_INIT_FINALLY(&feedback_edges, 0); IGRAPH_VECTOR_INIT_FINALLY(&outdegs, no_of_nodes); IGRAPH_VECTOR_INIT_FINALLY(&indegs, no_of_nodes); /* Find an approximate feedback edge set */ IGRAPH_CHECK(igraph_i_feedback_arc_set_eades(graph, &feedback_edges, weights, 0)); igraph_vector_sort(&feedback_edges); /* Calculate in- and out-strengths for the remaining edges */ IGRAPH_CHECK(igraph_strength(graph, &indegs, igraph_vss_all(), IGRAPH_IN, 1, weights)); IGRAPH_CHECK(igraph_strength(graph, &outdegs, igraph_vss_all(), IGRAPH_IN, 1, weights)); j = igraph_vector_size(&feedback_edges); for (i = 0; i < j; i++) { long int eid = (long int) VECTOR(feedback_edges)[i]; long int from = IGRAPH_FROM(graph, eid); long int to = IGRAPH_TO(graph, eid); VECTOR(outdegs)[from] -= weights ? VECTOR(*weights)[eid] : 1; VECTOR(indegs)[to] -= weights ? VECTOR(*weights)[eid] : 1; } /* Configure GLPK */ glp_term_out(GLP_OFF); glp_init_smcp(&parm); parm.msg_lev = GLP_MSG_OFF; parm.presolve = GLP_OFF; /* Set up variables and objective function coefficients */ glp_set_obj_dir(ip, GLP_MIN); glp_add_cols(ip, (int) no_of_nodes); IGRAPH_CHECK(igraph_vector_sub(&outdegs, &indegs)); for (i = 1; i <= no_of_nodes; i++) { glp_set_col_kind(ip, (int) i, GLP_IV); glp_set_col_bnds(ip, (int) i, GLP_LO, 0.0, 0.0); glp_set_obj_coef(ip, (int) i, VECTOR(outdegs)[i - 1]); } igraph_vector_destroy(&indegs); igraph_vector_destroy(&outdegs); IGRAPH_FINALLY_CLEAN(2); /* Add constraints */ glp_add_rows(ip, (int) no_of_edges); IGRAPH_CHECK(igraph_vector_push_back(&feedback_edges, -1)); j = 0; for (i = 0; i < no_of_edges; i++) { int ind[3]; double val[3] = {0, -1, 1}; ind[1] = IGRAPH_FROM(graph, i) + 1; ind[2] = IGRAPH_TO(graph, i) + 1; if (ind[1] == ind[2]) { if (VECTOR(feedback_edges)[j] == i) { j++; } continue; } if (VECTOR(feedback_edges)[j] == i) { /* This is a feedback edge, add it reversed */ glp_set_row_bnds(ip, (int) i + 1, GLP_UP, -1, -1); j++; } else { glp_set_row_bnds(ip, (int) i + 1, GLP_LO, 1, 1); } glp_set_mat_row(ip, (int) i + 1, 2, ind, val); } /* Solve the problem */ IGRAPH_GLPK_CHECK(glp_simplex(ip, &parm), "Vertical arrangement step using IP failed"); /* The problem is totally unimodular, therefore the output of the simplex * solver can be converted to an integer solution easily */ for (i = 0; i < no_of_nodes; i++) { VECTOR(*membership)[i] = floor(glp_get_col_prim(ip, (int) i + 1)); } glp_delete_prob(ip); igraph_vector_destroy(&feedback_edges); IGRAPH_FINALLY_CLEAN(2); } else if (igraph_is_directed(graph)) { IGRAPH_CHECK(igraph_i_feedback_arc_set_eades(graph, 0, weights, membership)); } else { IGRAPH_CHECK(igraph_i_feedback_arc_set_undirected(graph, 0, weights, membership)); } #else if (igraph_is_directed(graph)) { IGRAPH_CHECK(igraph_i_feedback_arc_set_eades(graph, 0, weights, membership)); } else { IGRAPH_CHECK(igraph_i_feedback_arc_set_undirected(graph, 0, weights, membership)); } #endif return IGRAPH_SUCCESS; } static int igraph_i_layout_sugiyama_calculate_barycenters(const igraph_t* graph, const igraph_i_layering_t* layering, long int layer_index, igraph_neimode_t direction, const igraph_matrix_t* layout, igraph_vector_t* barycenters) { long int i, j, m, n; igraph_vector_t* layer_members = igraph_i_layering_get(layering, layer_index); igraph_vector_t neis; IGRAPH_VECTOR_INIT_FINALLY(&neis, 0); n = igraph_vector_size(layer_members); IGRAPH_CHECK(igraph_vector_resize(barycenters, n)); igraph_vector_null(barycenters); for (i = 0; i < n; i++) { IGRAPH_CHECK(igraph_neighbors(graph, &neis, (igraph_integer_t) VECTOR(*layer_members)[i], direction)); m = igraph_vector_size(&neis); if (m == 0) { /* No neighbors in this direction. Just use the current X coordinate */ VECTOR(*barycenters)[i] = MATRIX(*layout, i, 0); } else { for (j = 0; j < m; j++) { VECTOR(*barycenters)[i] += MATRIX(*layout, (long)VECTOR(neis)[j], 0); } VECTOR(*barycenters)[i] /= m; } } igraph_vector_destroy(&neis); IGRAPH_FINALLY_CLEAN(1); return IGRAPH_SUCCESS; } /** * Given a properly layered graph where each edge points downwards and spans * exactly one layer, arranges the nodes in each layer horizontally in a way * that strives to minimize edge crossings. */ static int igraph_i_layout_sugiyama_order_nodes_horizontally(const igraph_t* graph, igraph_matrix_t* layout, const igraph_i_layering_t* layering, long int maxiter) { long int i, n, nei; long int no_of_vertices = igraph_vcount(graph); long int no_of_layers = igraph_i_layering_num_layers(layering); long int iter, layer_index; igraph_vector_t* layer_members; igraph_vector_t neis, barycenters, sort_indices; igraph_bool_t changed; /* The first column of the matrix will serve as the ordering */ /* Start with a first-seen ordering within each layer */ { long int *xs = igraph_Calloc(no_of_layers, long int); if (xs == 0) { IGRAPH_ERROR("cannot order nodes horizontally", IGRAPH_ENOMEM); } for (i = 0; i < no_of_vertices; i++) { MATRIX(*layout, i, 0) = xs[(long int)MATRIX(*layout, i, 1)]++; } free(xs); } IGRAPH_VECTOR_INIT_FINALLY(&barycenters, 0); IGRAPH_VECTOR_INIT_FINALLY(&neis, 0); IGRAPH_VECTOR_INIT_FINALLY(&sort_indices, 0); /* Start the effective part of the Sugiyama algorithm */ iter = 0; changed = 1; while (changed && iter < maxiter) { changed = 0; /* Phase 1 */ /* Moving downwards and sorting by upper barycenters */ for (layer_index = 1; layer_index < no_of_layers; layer_index++) { layer_members = igraph_i_layering_get(layering, layer_index); n = igraph_vector_size(layer_members); igraph_i_layout_sugiyama_calculate_barycenters(graph, layering, layer_index, IGRAPH_IN, layout, &barycenters); #ifdef SUGIYAMA_DEBUG printf("Layer %ld, aligning to upper barycenters\n", layer_index); printf("Vertices: "); igraph_vector_print(layer_members); printf("Barycenters: "); igraph_vector_print(&barycenters); #endif IGRAPH_CHECK((int) igraph_vector_qsort_ind(&barycenters, &sort_indices, 0)); for (i = 0; i < n; i++) { nei = (long)VECTOR(*layer_members)[(long)VECTOR(sort_indices)[i]]; VECTOR(barycenters)[i] = nei; MATRIX(*layout, nei, 0) = i; } if (!igraph_vector_all_e(layer_members, &barycenters)) { IGRAPH_CHECK(igraph_vector_update(layer_members, &barycenters)); #ifdef SUGIYAMA_DEBUG printf("New vertex order: "); igraph_vector_print(layer_members); #endif changed = 1; } else { #ifdef SUGIYAMA_DEBUG printf("Order did not change.\n"); #endif } } /* Moving upwards and sorting by lower barycenters */ for (layer_index = no_of_layers - 2; layer_index >= 0; layer_index--) { layer_members = igraph_i_layering_get(layering, layer_index); n = igraph_vector_size(layer_members); igraph_i_layout_sugiyama_calculate_barycenters(graph, layering, layer_index, IGRAPH_OUT, layout, &barycenters); #ifdef SUGIYAMA_DEBUG printf("Layer %ld, aligning to lower barycenters\n", layer_index); printf("Vertices: "); igraph_vector_print(layer_members); printf("Barycenters: "); igraph_vector_print(&barycenters); #endif IGRAPH_CHECK((int) igraph_vector_qsort_ind(&barycenters, &sort_indices, 0)); for (i = 0; i < n; i++) { nei = (long)VECTOR(*layer_members)[(long)VECTOR(sort_indices)[i]]; VECTOR(barycenters)[i] = nei; MATRIX(*layout, nei, 0) = i; } if (!igraph_vector_all_e(layer_members, &barycenters)) { IGRAPH_CHECK(igraph_vector_update(layer_members, &barycenters)); #ifdef SUGIYAMA_DEBUG printf("New vertex order: "); igraph_vector_print(layer_members); #endif changed = 1; } else { #ifdef SUGIYAMA_DEBUG printf("Order did not change.\n"); #endif } } #ifdef SUGIYAMA_DEBUG printf("==== Finished iteration %ld\n", iter); #endif iter++; } igraph_vector_destroy(&barycenters); igraph_vector_destroy(&neis); igraph_vector_destroy(&sort_indices); IGRAPH_FINALLY_CLEAN(3); return IGRAPH_SUCCESS; } #define IS_DUMMY(v) ((v >= no_of_real_nodes)) #define IS_INNER_SEGMENT(u, v) (IS_DUMMY(u) && IS_DUMMY(v)) #define X_POS(v) (MATRIX(*layout, v, 0)) static int igraph_i_layout_sugiyama_vertical_alignment(const igraph_t* graph, const igraph_i_layering_t* layering, const igraph_matrix_t* layout, const igraph_vector_bool_t* ignored_edges, igraph_bool_t reverse, igraph_bool_t align_right, igraph_vector_t* roots, igraph_vector_t* align); static int igraph_i_layout_sugiyama_horizontal_compaction(const igraph_t* graph, const igraph_vector_t* vertex_to_the_left, const igraph_vector_t* roots, const igraph_vector_t* align, igraph_real_t hgap, igraph_vector_t* xs); static int igraph_i_layout_sugiyama_horizontal_compaction_place_block(long int v, const igraph_vector_t* vertex_to_the_left, const igraph_vector_t* roots, const igraph_vector_t* align, igraph_vector_t* sinks, igraph_vector_t* shifts, igraph_real_t hgap, igraph_vector_t* xs); static int igraph_i_layout_sugiyama_place_nodes_horizontally(const igraph_t* graph, igraph_matrix_t* layout, const igraph_i_layering_t* layering, igraph_real_t hgap, igraph_integer_t no_of_real_nodes) { long int i, j, k, l, n; long int no_of_layers = igraph_i_layering_num_layers(layering); long int no_of_nodes = igraph_vcount(graph); long int no_of_edges = igraph_ecount(graph); igraph_vector_t neis1, neis2; igraph_vector_t xs[4]; igraph_vector_t roots, align; igraph_vector_t vertex_to_the_left; igraph_vector_bool_t ignored_edges; /* { igraph_vector_t edgelist; IGRAPH_VECTOR_INIT_FINALLY(&edgelist, 0); IGRAPH_CHECK(igraph_get_edgelist(graph, &edgelist, 0)); igraph_vector_print(&edgelist); igraph_vector_destroy(&edgelist); IGRAPH_FINALLY_CLEAN(1); for (i = 0; i < no_of_layers; i++) { igraph_vector_t* layer = igraph_i_layering_get(layering, i); igraph_vector_print(layer); } } */ IGRAPH_CHECK(igraph_vector_bool_init(&ignored_edges, no_of_edges)); IGRAPH_FINALLY(igraph_vector_bool_destroy, &ignored_edges); IGRAPH_VECTOR_INIT_FINALLY(&vertex_to_the_left, no_of_nodes); IGRAPH_VECTOR_INIT_FINALLY(&neis1, 0); IGRAPH_VECTOR_INIT_FINALLY(&neis2, 0); /* First, find all type 1 conflicts and mark one of the edges participating * in the conflict as being ignored. If one of the edges in the conflict * is a non-inner segment and the other is an inner segment, we ignore the * non-inner segment as we want to keep inner segments vertical. */ for (i = 0; i < no_of_layers - 1; i++) { igraph_vector_t* vertices = igraph_i_layering_get(layering, i); n = igraph_vector_size(vertices); /* Find all the edges from this layer to the next */ igraph_vector_clear(&neis1); for (j = 0; j < n; j++) { IGRAPH_CHECK(igraph_neighbors(graph, &neis2, (igraph_integer_t) VECTOR(*vertices)[j], IGRAPH_OUT)); IGRAPH_CHECK(igraph_vector_append(&neis1, &neis2)); } /* Consider all pairs of edges and check whether they are in a type 1 * conflict */ n = igraph_vector_size(&neis1); for (j = 0; j < n; j++) { long int u = IGRAPH_FROM(graph, j); long int v = IGRAPH_TO(graph, j); igraph_bool_t j_inner = IS_INNER_SEGMENT(u, v); igraph_bool_t crossing; for (k = j + 1; k < n; k++) { long int w = IGRAPH_FROM(graph, k); long int x = IGRAPH_TO(graph, k); if (IS_INNER_SEGMENT(w, x) == j_inner) { continue; } /* Do the u --> v and w --> x edges cross? */ crossing = (u == w || v == x); if (!crossing) { if (X_POS(u) <= X_POS(w)) { crossing = X_POS(v) >= X_POS(x); } else { crossing = X_POS(v) <= X_POS(x); } } if (crossing) { if (j_inner) { VECTOR(ignored_edges)[k] = 1; } else { VECTOR(ignored_edges)[j] = 1; } } } } } igraph_vector_destroy(&neis1); igraph_vector_destroy(&neis2); IGRAPH_FINALLY_CLEAN(2); /* * Prepare vertex_to_the_left where the ith element stores * the index of the vertex to the left of vertex i, or i itself if the * vertex is the leftmost vertex in a layer. */ for (i = 0; i < no_of_layers; i++) { igraph_vector_t* vertices = igraph_i_layering_get(layering, i); n = igraph_vector_size(vertices); if (n == 0) { continue; } k = l = (long int)VECTOR(*vertices)[0]; VECTOR(vertex_to_the_left)[k] = k; for (j = 1; j < n; j++) { k = (long int)VECTOR(*vertices)[j]; VECTOR(vertex_to_the_left)[k] = l; l = k; } } /* Type 1 conflicts found, ignored edges chosen, vertex_to_the_left * prepared. Run vertical alignment for all four combinations */ for (i = 0; i < 4; i++) { IGRAPH_VECTOR_INIT_FINALLY(&xs[i], no_of_nodes); } IGRAPH_VECTOR_INIT_FINALLY(&roots, no_of_nodes); IGRAPH_VECTOR_INIT_FINALLY(&align, no_of_nodes); for (i = 0; i < 4; i++) { IGRAPH_CHECK(igraph_i_layout_sugiyama_vertical_alignment(graph, layering, layout, &ignored_edges, /* reverse = */ (igraph_bool_t) i / 2, /* align_right = */ i % 2, &roots, &align)); IGRAPH_CHECK(igraph_i_layout_sugiyama_horizontal_compaction(graph, &vertex_to_the_left, &roots, &align, hgap, &xs[i])); } { igraph_real_t width, min_width, mins[4], maxs[4], diff; /* Find the alignment with the minimum width */ min_width = IGRAPH_INFINITY; j = 0; for (i = 0; i < 4; i++) { mins[i] = igraph_vector_min(&xs[i]); maxs[i] = igraph_vector_max(&xs[i]); width = maxs[i] - mins[i]; if (width < min_width) { min_width = width; j = i; } } /* Leftmost alignments: align them s.t. the min X coordinate is equal to * the minimum X coordinate of the alignment with the smallest width. * Rightmost alignments: align them s.t. the max X coordinate is equal to * the max X coordinate of the alignment with the smallest width. */ for (i = 0; i < 4; i++) { if (j == i) { continue; } if (i % 2 == 0) { /* Leftmost alignment */ diff = mins[j] - mins[i]; } else { /* Rightmost alignment */ diff = maxs[j] - maxs[i]; } igraph_vector_add_constant(&xs[i], diff); } } /* For every vertex, find the median of the X coordinates in the four * alignments */ for (i = 0; i < no_of_nodes; i++) { X_POS(i) = igraph_i_median_4(VECTOR(xs[0])[i], VECTOR(xs[1])[i], VECTOR(xs[2])[i], VECTOR(xs[3])[i]); } igraph_vector_destroy(&roots); igraph_vector_destroy(&align); IGRAPH_FINALLY_CLEAN(2); for (i = 0; i < 4; i++) { igraph_vector_destroy(&xs[i]); } IGRAPH_FINALLY_CLEAN(4); igraph_vector_destroy(&vertex_to_the_left); IGRAPH_FINALLY_CLEAN(1); igraph_vector_bool_destroy(&ignored_edges); IGRAPH_FINALLY_CLEAN(1); return IGRAPH_SUCCESS; } static int igraph_i_layout_sugiyama_vertical_alignment(const igraph_t* graph, const igraph_i_layering_t* layering, const igraph_matrix_t* layout, const igraph_vector_bool_t* ignored_edges, igraph_bool_t reverse, igraph_bool_t align_right, igraph_vector_t* roots, igraph_vector_t* align) { long int i, j, k, n, di, dj, i_limit, j_limit, r; long int no_of_layers = igraph_i_layering_num_layers(layering); long int no_of_nodes = igraph_vcount(graph); igraph_neimode_t neimode = (reverse ? IGRAPH_OUT : IGRAPH_IN); igraph_vector_t neis, xs, inds; IGRAPH_VECTOR_INIT_FINALLY(&neis, 0); IGRAPH_VECTOR_INIT_FINALLY(&xs, 0); IGRAPH_VECTOR_INIT_FINALLY(&inds, 0); IGRAPH_CHECK(igraph_vector_resize(roots, no_of_nodes)); IGRAPH_CHECK(igraph_vector_resize(align, no_of_nodes)); for (i = 0; i < no_of_nodes; i++) { VECTOR(*roots)[i] = VECTOR(*align)[i] = i; } /* When reverse = False, we are aligning "upwards" in the tree, hence we * have to loop i from 1 to no_of_layers-1 (inclusive) and use neimode=IGRAPH_IN. * When reverse = True, we are aligning "downwards", hence we have to loop * i from no_of_layers-2 to 0 (inclusive) and use neimode=IGRAPH_OUT. */ i = reverse ? (no_of_layers - 2) : 1; di = reverse ? -1 : 1; i_limit = reverse ? -1 : no_of_layers; for (; i != i_limit; i += di) { igraph_vector_t *layer = igraph_i_layering_get(layering, i); /* r = 0 in the paper, but C arrays are indexed from 0 */ r = align_right ? LONG_MAX : -1; /* If align_right is 1, we have to process the layer in reverse order */ j = align_right ? (igraph_vector_size(layer) - 1) : 0; dj = align_right ? -1 : 1; j_limit = align_right ? -1 : igraph_vector_size(layer); for (; j != j_limit; j += dj) { long int medians[2]; long int vertex = (long int) VECTOR(*layer)[j]; long int pos; if (VECTOR(*align)[vertex] != vertex) /* This vertex is already aligned with some other vertex, * so there's nothing to do */ { continue; } /* Find the neighbors of vertex j in layer i */ IGRAPH_CHECK(igraph_neighbors(graph, &neis, (igraph_integer_t) vertex, neimode)); n = igraph_vector_size(&neis); if (n == 0) /* No neighbors in this direction, continue */ { continue; } if (n == 1) { /* Just one neighbor; the median is trivial */ medians[0] = (long int) VECTOR(neis)[0]; medians[1] = -1; } else { /* Sort the neighbors by their X coordinates */ IGRAPH_CHECK(igraph_vector_resize(&xs, n)); for (k = 0; k < n; k++) { VECTOR(xs)[k] = X_POS((long int)VECTOR(neis)[k]); } IGRAPH_CHECK((int) igraph_vector_qsort_ind(&xs, &inds, 0)); if (n % 2 == 1) { /* Odd number of neighbors, so the median is unique */ medians[0] = (long int) VECTOR(neis)[(long int)VECTOR(inds)[n / 2]]; medians[1] = -1; } else { /* Even number of neighbors, so we have two medians. The order * depends on whether we are processing the layer in leftmost * or rightmost fashion. */ if (align_right) { medians[0] = (long int) VECTOR(neis)[(long int)VECTOR(inds)[n / 2]]; medians[1] = (long int) VECTOR(neis)[(long int)VECTOR(inds)[n / 2 - 1]]; } else { medians[0] = (long int) VECTOR(neis)[(long int)VECTOR(inds)[n / 2 - 1]]; medians[1] = (long int) VECTOR(neis)[(long int)VECTOR(inds)[n / 2]]; } } } /* Try aligning with the medians */ for (k = 0; k < 2; k++) { igraph_integer_t eid; if (medians[k] < 0) { continue; } if (VECTOR(*align)[vertex] != vertex) { /* Vertex already aligned, continue */ continue; } /* Is the edge between medians[k] and vertex ignored * because of a type 1 conflict? */ IGRAPH_CHECK(igraph_get_eid(graph, &eid, (igraph_integer_t) vertex, (igraph_integer_t) medians[k], 0, 1)); if (VECTOR(*ignored_edges)[(long int)eid]) { continue; } /* Okay, align with the median if possible */ pos = (long int) X_POS(medians[k]); if ((align_right && r > pos) || (!align_right && r < pos)) { VECTOR(*align)[medians[k]] = vertex; VECTOR(*roots)[vertex] = VECTOR(*roots)[medians[k]]; VECTOR(*align)[vertex] = VECTOR(*roots)[medians[k]]; r = pos; } } } } igraph_vector_destroy(&inds); igraph_vector_destroy(&neis); igraph_vector_destroy(&xs); IGRAPH_FINALLY_CLEAN(3); return IGRAPH_SUCCESS; } /* * Runs a horizontal compaction given a vertical alignment (in `align`) * and the roots (in `roots`). These come out directly from * igraph_i_layout_sugiyama_vertical_alignment. * * Returns the X coordinates for each vertex in `xs`. * * `graph` is the input graph, `layering` is the layering on which we operate. * `hgap` is the preferred horizontal gap between vertices. */ static int igraph_i_layout_sugiyama_horizontal_compaction(const igraph_t* graph, const igraph_vector_t* vertex_to_the_left, const igraph_vector_t* roots, const igraph_vector_t* align, igraph_real_t hgap, igraph_vector_t* xs) { long int i; long int no_of_nodes = igraph_vcount(graph); igraph_vector_t sinks, shifts, old_xs; igraph_real_t shift; /* Initialization */ IGRAPH_VECTOR_INIT_FINALLY(&sinks, no_of_nodes); IGRAPH_VECTOR_INIT_FINALLY(&shifts, no_of_nodes); IGRAPH_VECTOR_INIT_FINALLY(&old_xs, no_of_nodes); IGRAPH_CHECK(igraph_vector_resize(xs, no_of_nodes)); for (i = 0; i < no_of_nodes; i++) { VECTOR(sinks)[i] = i; } igraph_vector_fill(&shifts, IGRAPH_INFINITY); igraph_vector_fill(xs, -1); /* Calculate the coordinates of the vertices relative to their sinks * in their own class. At the end of this for loop, xs will contain the * relative displacement of a vertex from its sink, while the shifts list * will contain the absolute displacement of the sinks. * (For the sinks only, of course, the rest is undefined and unused) */ for (i = 0; i < no_of_nodes; i++) { if (VECTOR(*roots)[i] == i) { IGRAPH_CHECK( igraph_i_layout_sugiyama_horizontal_compaction_place_block(i, vertex_to_the_left, roots, align, &sinks, &shifts, hgap, xs) ); } } /* In "sinks", only those indices `i` matter for which `i` is in `roots`. * All the other values will never be touched. */ /* Calculate the absolute coordinates */ IGRAPH_CHECK(igraph_vector_update(&old_xs, xs)); for (i = 0; i < no_of_nodes; i++) { long int root = (long int) VECTOR(*roots)[i]; VECTOR(*xs)[i] = VECTOR(old_xs)[root]; shift = VECTOR(shifts)[(long int)VECTOR(sinks)[root]]; if (shift < IGRAPH_INFINITY) { VECTOR(*xs)[i] += shift; } } igraph_vector_destroy(&sinks); igraph_vector_destroy(&shifts); igraph_vector_destroy(&old_xs); IGRAPH_FINALLY_CLEAN(3); return IGRAPH_SUCCESS; } static int igraph_i_layout_sugiyama_horizontal_compaction_place_block(long int v, const igraph_vector_t* vertex_to_the_left, const igraph_vector_t* roots, const igraph_vector_t* align, igraph_vector_t* sinks, igraph_vector_t* shifts, igraph_real_t hgap, igraph_vector_t* xs) { long int u, w; long int u_sink, v_sink; if (VECTOR(*xs)[v] >= 0) { return IGRAPH_SUCCESS; } VECTOR(*xs)[v] = 0; w = v; do { /* Check whether vertex w is the leftmost in its own layer */ u = (long int) VECTOR(*vertex_to_the_left)[w]; if (u != w) { /* Get the root of u (proceeding all the way upwards in the block) */ u = (long int) VECTOR(*roots)[u]; /* Place the block of u recursively */ IGRAPH_CHECK( igraph_i_layout_sugiyama_horizontal_compaction_place_block(u, vertex_to_the_left, roots, align, sinks, shifts, hgap, xs) ); u_sink = (long int) VECTOR(*sinks)[u]; v_sink = (long int) VECTOR(*sinks)[v]; /* If v is its own sink yet, set its sink to the sink of u */ if (v_sink == v) { VECTOR(*sinks)[v] = v_sink = u_sink; } /* If v and u have different sinks (i.e. they are in different classes), * shift the sink of u so that the two blocks are separated by the * preferred gap */ if (v_sink != u_sink) { if (VECTOR(*shifts)[u_sink] > VECTOR(*xs)[v] - VECTOR(*xs)[u] - hgap) { VECTOR(*shifts)[u_sink] = VECTOR(*xs)[v] - VECTOR(*xs)[u] - hgap; } } else { /* v and u have the same sink, i.e. they are in the same class. Make sure * that v is separated from u by at least hgap. */ if (VECTOR(*xs)[v] < VECTOR(*xs)[u] + hgap) { VECTOR(*xs)[v] = VECTOR(*xs)[u] + hgap; } } } /* Follow the alignment */ w = (long int) VECTOR(*align)[w]; } while (w != v); return IGRAPH_SUCCESS; } #undef IS_INNER_SEGMENT #undef IS_DUMMY #undef X_POS #ifdef SUGIYAMA_DEBUG #undef SUGIYAMA_DEBUG #endif