Method for detecting differences between graphical programs

• US 5,974,254 A
• Filed: 06/06/1997
• Issued: 10/26/1999
• Est. Priority Date: 06/06/1997
• Status: Expired due to Term

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Hsu, Ray
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Pender, Jr., Michael J.
• Application Number:
  US08/870,262
• Time in Patent Office: 872 Days
• Field of Search: 395/703, 395/704, 395/183.13, 395/183.14
• US Class Current: 717/109
• CPC Class Codes: G06F 8/34 Graphical or visual programming
• CPC Class Codes: G06F 8/71 Version control security arrangements therefor G06F21/57; Configuration management

Abstract

A method for detecting differences between two graphical programs is disclosed. The graphical programs include objects, preferably arranged as a user interface panel, including controls and indicators, and a block diagram, including graphical code function blocks connected together as a data flow program. Directed graph data structures are created to represent the graphical programs, wherein the vertices of the graphs are the objects of the graphical programs and the edges of the graphs are data flow signals of the block diagram and/or hierarchical relationships of the user interface panel objects. The objects of the two graphical programs are heuristically matched together using a scoring approach. The scores are stored in a match matrix and indicate a degree of similarity between an object in the first graphical program and an object in the second graphical program according to one or more criteria. The matching criteria include object type, object connectivity and object attributes. The match matrix is resolved to generate a 1:1 or 1:0 correspondence between the objects in the first and second graphical programs based on the match scores. The matching information is used to determine differences in the two graphical programs. First, using the matching information and a compare engine, the objects are grouped into exact matching subgraphs and then into non-exact matching subgraphs. Non-exact matching subgraphs are matched and merged where possible using transitivity. Objects in the non-exact matching subgraphs are compared using the compare engine to detect additional differences. All detected differences are stored and displayed for the user. The differences may be displayed in various manners such as drawing a circle around the differences, highlighting the differences by color, and/or displaying a textual description of the differences.

Claims

1. A computer-implemented method for detecting differences between first and second graphical programs, wherein the method executes on a computer including a display screen and an input device, wherein the first and second graphical programs comprise graphical code, wherein the first graphical program comprises a first plurality of objects and wherein the second graphical program comprises a second plurality of objects, the method comprising:

creating data structures to represent said first and second graphical programs;

matching said first plurality of objects of said first graphical program with said second plurality of objects of said second graphical program;

determining differences between said first graphical program and said second graphical program in response to said matching; and

displaying an indication of said differences on the display screen.

2. The method of claim 1, wherein said matching includes determining matches between one or more of said first plurality of objects of said first graphical program with one or more of said second plurality of objects of said second graphical program.

3. The method of claim 2, wherein said matching comprises determining objects of said first graphical program which have a same type as objects of said second graphical program.

4. The method of claim 3, wherein said matching further comprises determining if an object of said first graphical program which has the same type as an object of said second graphical program has the same type as another object in said second graphical program.

5. The method of claim 1, wherein said determining differences includes determining objects present in said first graphical program which have no matching object in said second graphical program.

6. The method of claim 1, wherein said determining differences includes comparing matching objects in said first graphical program and said second graphical program to determine differences in said matching objects.

7. The method of claim 6, wherein each of said first plurality of objects and said second plurality of objects comprises a set of attributes and methods, wherein said comparing matching objects includes comparing attributes of said matching objects in said first graphical program and said second graphical program.

8. The method of claim 1, wherein said determining differences between said first and second graphical programs comprises finding functional differences between said first graphical program and said second graphical program, wherein a functional difference indicates a potential difference in execution of said first and second graphical programs.

9. The method of claim 8, wherein said determining differences between said first and second graphical programs comprises finding cosmetic differences between said first and second graphical programs, wherein a cosmetic difference is a non-functional difference.

10. The method of claim 1, wherein said first plurality of objects and said second plurality of objects include function block icons.

11. The method of claim 1, wherein said first plurality of objects and said second plurality of objects include controls and indicators.

12. The method of claim 1, wherein said first plurality of objects and said second plurality of objects include function block icons;

wherein said first plurality of objects and said second plurality of objects further include data flow paths coupled between said function block icons.

13. The method of claim 1, wherein said displaying said differences includes displaying a textual description of each of said differences.

14. The method of claim 1, wherein said displaying said differences comprises displaying said first and second graphical programs, wherein said displaying said differences further comprises highlighting each of said differences between said first and second graphical programs.

15. The method of claim 1, wherein said first and second graphical programs each comprise a block diagram comprising the graphical code, a user interface panel for displaying one or more of data output from the block diagram and data input to the block diagram, and graphical program attributes;

wherein said determining differences between said first graphical program and said second graphical program comprises;

determining differences between said block diagrams of said first and second graphical programs;

determining differences between said user interface panels of said first and second graphical programs;

determining differences between said graphical program attributes of said first and second graphical programs.

16. The method of claim 1, wherein said creating data structures includes:

creating one or more data structures which includes information regarding said first plurality of objects in said first graphical program and said second plurality of objects in said second graphical program.

17. The method of claim 16, wherein said one or more data structures each comprise directed acyclic graphs comprising a plurality of vertices connected by edges, wherein each of said vertices represents one of said first plurality of objects or said second plurality of objects in one of said graphical programs.

18. The method of claim 16, wherein said one or more data structures each comprise directed graphs comprising a plurality of vertices connected by edges, wherein each of said vertices represents one of said first plurality of objects or said second plurality of objects in one of said graphical programs.

19. The method of claim 18, wherein said first and second graphical programs each comprise a block diagram comprising the graphical code and a user interface panel for displaying one or more of data output from the block diagram and data input to the block diagram;

wherein, for each graphical program, said one or more data structures comprise;

a block diagram data structure comprising a directed graph, wherein the edges of said graph between said first or second plurality of objects represent directed flow of data and/or hierarchical relationship between said first or second plurality of objects in said block diagram;

a user interface panel data structure comprising a directed graph, wherein the edges of said graph between said first or second plurality of objects represent a hierarchical relationship between said first or second plurality of objects in said user interface panel.

20. The method of claim 1, wherein said first graphical program includes a first data structure stored in a memory of the computer system which comprises information regarding said first graphical program, and wherein said second graphical program includes a second data structure stored in the memory of the computer system which comprises information regarding said second graphical program, wherein said creating data structures includes:

creating a third data structure which includes information regarding said first plurality of objects in said first graphical program, wherein said third data structure is created in response to said first data structure;

creating a fourth data structure which includes information regarding said second plurality of objects in said second graphical program, wherein said fourth data structure is created in response to said second data structure.

21. The method of claim 1, wherein said creating data structures includes:

creating a first data stucture which includes information regarding said first plurality of objects in said first graphical program;

creating a second data structure which includes information regarding said second plurality of objects in said second graphical program;

wherein, for each respective object in said first graphical program, said matching comprises;

comparing the respective object in said first graphical program with one or more objects in said second graphical program;

determining a score value for a plurality of object pairs in response to said comparing, wherein each of said plurality of object pairs comprises two object elements, said two object elements comprising said respective object in said first graphical program and an object of said one or more objects in said second graphical program, wherein said score value indicates a degree of matching between said object elements comprising said object pair.

22. The method of claim 21, wherein said determining said score value for one of said plurality of object pairs includes examining connectivity of object elements comprising said object pair.

23. The method of claim 21, wherein said determining said score value for one of said plurality of object pairs includes examining attributes of object elements comprising said object pair.

24. The method of claim 21, wherein said score value is a weighted score value, wherein said determining said score value for one of said plurality of object pairs includes examining connectivity of object elements comprising said object pair and examining attributes of object elements comprising said object pair;

wherein said connectivity of object elements has greater weight than said attributes of said object elements.

25. The method of claim 24, wherein said attributes comprise functional attributes and cosmetic attributes;

wherein said functional attributes have greater weight than said cosmetic attributes.

26. The method of claim 21, wherein said matching further comprises:

storing said score values in a match matrix, wherein said match matrix comprises rows which correspond to said first plurality of objects in said first graphical program, and wherein said match matrix comprises columns which correspond to said second plurality of objects in said second graphical program;

wherein for an ith row and a jth column, the matrix element (i,j) includes the score value for the object pair comprising object i and object j.

27. The method of claim 26, wherein said matching further comprises:

resolving said match matrix using said match matrix score values, wherein said resolving produces a 1;

1 or 1;

0 relationship between objects in said first graphical program and objects in said second graphical program depending upon whether or not an object in said first graphical program has a matching object in said second graphical program.

28. The method of claim 26, wherein said matching further comprises:

resolving said match matrix using said match matrix score values, wherein, for each of at least a subset of said rows corresponding to said first plurality of objects, said resolving produces a column from said second plurality of objects in said second graphical program, wherein said produced column has a match matrix element with a highest score value for the respective row.

29. The method of claim 1,

wherein said creating data structures includes:

creating a first data structure which includes information regarding said first plurality of objects in said first graphical program;

creating a second data structure which includes information regarding said second plurality of objects in said second graphical program;

wherein said matching produces a resolved match matrix, wherein said resolved match matrix comprises matching information regarding matches between said first plurality of objects in said first graphical program and said second plurality of objects in said second graphical program;

wherein said determining differences between said first graphical program and said second graphical program comprises;

grouping objects which have exact matches with connectivity matches into exact matching connected components using said matching information;

grouping remaining objects to produce non-exact matching connected components wherein said grouping remaining objects produces a first list of non-exact-matching connected components for said first data structure and produces a second list of non-matching connected components for said second data structure;

matching said first and second lists of non-exact matching connected components, wherein said matching said first and second lists of non-exact matching connected components includes finding common objects in said first and second lists of non-exact matching connected components, wherein said matching said first and second lists of non-exact matching connected components produces second matching information;

merging said first and second lists of non-exact matching connected components using said second matching information, wherein said merging produces a composite non-exact matching connected component list;

storing corresponding non-exact matching connected components in a result data structure;

comparing matching objects in corresponding non-exact matching connected components to determine additional object differences;

storing said additional object differences in said result data structure.

30. The method of claim 29, wherein said grouping objects which have exact matches with connectivity matches comprises grouping objects which have exact matches with connectivity matches using said first and second data structures and said matching information to produce a first list of exact matching connected components for said first data structure and to produce a second list of exact matching connected components for said second data structure, wherein said grouping objects includes comparing objects according to one or more criteria to determine exact matches between objects, wherein an exact match comprises a match in the match matrix and match in said comparing.

31. The method of claim 1,

wherein said first graphical program comprise a first user interface panel including a subset of said first plurality of objects for displaying one or more of outputs from the block diagram or inputs to the block diagram;

wherein said second graphical program comprise a second user interface panel including a subset of said second plurality of objects for displaying one or more of outputs from the block diagram or inputs to the block diagram;

wherein said matching produces a user interface panel match matrix comprising matching information;

wherein said determining differences includes determining differences between said first user interface panel and said second user interface panel which comprises;

comparing matching top-level objects of said first and second user interface panels to determine differences between said top-level objects using said matching infounation;

comparing low-level objects of said top-level objects to determine differences between said low-level objects using said matching information;

storing said differences in response to said steps of comparing.

32. The method of claim 1, wherein said determining differences between said first graphical program and said second graphical program includes comparing differences between attributes of said first graphical program and attributes of said second graphical program.

33. The method of claim 1, wherein each of said first and second graphical programs comprises a user interface panel and a block diagram, wherein said first graphical program comprises a first user interface panel and a first block diagram, and wherein said second graphical program comprises a second user interface panel and a second block diagram;

wherein said creating data structures comprises creating a data structure for objects in said first block diagram and said first user interface panel and creating a data structure for objects in said second block diagram and said second user interface panel;

wherein said matching comprises matching one or more objects in said first block diagram with one or more objects in said second block diagram, and wherein said matching further includes matching one or more objects in said first user interface panel with one or more objects in said second user interface panel;

wherein said determining differences between said first graphical program and said second graphical program comprises determining differences between said first block diagram and said second block diagram and determining differences between said first user interface panel and said second user interface panel.

34. A computer system for detecting differences between first and second graphical programs, comprising:

a central processing unit (CPU);

a display screen operably coupled to the CPU;

an input device operably coupled to the CPU; and

a memory for storing said first and second graphical programs and for storing a difference program for detecting differences between said first and second graphical programs, wherein the fast and second graphical programs comprise graphical code, wherein the first graphical program comprises a first plurality of objects and wherein the second graphical program comprises a second plurality of objects;

wherein said CPU is operable to fetch program instructions of said difference program from said memory and to execute said program instructions to;

create data structures to represent said first and second graphical programs;

match said first plurality of objects of said first graphical program with said second plurality of objects of said second graphical program;

determine differences between said first graphical program and said second graphical program in response to the matching; and

display an indication of said differences on the display screen.

35. A computer-readable storage medium comprising program instructions for detecting differences between first and second graphical programs, wherein the program instructions execute on a computer including a display screen and an input device, wherein said program instructions are executable to implement:

creating data structures to represent first and second graphical programs, wherein the first and second graphical programs comprise graphical code, wherein the first graphical program comprises a first plurality of objects and wherein the second graphical program comprises a second plurality of objects;

matching said first plurality of objects of said first graphical program with said second plurality of objects of said second graphical program;

determining differences between said first graphical program and said second graphical program in response to said matching; and

displaying an indication of said differences on the display screen.

36. The medium of claim 35, wherein said matching includes determining matches between one or more of said first plurality of objects of said first graphical program with one or more of said second plurality of objects of said second graphical program.

37. The medium of claim 36, wherein said matching comprises determining objects of said first graphical program which have a same type as objects of said second graphical program.

38. The medium of claim 37, wherein said matching further comprises determining if an object of said first graphical program which has the same type as an object of said second graphical program has the same type as another object in said second graphical program.

39. The medium of claim 35, wherein said determining differences includes determining objects present in said first graphical program which have no matching object in said second graphical program.

40. The medium of claim 35, wherein said determining differences includes comparing matching objects in said first graphical program and said second graphical program to determine differences in said matching objects.

41. The medium of claim 40, wherein each of said first plurality of objects and said second plurality of objects comprises a set of attributes and methods, wherein said comparing matching objects includes comparing attributes of said matching objects in said first graphical program and said second graphical program.

42. The medium of claim 35, wherein said determining differences between said first and second graphical programs comprises finding functional differences between said first graphical program and said second graphical program, wherein a functional difference indicates a potential difference in execution of said first and second graphical programs.

43. The medium of claim 42, wherein said determining differences between said first and second graphical programs comprises finding cosmetic differences between said first and second graphical programs, wherein a cosmetic difference is a non-functional difference.

44. The medium of claim 35, wherein said first plurality of objects and said second plurality of objects include function block icons.

45. The medium of claim 35, wherein said first plurality of objects and said second plurality of objects include controls and indicators.

46. The medium of claim 35, wherein said first plurality of objects and said second plurality of objects include function block icons;

wherein said first plurality of objects and said second plurality of objects further include data flow paths coupled between said function block icons.

47. The medium of claim 35, wherein said displaying said differences includes displaying a textual description of each of said differences.

48. The medium of claim 35, wherein said displaying said differences comprises displaying said first and second graphical programs, wherein said displaying said differences further comprises highlighting each of said differences between said first and second graphical programs.

49. The medium of claim 35, wherein said first and second graphical programs each comprise a block diagram comprising graphical code, a user interface panel for displaying data input/output to/from the block diagram, and graphical program attributes;

wherein said determining differences between said first graphical program and said second graphical program comprises;

determining differences between said block diagrams of said first and second graphical programs;

determining differences between said user interface panels of said first and second graphical programs;

determining differences between said graphical program attributes of said first and second graphical programs.

50. The medium of claim 35, wherein said creating data structures includes:

creating one or more data structures which includes information regarding said first plurality of objects in said first graphical program and said second plurality of objects in said second graphical program.

51. The medium of claim 50, wherein said one or more data structures each comprise directed acyclic graphs comprising a plurality of vertices connected by edges, wherein each of said vertices represents one of said first plurality of objects or said second plurality of objects in one of said graphical programs.

52. The medium of claim 50, wherein said one or more data structures each comprise directed graphs comprising a plurality of vertices connected by edges, wherein each of said vertices represents one of said first plurality of objects or said second plurality of objects in a respective one of said graphical programs.

53. The medium of claim 52, wherein said first and second graphical programs each comprise a block diagram comprising the graphical code and a user interface panel for displaying one or more of data input to the block diagram and data output to the block diagram;

wherein, for each graphical program, said one or more data structures comprise;

a block diagram data structure comprising a directed graph, wherein the edges of said graph between said first or second plurality of objects represent directed flow of data and/or hierarchical relationship between said first or second plurality of objects in said block diagram;

a user interface panel data structure comprising a directed graph, wherein the edges of said graph between said first or second plurality of objects represent a hierarchical relationship between said first or second plurality of objects in said user interface panel.

54. The medium of claim 35, wherein said first graphical program includes a first data structure stored in a memory of the computer system which comprises information regarding said first graphical program, and wherein said second graphical program includes a second data structure stored in the memory of the computer system which comprises information regarding said second graphical program, wherein said creating data structures includes:

creating a third data structure which includes information regarding said first plurality of objects in said first graphical program, wherein said third data structure is created in response to said first data structure;

creating a fourth data structure which includes information regarding said second plurality of objects in said second graphical program, wherein said fourth data structure is created in response to said second data structure.

55. The medium of claim 35, wherein said creating data structures includes:

creating a first data structure which includes information regarding said first plurality of objects in said first graphical program;

creating a second data structure which includes information regarding said second plurality of objects in said second graphical program;

wherein, for each respective object in said first graphical program, said matching comprises;

comparing the respective object in said first graphical program with one or more objects in said second graphical program;

determining a score value for a plurality of object pairs in response to said comparing, wherein each of said plurality of object pairs comprises two object elements, said two object elements comprising said respective object in said first graphical program and an object of said one or more objects in said second graphical program, wherein said score value indicates a degree of matching between said object elements comprising said object pair.

56. The medium of claim 55, wherein said determining said score value for one of said plurality of object pairs includes examining connectivity of object elements comprising said object pair.

57. The medium of claim 55, wherein said determining said score value for one of said plurality of object pairs includes examining attributes of object elements comprising said object pair.

58. The medium of claim 55, wherein said score value is a weighted score value, wherein said determining said score value for one of said plurality of object pairs includes examining connectivity of object elements comprising said object pair and examining attributes of object elements comprising said object pair;

wherein said connectivity of object elements has greater weight than said attributes of said object elements.

59. The medium of claim 58, wherein said attributes comprise functional attributes and cosmetic attributes;

wherein said functional attributes have greater weight than said cosmetic attributes.

60. The medium of claim 55, wherein said matching further comprises:

storing said score values in a match matrix, wherein said match matrix comprises rows which correspond to said first plurality of objects in said first graphical program, and wherein said match matrix comprises columns which correspond to said second plurality of objects in said second graphical program;

wherein for an ith row and a jth column, the matrix element (i,j) includes the score value for the object pair comprising object i and object j.

61. The medium of claim 60, wherein said matching flurther comprises:

resolving said match matrix using said match matrix score values, wherein said resolving produces a 1;

1 or 1;

0 relationship between objects in said first graphical program and objects in said second graphical program depending upon whether or not an object in said first graphical program has a matching object in said second graphical program.

62. The medium of claim 60, wherein said matching further comprises:

resolving said match matrix using said match matrix score values, wherein, for each of at least a subset of said rows corresponding to said first plurality of objects, said resolving produces a column from said second plurality of objects in said second graphical program, wherein said produced column has a match matrix element with a highest score value for the respective row.

63. The medium of claim 35,

wherein said creating data structures includes:

creating a first data structure which includes information regarding said first plurality of objects in said first graphical program;

creating a second data structure which includes information regarding said second plurality of objects in said second graphical program;

wherein said matching produces a resolved match matrix, wherein said resolved match matrix comprises matching information regarding matches between said first plurality of objects in said first graphical program and said second plurality of objects in said second graphical program;

wherein said determining differences between said first graphical program and said second graphical program comprises;

grouping objects which have exact matches with connectivity matches into exact matching connected components using said matching information;

grouping remaining objects to produce non-exact matching connected components wherein said grouping remaining objects produces a first list of non-exact-matching connected components for said first data structure and produces a second list of non-matching connected components for said second data structure;

matching said first and second lists of non-exact matching connected components, wherein said matching said first and second lists of non-exact matching connected components includes finding common objects in said first and second lists of non-exact matching connected components, wherein said matching said first and second lists of non-exact matching connected components produces second matching information;

merging said first and second lists of non-exact matching connected components using said second matching information, wherein said merging produces a composite non-exact matching connected component list;

storing corresponding non-exact matching connected components in a result data structure;

comparing matching objects in corresponding non-exact matching connected components to determine additional object differences;

storing said additional object differences in said result data structure.

64. The medium of claim 63, wherein said step of grouping objects which have exact matches with connectivity matches comprises grouping objects which have exact matches with connectvity matches using said first and second data structures and said matching information to produce a first list of exact matching connected components for said first data structure and to produce a second list of exact matching connected components for said second data structure, wherein said grouping objects includes comparing objects according to one or more criteria to determine exact matches between objects, wherein an exact match comprises a match in the match matrix and match in said comparing.

65. The medium of claim 35,

wherein said first graphical program comprise a first user interface panel including a subset of said first plurality of objects for displaying one or more of outputs from the block diagram or inputs to the block diagram;

wherein said second graphical program comprise a second user interface panel including a subset of said second plurality of objects for displaying one or more of outputs from the block diagram or inputs to the block diagram;

wherein said matching produces a user interface panel match matrix comprising matching information;

wherein said determining differences includes determining differences between said first user interface panel and said second user interface panel which comprises;

comparing matching top-level objects of said first and second user interface panels to determine differences between said top-level objects using said matching information;

comparing low-level objects of said top-level objects to determine diferences between said low-level objects using said matching information;

storing said differences in response to said steps of comparing matching top-level objects of said first and second user interface panels and comparing low-level objects of said top-level objects.

66. The medium of claim 35, wherein said determining differences between said first graphical program and said second graphical program includes comparing differences between attributes of said first graphical program and attributes of said second graphical program.

67. The medium of claim 35, wherein each of said first and second graphical programs comprises a user interface panel and a block diagram, wherein said first graphical program comprises a first user interface panel and a first block diagram, and wherein said second graphical program comprises a second user interface panel and a second block diagram;

wherein said creating data structures comprises creating a data structure for objects in said first block diagram and said first user interface panel and creating a data structure for objects in said second block diagram and said second user interface panel;

wherein said matching comprises matching one or more objects in said first block diagram with one or more objects in said second block diagram, and wherein said matching further includes matching one or more objects in said first user interface panel with one or more objects in said second user interface panel;

wherein said determining differences between said first graphical program and said second graphical program comprises determining differences between said first block diagram and said second block diagram and determining differences between said first user interface panel and said second user interface panel.