Method and System of Determining Transitive Closure
AssigneePervasive Health, Inc.
InventorsJames LATHAM, Michael OLTMAN
Life of this patent
Estimating the term…
Abstract
A method for determining paths from a first vertex and a second vertex in an acyclic directed graph comprises determining a plurality of paths from one or more root vertices in the graph to one or more leaf vertices in the graph, storing each of the plurality of paths as a respective array in a computer database, each respective array comprising a respective root, a respective leaf, and up to a plurality of intermediate vertices, and determining whether the first vertex and the second vertex are both represented in one or more of the arrays.
Claims12
A method for determining paths including a first vertex and a second vertex in an acyclic directed graph, the method comprising:
- determining a plurality of paths from one or more root vertices in the graph to one or more leaf vertices in the graph;
- storing a representation of each of the plurality of paths as a respective array in a computer database, each respective array comprising a respective root, a respective leaf, and up to a plurality of intermediate vertices;
- and
- determining whether the first vertex and the second vertex are both represented in one or more of the arrays.
A system for determining paths including a first vertex and a second vertex in an acyclic directed graph, the system comprising:
- a database storing a representation of an acyclic directed graph, the representation comprising a plurality of paths from one or more root vertices in the graph to one or more leaf vertices in the graph, each of the plurality of paths stored as a respective array in the database, each respective array comprising a respective root, a respective leaf, and up to a plurality of intermediate vertices;
- and
- an electronic control unit (ECU) in communication with the database, the ECU comprising:
- a memory configured to store instructions;
- and
- a processor configured to execute the instructions to search the database to determine whether the first vertex and the second vertex are both represented in one of said plurality of arrays.
Dependencies are inferred from the claim text.