Complete, randomly ordered traversal of cyclic directed graphs
AssigneeAutodesk, Inc.
InventorsJohn Thomas Mongan, Dorothy Mack Cribbs
Life of this patent
Estimating the term…
Abstract
A test generator creates a cyclic directed graph representation of the interface of a program being tested and then generates tests from this representation. In generating the tests, the test generator iteratively selects traversal paths through the cyclic directed graph that result in traversal of every edge in the graph in a random order with a minimum number of iterations. The resulting tests contain randomly selected actions and randomly generated data, and thus when executed, these tests randomly manipulate the program being tested.
Claims27
An apparatus for performing a complete, randomly ordered traversal of a cyclic directed graph, comprising:
- (a) a computer;
- and
- (b) means, executed by the computer, for creating a cyclic directed graph representation in the computer;
- and
- (c) means, executed by the computer, for iteratively selecting traversal paths through a cyclic directed graph that result in traversal of every edge in the graph in a random order with a minimum number of iterations.
A computer-implemented method for performing a complete, randomly ordered traversal of a cyclic directed graph, comprising the steps of:
- (a) creating a cyclic directed graph representation in the computer;
- and
- (b) iteratively selecting traversal paths through a cyclic directed graph that result in traversal of every edge in the graph in a random order with a minimum number of iterations.
A program carrier, readable by a computer, embodying one or more instructions executable by the computer to perform method steps for performing a complete, randomly ordered traversal of a cyclic directed graph, the method comprising the steps of:
- (a) creating a cyclic directed graph representation in the computer;
- and
- (b) iteratively selecting traversal paths through a cyclic directed graph that result in traversal of every edge in the graph in a random order with a minimum number of iterations.
Dependencies are inferred from the claim text.