System and method for visualizing massive multi-digraphs

• US 6,781,599 B2
• Filed: 01/04/2001
• Issued: 08/24/2004
• Est. Priority Date: 01/04/2001
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: Abello, James, Korn, Jeffrey
• Primary Examiner(s): Wong, Don
• Assistant Examiner(s): MANCUSO, HUEDUNG XUAN CAO
• Application Number:
  US09/754,173
• Publication Number:
  US 20020154175A1
• Time in Patent Office: 1,328 Days
• Field of Search: 345/629, 345/440
• US Class Current: 345/629
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

In accordance with a feature of the invention, a hierarchy of multi-digraph layers may be constructed on top of an input multi-digraph. Each layer represents a multi-digraph obtained from an equivalence relation defined on the edge set of the input multi-digraph. In accordance with a further feature of the invention, each subgraph is small enough to be represented visually in a variety of novel ways.

Claims

1. A method of processing an input multi-digraph comprising:

constructing a hierarchy of multi-digraph layers on top of the multi-digraph, where a multi-digraph layer is a multi-digraph obtained from an equivalence relation defined on an edge set of the input multi-digraph, which multi-digraph layer is obtained by coalescing disjoint sets of vertices at a previous layer and aggregating their corresponding weighted edges, and where a first layer is obtained by coalescing disjoint sets of vertices of said input multi-digraph and aggregating their corresponding weighted edges;

extracting a graph slice from the hierarchy; and

creating a visual representation of the graph slice.

2. The invention of claim 1, wherein each layer has edges representing an equivalence class of edges at a previous layer.

3. The invention of claim 1 further comprising the steps of:

receiving input from a user;

replacing the graph slice with a second graph slice extracted from the hierarchy; and

creating a visual representation of the second graph slice.

4. The invention of claim 1 wherein amount of storage needed for storing the input multi-digraph in a computer that includes a main memory and a bulk storage means is larger than the main memory.

5. A system for visualizing an input multi-digraph that includes a maim memory and a bulk storage device comprising:

a computational engine enabled to construct a hierarchy of multi-digraph layers on tap the multi-digraph and to extract graph slices from the hierarchy, where a multi-digraph layer is a multi-digraph obtained from an equivalence relation defined on an edge set of the input multi-digraph, which multi-digraph layer is obtained by coalescing disjoint sets of vertices at a previous layer and aggregating their corresponding weighted edges, and where a first layer is obtained by coalescing disjoint sets of vertices of said input multi-digraph and aggregating their corresponding weighted edges; and

a graphical engine coupled to said main memory in communication with the computational engine and enabled to create visual representations of the graph slices.

6. The invention of claim 5 wherein each layer has edges representing an equivalence class of edges at a previous layer.

7. The invention of claim 5 wherein the graphical engine requests graph slices from the computational engine in response to navigational commands from a user.

8. The invention of claim 5 wherein the computational engine and the graphical engine communicate across a communication network.

9. The invention of claim 5 wherein amount of storage needed to store the input multi-digraph is larger than storage capacity of the main memory.