Patent ID: 6804634
Filing Date: 2004-10-12
Classification: G06F

Abstract:
A method for generating a covering set of test cases from a directed graph, G, having a plurality of nodes and a plurality of edges connecting the nodes, a test case being a path through G, the method comprising the steps of:classifying the nodes and edges in G as required, optional or forbidden, wherein optional edges are contained in selected test cases; removing forbidden nodes and edges from G, wherein the removing step provides a graph, G1; identifying unreachable nodes and strongly connected components of G1; removing the unreachable notes and edges from G1; replacing each of the strong connected components with a replacement node, wherein each of the replacement nodes is classified as required if the replaced strong component contained a required node or a required edge and as optional if the replaced strong component contained no required nodes or edges, wherein the removing and replacing steps provide a graph, G2; translating node classification in G2 to equivalent edge classifications in G2, wherein the translating step provides a graph G3; computing a deficit for each node in G3, the deficit being a difference between the required edges exiting a node and the required edges entering a mode; constructing a network, N, from G3 using the deficits; solving a minimum cost, maximum flow problem on N, the solving step providing a value indicating an optional edge; constructing a graph H from N, wherein optional edges are removed from N; constructing a graph Hâ€² by translating the equivalent edge classifications in H to node classification; and constructing a covering test case set from Hâ€².