Minimal representation of connecting walks

• US 10,394,778 B2
• Filed: 09/06/2011
• Issued: 08/27/2019
• Est. Priority Date: 09/03/2010
• Status: Active Grant

• Current Assignee: Robert Lewis Jr. Jackson
• Original Assignee: Robert Lewis Jr. Jackson
• Inventors: Jackson, Jr., Robert Lewis
• Primary Examiner(s): Saeed, Usmaan
• Application Number:
  US13/226,299
• Publication Number:
  US 20120059858A1
• Time in Patent Office: 2,912 Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Systems and methods for use in representing a path in a graph of nodes. A computing device determines an acyclical collection of primary edges that collectively reach all nodes within the graph, and also determines one or more secondary edges (e.g., edges other than the primary edges) between nodes of the graph. The computing device further determines a path between a first node of the graph and a second node of the graph. The path includes one or more of the primary edges and one or more of the secondary edges. The computing device represents the path as an abbreviated path including the first node, the second node, and the secondary edges in the path. The abbreviated path excludes one or more of the primary edges in the path.

Claims

1. A computer-implemented method for representing all the edges in an original path in a graph of nodes as an abbreviated path, the method comprising a computing device:

determining an acyclical collection of edges that collectively reach all nodes within the graph, wherein the edges in the acyclical collection are defined as primary edges, and all edges in the graph other than primary edges are defined as secondary edges;

identifying an original path between a first node of the graph and a second node of the graph, wherein the original path includes one or more primary edges and one or more secondary edges;

representing the original path as an abbreviated path, said abbreviated path including the first node, the second node, and all the secondary edges from the original path, but excluding one or more of the primary edges from the original path;

deriving the primary edges in the original path that were excluded in the abbreviated path; and

reconstructing the original path from the abbreviated path based on the derived primary edges.

2. A device comprising:

a memory device for storing a graph of nodes connected by edges; and

a processor coupled to the memory device and programmed to;

determine an acyclical collection of edges that collectively reach all nodes within the graph, wherein the edges in the acyclical collection are defined as primary edges, and all other edges in the graph other than primary edges are defined as secondary edges;

determine an original path between a first node of the graph and a second node of the graph, wherein the original path includes one or more primary edges and one or more secondary edges; and

represent the original path as an abbreviated path, said abbreviated path including the first node, the second node, and all the secondary edges from the original path, but excluding one or more of the primary edges from the original path;

represent the original path as an abbreviated path at least in part by creating a textual representation of the abbreviated path; and

create the textual representation of the abbreviated path by including, in the textual representation, just those nodes that are endpoint nodes of the abbreviated path and those nodes that are endpoint nodes of each secondary edge in the abbreviated path, said textual representation excluding at least one node from the path.

3. A device in accordance with claim 2, wherein the processor is further programmed to include, in the textual representation, delimiters between just those nodes that are endpoint nodes of each secondary edge in the abbreviated path.

4. One or more non-transitory computer-readable media having computer-executable instructions embodied thereon, wherein when executed by at least one processor, the computer-executable instructions cause the processor to:

determine an acyclical collection of edges that collectively reach all nodes within a graph that includes a plurality of nodes connected by edges, wherein the edges in the acyclical collection are defined as primary edges, and all edges in the graph other than primary edges are defined as secondary edges;

determine an original path including a plurality of nodes within the graph, wherein the original path includes endpoint nodes connected by one or more primary edges and one or more secondary edges; and

represent the original path as an abbreviated path, said abbreviated path including the endpoint nodes of the original path and endpoint nodes of the secondary edges, wherein the abbreviated path excludes at least one of the primary edges from the original path;

wherein the computer-executable instructions further cause the processor to create a graphical representation of the abbreviated path by;

depicting the endpoint nodes of the abbreviated path, the endpoint nodes of the secondary edges, and the secondary edges connecting the endpoint nodes of the secondary edges; and

depicting the primary edges as a single primary edge, wherein the secondary edges are graphically distinguished from the primary edges.