Abstract:
Method for displaying and identifying relevant paths through a graph by displaying them in a tabular format and providing user defined and computed values and filters. Each graph is represented as a set of nodes and edges. Each path through the graph is displayed as a row in a table where the user can apply sorting, filtering, and compute intrinsic or extrinsic information to augment the data.

Description:
STATEMENT OF GOVERNMENT INTEREST 
     The invention described herein may be manufactured and used by or for the Government for governmental purposes without the payment of any royalty thereon. 
    
    
     BACKGROUND OF THE INVENTION 
     Mathematical graphs which are made up of nodes and edges are pervasive in day to day life. Graphs are even more essential for analysts that rely on graph based data for analyzing domains such as social networks, computer networks, road networks, subway maps and command and control structures. This makes graph visualization and understanding pivotal to effectively using these potentially large and complex graph based data sources. 
     Traditional graph visualization uses one or more graph layout algorithms to draw rectangles and lines to depict nodes and edges in the graph. These visualizations often rely on algorithms that attempt to layout the graph using poorly balanced aesthetic principles. While the readability of the graphs is the principle purpose of these layout algorithms, increasing graph size and complexity are reducing the effectiveness of these algorithms to allow the user to quickly and easily digest both the structure and the content of these graphs. This problem is further exacerbated for graphs where the number of nodes greatly exceeds the display area. 
     Traditional graph visualizations also often fail to maintain the gestalt principle of proximity where the viewer automatically correlates graph elements&#39; proximity to some form of relationship between those elements. Another failing of traditional graph visualizations is that they are ill-suited to address rapid sequential questions where each layout that optimizes a particular question can often cause the entire display to change radically. A layout optimizing a single path through a graph may omit values at the nodes; another layout that bundles edges to give the overall flow within a graph makes it impossible to see which paths actually exist. Overall, each traditional layout compromises which aspects of a graph is displayed. 
     OBJECTS AND SUMMARY OF THE INVENTION 
     One object of the present invention is to provide a method and apparatus for displaying computer generated graphs as a series of paths in a tabular form. 
     Another object of the present invention is to provide a method and apparatus for prioritizing the order of the computer generated data paths that are displayed in order to satisfy dynamic user queries for information. 
     Yet another object of the present invention is to provide a method and apparatus to allow the user to interact with a computer system to generate new information based on data both internal and external to the graph while still being able to use these new results for prioritizing the sorting order of the paths. 
     The invention disclosed herein provides a method and apparatus for displaying computer generated graphs as a series of paths with the ability to filter and sort those paths based on intrinsic and extrinsic values. In particular, this invention allows the user to display and intuitively interact with computer generated graphs using a common spreadsheet style metaphor. A graph consists of a set of edges and nodes where edges connect nodes to nodes. Each edge and/or node can have any amount of other data associated with it, whether integer, real, boolean, textual or otherwise. The present embodiment of Graphtables allows the user to interactively: configure the sorting order of the columns of the table; define which data to display in each column; and compute new values or fields. By providing these few, but powerful set of operations, the user can quickly get a list of paths through a graph to answer targeted questions such as: which paths are of length 5 starting from a particular node; which nodes are directly connected to a particular node; and display all the paths that have a node with an address that is also 5 minutes away from another user-supplied address. 
     According to an embodiment of the present invention, Graphtables, comprises the steps of: accepting into a computer system an input graph from the user; computing all possible paths through the graph such that each path is unique and has no cycles; and display each path in a single row where upon initialization the first row starts with the shortest paths and the last row contains the longest path. 
     According to the preferred embodiment of the present invention, Graphtables, the spreadsheet metaphor is slightly changed in that the user is presented with a set of overall columns in the order of Node, Edge, Node, Edge, etc. There is one column for each element in the longest path, so if the longest path is of length 15, there are 15 main columns each labelled with Node or Edge. In the preferred embodiment, each main column is broken up into sub columns where each attribute of the node or edge is displayed in a sub column. The number of sub columns is equivalent to the number of unique attributes for all nodes or edges. This allows the present invention to accommodate nodes or edges with non-homogenous data and data types. In the preferred embodiment, when a node or edge does not contain a particular attribute, it simply doesn&#39;t display any value in that cell. Other embodiments may choose to display NULL or other value or symbol. 
     According to a feature of the present invention, Graphtables, the user can instruct the computer system to re-order the sub columns not labelled Node or Edge. In the preferred embodiment, this only alters the location within that one Node or Edge but in another embodiment, changing the column display order for sub columns could alter the display order for the other Node or Edge columns. There is no utility in moving the main columns labelled Node and Edge as they only let the user know that the column is displaying node or edge information. 
     According to a feature of the present invention, Graphtables, the user can instruct the computer system to sort any number of columns as is common in spreadsheet applications. The user selecting columns to sort is equivalent to a complex graph matching search where more relevant results are displayed first, but Graphtables achieves this effect without requiring any complex textual input. It is not necessary that each node or edge contain the same number of attribute data values. The preferred embodiment allows the user to decide when a node or edge does not contain a value, whether to consider that the node or edge lacking a value is displayed earlier or later in the table. 
     According to another embodiment of the present invention, Graphtables, the user can instruct the computer system to filter the data by all or any of the following: 1) all nodes and edges, 2) any subset of nodes or edges, and 3) any number of rows. When a path fails the filter, the preferred embodiment does not hide that path, it just makes its sorting order to be later in the list. This allows the user to still sort and view the filtered results in context with the other information. The preferred embodiment still sorts the filtered data in the same way as specified by the user and displays a line to depict that the rows below that line are filtered. This embodiment effectively converts filtering to a simple ranking calculation, showing possible relevant results where other graph implementations would have excluded those nodes or edges from the graph entirely. Those traditional implementations do not allow the user to see that there are paths that might have closely matched their filter. 
     According to another feature of the present invention, Graphtables, the user can instruct the computer system to insert main columns or sub columns that generate derived data for the entire graph, or any number of steps along the path. If the inserted columns are at the main level, the inserted columns are moveable next to any other already existing main column. If the inserted column is a sub column, that sub column location can be moved but is limited to the inserted main column. 
     According to another feature of the present invention, Graphtables, the user can instruct the computer system to choose to bundle edges so that if two neighboring rows share the same edge, the node is only displayed once and the edge is only displayed once on the first occurrence and all subsequent contiguous edges are displayed as edges from the primary edge. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  depicts a sample graph with the default sorting, called the Initial State. 
         FIG. 2  shows the result of sorting by a single column from the Initial State. 
         FIG. 3  shows the result of sub sorting by a second column from the state depicted in  FIG. 2 . 
         FIG. 4  shows the result of filtering the entire table from the Initial State. 
         FIG. 5  shows the result of filtering a single column from the Initial State. 
         FIG. 6  shows the result of edge bundling. 
         FIG. 7  shows the result of inserting a custom main level computed column. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     This invention displays a user defined ordered set of paths with optional filters and user defined columns. In particular, this invention provides an interface to explore graph paths that satisfy extrinsic user needs. 
     Referring to  FIG. 1 , the graph G is displayed in its initial state assuming the user had loaded a graph with the nodes and edges as defined in  100 .  120  displays the same graph as the traditional node-link style of the same graph as defined in  100 .  140  contains the additional metadata for each node and edge.  160  is the canonical depiction of the same graph as defined in  100 ,  120 , and  140 .  160  consists of 5 major columns, where each major column is named based upon the type of item that it contains, either nodes or edges and has a monotonically increasing column number for each node-edge pair and has subcolumns as in  165 . The number of columns in  160  is defined based on the length of the longest path through the graph as defined by  100 . The titles of the subcolumns as in  165  are based on the metadata in the underlying graph as defined by  140 . Each row of the table as in  170  displays a single walk through the graph and its contents are based on the sorting order of the subcolumns in  165 . The canonical representation for a node as in  175  is to simply surround the contents of the primary column as in  160  with a rounded rectangle. The visual depiction in  175  is solely to improve the user&#39;s interpretation and in no way affects the ability to: sort contents, alter the order of the columns, or insert user defined columns. The canonical representation for an edge as in  185  is to simply to draw a thick line behind the contents of the primary column as in  160 . The visual depiction in  185  is solely to improve the user&#39;s interpretation and in no way affects the ability to: sort contents, alter the order of the columns, or insert user defined columns.  180  displays the canonical method of displaying NULL values metadata fields as empty cells. 
     Referring to  FIG. 2  is the result of sorting the value column  200  in the graph as defined by  140  in descending order. This action causes the rows to be reordered based on the contents of that cell. Note that the entire path stays together and entire rows are sorted, not just the contents of a single column or subcolumn. 
     Referring to  FIG. 3  is the result of sorting the weight column  300  in the graph as defined by  140  in ascending order after previously sorting was applied as in  FIG. 2 . Note that sorting precedence is applied, and the sort as applied in  FIG. 2  stays consistent. 
     Referring to  FIG. 4  is the result of applying a graph filter  400  based off the initial state as displayed in  FIG. 1 . A graph based filter evaluates all elements in all paths for the entire graph. If any element fails the check, then the entire path fails the check and is considered filtered. In the canonical implementation, a filter doesn&#39;t eliminate the element, but instead serves as a sorting order modifier. In the canonical implementation, all non-filtered elements are displayed before all filtered elements, but regardless of filtered or non-filtered, all elements are still sorted. In the current embodiment, a dark line is drawn  450  to visually separate the filtered from non-filtered elements. 
     Referring to  FIG. 5  is the result of applying a column based filter  500  off the initial state as displayed in  FIG. 1 . A column based filter only compares a filter equation (i.e., criteria) versus elements in the column in which it is defined. If any element in the subordinate column  500  fails the filter criteria then the entire row (aka path) fails the check and is considered filtered. In the canonical implementation, a filter doesn&#39;t eliminate the element, but instead serves as a sorting order modifier. In the canonical implementation, all non-filtered elements are displayed before all filtered elements, but regardless of filtered or non-filtered, all elements are still sorted. 
     Referring to  FIG. 6  is the result of sorting the label column  500  in the graph as defined by  140  in descending order. This action causes the rows to be reordered based on the contents of that cell. Note that the entire path stays together and entire rows are sorted, not just the contents of a single column or subcolumn. Additional to the sorting,  FIG. 6  depicts the process of edge bundling. Subsequent consecutive rows that would duplicate the same value  520 ,  540  are displayed as a forked edge  560  instead of duplicating the values. This reduces the visual clutter and is intended to preserve the visual the uniqueness of each path. 
     Referring to  FIG. 7  is the result of inserting a custom top level column  700  used to compute some value based on the contents of the path or the graph. In this case, the value as seen in  750  displays the computed path length. These computed column(s) can also be used as sorting column and work the same as in previous examples. Unlike the path based main level columns  160 , custom columns can be relocated to anywhere the user desires. 
     Other embodiments do not display filtered elements, and the number of failed filters can also be used to further reduce the rank of a filtered path. This means that a path that only fails one filter would rank higher than a path that failed two filters. 
     Other embodiments may choose to hide columns or rows to reduce the amount of displayed content. Other embodiments may also dramatically change the visual metaphor of using rounded rectangles for nodes and lines for edges. 
     While the preferred embodiments have been described and illustrated, it should be understood that various substitutions, equivalents, adaptations and modifications of the invention may be made thereto by those skilled in the art without departing from the spirit and scope of the invention. Accordingly, it is to be understood that the present invention has been described by way of illustration and not limitation.