VISUALIZING LARGE GRAPHS

• US 20150138203A1
• Filed: 11/19/2013
• Published: 05/21/2015
• Est. Priority Date: 11/19/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nachmanson, Lev, Lee, Bongshin, Chen, Xiaoji, Holroyd, Alexander E., Henry Riche, Nathalie
• Granted Patent: US 9,299,176 B2
• Time in Patent Office: Days
• US Class Current: 345/440
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

Large graph visualization embodiments are presented which generally render and display the more important elements for a current view. To this end, a measure of importance referred to as a zoom level is assigned to the vertices and rails of a graph. Each rail is a curve segment in the graph that represents an edge or a set of edges passing through it. The rendering and displaying of a graph (or a part thereof) is done quickly, even as a user moves about the graph, and the visualization of the large graph is not so dense and so full of detail that the user becomes disoriented. In general, this is accomplished by specifying a current viewport, or a current zoom level, or both. Furthermore, the visualization is stable in that the layout of vertices and rails will be the same for the same zoom level and viewport.

Claims

1. A computer-implemented process for assigning zoom level values to vertices and rails of a graph, comprising:

using a computer to perform the following process actions;

computing and assigning zoom level values to vertices of the graph, wherein at each zoom level, vertices deemed to be the most important are assigned, in hierarchical order, a zoom level value associated with the zoom level, until at least one region of the graph associated with the zoom level has a prescribed maximum number of vertices assigned the zoom level value associated with the zoom level; and

computing and assigning zoom level values to rails of the graph, said rails each being a curve segment in the graph that represents an edge or a set of edges passing through it.

2. The process of claim 1, wherein the process action of computing and assigning zoom level values to vertices of the graph, comprises the actions of:

a) receiving a set of vertices of the graph;

b) receiving a layout of the graph comprising locations of each vertex in the received set of vertices;

c) receiving vertex importance data comprising a hierarchical list of the received set of vertices ordered from the vertex deemed to be the most important to the vertex deemed to be the least important;

d) selecting the smallest previously unselected zoom level value from a hierarchically-ordered set of zoom levels which ranges from smaller zoom level values to larger zoom level values;

e) identifying a prescribed-sized bounding region associated with the currently-selected zoom level value;

f) dividing the graph as laid-out based on the received graph layout into one or more tiles, each of which has a size corresponding to the currently-identified bounding region;

g) determining whether there are one or more vertices from the received set of vertices that have not yet been assigned a zoom level value, and whenever there are, selecting a vertex from the set of vertices that has not yet been assigned a zoom level value in an order dictated by the vertex importance data starting with the vertex not yet having an assigned zoom level value that is deemed to be the most important, yet-unselected vertex in the vertex importance data, and whenever there are no more vertices from the received set of vertices that have not yet been assigned a zoom level value, ending the process action of computing and assigning zoom level values to vertices of the graph;

h) identifying the location of a center of bounding region containing the currently-selected vertex using said received graph layout;

i) identifying the tile that the currently-identified vertex center location resides within;

j) determining whether the number of vertices whose vertex center locations reside within the currently-identified tile and who have been assigned the currently-selected zoom level value exceed a prescribed maximum vertex quota;

k) whenever the number of vertices whose vertex center locations reside within the currently-selected tile and who have been assigned the currently-selected zoom level value does not exceed the prescribed maximum vertex quota, assigning the currently-selected zoom level value to the currently-selected vertex, and repeating actions g) through I); and

l) whenever the number of vertices whose vertex center locations reside within the currently-selected tile and who have been assigned the currently-selected zoom level value exceeds the prescribed maximum vertex quota, repeating actions d) through I).

3. The process of claim 2, wherein the process action of computing and assigning zoom level values to rails of the graph, comprises the actions of:

a) receiving a set of edges of the graph;

b) selecting the smallest zoom level value from the hierarchically-ordered set of zoom levels which has not been selected in connection computing and assigning zoom level values to rails of the graph;

c) selecting vertices that are assigned the currently-selected zoom level value or a lower zoom level value;

d) identifying all edges using said graph layout that directly link a one of the currently-selected vertices to another one of the currently-selected vertices;

e) identifying up to a prescribed number of the highest ranking vertices that are also part of currently-selected vertices based on said vertex importance data, and designate the identified vertices as the top ranking vertices;

f) identifying edges of each sequence of edges using said graph layout which form the shortest, non-direct distance from a one of the currently-selected vertices to a one of the currently identified top ranking vertices;

g) routing the currently-identified edges;

h) selecting a previously unselected one of the currently-identified edges;

i) identifying the route of the selected edge;

j) identifying each curve segment in the identified edge route;

k) selecting a previously unselected one of the curve segments;

l) determining whether the route of the currently-selected curve segment corresponds to an established rail;

m) whenever it is determined the route of the currently-selected curve segment does not correspond to an established rail,

establishing the route of the currently-selected curve segment as a rail of the graph,

assigning the currently selected zoom level value to the newly established rail, and

determining whether there are any edges that are not yet part of one or more of the established rails, and whenever it is determined that there are edges that are not yet part of one or more of the established rails, repeating actions b) through n); and

n) whenever it is determined the route of the currently-selected curve segment does correspond to an established rail, repeating actions h) through n).

4. A computer-implemented process for rendering vertices and edges of a graph, comprising:

using a computer to perform the following process actions;

receiving a set of vertices of the graph, each of which comprises an assigned zoom level value;

receiving a set of rails of the graph, said rails each representing either a graph edge or a combination of portions of different graph edges, and each rail comprising an assigned zoom level value;

receiving a currently-specified viewport which specifies a portion of the graph that is to be rendered;

receiving a currently-specified zoom level; and

rendering those graph vertices and rails intersecting the currently-specified viewport whenever the assigned zoom level of the intersecting vertex or rail is less than or equal to the currently-specified zoom level.

5. The process of claim 4, wherein the process action of rendering those graph vertices and rails intersecting the currently-specified viewport whenever the assigned zoom level of the intersecting vertex or rail is less than or equal to the currently-specified zoom level, comprises the actions of:

computing a scale factor representing the ratio of a size of the currently specified viewport to a size of the smallest bounding region that contains the entire graph;

identifying each rail that intersects the currently-specified viewport and which has an assigned zoom level value that is less than or equal to the product of a prescribed size parameter and the computed scale factor;

identifying each vertex having a bounding region containing the vertex that intersects the currently-specified viewport, having an assigned zoom level value that is less than or equal to the product of the prescribed size parameter and the computed scale factor, and which is adjacent to at least one of the identified rails;

rendering the identified rails; and

rendering the identified vertices.

6. The process of claim 5, wherein the process action of rendering the identified rails, comprises the actions of:

rendering rails with a setting of no transparency whenever the rail has an assigned zoom level value that is less than or equal to the scale factor;

rendering rails with a setting of full transparency whenever the rail has an assigned zoom level value that is equal to the product of the size parameter and the scale factor; and

rendering each rail having an assigned zoom level value between the scale factor and the product of the size parameter and the scale factor to a transparency setting between no transparency and full transparency.

7. The process of claim 6, wherein the process action of rendering each rail having an assigned zoom level value between the scale factor and the product of the size parameter and the scale factor to a transparency setting between no transparency and full transparency, comprises setting the transparency setting linearly between no transparency and full transparency based on the where the assigned zoom level value falls between the scale factor and the product of the size parameter and the scale factor.

8. The process of claim 5, wherein the process action of rendering the identified vertices, comprises the actions of:

rendering a bounding region containing a vertex for each vertex having an assigned zoom level value that is less than or equal to the scale factor; and

rendering a bounding region containing a vertex for each vertex having an assigned zoom level value that is greater than or equal to the product of the size parameter and the scale factor so as to exhibit a size that varies depending a scaling parameter that ranges between 0 and 1 based on the currently-specified zoom level value wherein the scaling parameter increases as the currently-specified zoom level value decreases.

9. The process of claim 8, wherein the scaling parameter increases linearly as the currently-specified zoom level value decreases.

10. The process of claim 4, wherein the process action of rendering those graph vertices and rails intersecting the currently-specified viewport whenever the assigned zoom level of the intersecting vertex or rail is less than or equal to the currently-specified zoom level, comprises the actions of:

deeming a vertex to be intersecting the currently-specified viewport whenever a central point of a bounding region containing the vertex falls within the viewport; and

deeming a rail to be intersecting the currently-specified viewport whenever any part of the rail falls within the viewport.

11. The process of claim 10, further comprising a process action of rendering each vertex not having an assigned zoom level which is less than or equal to the currently-specified zoom level whenever a central point of a bounding region containing the vertex falls within the viewport and the vertex is a terminus of a rail having an assigned zoom level that is less than or equal to the currently-specified zoom level which intersects the currently-specified viewport.

12. The process of claim 11, further comprising rendering each vertex not having an assigned zoom level which is less than or equal to the currently-specified zoom level whenever a central point of a bounding region containing the vertex falls within the viewport and the vertex is a terminus of a rail having an assigned zoom level that is less than or equal to the currently-specified zoom level which intersects the currently-specified viewport, so as to distinguish the vertex from other rendered vertices that have an assigned zoom level which is less than or equal to the currently-specified zoom level.

13. The process of claim 12, wherein the process action of rendering each vertex not having an assigned zoom level which is less than or equal to the currently-specified zoom level whenever a central point of a bounding region containing the vertex falls within the viewport and the vertex is a terminus of a rail having an assigned zoom level that is less than or equal to the currently-specified zoom level which intersects the currently-specified viewport, so as to distinguish the vertex from other rendered vertices that have an assigned zoom level which is less than or equal to the currently-specified zoom level, comprises an action of rendering the vertex so as to exhibit a transparency setting that is greater than no transparency.

14. A system for browsing a graph comprising of vertices and edges, comprising:

a computing device comprising a display device and an user input device; and

a computer program having program modules executable by the computing device, the computing device being directed by the program modules of the computer program to,

provide a currently-specified viewport which is specified by a user via said user input device and which specifies a portion of the graph that is to be viewed, or a currently-specified zoom level, or both,

receive rendering data representing those graph vertices and rails intersecting the currently-specified viewport whenever the assigned zoom level of the intersecting vertex or rail is less than or equal to the currently-specified zoom level, wherein said rails each represent either a graph edge or a combination of portions of different graph edges, and

display the portion of the graph specified by the currently specified viewport on the display device using the received rendering data.

15. The system of claim 14, further comprising program modules which are executed prior to executing the program module for displaying the portion of the graph specified by the currently specified viewport on the display device using the received rendering data, said program modules comprising:

providing an instruction input by the user via said user input device which directs that vertices intersecting the currently-specified viewport that do not have an assigned zoom level which is less than or equal to the currently-specified zoom level to be rendered so as to exhibit a transparency setting that is greater than no transparency when displayed; and

receiving rendering data representing those vertices intersecting the currently-specified viewport that do not have an assigned zoom level which is less than or equal to the currently-specified zoom level.

16. The system of claim 14, further comprising program modules which are executed prior to executing the program module for displaying the portion of the graph specified by the currently specified viewport on the display device using the received rendering data, said program modules comprising:

providing an instruction input by the user via said user input device which directs that rails intersecting the currently-specified viewport that do not have an assigned zoom level which is less than or equal to the currently-specified zoom level to be rendered so as to exhibit a transparency setting that is greater than no transparency when displayed; and

receiving rendering data representing those rails intersecting the currently-specified viewport that do not have an assigned zoom level which is less than or equal to the currently-specified zoom level.

17. The system of claim 14, further comprising program modules which are executed prior to executing the program module for displaying the portion of the graph specified by the currently specified viewport on the display device using the received rendering data, said program modules comprising:

providing an instruction input by the user via said user input device which directs that rails intersecting the currently-specified viewport which are located adjacent a vertex also intersecting the currently-specified viewport be rendered regardless of the zoom level value assigned to the rails; and

receiving rendering data representing those rails intersecting the currently-specified viewport which are located adjacent a vertex also intersecting the currently-specified viewport.

18. The system of claim 14, wherein said zoom level values assigned to the vertices and rails are chosen from a set of zoom level values defined by 2ⁿ⁻

1 wherein n={1, 2, 3, . . . }, and wherein a zoom level value of “

1”

is the smallest zoom level value in the set.

19. The system of claim 18, wherein the set of zoom level values that can be assigned to the vertices and rails further comprises a global zoom level value which when assigned to a vertex or rail causes that vertex or rail to be rendered and displayed regardless of the currently-specified zoom level if the vertex or rail intersects the currently-specified viewport, said system further comprising program modules which are executed prior to executing the program module for displaying the portion of the graph specified by the currently specified viewport on the display device using the received rendering data, said program modules comprising:

providing an instruction input by the user via said user input device which directs that one or more vertices or rails, or both, be assigned the global zoom level value; and

receiving rendering data representing those vertices or rails, or both, that have been assigned the global zoom level value and which intersect the currently-specified viewport.

20. The system of claim 14, wherein a vertex or rail, or both, can be rendered so as to exhibit a transparency setting that is greater than no transparency when displayed, further comprising program modules comprising:

providing an instruction input by the user via said user input device by the user selecting a vertex or rail exhibiting a transparency setting that is greater than no transparency in a currently displayed portion of the graph or selecting a blank area in a currently displayed portion of the graph associated with a vertex or rail that is not currently displayed owing to it having an assigned zoom level value that is not less than or equal to the currently-specified zoom level, to change the zoom level value assigned to the selected vertex or rail to the currently-specified zoom level;

receiving rendering data representing those graph vertices and rails intersecting the currently-specified viewport whenever the assigned zoom level of the intersecting vertex or rail is less than or equal to the currently-specified zoom level, and

displaying the portion of the graph specified by the currently specified viewport on the display device using the received rendering data.