Introduction
|
|  Yüklə 3.14 Mb.
|
The Sugiyama HeuristicReal world graph applications data often exist already in different forms or formats. Hence, the proposed dynamic drawing system shall include a modified Sugiyama heuristic proposed by Eiglsperger, Siebenhaller, and Kaufmann (2005) for generating graph data from existing graph data. This section shall review algorithms in the Sugiyama heuristic. As described in chapter 2, the Sugiyama heuristic comprises four steps. The first step is to remove any cycles or loops if applicable. Several algorithms have been proposed for solving this step--the feedback arc set problem. Though the brute force DFS (Depth First Search) or BFS (Breath First Search) is simple, it does not provide a reliable result (Stedile, 2001). The penalty graph proposed by Finocchi (2003) can provide good results but its performance is quadratic O (|V| * |E|). On the other hand the Greedy-Cycle-Removal algorithm (Eades et al., 1993) provides a good result and its runtime is linear. The constrained dynamic framework shall utilize the Greedy-Cycle-Removal algorithm for reversing temporary cycles if any. Since the context of the Greedy-Cycle-Removal algorithm has been described in chapter 2, this section presents a pseudocode of the Greedy-Cycle-Removal algorithm. Table 5 shows the pseudocode. Table 5. Pseudo code of the Greedy-Cycle-Removal algorithm (Eades et al., 1993)
For the second step, layer assignment, Longest Path is simple and has linear runtime but no limit on the width, so it could produce a layer with a large width. On the other hand, the Coffman-Graham algorithm (Coffman & Graham, 1972) also runs in linear but has a width limit with no height limit. According to Battista et al. (1999), in real applications vertices can have different shapes and sizes so the minimizing the width is more important than minimizing the height. Hence, constrained dynamic graph drawing frameworks shall utilize the Coffman-Graham layering algorithm (Coffman & Graham, 1972) for assigning vertices into layers. Table 6 shows the pseudocode of the Coffman-Graham algorithm. Table 6. Pseudocode of the Coffman-Graham algorithm (Battista et al., 1999)
The third step in the Sugiyama heuristic is to reduce the number of edge crossings. As mentioned in chapter 2, this step employs an approach called the layer-by-layer sweep algorithm. The layer-by-layer sweep algorithm starts from the top and moves through each layer. At each layer the one-sided two-layered crossing reduction shall be computed. Once reaching the bottom, the algorithm moves upward and performs the one-sided two-layered crossing reduction algorithm at each layer. This process is repeated until the algorithm cannot find fewer edges crossings and the algorithm is terminated. As discussed in the barrier section, in real world applications the algorithm can sometimes run a long time before reaching the optimal solution. A solution to this problem used by most commercial products is to provide a maximum allowable iterations value. The algorithm is terminated when either an optimal solution is found or the predefined maximum allowable iterations value is reached. The pseudocode of the layer-by-layer sweep algorithm is displayed in Table 7. Table 7. A modified version of the pseudocode of the layer-by-layer sweep algorithm (Battista et al., 1999)
The one-sided two-layered crossing reduction problem has been studied extensively in the past decade. Results from experiments using real world graph data (Marti & Laguna, 2003; Junger & Mutzel, 1997) show that the barycenter heuristic often outperforms other algorithms. Hence, the barycenter algorithm will be employed in the Sugiyama heuristic. The pseudocode of the barycenter algorithm for the one-sided two-layered crossing reduction problem is displayed in Table 8. Table 8. Pseudocode of the barycenter algorithm (Battista et al., 1999)
Step 4 in the Sugiyama heuristic is assigning coordinates for vertices. As mentioned in the limitation of this thesis, the constrained on-line graph framework (COGF) will not take into account the actual sizes and shapes of real world vertices. All vertices will have the size and a shape of circle. A potential future work could take the size and shapes of vertices into account when computing the vertices coordinates. Though the constrained graph framework does not assign the coordinates for vertices and edges during the process of importing graph data into the framework, the framework shall utilize the coordinate assignment algorithm in the visualization module in computing the vertex coordinates. One of the well known algorithms for assigning the coordinates is proposed by Gansner et al. (1993). Gansner et al. (1993) defined the assignment of x coordinates for vertices as an integer optimization problem, as shown in Figure 17. To solve this problem the authors transform the problem into a linear program and use simplex programming to solve this problem. Though simplex network programming has not been proved running in linear, the experiment by Gansner et al. (1993) shows that simplex network programming can run fast in real world applications. The pseudocode of the coordinate assignment problem is described in Table 9. 
Figure 17. Integer program for coordinate assignment Table 9. The pseudocode of the coordinate assignment problem (Ganser et al., 1993)
|
E }