Abstract:
A candidate graph crossing point counter can be initialized. Level pairs can be sorted in descending order according to a number of connections between the level pairs. Evaluation of the candidate graph can progress according to the order of the level pairs so that those pairs likely to have the greatest number of connections are processed first. While the candidate graph crossing point counter is at an intermediate value and before a crossing point total is calculated for the candidate graph, it can be determined that the intermediate value is at least as great as a crossing point total of a best current graph for the directional graph. Calculation of the candidate graph crossing point total can be halted at the intermediate value. The candidate graph can be discarded from a possibility of being a minimized graph during a determination of a graph drawing for the directional graph.

Description:
BACKGROUND 
       [0001]    The present invention relates to the field of graph rendering and, more particularly, to optimizing edge crossing computations when creating a drawing of a directed graph having a minimum number of edge crossings. 
         [0002]    One objective of software that draws directed graphs or digraphs is to produce a graph that is easy to comprehend and that is aesthetically pleasing. One factor that influences the clarity of a directed graph is a number of crossings of edges between nodes, where fewer crossings generally results in superior clarity. Minimizing a number of crossings of edges, however, is a difficult mathematical problem, which is non-deterministic (e.g., NP-hard) in nature. Solutions (e.g., Sugiyama algorithm) to minimize crossings of edges use heuristic methods to refine graph structures, which are generally easy to compute and result in graphs with acceptably low numbers of edge crossings. One of the time consuming aspects of this type of approach is to determine the total number of edge crossings for the entire graph, which is repeated for a large number of possible graphs, referred to as candidate graphs. 
         [0003]    The Sugiyama algorithm initially changes a graph into a “proper” hierarchical graph that has no cycles, and only has edges between adjacent levels. That is, cycles are removed from the graph by reversing and marking edges that cause cycles and inserting dummy nodes to ensure that no edges span more than one node. Each pair of levels in the layered graph is taken sequentially and a connection matrix is calculated, with which a number of crossings can be computed. A count for each pair of levels is accumulated and a total of crossing counts for each level pair is taken as the total number of edge crossings for the graph. 
         [0004]    The Sugiyama algorithm includes steps that perform sweeps down and up the layered graph, which render nodes at each level in an attempt to obtain a better solution with a reduced number of crossings. If the number of edge crossings for a candidate graph is lower than a current best graph with the lowest number of crossings, then the candidate graph becomes the current best graph. When optimizations are finished, a current best graph is used as the graph with a minimized number of crossings. 
         [0005]    Currently used algorithms calculate a number of crossings for an entire graph before the comparison between the candidate and current best graph is evaluated. This can be inefficient, as calculations for the total number of crossings of a candidate graph are performed, even after it is mathematically apparent that the candidate graph will include more crossings than the current best graph. 
     
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         [0006]      FIG. 1  is a schematic diagram of a system for drawing graphs having a minimized number of edge crossings in accordance with an embodiment of the inventive arrangements disclosed herein. 
           [0007]      FIG. 2  is a flow chart of a method for drawing graphs having a minimized number of edge crossings in accordance with an embodiment of the inventive arrangements disclosed herein. 
       
    
    
     DETAILED DESCRIPTION 
       [0008]    The disclosure determines as early as possible during a crossing point computation whether a candidate graph is likely to have fewer crossing points than a current best graph. As a candidate crossing count is determined, it is compared against a current best graph count. Processing stops immediately when the candidate count equals or exceeds the current best graph count, which saves needless processing since the candidate graph will not replace the current best graph. 
         [0009]    In one embodiment, the pairs of levels can be ordered, so that those level pairs likely to have the most crossing points are calculated first for each candidate graph. For example, it can be assumed that for most acyclic, layered graphs, most edge crossings will occur in those pairs of levels in which there are the most connections. Thus, the level pairs can be ordered by connection quantity. 
         [0010]    As will be appreciated by one skilled in the art, the present invention may be embodied as a system, method or computer program product. Accordingly, the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, the present invention may take the form of a computer program product embodied in any tangible medium of expression having computer usable program code embodied in the medium. 
         [0011]    Any combination of one or more computer usable or computer readable medium(s) may be utilized. The computer-usable or computer-readable medium may be, for example but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, device, or propagation medium. More specific examples (a non-exhaustive list) of the computer-readable medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CDROM), an optical storage device, a transmission media such as those supporting the Internet or an intranet, or a magnetic storage device. Note that the computer-usable or computer-readable medium could even be paper or another suitable medium upon which the program is printed, as the program can be electronically captured, for instance, via optical scanning of the paper or other medium, then compiled, interpreted, or otherwise processed in a suitable manner, if necessary, and then stored in a computer memory. In the context of this document, a computer-usable or computer-readable medium may be any medium that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. The computer-usable medium may include a propagated data signal with the computer-usable program code embodied therewith, either in baseband or as part of a carrier wave. The computer usable program code may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc. 
         [0012]    Computer program code for carrying out operations of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on the user&#39;s computer, partly on the user&#39;s computer, as a stand-alone software package, partly on the user&#39;s computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user&#39;s computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). 
         [0013]    The present invention is described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. 
         [0014]    These computer program instructions may also be stored in a computer-readable medium that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable medium produce an article of manufacture including instruction means which implement the function/act specified in the flowchart and/or block diagram block or blocks. 
         [0015]    The computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. 
         [0016]      FIG. 1  is a schematic diagram of a system  100  for drawing graphs having a minimized number of edge crossings in accordance with an embodiment of the inventive arrangements disclosed herein. 
         [0017]    In system  100 , a directed graph  141  can be processed by a graph drawing engine  122  in order to render  142  a drawn graph  144 . Example  140  provides a sample illustration of this and is not intended to limit the disclosure in any fashion. The drawn graph  144  can include a set of nodes  145  (e.g., Nodes A-E in drawn graph  144 ), which are connected by a set of directed edges  146  denoting various relationships between the nodes  145 . 
         [0018]    The graph drawing engine  122  can utilize a heuristic approach that involves an acyclic layered graph representation of the directed graph  141 . For example, in one embodiment, graph drawing engine  122  can produce drawn graph  144  using a modified Sugiyama algorithm. The modification is that a crossing minimizer  125  can be configured to reject candidate graphs as soon as a crossing point count exceeds a current crossing point count of a current best graph. In one embodiment, layer pairs can be ordered so that those likely to have the greatest number of edge crossings are processed first. This minimizes a number of layer pairs that need to be evaluated in many cases. 
         [0019]    Sample code  160  describes a stage that is performed once per graph rendering. Code  160  represents one contemplated manner of ordering layered pairs so that those layered pairs having a highest quantity of edge crossings are processed first. Code  160  assumes that those layered pairs having the greatest number of connections between nodes are the layers most likely to have the greatest number of edge crossings. Code assumes that a directed graph  141  is internally represented as a list of pairs of levels. That is, before code  160  executes, a graph transformer  124  can convert a directed graph  141  into an acyclic, layered graph, such as a (k, 2) partite graph. Before code  160  executes, each level can contain a set of nodes in an initially indeterminate order. 
         [0020]    According to sample code  160 , a clone of each list of level pairs can be created. For each level pair of the cloned list of level pairs, a number of connections between the two levels can be counted. A number of connections between the two levels can then be assigned to each level pair. The level pairs can be sorted or ordered in descending order from a greatest number of connections to a least number of connections. 
         [0021]    In one embodiment, an enhancement to code  160  can be included so that a hierarchical graph does not include a first level pair in the list of sorted level pairs. In other words, the edge crossings between the root node and the first level of nodes are not counted, because no edge crossings can exist between the root node and the first level of nodes. 
         [0022]    Sample code  165  can execute whenever a graph layout algorithm (contained in crossing minimizer  125 ) needs to determine whether a candidate graph is better (i.e., have less edge crossings) than a current best graph. As shown, a count of edge crossings for the candidate is to accumulate, until the count equals or exceeds a crossing count of the current best graph. At this point, a counting of the edge crossings for the candidate is halted, and the candidate is discarded since the current best graph has a lower crossing count than the discarded candidate does. 
         [0023]    More specifically, code  165  shows that a total number of crossings for a candidate can be initialized at zero. For each ordered (as per code  160 ) level pair in the layered graph, a number of crossings between the two levels can be performed. The crossings per level pair can be added to the total number of crossings for the candidate. If the total number of crossings exceeds the number of crossings for the best graph, the for-loop can be immediately exited (and the candidate can be discarded). Otherwise, the for-loop can continue for the next ordered level pair. 
         [0024]    Once a crossing minimizer  125  completes and determines a best graph (one having a minimum number of edge crossings), a position adjuster  126  can optionally execute. The position adjuster  126  can adjust or manipulate a horizontal position of each node  145  to reduce a length of edges for aesthetic purposes. Graph drawer  127  can then draw the graph (producing drawn graph  144 , for example). 
         [0025]    The graph drawing engine  122  can be a software/firmware component  120  executed on a computing device  110  including hardware  112 . In one embodiment, engine  122  can be a component of a graphic editor  130 . The software/firmware  120  can be stored in a non-volatile memory  117  or a volatile memory  116  connected to one or more processors  114  via a bus  115 . The processer  114  can read and execute programmatic instructions of the software/firmware  120 . The programmatic instructions can include a variation of sample code  160  and sample code  165 . 
         [0026]    It should be appreciated that the sample code  160 ,  165  shown in system  100  is for illustrative purposes only and is not to be construed as a limitation of the disclosure. Derivatives and adjustments to the code  160 ,  165  are expected for different implementation situations. A salient characteristic of code  160  is an ordering of level pairs before processing, where the ordering is from highest expected edge crossing to lowest. A salient characteristic of code  165  is that a count of the number of edge crossings of a candidate graph is halted at an intermediate stage (before a total count of the edge crossing is determined) whenever an intermediate crossing count is at least as high as a count associated with a current best graph. 
         [0027]      FIG. 2  is a flow chart of a method  200  for drawing graphs having a minimized number of edge crossings in accordance with an embodiment of the inventive arrangements disclosed herein. Method  200  can be performed in context of system  100 . 
         [0028]    Method  200  can begin in step  205 , where a directed graph can be identified. In step  210 , an acyclic layered graph representation of the directed graph can be created. In one embodiment, cycles can be removed by reversing and marking edges that cause the cycles. Dummy nodes can be inserted to ensure that no edges span more than one node. Hence, the acyclic layered graph can be a (k, 2)-partite graph. That is, the graph can include k layers and each layer can have edges only to the layers adjacent to it (i.e., above and below it). 
         [0029]    In step  215 , connections between each layered pair can be counted. The layered pairs can be ordered by connection count in descending order, as shown by step  220 . In step  225 , variables for a current best graph and a current best graph (CBG) count can be initialized. The CBG count can represent a number of edge crossings present in the current best graph. 
         [0030]    A candidate graph can be determined in step  230 . In step  235 , a crossing count for the candidate graph can be initiated. In step  240 , a layered pair (starting with the ordered pair having the greatest connection count) can be processed to determine a layered pair count. The layered pair count can be added to the crossing count, as shown by step  245 . When the crossing count is less than the CBG count and when another layered pair exists for the candidate graph, the method can loop back to step  240 , where the next ordered layered pair can be processed. 
         [0031]    When in step  250 , the crossing count for the candidate graph is greater than or equal to the CBG count, the method can proceed from step  250  to step  260 . This exit can occur before crossing counts for all layered pairs is determined, since the candidate graph will not replace the current best graph regardless of the additional processing due to the crossing count of the candidate graph at this intermediate processing point. 
         [0032]    After all layered pairs are processed or an exit occurs, step  260  can execute. When the candidate count is less than the CBG count, then the best current graph can be set to the candidate graph, as shown by step  265 . Otherwise, the method can proceed to step  270 , where a check for another candidate graph can be made. When other candidate graphs are to be evaluated, the method can proceed from step  270  to step  230 , where a next candidate graph can be determined and processed. Once all candidate graphs are processed, an optional adjustment of the current best graph can be made to minimize edge length, as shown by step  275 . The current best graph, which is a graph having a minimized number of crossing edges, can be drawn in step  280 . 
         [0033]    The flowchart and block diagrams in the  FIGS. 1-2  illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which includes one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.