Algorithm For Drawing Directed Acyclic Graphs
AssigneeFair Isaac Corporation
InventorsKashyap Babu Rao Kolipaka, Navin Doshi, Gaurav Chhaparwal
Life of this patent
Estimating the term…
Abstract
A system and method for drawing directed acyclic graphs is disclosed. In particular, an algorithm, as implemented in a method and system, to aesthetically layout directed acyclic graphs is presented. The algorithm includes methods to reduce the number of edge crossings and increase the number of straight edges in such drawings. The algorithm keeps short and straight edges wherever possible and gives preference to vertical edges. It also provides an edge-crossing reduction heuristic to refine the layout obtained after standard median heuristic layout, and further provides a method to focus on important paths in the graph through layout.
Claims24
A computer-implemented method for drawing directed acyclic graphs, the method comprising:
- receiving, in a computing system, information representing a directed acyclic graph, a computer processor of the computing system configured for:
- generating a layout of the directed acyclic graph, the layout comprised of one or more subgraphs, each subgraph comprising two or more nodes and edges that connect pairs of nodes, the nodes and edges being defined in x- and y-coordinates;
- reducing the number of edge crossings in the layout of the directed acyclic graph;
- straightening the edges of the layout of the directed acyclic graph;
- compacting one or more subgraphs along x-coordinate axis to generate a compacted DAG layout;
- and
- assigning new y-coordinates to the nodes of the one or more subgraphs such that the nodes do not overlap in the y-coordinate to generate a new layout of directed acyclic graph.
A method, executable by a computer processor, for drawing directed acyclic graphs, the method comprising:
- generating a layout of the directed acyclic graph, the layout comprised of one or more subgraphs, each subgraph comprising two or more nodes and edges that connect pairs of nodes, the nodes and edges being defined in x- and y-coordinates;
- reducing the number of edge crossings in the layout of the directed acyclic graph;
- straightening the edges of the layout of the directed acyclic graph;
- compacting the nodes of the one or more subgraphs along x-coordinate axis to generate a compacted DAG layout;
- and
- assigning new y-coordinates to the nodes of the one or more subgraphs such that the nodes do not overlap in the y-coordinate to generate a new layout for directed acyclic graph.
A computer-implemented method for drawing directed acyclic graphs, the method comprising:
- receiving information representing a directed acyclic graph;
- generating a layout of the directed acyclic graph, the layout comprising two or more nodes and edges that connect pairs of nodes, the nodes and edges being defined in x- and y-coordinates;
- reducing the number of edge crossings in the layout of the directed acyclic graph;
- straightening the edges of the layout of the directed acyclic graph;
- compacting along x-coordinate axis to generate a compacted DAG layout;
- and
- assigning new y-coordinates to the nodes of the compacted DAG layout such that the nodes do not overlap in the y-coordinate, to generate a new layout for directed acyclic graph.
A method, executable by a computer processor, for focusing on interesting paths in the directed acyclic graphs through layout, the method comprising:
- dividing interesting paths into one or more path-clusters;
- dividing the nodes of the interesting paths into node clusters;
- determining an order in which to lay out the node clusters.
Dependencies are inferred from the claim text.