Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
5689711
Bardasz , ; et al.
November 18, 1997
Title
Method and apparatus for representing data dependencies in software modeling systems
Abstract
A method and apparatus for converting a set of functions of any software system that does modeling into a corresponding set of parametric functions that, when called, generate not only a resulting model, but also a dependency graph representation of the model. The dependency graph can include directed functions and non-directed constraint relationships, and is used when a change is made to the model so that only affected portions of the model are reevaluated. The dependency graph can be visually presented to a user, and can be created or edited through a visual programming environment. The graph can be modified to change either input values to the model, or the graph elements that represent the functions used in creating the model. When changes to the dependency graph are made, it can be reevaluated to incorporate the changes into the model. When the visual programming environment is used to modify the graph, the environment calls the parametric set of functions. The set of parametric functions is generated by creating wrappers in a standard programming language around the functions of the software system. The dependency graph can also be used to generate a computer program in a standard language that, when executed on the software system, regenerates the model as well as the dependency representation. The computer program can also be edited and then executed on the software system to generate a modified version of the model.
Inventors:
Bardasz; Theodore
(Chelmsford,
MA
)
, Malnati; Stefano
(N. Andover,
MA
)
Appl. No.:
426594
Filed:
April 21, 1995
Current U.S. Class:
717/105
719/328
345/420
715/866
715/961
715/964
Current International Class:
G06F 9/44 (20060101)
Field of Search:
395/701,702,682,964,333,334,335,118,120,125,356,357 364/578
U.S. Patent Documents
5265197
November 1993
Kondo
5325533
June 1994
McInerney et al.
5327529
July 1994
Fults et al.
5438659
August 1995
Notess et al.
5479601
December 1995
Matheny et al.
5530864
June 1996
Matheny et al.
5581672
December 1996
Letcher, Jr.
5603034
February 1997
Swanson
Primary Examiner:
Oberley; Alvin
Assistant Examiner:
Chaki; Kakali
Attorney, Agent or Firm:
Wolf, Greenfield & Sacks, P.C.
Claims
What is claimed is:
1. A method for providing parametric capabilities to a software modeling system having a plurality of functions and a user interface that responds to receipt of each one of a plurality of commands by calling a corresponding one of the plurality of functions, the plurality of functions being executed during a modeling session to create a model, the method including steps of:
A. providing a wrapper around each of the plurality of functions in the software system to create a corresponding plurality of associative functions, each of the associative functions including a call to its corresponding function and further including a capability of creating and adding graph entities to a dependency representation of the model when its corresponding function is executed during the modeling session; and
B. modifying the user interface so that in response to each received command, the associative function that corresponds to the function corresponding to the received command is called.
2. The method of claim 1, wherein at least one of the plurality of functions has no inherent parametric capabilities.
3. The method of claim 1, wherein the plurality of functions includes a first function that operates upon a first set of arguments formatted in a first format, and wherein step A includes a step of:
providing a first wrapper around the first function, the first wrapper being capable of receiving a second set of arguments formatted in a second format that is different from the first format, the first wrapper converting the second set of arguments to the first set of arguments when calling the first function.
4. The method of claim 1, wherein step A includes providing each of the wrappers in an object oriented computer programming language.
5. The method of claim 1, wherein steps A and B are implemented by a computer executing a computer program written in an object oriented language.
6. The method as recited in claim 1, further comprising a step of:
providing a tool that, when a modification is made to the model, uses the dependency representation to reevaluate only the functions used in creating the model that correspond to graph entities affected by the modification to the design.
7. The method of claim 1, further comprising a step of:
creating a hash table with a table entry for each associative function, each table entry identifying a topology of the graph entities created and added to the dependency representation when the associative function is executed.
8. The method of claim 7, wherein the step of creating a hash table includes a step of:
creating each table entry to identify a number of input data arguments required by the associative function, a result of the associative function and descriptions of each input data argument and the result.
9. The method of claim 1, wherein step A includes a step of providing each of the wrappers in a standard computer programming language.
10. The method of claim 9, wherein step A includes a step of providing each of the wrappers in an object oriented computer programming language.
11. The method of claim 1, further including a step of:
C. creating a single processor function that cooperates with each of the associative functions to create and add the graph entities to the dependency representation.
12. The method of claim 11, wherein step C includes a step of:
creating the single processor function to generate a hash table with a table entry for each associative function, each table entry identifying a topology of the graph entities created and added to the dependency representation by the single processor function when the associative function is executed.
13. The method of claim 12, wherein step C further includes a step of:
creating the single processor function to create the dependency graph by accessing an entry in the hash table, the single processor being generic and operating according to arguments passed to it when it is called by the associative function.
14. The method of claim 12, wherein step C includes a step of:
creating the single processor function to create each table entry to identify a number of input data arguments required by the associative function, an output of the associative function and descriptions of each input data argument and the output.
15. A software modeling system for creating a model during a modeling session, the model being formed from a plurality of design entities, the software modeling system comprising:
a processor having a plurality of functions that are executed thereon to create the plurality of design entities that form the model;
a user interface that responds to receipt of each one of a plurality of commands by calling a corresponding one of the plurality of functions;
a wrapper around each of the plurality of functions that creates a corresponding plurality of associative functions, each of the associative functions including a call to its corresponding function, each of the associative functions further including means for creating and adding entries to a dependency representation when its corresponding function is executed during the modeling session, the dependency representation indicating dependencies of the plurality of design entities that form the design; and
means for modifying the user interface so that in response to each received command, the associative function that corresponds to the function corresponding to the received command is called.
16. The software modeling system of claim 15, wherein the plurality of functions includes directed and non-directed operations and wherein the software modeling system further includes:
means for creating the dependency representation to include design entities created by both the directed and non-directed operations.
17. The software modeling system of claim 15, further including:
means for generating a standard programming language computer program from the dependency representation.
18. The software modeling system of claim 15, wherein the plurality of functions includes directed and non-directed operations;
wherein the creating means includes means for creating the dependency representation to include design entities created by both the directed and non-directed operations; and
wherein the software modeling system further includes means for representing at least two of the plurality of design entities in the dependency representation with a same hierarchical operator.
19. The software modeling system of claim 15, wherein the plurality of functions includes directed and non-directed operations;
the creating means includes means for creating the dependency representation to include design entities created by both directed and non-directed operations; and
wherein the software modeling system further includes means for graphically editing the dependency representation to create a modified dependency representation.
20. The software modeling system of claim 15, wherein the plurality of functions includes directed and non-directed operations;
wherein the creating means includes means for creating the dependency representation to include design entities created by both directed and non-directed operations; and
wherein the software modeling system further includes means for generating a standard programming language computer program from the dependency representation.
21. The software modeling system of claim 15, further including:
means for displaying the dependency representation; and
means for generating a standard programming language computer program from the dependency representation.
22. The software modeling system of claim 15, wherein the plurality of functions includes a first function that operates upon a first set of arguments formatted in a first format, and wherein the software modeling system further includes means for providing a first wrapper around the first function, the first wrapper being capable of receiving a second set of arguments formatted in a second format that is different from the first format, the first wrapper converting the second set of arguments into the first set of arguments when calling the first function.
23. The software modeling system as recited in claim 15, further comprising:
means for, when a modification is made to the model, using the dependency representation to reevaluate only those functions used to create the model that correspond to the design entities affected by the modification to the model.
24. The software modeling system of claim 15, wherein the plurality of functions includes directed and non-directed operations;
wherein the creating means includes means for creating the dependency representation to include design entities created by both directed and non-directed operations, and wherein the software modeling system further includes:
means for representing at least two of the plurality of design entities in the dependency representation with a same hierarchical operator;
means for graphically editing the dependency representation to create a modified dependency representation; and
means for generating a standard programming language computer program from the dependency representation.
25. The software modeling system of claim 24, wherein the plurality of functions includes a first function that operates upon a set of arguments formatted in a first format, and wherein the software modeling system further includes means for providing a first wrapper around the first function, the first wrapper being capable of receiving a second set of arguments formatted in a second format that is different from the first format, the first wrapper converting the second set of arguments into the first set of arguments when calling the first function.
26. The software modeling system of claim 15, further including means for displaying the dependency representation.
27. The software modeling system of claim 26, wherein the means for displaying the dependency representation includes a visual programming environment.
28. The software modeling system of claim 26, further including:
means for representing at least two of the plurality of design entities in the dependency representation with a same hierarchical operator.
29. The software modeling system of claim 26, further including:
means for graphically editing the dependency representation to create a modified dependency representation.
30. The software modeling system of claim 29, further including:
means for generating a modified design from the modified dependency representation.
Description
FIELD OF THE INVENTION
This invention relates to a method and apparatus for representing data dependencies in software modeling systems.
BACKGROUND OF THE INVENTION
Software systems exist in many different fields in which a user interacts with the system by entering a series of commands during an interactive session, and in response, the software system executes a number of functions that take actions defined by the user commands. Computer aided design (CAD) systems which generate a computer model of a design during an interactive design session are one example of such systems. CAD systems, such as the CADDS line available from Computervision Corp. of Bedford, Mass., provide tools for generating computer models of mechanical devices in two and/or three dimensions. Typically, a user interactively builds a model by entering, into a user interface, a series of system-defined commands to generate a product design. For example, a user may input a command such as insert box, along with desired dimensions (length, height and width) and a desired location for the box, to add a box with the specified characteristics to the design. Other commands can add elements such as cylinders, spheres, bores, etc., which can be integrated with the box to complete the product design. Thus, by inputting such system-defined commands, the user can build a computer model of a mechanical device.
The user interface in a CAD system conventionally includes a command processor that processes commands received from the user. The command processor generally can generate a command file that stores the received commands to generate a record of the interactive session between the user and the CAD system. Since the commands and command processor are generally proprietary to the particular CAD system, the command file is by nature a proprietary language. On receiving a command, the user interface calls an application programming interface (API), which is a software function that causes the system to perform some activity. For example, in a CAD system, an API causes a geometric modeler to generate and interconnect entities, such as edges, faces, and vertices to achieve the design action required by the proprietary command, and stores the entities in a database. The combination of the entities created by a series of commands received from the user during an interactive session defines the product design.
If the user desires to change the product design by changing a parameter of one of the previously created entities (e.g., the height of a box), the user can modify the history module to reflect the change, and then provide the history module as the source of commands to the system which re-executes all the commands in the history module. When the commands are re-executed, they are provided to the command processor, which again calls the appropriate APIs, which in turn typically discard the old design entities and create new entities to effect the new product design, as well as a new history module. This type of system is referred to as a "command based" system since the command is the basic building block.
Although the above-described command based systems allow a user to record an interactive session, to modify a record thereof, and to re-execute based on those modifications, they have several disadvantages. The history module created by these systems reflects the sequence in which the commands were received during the interactive design session, and does not represent the structural dependency of the resulting design. Thus, when any modification is made to the design, no matter how small, the entire history module must be re-executed to generate a new design, which can delay the design process.
Some CAD systems have been developed that include parametric capabilities so that when changes are made to a design parameter, the system modifies the design by updating only the portions thereof that are affected by the modified parameter. However, these parametric capabilities are conventionally incorporated into the proprietary commands used by the system. Therefore, if a third party vendor desires to provide add-on capabilities to the software system, the new capabilities must be integrated into the proprietary command set of the system if the parametric capabilities of the system are to be maintained.
Another disadvantage suffered by the above-described command based systems, whether or not they include parametric capabilities, is that modifications to the history module must be made using the proprietary commands. Thus, the user must learn a new "programming language" in order to modify the design reflected in the history module. In addition, history modules of this type are difficult for a designer to work with because they do not represent the structural dependency of the design, but rather, relate only to the sequential manner in which the commands were received during the design process.
SUMMARY OF THE INVENTION
In accordance with one illustrative embodiment of the invention, a method and apparatus is provided for converting a set of functions for any software system that does modeling into a corresponding set of functions having parametric capabilities. Thus, parametric capabilities can be provided to a software system whose set of functions have no inherent parametric capabilities.
In another illustrative embodiment, when the parametric functions created by the present invention are called during an interactive user session or by a program to create a design or model, the parametric functions generate not only the resulting model, but also a dependency graph representation of the model.
In a further illustrative embodiment, the dependency graph created by the present invention is created and evaluated in such a way that directed functions and non-directed constraint relationships can be intermingled in a single dependency graph.
In a still further illustrative embodiment, the dependency representation created by the present invention is used when a change is made to the model, so that only portions of the model affected by the change are reevaluated in creating the updated model.
In accordance with another illustrative embodiment of the invention, the dependency graph can be visually presented to a user to represent the dependencies of the model.
In accordance with another illustrative embodiment of the invention, functions executed on the software system can be grouped into hierarchical groups in the dependency graph. Thus, design goals of the user involving multiple functions can be represented with a single hierarchical entry in the dependency graph.
According to another illustrative embodiment of the invention, the dependency graph can be created or edited through a visual programming environment. When changes to the dependency graph are made, the graph can be reevaluated to incorporate the corresponding changes into the model.
In another illustrative embodiment, the dependency graph created by the present invention can be modified by the user to change either input values to the model, or the graph elements that represent the functions used in creating the model.
In a further illustrative embodiment, when the visual programming environment is used to modify the dependency graph, the environment calls the parametric set of functions created by the present invention. The parametric functions are compatible with visual programming techniques that allow a user to graphically generate and edit the dependency graph.
In a further illustrative embodiment, the set of parametric functions created in accordance with the present invention are generated by creating wrappers around the functions of the software system. The wrappers are written in a standard computer programming language so as to be compatible with non-proprietary tools, such as the visual programming environment discussed above.
According to a further illustrative embodiment of the invention, a method and apparatus is provided for generating a computer program from a representation of a model or design on a software system, the representation defining the model in terms of the dependency relationships amongst a plurality of model entities that form the model. The computer program can be written in a standard programming language. When the program is executed on the software system, it generates the model as well as the dependency representation. Thus, the computer program can convert a modeling session into a standard language program for efficient storage. The computer program can be generated from a dependency graph created in accordance with the present invention.
In another illustrative embodiment, the computer program can be edited, and then executed on the software system to generate a modified version of the design.
BRIEF DESCRIPTION OF THE DRAWINGS
Other features and advantages will become apparent from the following detailed description and from the drawings, in which:
FIG. 1 is a high level flowchart representing the steps of a method in accordance with the present invention;
FIG. 2 is an illustrative dependency graph created in accordance with the present invention;
FIG. 3 is a graphical representation of a user's perspective of a CAD system that employs the present invention;
FIG. 4 is a graphical representation of the relationship between the associative API builder tool of the present invention, the associative APIs that it creates, and the proprietary APIs of a software system on which the associative subsystem of the present invention is installed;
FIG. 5 is a graphical representation of the manner in which commands received at the user interface of a CAD system using the present invention call an associative API and the associative API processor to construct dependency graph entities to represent the command, and to evaluate those entities to perform the design action requested by the user;
FIG. 6 is a flowchart representing the steps performed by the associative API processor of the present invention when it is called by an associative API;
FIGS. 7a-7b are flowcharts representing the steps performed by the operator evaluator for an associative API of the present invention when it is called to evaluate an operator in the dependency graph;
FIG. 8 is a flowchart of one implementation of the evaluation symbolic pass of the evaluation method of FIGS. 7a-7b;
FIG. 9 is a flowchart of the directed operator processing routine of the present invention;
FIGS. 10a-10b are flowcharts illustrating the non-directed operator processing routine of the present invention;
FIG. 11 is a flowchart illustrating the evaluation pass of the evaluation method of FIGS. 7a-7b;
FIG. 12 is a flowchart representing the steps of an integration process of the present invention that integrates the present invention into a software system;
FIGS. 13a-e are flowcharts representing the steps of the program generation method and supporting routines of the present invention; and
FIG. 14 is a block diagram of a hardware system on which the present invention can be operated;
FIG. 15 illustrates a box having a countersunk hole provided therein;
FIG. 16 is an illustrative dependency graph of the present invention without the use of a hierarchical operator;
FIG. 17 is a representation of the dependency graph of FIG. 16 using a hierarchical operator;
FIG. 18 is a conceptual illustration of the implementation of the hierarchical operator in the dependency graphs of FIGS. 16-17;
FIGS. 19a-19d are flowcharts of a method operated upon each operator committed to the dependency graph of the present invention;
FIG. 20 is a flowchart illustrating the interpreter routine of the present invention;
FIG. 21 is a flowchart illustrating a method for processing edits a design and dependency graph of the present invention using a visual programming environment;
FIG. 22 is a flowchart illustrating the steps of a redefine input routine of the present invention;
FIG. 23 is a flowchart illustrating the steps of a replace operator routine of the present invention;
FIGS. 24a-24b illustrate an exemplary visual representation of a dependency graph according to the present invention; and
FIG. 25 is a high level flowchart representing the steps of a method in accordance with the present invention.
DETAILED DESCRIPTION
I. Overview
In accordance with the present invention, a method and apparatus is provided for converting the APIs in a modeling system into associative APIs that, when called from a user interface or as part of a larger program during a modeling session, generate a graph representing the dependencies between the API functions called during the modeling session, the arguments to the APIs, and the results of the API functions. From the dependency graph, the present invention allows a user to: (1) change inputs to the graph and have only the affected functions be re-executed; (2) generate a non-proprietary computer program that represents the structural dependency of the graph, and that when executed, produces the same result as the modeling session that created the graph; (3) view the graph to visualize the dependencies; (4) edit the graph to alter the dependency structure of the model; and (5) edit the graph to change the API functions used to generate the model.
In accordance with one aspect of the present invention, a method and apparatus is provided for generating, based on an execution of software system functions that produces a design, a dependency graph representation of the design, and a non-proprietary computer program that is generated from the dependency graph and also represents the structural dependency of the design. The method is illustrated in the flowchart of FIG. 1. In step 201, the design is generated by the execution of a group of functions in the software system during a design session, and a dependency graph representation of the design is generated in step 203. If the design is modified during the design session, the present invention uses the dependency graph to determine which portions of the design will be affected by the modification, and re-executes only so much code as is necessary to change the affected portions of the design. As shown in step 205, after completion of the design session, the dependency graph can also be used to generate a computer program in a standard language that, when executed, will generate the dependency graph and the design that it represents. The user can, as shown in step 207, edit the computer program to represent a modified design, and run the computer program on the software system (step 209) to produce the modified design. Because the computer program is in a non-proprietary language, the designer need not learn a proprietary language to modify it. Furthermore, since the program is developed from the dependency graph, rather than from the sequence in which commands were received from the user during the design session, the computer program represents the structural dependency of the design. Thus, the organization of the program is easily understood by the user, allowing for easy modification of the program, even if the user does not have significant computer programming experience.
As stated above, software systems conventionally include application programing interfaces (APIs), which are high level functions that generally map in a one-to-one relationship with system-defined user commands. In accordance with the present invention, a tool is provided which, as part of an integration process for integrating the present invention into a software system, initially is run over each API in the software system to generate a new set of APIs. The user interface for the software system is then modified to call these new APIs in response to commands received from the user. The new APIs created by the tool of the present invention do essentially two things. First, the new APIs perform essentially all of the functions performed by the set of APIs provided by the software system. Second, the new APIs also create and maintain a dependency graph representation of the design generated by the user, which can be used to provide the parametric capabilities discussed above, to allow for graphical editing of the design through edits to the graph, and which can also be used to generate the standard language computer program that represents the structural dependency of the design. In this manner, the tool of the present invention forms an associativity subsystem that can be initially run over any software system that is composed of high level functions or APIs to convert the system, in a manner transparent to the user, into one that has the above-described associative capabilities provided by the present invention.
As should be appreciated from the foregoing, and as will become clearer in the description below, the present invention can provide parametric capability to any software system composed of APIs, even if that system does not include such a capability in its command set. This feature of the present invention is advantageous in allowing third parties to provide add-on capabilities to a software system. To provide additional capabilities to the software system, a third party need only provide commands and corresponding APIs that are compatible with those of the system. The additional commands need not be integrated into the command set of the software system to provide parametric capabilities, because when the tool of the present invention is run over the software system having the third party's commands and APIs installed, parametric capabilities are provided in the new APIs generated by the tool of the present invention, and in the manner in which these new APIs are used to generate, maintain and update the dependency graph representation of the design created during a design session.
In the description below, the illustrative example provided for the software system on which the present invention is operated is a CAD system which receives commands from a designer during an interactive design session to create a product design. However, it should be understood that the present invention is not limited to use with CAD systems, or with systems that receive inputs during an interactive session. The present invention can be used with any software system that is composed of functions, and that receives inputs from a user in any number of ways. For example, the present invention can be used with a software system for creating economic models based on a number of parameters, or many other types of software systems. Thus, although the terms "model" and "design" are used to refer to the software system output that is modeled by the dependency graph, these terms are not intended to be limited to CAD models, and are intended to encompass the output produced by any software system based on the execution of a number of functions.
FIG. 2 is an example of a simple dependency graph 1 generated in accordance with the present invention operating on a CAD system. The graph 1 is generated during an interactive design session wherein a designer enters commands to insert a box into the design and to calculate the weight of the box. Along with the command to insert the box, the designer provides arguments which establish the length, width and height of the box, as well as the coordinates for the center of the box. These arguments are respectively represented in the graph 1 as data objects 3-6. Data objects are components in the graph that contain values. Each of the data objects 3-6 is connected to an operator 7 that indicates the function with which it is associated, i.e., insert box. Operators are components in the graph that take action on at least one data object and are functions or evaluable expressions that represent the design actions taken by the user. The data objects 3-6 are respectively coupled to the operator 7 via relations 9-12. Relations are components in the graph that identify what role each data object plays with respect to an associated operator. In the example shown in FIG. 2, the relations 9-12 respectively identify their associated data objects as establishing the length, width, height and center of the box. The result of operator 7 taking action on data objects 3-6 is represented in the graph by relation 15 and data object 17. Data object 17 represents the software entity created by operator 7, and relation 15 identifies the result of the operator as a box.
The command to calculate the weight of the box is represented in the graph by operator 19. A box is one of many structures that is more broadly classified as a solid. To calculate the weight of a solid, the operator 19 multiplies the volume of the solid, received via a first relation 21, by the density of the solid received via a second relation 23. In this example, the solid was already specified in the design, rather than being provided as an argument with the calculate weight command. This dependency relationship is represented in the graph by the relation 21 being connected to the data object 17 that represents the box. Since the density was not previously specified in the design, it is provided by the user as an argument with the command to calculate the weight of the box. This lack of dependency is represented in the graph by the relation 23 being connected to a data object 25 that represents the density argument and is not output from any operator in the graph. The result of operator 19 taking action on data objects 17 and 25 is represented in the graph by relation 27 and data object 29. Data object 29 represents the software entity created by operator 19, and relation 27 identifies the result of the operator as being the weight of the box.
As seen from the simple example shown in FIG. 2, the dependency graph created in accordance with the present invention illustrates the structural dependency of the design created during an interactive session. The graph illustrates that the weight 29 of the box is dependent upon the density data object 25, as well as data objects 3-5 representing the dimensions of the box. Similarly, the graph illustrates that the data object 17 representing the box is not dependent on the density data object 25. Therefore, if the designer chose to modify the density of the box during the interactive session, the only portion of the graph that would need to be re-evaluated to update the design would be operator 19; operator 7 would not need to be re-evaluated. Thus, when a design modification is made, the dependency graph enables the present invention to re-evaluate only operators that are dependent on a modified data object. Although the illustrated example is quite simple, it should be appreciated that the computational time savings provided by this feature of the present invention can be significant, especially for large designs.
A graphical representation of the user's perspective of a CAD system on which the associativity subsystem of the present invention has been installed is shown in FIG. 3. The CAD system 35 includes a user interface 37 that receives inputs from the user as conventional CAD commands 39. Typically, a user will conduct an interactive design session with the CAD system by inputting a series of CAD commands 39. In response to the series of CAD commands, the user interface 37 calls corresponding associative APIs 42, which in turn call corresponding proprietary APIs 43 of the CAD system. The APIs 43 are executed to produce a product design 45. During the interactive design session, the associative APIs 43 and a graph controller 47 together generate a dependency graph, such as the one illustrated in FIG. 2, that represents the structural dependency of the product design 45. At the end of the design session, the CAD system can also generate, from the dependency graph, a computer program 49
in a non-proprietary language such as C++ that, when executed, will also represent the structural dependency of the product design 45. The user can then, using an editor/compiler/linker 51 of the CAD system, edit the computer program 49 to represent a modified product design, and compile and link the program to the CAD system to generate a modified product design 45. Alternatively, the user can use a visual programming environment 50 to graphically edit the dependency graph, which can then be used to generate a modified product design 45 and a modified computer program 49. The output of the visual programming environment is provided to an interpreter 52 that translates expressions received from the visual programming environment 50 into corresponding associative APIs that implement the desired design actions to modify the design.
II. Integration of Associativity Subsystem
As discussed above, to enable the present invention to be used with any of a variety of software systems in a manner that is transparent to the users of those systems, a software tool is provided that is executed once on each software system to provide it with the capabilities of the present invention. This software tool can be written in any standard computer language, and is preferably written in an object-oriented programming language such as C++. FIG. 4 illustrates the architecture of this tool, which is referred to as the associative API builder tool 61. The tool 61 is executed once in connection with each application programming interface (API) in a software system which is to incorporate the features of the present invention, and generates a corresponding associated application programming interface (AAPI) for each. In one embodiment of the invention, the builder tool 61 operates upon each API for the software system individually.
As discussed above, an API is essentially a high level software function in a system that typically corresponds to a command that can be received from a user. In the example of FIG. 2, the CAD system would have APIs that implement the functions of inserting the box and calculating the weight of a solid. Conceptually, the associative API generated by the builder tool 61 for each API performs two roles. First, it performs the same role that its corresponding API performs in connection with generating the product design for the software system. For example, an associative API generated for the API in the FIG. 2 example to insert a box will perform the function of inserting the box into the product design and displaying it on the CAD system. Second, each associative API also performs the role of representing in the dependency graph the action taken by its corresponding API, so that the portions of the design generated by the API understand how they are associated with other aspects of the product design.
Because each associative API performs two roles, the builder tool 61 can simply generate two functions for each API, i.e., one function to perform each role. However, in a preferred embodiment of the present invention, the builder tool 61
generates a macro call that resolves to a call to a generic function, referred to as the associative API processor, for generating the graph structure of each associative API, and one software function for each associative API that performs the role of implementing the design action in the product design. The arguments provided to the associative API processor are the name of the associative API calling it, and the arguments to that associative API. The builder tool 61 also produces a software entity (described below) for each associative API that describes the topology of the graph entities to be constructed for that associative API, and the function represented by the operator created in the graph to represent the design action taken by the associative API.
As shown graphically in FIG. 4, the builder tool 61 operates on function templates of the proprietary APIs 62 in the software system, and function templates for corresponding associative APIs 66 to generate an associative API 63 for each API. The function template for each API and associative API defines the name of the function, the data type of its arguments and result, and the names of its arguments and result. Each associative API created by the builder tool includes three components, i.e., an associative API macro call 65, an associative API data component 67, and an associative API operator evaluator 69. As discussed more fully below, when the builder tool 61 is executed on the APIs of a new software system to generate an associative API for each, the user interface of the system is also modified so that each user command calls its corresponding associative API, rather than calling its corresponding API directly. In this manner, wrappers are provided around each of the APIs in the software system so that the added capabilities of the present invention are provided in a manner that is transparent to the user.
When called by a user command during an interactive design session, each associative API in turn calls the associative API processor 71 (FIG. 5). The processor 71 first updates the dependency graph to include an operator that represents the design action taken by the command, and then ensures that the function that actually takes the design action on the product design is called. Because the role played by each of the components of the associative APIs 63 is closely tied with the role of the associative API processor 71, these aspects of the present invention are described together, making reference to FIG. 5. FIG. 5 graphically illustrates the relationship of the AAPI components 63 to the associative API processor 71 and the CAD user interface 37.
Each associative API that calls the processor 71 is represented in the dependency graph by an operator having a specified number of data objects and a corresponding number of relations that each defines the relationship of one of the data objects to the operator. The associative API processor creates a software entity to represent each operator, relation and data object in the dependency graph. In this context, the term software entity is intended to indicate entities created by a software program which may be an object in an object-oriented programming language such as C++, or for example a structure in a programming language such as C. The associative API processor 71 is generic in that it handles calls from every associative API in the same manner, without regard to the particular design action performed by the AAPI. For example, making reference to the illustrative dependency graph shown in FIG. 2, the associative API processor 71 treats the operators 7 and 19 that respectively represent insertion of the box and calculation of its weight in the same manner, simply connecting them up in the dependency graph to their respective data objects and relations.
As mentioned above, in addition to executing the builder tool 61 on each API in the software system to generate an associative API for each, the integration process of the present invention also modifies the user interface 37 of the system so that in response to each command received from the user, the interface 37 calls a corresponding associative API, rather than calling an API directly. Specifically, it is the macro call component 65 of each associative API 63 that is called by the user interface. The user interface passes the associative API any data arguments included in the received command. For the illustrative example shown in FIG. 2, when the user inputs the command to insert the box, the user interface calls an associative API corresponding to that command and passes it the data arguments received in the command relating to the length, width, height and center position of the box. When the macro call 65 of an associative API is called by the user interface, it in turn calls the associative API processor 71 (FIG. 5) and passes to the processor a string of data that contains an ordered list of the arguments received with the command that called the macro 65, as well as the name of the macro which is used to identify its function (e.g., insert box, calculate weight).
Because the associative API processor 71 is a generic dependency graph builder and is not specifically designed to handle any particular associative API, the string that includes the name of the calling macro and the list of ordered data is insufficient to specify the manner in which the dependency graph is to be updated based upon the calling macro. Thus, the processor 71 uses the macro name in the calling string to receive additional information about the calling AAPI 63 from its data component 67. The data component 67 of each associative API includes textual information that defines the number of input data objects for its corresponding API, their respective relations to the operator, and the relation of the result data object. Whenever the software system is started-up, and before initiation of a design session, the associative API processor 71 parses an ASCII data file that describes each associative API 63 (provided by its data component 65) to generate a hash table 73 that includes an entry for each AAPI, hashed by the AAPI name. When called by an AAPI during an interactive design session, the processor 71 uses the corresponding entry in the hash table 73 to create the operator, relations and data objects that represent the calling AAPI in the dependency graph. The hash table entry for each associative API is in the form of a software entity, and identifies the number of input data objects for the AAPI, the relation of each to the AAPI's operator, and the relation of the AAPI output data object.
III. Dependency Graph Creation
When the associative API processor 71 is called by a macro call 65 during a design session, the processor 71 uses the name of the calling macro to index into the hash table 73, which outputs the software entity that includes the information relating to the structural characteristics of the calling AAPI. For example, for a call from the AAPI that relates to the function for inserting a box as described in connection with FIG. 2, the corresponding software entity output from the hash table
73 would include information indicating that the first argument in the ordered list of data passed to the processor 71 along with the macro name is the length of the box, the second argument is the width, the third is the height, and the fourth is the center position of the box. The associative API processor 71 includes a function that queries the software entity output from the hash table 73 to determine the manner in which the dependency graph should be updated for the particular AAPI macro that called the processor. This function asks the software entity output from the hash table how many inputs are associated with the calling AAPI. Next, the associative API processor 71 asks the entity what name is associated with the first argument in the list of ordered data, and uses the name (e.g., length, width, height) to define the relation of the data object to the operator. The associative API processor 71 continues in this manner until the relations of all of the input and output data objects are defined. The processor 71 derives the name of the operator from the name of the calling macro, which is included in the string of information passed to the processor 71.
As stated above, the associative API processor creates software graph entities to represent each of the operators, relations and data objects in the dependency graph. The graph entity created for each operator (e.g., insert box and calculate weight in the FIG. 2 example) includes a list of pointers to the graph entities that represent its relations. Each pointer includes the address of a memory location that stores a graph entity representing one of the relations. The graph entity created for each relation includes the name of the relation, and a pointer that includes the address of the memory location that stores the graph entity that represents the data object connected to the relation in the graph. Finally, each graph entity that represents a data object in the dependency graph includes a pointer to a memory location wherein the argument value corresponding to the data object is stored.
It should be appreciated from the foregoing that the provision in the hash table of a software entity for each AAPI that it can be queried by the associative API processor 71 to determine the structural relationship of the operator, relations and data objects related to the AAPI enables the creation of the dependency graph to be accomplished by only a single additional function (i.e., the processor 71) added to the software system, rather than requiring that a separate graph manipulation function be generated for each API in the system.
IV. Overview of Dependency Graph Evaluation
In addition to updating the dependency graph in response to an associative API macro call, the associative API processor also triggers the evaluation of each newly created operator to take the design action on the product design specified by the calling associative API. The software entity that represents each operator in the dependency graph includes two pointers relating to the operator evaluator 69 (FIG. 5) of the AAPI whose macro call resulted in the creation of the operator. The first pointer points to a library wherein the operator evaluator 69 is stored, and the second pointer specifies the name of the function in the library that is the operator evaluator. Thus, after the associative API processor 71 updates the dependency graph in response to a call from an AAPI, the processor 71 calls the newly created operator to evaluate itself. This process is illustrated graphically in FIG. 5, wherein the associative API processor 71 is shown calling the calculate weight operator 19 of FIG. 2 to evaluate itself.
As discussed above, each AAPI created by the builder tool 61 (FIG. 4) is a wrapper around a proprietary API in the software system. The operator evaluator 69 for each AAPI is a function that calls the name of the proprietary API around which it is wrapped. When called, the operator evaluator 69 collects the arguments from the input data objects connected to the evaluated operator in the dependency graph, formats the arguments in the form expected by the proprietary API, and calls the API with the arguments in the correct order to perform the desired design function. Referring again to FIG. 2, the proprietary API in the CAD system for inserting a box may, for example, be named "CV.sub.-- INSERT.sub.-- BOX (1, w, h, center)", expecting that data arguments passed to it be ordered as length, width, height and center. If a user input the command to insert a box with arguments specifying the length as two, width as three, height as four and center coordinates as (zero, zero), the user interface would call the AAPI wrapped around the CV.sub.-- INSERT.sub.-- BOX API, leading to the creation of data objects 3-5 and 17, relations 9-12 and 15, and operator 7 in the dependency graph. When the AAPI processor 71 instructs the operator 7 to evaluate itself, the operator evaluator 69 (FIG. 5) of the associative API would collect and order the arguments stored in data objects 3-5 and call the proprietary API as "CV.sub.-- INSERT.sub.-- BOX (2, 3, 4, 0, 0)". This call is identical to one that would have been made directly by the user interface 37 in the software system if the software tools of the present invention had not been installed on the system to create a wrapper around the proprietary API.
When the processor 71 calls a graph operator to evaluate itself, it is a straightforward process for the corresponding operator evaluator 69 (FIG. 5) to collect and organize the arguments in the order required by the proprietary API that will be called to take the specified design action on the product design. The operator evaluator 69 for each AAPI includes not only the name of the corresponding proprietary API to be called, but also the names and order of the arguments to be provided to the API. For example, when evaluating the operator 7 shown in FIG. 2, the corresponding AAPI evaluator 69 would first request the operator 7 to provide it with the argument representing the length of the box. The graph entity representing the operator 7
would execute a function requesting each of its relations to identify itself. Once the length relation is identified, the graph entity representing the operator 7 would request the graph entity representing the length relation 9 to provide it with the argument defining the box length. The graph entity representing the length relation 9 would then request the graph entity representing the data object 3 to pass its argument, and once the argument is received, would in turn pass the argument to the graph entity representing the insert box operator 7, which would return it to the operator evaluator 69. The evaluator 69 would request and receive the remaining arguments in the same manner. Once all the arguments were collected, the operator evaluator would call the proprietary API "CV.sub.-- INSERT.sub.-- BOX", with the call itself specifying the order of the arguments, to take the appropriate action on the product design.
When a proprietary API is called, it performs a design action on the arguments passed to it, and in addition, passes the result back to the operator evaluator, which in turn passes the result to the graph entity representing the operator being evaluated. The graph entity representing the evaluated operator then passes the result to the graph entity representing the output relation of the operator, which in turn passes it to the graph entity representing its data object, which finally stores the result in a memory location pointed to by the data object. In this manner, the result of the evaluated operator, which may serve as an argument to other operators, is inserted into the dependency graph.
1. Expanded Command Format Flexibility
In one embodiment of the invention, one or more operator evaluators 69 (FIGS. 4 and 5) are provided with a capability that increases the software system's flexibility in terms of the manner in which certain design actions can be defined at the user level. For example, although the example described above illustrates a box as being defined by its length, width, height and the coordinate position of the center of the box, it should be understood that there are other ways in which a user may want to define a box, such as by defining only the positions of the box corners. This may be desired for certain design environments where the approach taken by the designer is more conducive to defining a box in this manner, rather than by specific length, width and height. Conventionally, if the CAD system does not include a proprietary API in which a box is defined by its corners, the user is not provided with a command to define a box in this manner. However, the operator evaluator function of the present invention provides a wrapper around the proprietary APIs that can provide increased flexibility in the format of the commands available to the user. For example, if a CAD system on which the tool of the present invention is run only provides for the creation of a box that is defined in terms of its length, width, height and center, the operator evaluator function of the present invention can enable the user to define a box in additional ways, such as by its corners.
In a preferred embodiment of the present invention, the dependency graph and the computer program generated therefrom represent the structural dependency of the product design in a manner that most closely correlates to the design actions taken by the user during the design session. Therefore, when the feature of the present invention that provides additional command formats is used, the dependency graph is preferably created and stored in the manner specified by the user. For example, if the capability is provided for the user to define a box by its corners and the user exploits this capability, the dependency graph operator that represents the design action of inserting the box will include data objects and relations that define the box by its corners. When the operator is called to evaluate itself and in turn calls its AAPI operator evaluator 69 (FIG. 5), the evaluator converts the representation of the operator in the dependency graph into the form required for calling the proprietary API of the software system. Using the example for inserting the box described above, the operator evaluator associated with the insert box operator would collect the arguments defining the corners of the box in the manner described above, and would process those arguments to generate length, width, height and center coordinate arguments to be passed to the proprietary insert box command, which operates only upon arguments arranged and ordered in that fashion. The increased flexibility provided to the user does not require the creation of new proprietary APIs, because the flexibility is implemented by the wrappers provided by the present invention around the proprietary APIs.
Although in the preferred embodiment of the invention the flexibility in the command format provided to the user is implemented in the AAPI operator evaluator 69 that corresponds to each command, it should be understood that this feature of the present invention can be implemented in other ways. For example, the conversion between the format input from the user and that required by the proprietary API can be performed in the AAPI data component, so that the dependency graph will be generated in the format expected by the proprietary API. When the format conversion is implemented in this manner, the AAPI operator evaluator need not perform any format conversion.
V. Updating Software Application Entities To Reflect Participation In Dependency Graph
In addition to generating an AAPI wrapper around each proprietary API in the software system, the present invention also modifies the software application entities that are generated by the software system to represent the product design, so that each application entity knows if and where it is participating in the dependency graph. For example, if the software system on which the present invention is installed is a CAD system, the application entities generated thereby can include boxes, cylinders, and other structures that represent the product design. For example, in the illustrative example of FIG. 2, the result of evaluating the operator 7 to insert a box is an application entity that represents the box, and whose description inherently includes the arguments (length, width, height and center position) used to define the box.
As discussed above, the present invention is preferably implemented in an object-oriented programming language. Although other programming languages can be used to practice the present invention, object-oriented programming languages are advantageous in that they have capabilities which allow for a simple modification to the application entities created by the software system during a design session to enable each application entity to understand if and where it is participating in the dependency graph. Object-oriented programming languages allow application entities having some common characteristics to be defined in a common class. Referring to the illustrative dependency graph of FIG. 2, the calculate weight operator 19 calculates the weight of a solid by multiplying its volume by a density. The specific solid being operated upon in FIG. 2 is a box, which is one of a broader class of solids, which could include cylinders, spheres, etc. When defining various types of application entities in an object-oriented programming language, a hierarchical structure can be used. For example, functions and characteristics that are common to all the specific types of application entities that belong the class solids (e.g., a function to provide the weight of the solid by multiplying its volume by its density) may be defined once in the definition of the solid class. The definition of each of the more specific application entities (e.g., box, cylinder, sphere, etc.) within the class will include a reference to the solid class and will inherit therefrom. Thus, the functions and characteristics provided in the definition of the solid class form part of the definition of each of the application entities that inherit from it, and need not be duplicated in the definition of each of the more specific classes of application entities. For example, each application entity in the box class has the capability of determining its weight, without a specific function to make this determination for the box, because that function is defined in the definition of a solid, from which the box class inherits.
Using the inheritance capability available in an object-oriented programming language, the functions and capabilities necessary to enable each application entity to determine if and where it is participating in the dependency graph can be provided in a single class, referred to as an associative variable class, from which each application entity created by the software system to represent a portion of the product design is made to inherit. Each argument input to the design by the user is also defined as an application entity that inherits from the associative variable class. The associative variable class includes a field for identifying a pointer to a particular data object in the dependency graph (e.g, data objects 3-6, 17, 25 and 29
in FIG. 2). Thus, each application entity created by the software system to represent a portion of the product design, or to represent an argument input from the user, uses this pointer to point to a particular data object, if any, that represents it in the dependency graph. If the pointer field is nil in a particular application entity, it indicates that the application entity has not been assigned a corresponding data object in the dependency graph, and therefore, is not yet participating in the graph. If the pointer field has a value, the application entity is represented in the graph by the data object pointed to.
The associative variable class also provides two functions that are passed to each of the application entities that inherit from it. The first function sets the above-described pointer field to a particular value identifying the location of a corresponding data object when the application entity is added to the dependency graph. The second function retrieves the pointer value and returns it when the application entity is questioned as to where it is present in the dependency graph. As stated above, in addition to application entities generated by the software program, arguments input to the system by the user are also represented as application entities that depend from the associative variable class. Therefore, each of the application entities represented in the dependency graph as a data object depends from the associative variable class, so that each includes the data object pointer field and the functions to set and retrieve the pointer value.
The capabilities provided to each of the application entities by the associative variable class are used in the creation and management of the graph in the following manner, making reference to the example shown in FIG. 2. Initially, the user enters a command to insert a box. The entry of this command results in an AAPI 63 (FIG. 5) calling the associative API processor 71 in the manner described above. In calling the API processor 71, the AAPI macro call 65 passes the processor each of the arguments associated with the calling macro, i.e., the length, width, height and center position for the box. Each of these arguments is passed in the form of an application entity that depends from the associative variable class. Thus, in order to determine the affect of the macro call on the dependency graph, the associative API processor 71 queries each of the application entities that represents an argument to determine whether and where in the graph each argument is represented. Since none of the arguments was previously represented in the graph, each of the application entities representing one of the arguments includes a nil value in its data object pointer. Upon reading these nil pointers, the API processor 71 creates a new graph entity to represent a data object for each argument, and instructs each of the argument application entities to set its data object pointer to the memory location of its newly created graph entity. The API processor then creates graph entities representing the operator 7 for inserting the box and the relations 9-12 in the manner discussed above. In addition, the API processor 71 creates graph entities representing the relation 15 and the result data object 17. The processor 71 then instructs the operator 7
to evaluate itself, resulting in a call to its AAPI operator evaluator 69. In the manner described above, the operator evaluator calls the insert box proprietary API, which returns to the evaluator an application entity representing the box that it created. The operator evaluator 69 then updates the data object pointer in the application entity defining the box to point to the memory location for the data object 17, thereby providing the application entity that defines the box with the information relating to its participation in the dependency graph.
Continuing with the example relating to FIG. 2, the next command received from the user is to calculate the weight of the box. In response to this command, the corresponding AAPI macro call 65 passes to the associative API processor 71 the argument upon which the calculate weight function is to be performed, i.e., the application entity defining the box. The API processor 71 asks this application entity to specify the pointer value that identifies its corresponding data object in the dependency graph. Since such a data object was previously created, the address of data object 17 is returned to the processor 71. The processor 71 then updates the dependency graph by generating graph entities representing the calculate weight operator
19 and the relation 21. In the graph entity that represents the relation 21, a pointer is updated to include the address of the memory location that stores the graph entity that represents data object 17. In this manner, the dependency relationship of the calculate weight operator 19 on the insert box operator 7 is reflected in the dependency graph. The associative API processor 71 also creates new data objects 25 and 29, as well as their associated relations, to complete the dependency graph in the manner described above.
VI. Associative API Processor Routine For Creating And Evaluating Dependency Graph
The above-described capabilities of each argument and application entity to understand if and where they are participating in the dependency graph is utilized by the associative API processor 71 during the creation of the dependency graph in the manner illustrated in FIG. 6, which illustrates the steps that the processor 71 performs when it is called by an AAPI macro. Initially, in step 401, the associative API processor 71 creates a graph entity to represent an operator in the dependency graph that corresponds to the design action of the calling macro. At step 403, the method then selects a first of the macro's arguments for processing. As discussed above, each argument is passed to the associative API processor 71 as an application entity that includes a pointer field indicating if and where the argument is represented in the dependency graph by a data object.
In step 405, the method reads the data object pointer of the selected argument to determine whether it is nil, and when it is, the method proceeds to step 407 wherein a graph entity is created to represent a new data object in the dependency graph, and the application entity representing the argument is updated so that its data object pointer points to the newly created data object. After the creation of the data object in step 407, or if it is determined at step 405 that a data object already exists for the argument, the method proceeds to step 409 wherein a relation is created between the data object and the operator created in step 401. In step 411, a determination is made as to whether the argument being processed is the last argument associated with the calling macro, and when it is not, the method returns to step 403 to select another argument for processing. In this manner, the method proceeds through steps 403-411 to create the input relations and data objects associated with the operator created in step 401 and to connect them to the operator.
When it is determined at step 411 that the last argument has been processed, the method proceeds to steps 413 and 415 wherein a result data object and relation are respectively created for the operator. The method then proceeds to step 417
wherein the associative API processor 71 requests the operator to evaluate itself. The evaluation, performed by the AAPI operator evaluator 69 calling its corresponding proprietary API with an ordered list of data, returns a result in the form of an application entity to the associative API processor 71. In step 418, the result is associated with the result data object created in step 413 but updating the data object pointer in the application entity that defines the result. Finally, in step 419, the processor 71 returns the application entity that defines the result to the macro whose call initiated the method.
VII. Evaluating The Dependency Graph
In response to the processor 71 requesting evaluation of an operator in step 417 of the method of FIG. 6, argument collection and operator evaluator routines are called that are generic to all operators, and that ensure that all of the arguments required by the operator are up-to-date before calling the operator evaluator 69 of the evaluated operator. The steps of the argument collection routine are shown in FIG. 7a. Initially, a first argument associated with the evaluated operator is selected for processing in step 501, and a determination is made at step 502 as to whether this argument is "out of synch". The phrase out of synch is used to indicate that the data object that represents the argument is dependent upon at least one other graph entity that has been changed, but that has not yet been re-evaluated. Thus, if the argument is out of synch, the method proceeds to step 503 wherein updating of the argument is requested. After updating is requested at step 503, or if it is determined at step 502 that the argument is not out of synch, the method proceeds to step 504, wherein a determination is made as to whether all of the arguments for the operator being evaluated have been collected. When it is determined that they have not, the method returns to step 501 where a new argument is selected for collection. In this manner, the method proceeds through steps 501-504 until all of the arguments for the operator have been collected, and those that were out of synch have been updated. The method then proceeds to step 505 wherein the operator evaluator 69 that corresponds to the evaluated operator is called.
The steps of the operator evaluator routine are shown in FIG. 7b. Initially, a first argument associated with the evaluated operator is selected in step 506, and then in step 507 the value associated with the selected argument is retrieved from the data object pointer that represents the argument in the dependency graph. The method then proceeds to step 507, wherein the argument value is cast into a data type that is expected by the proprietary API that will be called by the operator evaluator. Each data object in the dependency graph is generic, and does not contain information as to the format of the argument that it points to. For example, the argument could be an integer, an application entity that defines a box, an application entity that defines a cylinder, etc. Therefore, before the operator evaluator calls the API, it casts the argument into the data type expected by the API.
At step 509, a determination is made as to whether all of the arguments to be passed to the API have been processed, and when they have not, the method returns to step 506 wherein another argument is selected for processed. In this manner, the method proceeds through steps 506-509 to process all of the arguments associated with the operator. When all of the arguments have been processed, the method proceeds to step 510, wherein the arguments are formatted in the manner expected by the proprietary API to be called. As discussed above, in one embodiment of the invention, the operator evaluator for an AAPI can provide additional options to the user in the manner in which commands can be formatted. If the user command and its corresponding operator in the dependency graph are formatted differently from the API, the method reformats the arguments in step 510 to that expected by the API. After the arguments are formatted, the method proceeds to step 511 wherein the proprietary API that corresponds to the operator is called, and is passed the arguments ordered in the manner that it requires. The proprietary API returns to the operator evaluator an application entity that represents the result of the design action taken by the API. At step 512, the operator evaluator updates the data object pointer in the graph entity created for the operator result in step 413 of FIG. 6.
VIII. Representing Non-Directed Operations
The foregoing discussion has related solely to directed operations, which are represented in the dependency graph of the present invention with directed operators. A directed operator has a flow in one direction, from one or more inputs to an output. However, the present invention can also be employed in a software system that supports non-directed operations. For example, a command may be executed that represents the relationship A=B*C. If this were a directed operation, the user would only be able to edit the values of B and C and the directed operator would produce the appropriate value for A. However, if the command was a non-directed operation, the user would have the option of alternatively specifying a value for A, and having the system determine values of B and C so that their product equaled the value of A. A non-directed operation can propagate a change from any of its parameters, and there is no strict concept of inputs and outputs.
The present invention provides the capability to represent both directed and non-directed operations in a single dependency graph, with directed operations being represented by directed operators, and non-directed operations being represented by non-directed operators. Subject to some limitations discussed below, the present invention enables directed and non-directed operators to be implemented homogeneously throughout a dependency graph, such that the results of directed operators can be provided as inputs to non-directed operators, and vice versa.
It should be understood that in order to solve a group of interconnected non-directed operators, some solving engine must be provided. Non-directed operations are also commonly referred to as constraints, with a group of inter-dependent non-directed operations forming a constraint set. The present invention is directed to a method for representing non-directed operators in a dependency graph, with or without directed operators, but is not directed to any particular engine for solving constraint sets formed by groups of non-directed operators. The present invention represents the structural dependency of non-directed operators, groups them together constraint sets in a manner described below, and then provides the constraint sets to a constraint solving engine that solves them.
Examples of non-directed operations (i.e., constraints) include algebraic constraints such as the example discussed above, geometric constraints between two objects, such as establishing two lines to be parallel, perpendicular, etc., and spacial constraints for two objects requiring that the objects maintain some sort of spacial relationship. For example, the present invention may represent the structural dependency of a group of simultaneous equations and can provide them together as a constraint set to a solving engine. However, the present invention is not directed to any particular engine for solving the simultaneous equations.
As should be appreciated from the foregoing, when the embodiment of the present invention that supports non-directed operators is used, the software system on which the associativity subsystem of the present invention is installed will be provided with a constraint solving engine. The present invention is not limited in the types of constraints that can be represented. However, any particular software system on which the associativity subsystem of the present invention is installed may have a constraint solving engine that is limited in the types of constraints it can solve. When this occurs, the present invention checks the design generated by the user to determine whether each constraint set formed in the design is valid, i.e., is of a type that the constraint solving engine can form. If an unsupported constraint set is formed, the present invention detects this as an error condition in the manner described below.
Since directed operators can only be evaluated in one direction, there are limits on the manner in which directed and non-directed operators can be connected in a single dependency graph. An input to a non-directed operator is considered to have a fixed value if it is the result of a directed operator. Each non-directed operator must have at least one input that is not fixed. For example, for the non-directed operation discussed above wherein A=B*C, both inputs B and C cannot be fixed, because if they were, the operator would not be non-directed in that the required relationship cannot be maintained if the value of A were altered, because both B and C are fixed. Thus, the inputs B and C could not both be provided from directed operators, because both would be fixed, leading to an over-constrained case or error condition. However, so long as one of inputs B and C is unconstrained, for example being provided from another non-directed operator, no error condition occurs because as the value of A is altered, the unconstrained input B or C can be altered in the corresponding manner.
Another limitation placed on the use of directed and non-directed operators in a single dependency graph is that a cycle should not be formed in a graph to include any directed operators. As should be understood by those skilled in the art, a cycle in a graph occurs when the tracing of any valid flow path through the graph from a start points leads back to the start point. Although cycles can validly exist that include only non-directed operators, any cycle that includes a directed operator results in an over-constrained error condition.
When a non-directed operation is performed in a design, a checking routine of the present invention analyzes the dependency graph to determine whether a corresponding non-directed operator can be added without violating one of the above-described limitations. In particular, the routine ensures that the non-directed operator is not over-constrained and has at least one input whose value is not fixed. Additionally, the routine ensures that the adding of the non-directed operator does not result in the formation of a cycle in the graph that includes a directed operator. This is accomplished by the routine beginning at the added non-directed operator and walking through each valid path of the dependency graph to determine whether any of those paths arrives back at the non-directed operator being added. If either of the two prohibited conditions occurs, an error signal is generated such that the non-directed operator cannot be added to the dependency graph in the manner attempted by the user. If no error occurs, the non-directed operator is added to the graph.
As discussed above, the present invention is not directed to any particular engine for solving a set of constraints. Rather, the present invention is directed to the graphical representation of designs that may include sets of non-directed constraints. In the manner discussed below, the present invention determines the boundaries of each non-directed constraint set in a design, and provides those constraint sets to the solving engine for simultaneous resolution. Each cycle that includes only non-directed operators forms a constraint set, with the boundaries of the constraint sets being determined by the location of directed operators in the graph, or the boundaries of the graph itself.
1. Symbolic Evaluation Pass
As discussed above in connection with FIGS. 7a-7b, when the associative API processor 71 requests that an operator in the dependency graph be evaluated, an evaluate method is called that is generic to all operators. The evaluate method is called by a graph manager 75 (FIG. 5), which is a software entity described in further detail below and performs tasks involved in managing the dependency graphs created in accordance with the present invention. The basic steps performed by the evaluation method were described above in connection with FIGS. 7a-7b. A specific implementation for this method will now be described for the embodiment of the present invention that supports the use of non-directed operators. In accordance with this embodiment of the invention, a two-pass method is executed with respect to the dependency graph. During a first pass, referred to as the symbolic pass, the graph is interrogated to form a list of operators to be evaluated, as well as the order in which the list should be evaluated. The operators included in the list are either single directed operators, or constraint sets of non-directed operators that should be evaluated simultaneously by the constraint solving engine. The second step is the evaluation of each of the operators in the order specified by the list formed during the symbolic pass, and is referred to as the evaluation pass.
The symbolic pass is represented by the flowchart of FIG. 8, and is called whenever the associative API processor 71 requests that an operator in the dependency graph evaluate itself. Initially, in step 800 a stack is opened up for the operator evaluation list which is created during the symbolic pass to define the order in which the operators and sets of constraints are to be evaluated. The stack created for this purpose is a first-in first-out stack onto which operators and constraint sets are pushed and popped in the manner described below. After the stack list is opened, the method proceeds to step 802 wherein an edited (i.e., out of synch) data object for the operator being evaluated is selected for processing. Typically, the associative API processor 71 will not demand the evaluation of an operator unless one of its data objects has been edited, requiring re-evaluation. However, when the visual editing capabilities of the present invention described below are employed, the operator itself may be changed without changing one of its data object inputs. If this occurs, the present invention establishes each of the data objects as being out of synch, so that each will be processed during the symbolic pass.
In step 804, the dependency graph is interrogated to form a list of all operators that are directly dependent on the data object selected for processing in step 802. A directed operator is directly dependent upon a data object when the data object is provided as an input to the operator, whereas a non-directed operator is directly dependent on a data object when it is directly connected to the data object in any fashion. No attempt is made in step 804 to propagate through the dependency graph and locate other operators that are indirectly dependent on the data object in that they may be affected by a change to it, because those operators will be identified through the recursive nature of the symbolic pass in the manner described below.
In step 806, one of the operators identified in the list formed during step 804 is selected for processing, and in step 808, a determination is made as to whether this operator is directed. When the selected operator is directed, the method proceeds to step 810, wherein a routine for processing directed operators (FIG. 9) is called. Conversely, when the selected operator is non-directed, the method proceeds to step 812, wherein a routine for processing non-directed operators (FIGS.
10a-10b) is called. The operator processing routines push the processed operators onto the operator evaluation stack in the proper order for evaluation, and are discussed in detail below.
When the appropriate processing routine called in either step 810 or 812 to handle the processing of the most recently selected operator returns to the symbolic pass, the method proceeds to step 814, wherein a determination is made as to whether any operators in the list formed in step 804 remain to be processed, and when any remain, the method returns to step 806 wherein another operator is selected for processing. In this manner, the method proceeds through steps 806-814 to process all of the operators in the list created in step 804 that are directly dependent upon the first edited data object selected for processing in step 802.
When it is determined at step 814 that no operators remain for processing, the method proceeds to step 816, wherein a determination is made as to whether any edited data objects for the operator whose evaluation called the method remain for processing, and when at least one remains for processing, the method returns to step 802, wherein another edited data object is selected for processing. In this manner, the method proceeds through steps 802-816 until all of the edited data objects for the operator being evaluated have been processed. When it is determined at step 816 that all of those data objects have been processed, the method terminates.
The direct operator processing routine called in step 810 of FIG. 8 is represented by the flowchart of FIG. 9. Initially, in step 820 the routine determines whether the operator being processed has already been pushed onto the operator evaluator stack, and when it has, the routine simply terminates. When it is determined that the operator has not already been pushed onto the stack, the method proceeds to step 822, wherein one of the data objects input to the directed operator is selected for processing. In step 824, a determination is made as to whether the selected data object is out of synch, and when it is, the method proceeds to step 826 wherein the operator that sources that data object is selected for processing. The method then proceeds to step 828, wherein a determination is made as to whether the operator selected for processing in step 826 is a directed or non-directed operator.
When the source operator is a non-directed operator, the method proceeds to step 830 wherein the non-directed operator processing routine is called to process that operator in the manner discussed below. Conversely, when the source operator is directed, the directed operator processing routine is re-called to process that operator in step 832. In this manner, the directed and non-directed operator processing routines are executed in a recursive manner to step through the dependency graph and process all of the operators that require reevaluation to generate the data objects operated upon by the operator whose evaluation initiated the call to the symbolic evaluation pass (FIG. 8). It should be understood that the evaluation or re-evaluation of the dependency graph should be performed by evaluating the operators or sets of constraints on the left-hand side of the graph first, and the proceeding through the graph in a left-to-right manner. By executing the operators in this manner, it will be ensured that no operator is evaluated until all operators that affect its data objects have been updated.
When it is determined at step 824 that the selected data object of the operator being processed is not out of synch, or after the appropriate routine has been called to process the source operator for that data object in either of steps 830 or
832 when the data object is out of synch, the method proceeds to step 834, wherein a determination is made as to whether any data objects for the selected operator remain to be processed. When it is determined at step 834 that at least one data object remains to be processed, the routine returns to step 822, wherein another data object is selected for processing. In this manner, the method proceeds through steps 822-834 to process all of the data objects for the operator whose evaluation caused the symbolic evaluation pass (FIG. 8), and thus the directed operator processing routine, to be called.
Finally, when it is determined at step 834 that no data objects remain to be processed for the operator whose evaluation called the processing routine, the operator is pushed onto the operator evaluation stack in step 836.
The recursive nature of the directed and non-directed operator processing routines ensures that the operators in the dependency graph will be evaluated in the correct order to achieve the above-described desired results. As seen from the foregoing description of FIG. 9, an operator is not pushed onto the evaluation stack in step 836 until it is determined at step 834 that all of its data objects have been processed. Furthermore, during the processing of the data objects, for each that is out of synch, the directed or non-directed operator processing routine is called to process the operator that sources the data object. When the processing routine of FIG. 9 is called to operate upon to those source operators, a determination is similarly made to ensure that each of its data objects are up to date, and when any is not, the routine is called again to process that source operator. Because of this recursive nature of the routine, each operator that must be evaluated to provide an updated data object to another operator is pushed onto the stack in step 836 during its corresponding execution of the routine before the operator that responds to its data object, and therefore, will be evaluated before any operator that is dependent upon its result. The operator whose evaluation initially called the symbolic pass routine (FIG. 8) is the first to be processed, and therefore, is at the highest level of the recursive process of the routine. Therefore, this operator is pushed onto the operator evaluator stack only after each of the operators that produce a result that it depends upon have been pushed onto the stack during previous iterations of the recursire process.
The non-directed operator processing routine is represented by the flowchart of FIG. 10. As with the directed operator routine of FIG. 9, the routine of FIG. 10 is initially called when the associative API processor 71 demands the evaluation of an operator in the dependency graph. In step 840, a determination is made as to whether the operator has already been pushed onto the operator evaluator stack as part of a previously defined constraint set, and when it has, the routine terminates. If the operator is not already on the stack, the method proceeds to step 842, wherein a determination is made as to whether a constraint set is currently open, and if one is not, the method proceeds to step 844 wherein a constraint set is opened.
As discussed above, the present invention may be installed on a software system that includes a constraint evaluator engine for evaluating constraint sets that can include multiple non-directed operators. In order to evaluate such a constraint set correctly, the engine should receive the the set of tightly coupled non-directed operators as a group. Therefore, when evaluating a dependency graph that includes both directed and non-directed operators, the dependency graph is organized by the symbolic pass of FIG. 8 so that the constraint sets can be provided to the engine as a group.
As discussed above, directed operators are simply pushed onto the operator evaluator stack in their proper order for evaluation due to the recursire nature of the directed operator processing routine. However, a constraint set is not pushed onto the operator evaluator stack until the entire set has been processed. Only after each of its non-directed operators has been processed is the constraint set pushed onto the operator evaluator stack. Each constraint set is pushed onto the stack in the proper evaluation order relative to other constraints sets and directed operators in the dependency graph, which may occur well after the set was opened.
After a constraint set is opened in step 844, or when it is determined that one was already opened in step 842, the method proceeds to step 846 wherein the non-directed operator being processed is added to the open constraint set. Thereafter, in step 848, one of the data objects associated with the non-directed operator is selected for processing. The method then proceeds to step 850, wherein a list is formed of the operators that directly source the data object selected in step 848. Non-directed operators directly source the data object if they are directly connected to it, whereas directed operators directly source the data object if it is their result data object.
In step 852, a determination is made as to whether the list of direct source operators generated in step 850 includes a directed operator. No more than one directed operator may source any single data object. When it is determined that the list of direct source operators includes a directed operator, the method proceeds to step 854, wherein a determination is made as to whether the selected data object is out of synch. When the data object is out of synch, the method proceeds to step 856, wherein the directed operator processing routine of FIG. 9 is called to process the directed operator that sources the selected data object.
As discussed above in connection with FIG. 9, the calling of the directed operator processing routine will result in the processing of not only the directed operator that it is initially called to process, but also all other operators, directed or non-directed, that generate data objects on which it directly or indirectly depends. Thus, by calling the directed operator processing routine prior to completing the processing of the constraint set, the non-directed operator processing routine of FIG. 10 ensures that any directed operators that feed the constraint set will be placed upon the operator evaluator stack before the constraint set. Since the output of a directed operator will be fixed with respect to the constraint set, the method of FIG. 10 ensures that any fixed values to the constraint set are evaluated before the constraint set is passed to the constraint solving engine for resolution.
When either the directed operator processing routine returns to step 856, it is determined at step 854 that the selected data object is not out of synch, or it is determined at step 852 that the list of source operators generated at step 850 does not include a directed operator, the method proceeds to step 858. In step 858, a determination is made as to whether the list of source operators generated in step 850 includes a non-directed operator, and when it does, the method proceeds to step 860, wherein a non-directed operator is selected for processing, and then to step 862 wherein the non-directed operator processing routine is called for the selected operator.
As should be appreciated from the foregoing, like the routine of FIG. 9 for processing directed operators, the non-directed operator processing routine of FIG. 10 operates in a recursive manner, However, there is a significant difference between the recursive nature of these routines. As discussed above, the recursive nature of the directed operator routine of FIG. 9 is the technique by which the directed operators are pushed onto the operator evaluator stack in the order in which they are to be executed. By contrast, and as should be seen from the above-described steps of the non-directed operator processing routine, when non-directed operators are processed, they are not individually pushed onto the operator evaluator stack, but rather, are simply added to an open constraint set. The order in which the non-directed operators are placed into the constraint set is not significant, since the constraint resolving engine will operate upon all of the non-directed operators in the set simultaneously. Therefore, the recursire nature of the routine shown in FIG. 10 is employed solely to ensure that all of the non-directed operators in a constraint set are added to the set, and is not employed to ensure any order in which they are added to the set because that order is irrelevant.
After the non-directed operator processing routine returns from processing the non-directed operator selected in step 860, the method proceeds to step 864. In step 864, a determination is made as to whether any non-directed operators remain for processing, and when at least one remains to be processed, the method returns to step 860 wherein another non-directed operator is selected for processing. In this manner, the routine steps through each of the non-directed operators in the list of source operators generated in step 850, until it is determined in step 864 that all of the non-directed operators have been processed.
When it is determined in step 864 that no non-directed operators remain to be processed, or when it is determined at step 858 that the list of source operators does not include any non-directed operators, the method proceeds to step 866. In step
866, a determination is made as to whether any data objects remain to be processed for the non-directed operator for which the routine was called, and when at least one data object remains to be processed, the method returns to step 848 wherein another data object is selected for processing. In this manner, the method proceeds through steps 848-866 until all of the data objects for the operator for which the routine was called have been processed.
When it is determined at step 866 that no data objects remain to be processed, the method proceeds to step 868 wherein a determination is made as to whether the non-directed operator for which the routine was called opened a constraint set. This step is included in the routine due to the recursire nature of its execution. When the routine is executed for an operator that did not open the currently open constraint set, other non-directed operators may remain to be processed that should be added to the constraint set, and therefore, the constraint set should not yet be closed and added to the operator evaluator stack. Therefore, when it is determined at step 868 that the calling operator did not open the constraint set, the method simply terminates, which will return to step 858 of the next highest level in the recursire execution of the routine.
When it is determined at step 868 that the calling operator opened the currently open constraint set, the method proceeds to step 870 wherein a determination is made as to whether the constraint set is empty, and when it is, the method proceeds to step 872 where the constraint set is deleted prior to termination of the method. When the constraint set is not empty, the method proceeds to step 874 where the constraint set is closed, and then in step 876 the closed constraint set is pushed onto the operator evaluator stack as its most recent entry prior to termination of the method.
2. Evaluation Pass
As should be appreciated from the foregoing, the recursive execution of the directed and non-directed operator processing routines of FIGS. 9 and 10 during the symbolic pass places directed operators and constraint sets of non-directed operators onto the operator evaluator stack in the order in which they should be evaluated. Therefore, the routine that executes the actual evaluation pass to update the graph is straightforward, and is represented by the flowchart of FIG. 11.
Initially, in step 880 the method executes the operators and constraint sets in the order specified by the stack. The evaluation routine implemented for each operator and constraint set was discussed above in connection with FIGS. 7a and 7b and involves the collection and formatting of arguments, and then calling the appropriate proprietary APIs to update the design. The method then proceeds to step 882, wherein the stack is saved for potential re-use in connection with one embodiment of the invention. Depending upon the nature of the changes made by the user, it may be possible to re-evaluate the graph two or more times without requiring separate symbolic passes for each re-evaluation. In particular, if a user re-edits any leaf node data objects that are input to the graph, the symbolic pass need not be re-executed because the results on the operator evaluator stack will be identical. Additionally, if the only change to the design is the editing of data objects that are inputs to directed operators that are already on the operator evaluator stack, the symbolic pass again need not be executed.
IX. Integration Process
As should be appreciated from the foregoing, the present invention can be used in conjunction with any software system composed of functions, following the installation of the software of the present invention, and the execution of an integration process on the software system. The associated API processor function and the associative variable class are generic with respect to the specifics of the software systems on which the present invention can be installed, and therefore, are provided in the installed software. The installed software executes an integration process shown in FIG. 12. The details of each step of the process were described above. Initially, in step 301 the class definition of each application entity generated by the software system to represent a portion of the product design, as well as those that represent the arguments input to the design, are modified to inherit from the associative variable class so that they have the above-described capabilities used in determining if and where they are participating in the dependency graph. Next, an AAPI is generated for each proprietary API in the software system in step 302.
Thereafter, the user interface is modified at step 303 so that in response to commands received from the user, the user interface calls the AAPIs generated in step 302, rather than directly calling the APIs of the software system. Finally, in step 304 an initialization function is executed which generates the graph manager, and which causes the graph manager to create the software entities that form the entries of the hash table.
Once the integration process of FIG. 12 is executed on a software system, the system is provided with the capabilities of the present invention in a manner that is transparent to the user, and does not require special user training. In addition, it should be appreciated that the operation of the integration process on a software system provides parametric capability to the system, even if no such capability was provided in the proprietary commands and corresponding APIs in the system. As discussed above, this characteristic of the present invention facilitates third parties providing add-on capabilities to the software system, because additional commands provided by the third party need not be integrated into the command set of the software system to provide parametric capabilities.
X. Parametric Capabilities
As discussed above, one of the advantages of the present invention is that when modifications are made to the product design, the modifications are incorporated into the design using the dependency graph so that only those operators with results that are affected by the modification are re-evaluated. This aspect of the present invention is controlled by the graph manager 75 (FIG. 5). The graph manager is a software entity that receives inputs from the user interface 37 to determine when modifications have been made to the product design. Most CAD systems include a parametric interactor which, after an application entity (e.g., a box, cylinder, etc.) has been added to the design, allows the user to make modifications to the parameters relating thereto, e.g., changing the length, width and/or height of a previously created box.
In conjunction with the present invention, a change to a parameter in the design results not only in a change to the product design 45 (FIG. 3) output from the system, but also modifies at least one argument associated with a data object in the dependency graph. Thus, when the software system provides a parametric interactor that allows a user command to change a parameter of the design, the present invention associates the command received from the user with the data object that represents the changed parameter in the dependency graph. Specifically, when the user enters a command to change a parameter, the new argument is passed from the user interface 37 to the graph manager 75, which updates the memory location pointed to by the corresponding data object in the dependency graph to reflect the changed argument.
Thereafter, the graph manager 75 executes the two pass process for propagating the change into the product design 45 discussed above in connection with FIGS. 8-11.
In one embodiment of the invention, changes to existing design parameters are not immediately incorporated into the product design. Rather, updates to the design are not implemented unless and until the user requests recalculation. This feature is advantageous when, for example, a user wishes to change several parameters before updating the design, because the system conserves resources by not recalculating after each parameter change. When the user requests recalculation, the graph manager 75
instructs the associative API processor 71 to cause the operators in the dependency graph that depend upon a changed parameter to re-evaluate themselves in the manner described above. In one embodiment of the invention, two modes of recalculation are provided. A first mode is known as regeneration forward and involves the recalculation of all operators that are dependent upon a change parameter. The second mode is known as regeneration on demand and is demand driven. In this second mode, the user can specify only a subset of the design to be updated. For example, the user may request to see the results of a parameter change on only a portion of the design. Making reference to the illustrative example of FIG. 2, the user could for example make a change to the length parameter associated with data object 3, and request to see the impact that this parameter change would have with respect only to the generated box. If the user made such a demand, the graph manager 75 would instruct the associated API processor 71 to cause only the operator 7 to re-evaluate itself. Thus, although the operator 19 is also dependent upon the parameter associated with data object 3, the graph manager would not instruct the associative API processor 71 to cause operator 19 to re-evaluate itself because this was not demanded by the user.
XI. Hierarchical Operators
In one embodiment of the invention, a capability is provided to represent operations performed by the user in a hierarchical manner in the dependency graph. Hierarchical operators are created that each represents one or more lower level operators arranged in some logical manner to represent a design goal of the user. As discussed in more detail below, the hierarchical capability can be employed by the user to group together in a hierarchical manner multiple commands of the software system on which the associativity subsystem of the present invention is installed, and can also be used by the software system to group a command and one or more subcommands in a single hierarchical group.
The hierarchical capability of the present invention allows a set of low level design operations to be organized and represented as a single higher level goal oriented activity of the user in the dependency graph. For example, a user designing a rotor for an automobile on a CAD system may create a first hierarchical operator by grouping together all of the low level operators used to define the lug connections for the rotor, and a second hierarchical operator by grouping together the low level operators used to add cooling channels into the rotor. By grouping together a number of low level operators and representing them with a single hierarchical operator, the dependency graph generated for the design can be simplified to represent the goal oriented activity of the user more meaningfully. Additionally, once they are formed, the hierarchical operators can be copied for use in other places in the design so that the low level design operations that created the hierarchical group need not be duplicated.
When the associativity subsystem of the present invention is integrated into a software system, the resulting associative system can also implement the hierarchical capability to group together a command with a corresponding series of subcommands that are typically executed by the user along with the command to define certain characteristics of the command. For example, many CAD systems employ features, which are a form of higher level geometric modeling that correlates to the design goals of the user, but require the execution of subcommands with the feature to define the specifics of the design goal. Employing the hierarchical capability of the present invention, a CAD system on which the associativity subsystem of the present invention is installed can represent high level features in the dependency graph using a hierarchical operator, rather than requiring that each feature be represented by separate operators for the main command and all of its supporting subcommands that may be required to define the potentially complex geometric modeling function performed by the feature.
An example of a common CAD feature is a hole, of which there are many different types. FIG. 15 shows an example of a countersunk hole 700 provided in a box 702. To insert the countersunk hole in the box 702, the user specifies a number of defining parameters, including a face datum 704 into which the hole is to be provided, the position of the hole center on the face datum, the depth 706 of the hole, the radius R.sub.2 of the hole, the radius R.sub.1 of the countersink, and the angle .theta. of the countersink. These parameters are specified by executing a group of subcommands along with the feature command for creating the countersunk hole.
If the hierarchical capability of the present invention were not employed, the design action of a user defining a box with a countersunk hole would be represented by a dependency graph such as the one shown in FIG. 16. The output of operator 716
is a data object 724 that represents the resulting application entity defining the box with a countersunk hole. As shown, box itself is represented by a data object 712 that is the result of a box operator 710 having a plurality of relations and data objects as inputs. The insertion of the countersunk hole in the box is represented by three operators 714-716 that correspond to the feature command and two supporting subcommands. The operator 714 is connected to the data object 712 representing the box, and represents a subcommand executed by the user to select the top face of the box as the portion thereof into which the countersunk hole is to be provided. The result of operator 714 is the top face of the box. Operator 715 receives this result and represents a subcommand executed by the user to select the datum for the top face to receive the countersunk hole. The result of operator 715 is input to the countersunk hole operator 716, which represents the feature command. In addition to the datum input, the countersunk hole operator also is connected to data object 718 that represents the location of the hole, data object 712 representing the solid (i.e., the box into which the hole is to be provided), and data objects 720-723 that respectively represent the radiuses R.sub.1, R.sub.2, the angle .theta., and the depth for the countersunk hole.
When the hierarchical capability of the present invention is employed, the dependency graph that represents the above-described design action can be generated in a manner shown in FIG. 17. The operators 714-716 of FIG. 16 are represented by a single hierarchical operator 726, which represents the creation of a countersunk hole in the box. The hierarchical operator 726 is shown as having two inputs that import data object 712 that represents the box into the hierarchy for connection to i