Minimal representation of connecting walks
OwnerRobert Lewis Jackson, JR.inventor
Life of this patent
Estimating the term…
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.
Claims20
A method for use in representing a path in a graph of nodes, the method comprising:
- determining, by a computing device, an acyclical collection of primary edges that collectively reach all nodes within the graph;
- determining, by the computing device, one or more secondary edges between nodes of the graph, wherein the secondary edges are edges other than the primary edges;
- determining, by the computing device, a path between a first node of the graph and a second node of the graph, wherein the path includes one or more of the primary edges and one or more of the secondary edges;
- representing, by the computing device, the path as an abbreviated path including the first node, the second node, and the secondary edges in the path, wherein the abbreviated path excludes one or more of the primary edges in the path;
- and
- outputting, by the computing device, the abbreviated path.
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 primary edges that collectively reach all nodes within the graph and one or more secondary edges between nodes of the graph, wherein the secondary edges are edges other than the primary edges;
- determine a path between a first node of the graph and a second node of the graph, wherein the path includes one or more of the primary edges and one or more of the secondary edges;
- and
- represent the path as an abbreviated path including the first node, the second node, and the secondary edges in the path, wherein the abbreviated path excludes one or more of the primary edges in the path.
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 primary edges that collectively reach all nodes within a graph that includes a plurality of nodes connected by edges;
- determine one or more secondary edges between nodes of the graph, wherein the secondary edges are edges other than the primary edges, and the nodes connected by each secondary edge are endpoints of the secondary edge;
- determine a tree including a plurality of nodes within the graph, wherein the tree includes endpoint nodes connected by one or more of the primary edges and one or more of the secondary edges;
- and
- represent the tree as an abbreviated tree including the endpoint nodes of the tree and the endpoint nodes of the secondary edges, wherein the abbreviated tree excludes at least one of the primary edges in the path.
Dependencies are inferred from the claim text.