Adventures in Abstraction: Reachability in Hierarchical Drawings
Panagiotis Lionakis Giacomo Ortali Ioannis G. Tollis
cs.DS cs.HC










P. Lionakis et al.



Computer Science Department, University of Crete, GREECE {lionakis,tollis}@csd.uoc.gr
 Tom Sawyer Software, Inc. Berkeley, CA 94707 U.S.A

 University of Perugia
giacomo.ortali@gmail.com




Adventures in Abstraction: Reachability in Hierarchical Drawings
    Panagiotis Lionakis1,2  Giacomo Ortali3Ioannis G. Tollis1,2
    date
================================================================




We present algorithms and experiments for the visualization of directed graphs that focus on
displaying their reachability information. Our algorithms are based on the concepts of the path and channel decomposition as proposed in the framework presented in <cit.> and focus on showing the existence of paths clearly.  In this paper we customize these concepts and present experimental results that clearly show the interplay between bends, crossings and clarity.   Additionally, our algorithms have direct applications to the important problem of showing and storing transitivity information of very large graphs and databases. Only a subset of the edges is drawn, thus reducing the visual complexity of the resulting drawing, and the memory requirements for storing the transitivity information.
Our algorithms require almost linear time, O(kn+m),  where k is the number of paths/channels, n and m is the number of vertices and edges, respectively.  They produce progressively more abstract drawings of the input graph.  No dummy vertices are introduced and the vertices of each path/channel are vertically aligned.










§ INTRODUCTION

The visualization of directed (sometimes acyclic) graphs has many applications in several areas of science and business. Such graphs often represent hierarchical relationships between objects in a structure (the graph).  In several applications, such as graph databases and big data, the graphs are very large and the usual visualization techniques are not applicable.  In their seminal paper of 1981, Sugiyama, Tagawa, and Toda <cit.> proposed a four-phase framework for producing hierarchical drawings of directed graphs. This framework is known in the literature as the Sugiyama framework, or algorithm. Most problems involved in the optimization of various phases of the Sugiyama framework are NP-hard.  In <cit.> a new framework is introduced  to visualize directed graphs and their hierarchies which departs from the classical four-phase framework of Sugiyama and computes readable hierarchical visualizations by hiding (abstracting) some selected edges while maintaining the complete reachability information of a graph.  
In this paper we present several algorithms that follow that framework.  Our algorithms reduce the visual complexity of the resulting drawings by (a) drawing the vertices of the graph in some vertical lines, and (b) by progressively abstracting some transitive edges thus showing only a subset of the edge set in the output drawing.  The process of progressively abstracting the edges gives different visualization results, but they all have the same transitive closure as the input graph.  Notice that this type of abstraction has additional applications in storing the transitive closure of huge graphs, which is a significant problem in the area of graph databases and big data <cit.>.  We also present experimental results that show a very interesting interplay between bends, crossings, clarity of the drawings, and the abstraction of edges.

A path and a channel are both ordered sets of vertices. In a path every vertex is connected by a direct edge to its successor, while in a channel any vertex is connected to it by a directed path (which may be a single edge). The concept of channel can be seen as a generalization of the concept of path. In the literature the channels are also called chains <cit.>.

Figure <ref> shows an example of three different hierarchical drawings: part (a) shows the drawing of a directed graph G computed by Tom Sawyer Perspectives <cit.> (a tool of Tom Sawyer Software) that follows the Sugiyama framework; part (b) shows a hierarchical drawing computed by our first variant algorithm taking G as input;  part (c) shows an abstracted hierarchical drawing computed by our final variant that removes all path edges and selected transitive cross edges. Notice that in part (b) the transitive edges within each vertical path are not shown. 
Part (c) shows a hierarchical drawing where all path edges and transitive cross edges are abstracted.  The advantages of the last drawing are (i) clarity of the drawing due to the sparse representation, (ii) all path edges and transitive edges (within a path) are implied by the x and y coordinates, (iii) the drawn graph has the same transitive closure as G, (iv) it gives us a technique to store the transitive closure of G in an extremely compact data structure, and (v) a path between vertices that are on different paths (of the decomposition) can be obtained by traversing one cross edge.

  

Even though the Sugiyama framework is very popular, and many of the (sub)problems for each phase have turned out to be NP-hard, its main limitation is the fact that the heuristic solutions and decisions that are made during previous phases (e.g., crossing reduction) will influence severely the results obtained in later phases. Nevertheless, previous decisions cannot be changed in order to obtain better results.  This framework can be viewed as a horizontal decomposition of G into (horizontal) layers.  By contrast, the framework of <cit.>  and all variants presented here can be viewed as a vertical decomposition of G into (vertical) paths/channels. Most problems here are vertically contained thus reducing their time complexity. It draws either (a) graph G without the transitive path/channel edges or (b) a condensed form of the transitive closure of G. Of course, the missing incident (transitive) edges of a vertex can be drawn interactively on demand. An added advantage of this framework is that it allows (or it even encourages) the user to use his/her own paths as input to the algorithms.  This means that paths/channels that are important for specific applications can be easily visualized by vertically aligning their nodes.

The algorithms presented in our paper are variants of the path based algorithm presented in <cit.>. Namely we present seven variants (including the original one) that progressively remove edges, crossings and bends.  Each variant has its own advantages and disadvantages that can exploited in various applications. Furthermore, due to its flexibility, new variants can be created based on the needs of specific applications. We also present experimental results that further demonstrate the power of edge abstraction and their impact on the number of bends, crossings, edge bundling, etc.  Notice that the above variants can be easily modified to work using the concepts of channel decomposition of a DAG and of channel graph as described in <cit.>.

Our paper is organized as follows: the next section presents necessary knowledge, including a brief description of the basic concepts of the path based algorithm of <cit.>. In Section 3 we present the variants that are based on the path based algorithm and the metrics of our experiments. Section 4 presents the experimental results and offers a comparison of the pros and cons of each variant with respect to bends, crossings, and clarity. In Section 5 we present our conclusions and interesting open problems.




§ OVERVIEW OF THE PATH BASED FRAMEWORK



The Path Based Hierarchical Drawing Framework exploits a new approach to visualize directed acyclic graphs that focus on their reachability information <cit.>.  This framework is orthogonal to the Sugiyama framework in the sense that it is a vertical decomposition of G into (vertical) paths/channels.  Most problems are vertically contained thus reducing their time complexity. The vertices of a graph G are partitioned into paths, called a path decomposition and the vertices of each path are drawn vertically aligned. It consists of only two steps: (a) the cycle removal step (if the graph contains directed cycles) and (b) the hierarchical drawing step. 

For the purposes of reachability we propose that Step (a) follows a simple approach: compute the Strongly Connected Components (SCC) of G in linear time and cluster and collapse each SCC into a supernode. Clearly, the resulting graph will be acyclic. This approach has been used in previous papers for various applications, see for example <cit.>.

Regarding Step (b), the path decomposition may be application defined, user defined or automatically computed by an algorithm.  There are several algorithms that compute a path decomposition of minimum cardinality <cit.>. For the rest of this paper, we will assume that the path decomposition is an input to the algorithm along with G.  We use an algorithm that computes a path based hierarchical drawing given a DAG G=(V,E) and a path decomposition S_p of G, see <cit.>. Due to space limitations we describe the algorithm and relevant results in the Appendix.



A path decomposition of G is a set of vertex-disjoint paths S_p= {P_1,...,P_k} such that every vertex v∈ V belongs to exactly one of the paths of S_p. A path P_i∈ S_p is called a decomposition path. The path decomposition graph of G associated with a path decomposition S_p is a graph H=(V,A) obtained from G by removing every edge e=(u,v) that connects two vertices on the same decomposition path P_i∈ S_p that are not consecutive in the order of P_i. An edge of H is a cross edge if it is incident to two vertices belonging to two different decomposition paths, else it is a path edge. Graph H is obtained from G by removing some transitive edges between vertices in a same path. A path based hierarchical drawing of G given S_p is a hierarchical drawing of H where two vertices of V are placed in a same x-coordinate if and only if they belong to a same decomposition path P_i∈ S_p. Algorithm PB-Draw computes a path based hierarchical drawing of G. Thus we can read and understand correctly any reachability relation between the vertices of G by visualizing H, as shown in Section <ref> of the Appendix.




 
Using a path decomposition with a small cardinality may improve the performance of our algorithm in terms of area, bends, number of crossings and computational time. As discussed at the beginning  of this section, computing such a minimum size path decomposition is a well known problem and it provides a great advantage to this framework. Also, the use of the path decomposition concept adds flexibility to the framework, since the paths can be user defined or application specific. The visibility of such important/critical paths is extremely clear in our drawings, since they are all vertically aligned. 
 



§ VARIANTS, METRICS, AND DATASETS



In this section we present the variants of Algorithm <ref> (see Appendix) that we used for our experiments and the metrics that we considered. We performed two types of experiments: (a) based on 
measurements over datasets with respect to the number of bends and crossings (Variant 0 and Variant 1) and (b) based on edge abstraction (Variant 2, Variant 3, Variant 4, Variant 5, and Variant 6).


All variants use edge bundling as described by Lemma <ref> of Section <ref> of the Appendix. Refer to Figure <ref>. Namely, all edges that start from vertices of a decomposition path P and go into the same target vertex v bend at the same point. All such edges use the same straight line segment from the bend to vertex v. For example, we bundle edges (21,30) and (28,30) by bending them at the same point and by overlapping them from this point to the target vertex, which is vertex 30. Similarly we do the same for edges (4,28) and (20,28). This type of edge bundling is very useful in the sense that it reduces the total number of bends and crossings, and it reuses some portions of edges. 
















 §.§ Variants
 We present now a suite of drawing techniques, our variants, that are based on Algorithm <ref>. Our variants can be further customized depending upon the requirements of an application or a user.


    
  ∙ Variant 0: This variant is precisely the same as our baseline, Algorithm <ref>. See, for example, Figure <ref>.
    
  ∙ Variant 1: We denote by jumping cross edge an edge e=(u,v) such that |X(v)-X(u)|>1. In this variant we place a bend on every jumping cross edge of Γ. Refer Figure <ref>, where, for example, the jumping cross edge e=(7,10) has a bend.
    
  ∙ Variant 2: For every vertex u we abstract edge e_1=(u,v) if there exists an edge e_2=(u,v') such that v' and v are in the same decomposition path P and v' precedes v in the order of P (edges have common source node). Refer to Figure <ref>, where, for example, e_1=(2,10) and e_2=(2,6). 
    
  ∙ Variant 3: For every vertex v we abstract the edge e_1=(u,v) if there exists an edge e_2=(u',v) such that u' and u are in the same decomposition path P and u precedes u' in the order of P (edges have common target node). Refer to Figure <ref>, where, for example, e_1=(21,30) and e_2=(28,30).
    
  ∙ Variant 4: Apply the removal of Variant 2 and Variant 3. Refer to Figure <ref>, where we removed both (2,10) and (21,30).


 


 
 
 

 §.§ Final Abstraction


An important aspect of our work is the preservation of the mental map that can be expressed by the reachability information of a DAG. Since the nodes in each path of the decomposition are vertically aligned, drawing the path edges does not add much information to the mental map of the user.  Hence their removal from the drawing will reduce the number of crossings and the number of edges drawn. Toward to that, we propose an extended abstraction drawing model generated as a combination of the aforementioned variants as shown in Figure <ref> and <ref>.
The main purpose of this abstraction is that we want to retain the visual reachability while minimizing the visual complexity of the drawing. For instance, in our variants as stated in previous sections, paths can be either application based e.g., critical paths or user defined.  Consider Variant 0 the path edges can be removed from the drawing since their existence is implied by the fact that they share the same x-coordinate. We refer to this variant as Variant 5.
Please notice that we do not remove any number of random edges in order to create less complex drawings of the same graph but rather we use the unique characteristics of the drawing which may also be application depended. We can further reduce the total number of edges drawn, and as a result the number of crossings, by using this abstraction in combination with Variant 4 to create a more abstracted drawing, called Variant 6. Therefore, we define the following two variants:

    
  ∙ Variant 5: These drawings are obtained from the drawings of Variant 0 by removing all path edges (see Figure <ref>).
    
  ∙ Variant 6: These drawings are obtained from the drawings of Variant 4 by removing all path edges (see Figure <ref>).


 




The following theorem is proved in Section <ref> of the Appendix.

 
     Let G be a DAG with n vertices and m edges, let S_p be a path decomposition of G and let k be the cardinality of S_p. It is possible to compute the drawings Γ_1 according to Variant 1 in O(n+m) time and the drawings Γ_2, Γ_3, Γ_4, Γ_5, and Γ_6 according to Variant 2, Variant 3, Variant 4, Variant 5, and Variant 6, respectively, in O(mk) time.



 §.§ Metrics and Datasets

The set of DAGs that was used in the experiments contains five Datasets (DAGs) which were produced in a controlled fashion in order to have a number of nodes and edges, as a factor of the density of the graph. DAG 1 is one of the DAGs that was used to illustrate Algorithm <ref> in <cit.>. Table <ref> in the Appendix gives a summary for each DAG.



  §.§.§ Metrics for the Experimental Results.
 Our analysis aims to evaluate the performance of the various variants of the basic algorithm for each of the aforementioned DAGs. To this end, we use the following:


  ∙ Number of edges drawn in the drawing.

  ∙ Number of cross edges drawn in the drawing.

  ∙ Number of bends.

  ∙ Number of crossings.

  ∙ Execution time:  is the average execution time for producing each drawing.



  



§ ANALYSIS OF THE PERFORMANCE


In this section we analyze the results of the experiments presented in this paper.  We remark that the variants and experiments are described for the path based framework, but they can be used with the channel based framework as well.

Table <ref> shows the performance, Execution time (ms), of the Java implementation  of our suite of drawing solutions as produced by Tom Sawyer Software TS Perspectives <cit.>. We do not report the execution times of Variant 5 and Variant 6 since they are similar to the execution times of Variant 0 and Variant 4, respectively. We observe that our variants produce hierarchical drawings suitable for large datasets since the reachability information can be seen with little effort while the execution time to produce these results is rather small.

The first figure reflects the the number of edges drawn for each of the variants over the five DAGs illustrated in Figure <ref>. Similar to that,  Figures <ref>, <ref>, and <ref> show the results regarding the number of cross edges drawn, bends and crossings respectively for each of the variants. 











First we discuss the number of edges drawn by our variants. By construction Variant 0 and Variant 1 draw exactly the same set of edges as it is evidenced by Figures <ref> and <ref>. The same figures show that Variant 2 and Variant 3 are similar in the number of edges they draw. Clearly, the number of edges drawn by Variant 4 is significantly lower than the number of edges drawn by the other variants. This effect is emphasized in Figure <ref>, where the number of cross edges drawn by Variant 4 for DAG 5 is about one sixth of the number of cross edges drawn by Variant 0 and Variant 1. Finally, we focus on Variant 5 and Variant 6. The sets E_5 and E_6 of the edges that Variant 5 and Variant 6 draw is a subset of the sets of edges E_0 and E_4 that Variant 0 and Variant 4 draw, respectively. The cardinality of E_5 and E_6 is much smaller than the cardinality of E_0 and E_4 if most of the edges drawn by Variant 0 and Variant 4 are path  edges, as shown in Figure <ref> for DAG 2. Variant 5 and Variant 6 by construction draw the same set of cross edges of respectively Variant 0 and Variant 4.


As can be seen in Figure <ref> the drawings computed by Variant 2,  Variant 3, and Variant 4 have very few bends on the average. For example, DAG 5 in Variant 3 has 270 edges and the corresponding drawing has only 38 bends, i.e., we have 0.14 bends per edge.
On the other hand, the drawing computed by Variant 1 is less efficient in placing bends. Refer again to DAG 5: in Variant 1 this DAG has 397 edges and the corresponding drawing has 88 bends, i.e, we have 0.22 bends per edge. The number of bends in drawings computed by Variant 5 and  Variant 6 and respectively Variant 0 and  Variant 4 is the same, since the path edges are drawn straight line in all our variants.
The number of crossings is influenced heavily by the number of edges drawn and the extent of edge bundling.  Figure <ref> shows that the performance of Variant 1 is slightly better than that of Variant 0. This can be explained by the fact that in Variant 1 there are more bundles of edges and this naturally decreases the number of crossings. The other variants all have much better performance than Variant 0 and Variant 1 because the corresponding drawings contain significantly fewer edges. Figure <ref> shows that the number of crossings is almost the same in the drawings of Variant 5 and  Variant 6 and Variant 0 and  Variant 4, respectively. This result is very important, since it is an evidence of the fact that path edges participate in a few crossings and, therefore, the decomposition paths can be visualized very clearly in our drawings.  










§ CONCLUSIONS AND OPEN PROBLEMS

We presented a set of variant algorithms that attempt to draw DAGs hierarchically with few bends and crossings, and by abstracting edges in order to improve the clarity of the drawings. 
Our study assumes that the path decomposition is given as part of the input, or a minimum size decomposition is computed by one of the known algorithms.  However, it is interesting to study the problem of computing a path decomposition and placement of the paths of G which implies the minimum number of jumping cross edges in our drawings. The use of such a decomposition and placement would considerably reduce the number of edges drawn, bends, and crossings in our drawings.  Another open problem is the development and implementation of some compaction strategies, which would improve the readability of our drawings and reduce their height. Finally, it would be important to comprehend human understanding issues related to the removal of some transitive edges and increasing reachability comprehension.






splncs04
 


CHAPTER: APPENDIX







§ ALGORITHM PB-DRAW



The following algorithm and theorems and lemmas are from <cit.>


	
	Let G be a DAG and let S_p be a path decomposition of G. The path based graph H of G associated with S_p have the same reachability properties of the G.








Let Γ be a drawing computed by PB-Draw. The following Lemmas and Theorem are proved in <cit.>.


	
	Any edge e=(u,v) does not intersect a vertex different from u and v in Γ.

The following lemma shows how Algorithm PB-Draw bundles the edges. We apply this technique of bundling in every variant of PB-Draw that we introduce in the next sections; for this reason, we better describe it in Section <ref>.

	
	Let e=(u,v) and e'=(u',v') be two edges drawn with a bend in Γ. Their bends are placed in the same point if and only if u and u' are in the same decomposition path and v=v'.



Finally, the following theorem shows that Algorithm PB-Draw computes efficiently path hierarchical drawings with a very small area, number of bends and number of bends per edge.

	
	Let G be a DAG with n vertices and m edges, let S_p be a path decomposition of G and let k be the cardinality of S_p. Algorithm PB-Draw computes a path based hierarchical drawing Γ of G given S_p in O(mk) time. Furthermore, Area(Γ)=O(kn) and every edge has at most one bend.




§  PROOF OF THEOREM <REF>



In this section we prove Theorem <ref>. First of all, we study the case of the drawing Γ_1 computed according to Variant 1. We can compute Γ_1 by simply ignoring Step 2 of Algorithm <ref>, which requires O(mk) time, and placing a bend in every jumping cross edge. This operation and all the other operations of Algorithm <ref> require O(n+m) time. Hence, we can compute Γ_1 in O(n+m) time. We now focus our attention on Variants 2-6.


Let G be a DAG and let S_p be a path decomposition of G having cardinality k. Let Γ_0 be a drawing of G computed by Algorithm <ref>. We present Algorithm Compute-V2, which describes how it is possible to compute a drawing Γ_2 according to Variant 2 given Γ_0. The algorithm  takes as input a path decomposition S_p of G and Γ_0 and it gives as output Γ_2. For every vertex of Γ_0 the algorithm checks the adjacent vertices and, for every path P_i, it stores the one having minimum y-coordinate  in an array A_k. Then it removes all edges (v,w) such that Y(w) is not stored in A_k.
 
 
 Algorithm Compute-V2 requires linear time, since it visits every vertex once and every edge twice and, for every visit, it performs a constant number of operations.
 
 It is easy to see that we can define two similar algorithms in order to compute drawings Γ_3 and Γ_4 according to  Variant 3 and Variant 4, respectively, by taking Γ_0 and S_p as input. Therefore, given Γ_0 it is possible to compute Γ_2, Γ_3 and Γ_4 in O(n+m) time. It is also true for the drawings Γ_5 and Γ_6 according to Variant 5 and Variant 6, since they can be computed from Γ_0 and Γ_4 by removing the path edges. Moreover, notice that Γ_0 can be computed in O(km), according to Theorem <ref>. Hence, we can compute Γ_2, Γ_3, Γ_4, Γ_5, Γ_6 in O(mk).  




 
 
   





§ EXPERIMENT DETAILS

Here we report the experimental details. The experiments  run on a single machine having an 3.1 Ghz i7 dual core, 16 GB main memory and 500GB flash storage disk space. We report the average time of 5 runs per DAG.


