Techniques For Drawing Curved Edges In Graphs
AssigneeFair Isaac Corporation
InventorsGaurav Chhaparwal, Navin Doshi, Kashyap Babu Rao Kolipaka
Life of this patent
Estimating the term…
Abstract
A system and method for drawing curved edges in graphs is disclosed. The system and method implement a heuristic algorithm to draw curved edges in graphs using Bezier curves. The algorithm assumes that every pair of nodes has a unique edge between them. It also assumes that the graph is “leveled,” which means the nodes can be grouped such that all the nodes in a group are laid out at the same y location in a vertical layout. Any generic graph can be converted to a leveled graph, so the techniques described in the algorithm are applicable to any graph.
Claims22
A computer-implemented method for drawing curved edges in graphs, the method comprising:
- receiving input information into a computer processing system, the input information representing a plurality of nodes and edges related to a graph;
- computing, using a computer processor of the computer processing system, one or more bridges of the graph;
- computing, using the computer processor of the computer processing system, candidate curves to depict the graph bases on the one or more bridges;
- computing, using the computer processor of the computer processing system, a cost function for the graph to iteratively evaluate two or more candidate curves, the cost function being based on, for each curve of the two or more curves, an intersection with the plurality of nodes, an intersection with the edges, a number of inflection points, and a maximum distance of any point on the curve from a straight line joining end points of the curve;
- and
- determining a selected curve from the two or more curves having a lowest cost based on the cost function.
A system for drawing curved edges in graphs, the system comprising:
- a computer processor;
- and
- code implemented in a tangible medium for instructing the computer processor to:
- receive input information into a computer processor, the input information representing a plurality of nodes and edges related to a graph;
- compute one or more bridges of the graph;
- compute candidate curves to depict the graph based on the one or more bridges;
- compute a cost function for the graph to iteratively evaluate two or more of the candidate curves, the cost function being based on, for each curve of the two or more curves, an intersection with the plurality of nodes, an intersection with the edges, a bridge computed for every edge and for every level that edge crosses, a number of inflection points, and a maximum distance of any point on the curve from a straight line joining end points of the curve;
- and
- determine a selected curve from the two or more curves having a lowest cost based on the cost function.
A computer-implemented method for drawing curved edges in graphs, the method comprising:
- receiving input information into a computer processing system, the input information representing a plurality of nodes and edges related to a graph;
- computing, using a computer processor of the computer processing system, two or more curves based on the plurality of nodes and edges, for each curve in the two or more curves:
- computing one or more bridges of the graph;
- generating candidate quadratic and cubic curves based on the one or more bridges;
- and
- computing a cost function to evaluate each curve against a maximum acceptable cost for the graph;
- and
- determining a selected curve from the two or more curves having a lowest cost based on the cost function.
Dependencies are inferred from the claim text.