System, method and memory medium for detecting differences between graphical programs

• US 6,138,270 A
• Filed: 06/23/1999
• Issued: 10/24/2000
• 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:
  US09/339,340
• Time in Patent Office: 489 Days
• Field of Search: 717/3
• US Class Current: 717/125
• 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. The graphical programs comprise graphical code. The graphical programs may 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, the method comprising:

determining differences between said first graphical program and said second graphical program, wherein said first graphical program and said second gaphical program each comprise graphical code; and

displaying an indication of said differences on the display;

wherein said differences are used to evaluate at least one of the first graphical program and the second graphical program.

2. The method of claim 1, wherein said first and second graphical programs each comprise a block diagram which includes interconnected function icons.

3. The method of claim 1, wherein said first and second graphical programs each include a user interface panel which displays data.

4. The method of claim 1, wherein said first graphical program includes a first user interface panel for viewing at least one of input to or output from the first graphical program;

wherein said second graphical program includes a second user interface panel for viewing at least one of input to or output from the second graphical program.

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

6. The method of claim 1, wherein said displaying said differences comprises displaying at least one of said first and second graphical programs, wherein said displaying said differences further comprises highlighting at least a subset of said differences between said first and second graphical programs.

7. 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.

8. The method of claim 1, wherein said first and second graphical programs each comprise a block diagram comprising 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.

9. 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.

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

11. The method of claim 1, 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 determining differences includes determining differences between said first plurality of objects of said first graphical program and said second plurality of objects of said second graphical program.

12. The method of claim 11, wherein said objects include function block icons.

13. The method of claim 11, wherein said objects include controls and indicators.

14. The method of claim 11,

wherein said objects include functions block icons;

and

wherein said objects also include data flow paths coupled between said functions block icons.

15. The method of claim 11, wherein said determining differences includes matching said first plurality of objects of said first graphical program with said second plurality of objects of said second graphical program.

16. The method of claim 15, further comprising:

creating data structures to represent said first and second graphical programs, wherein said matching uses said data structures.

17. The method of claim 15, 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.

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

19. The method of claim 18, 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.

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

21. The method of claim 15, 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.

22. The method of claim 21, 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.

23. The method of claim 15,

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.

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

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

26. The method of claim 23, 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.

27. The method of claim 26, wherein said attributes comprise functional attributes and cosmetic attributes;

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

28. The method of claim 23, 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.

29. The method of claim 28, 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.

30. The method of claim 28, 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.

31. The method of claim 15,

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 and produces a second list of non-matching connected components;

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.

32. The method of claim 31, wherein said grouping objects which have exact matches with connectivity matches comprises grouping objects which have exact matches with connectivity matches using said matching information to produce a first list of exact matching connected components and to produce a second list of exact matching connected components, 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.

33. The method of claim 15,

wherein said first graphical program comprises a first user interface panel including a subset of said first plurality of objects;

wherein said second graphical program comprises a second user interface panel including a subset of said second plurality of objects;

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 differences between said low-level objects using said matching information;

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

34. The method of claim 11, further comprising:

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;

wherein said determining differences uses said one or more data structures.

35. The method of claim 34, 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 objects in a respective one of said graphical programs.

36. The method of claim 1,

wherein said differences are useable in determining differences between the first graphical program and the second graphical program.

37. The method of claim 1,

wherein said differences are useable in determining errors in at least one of the first graphical program and the second graphical program.

38. The method of claim 1,

wherein said differences are useable in eliminating errors in at least one of the first graphical program and the second graphical program.

39. The method of claim 1, further comprising:

modifying at least one of the first graphical program and the second graphical program to eliminate errors in at least one of the first graphical program and the second graphical program, wherein said modifying is performed in response to said differences.

40. The method of claim 1, wherein the first graphical program comprises interconnected graphical objects which specify operation of the first graphical program, and wherein the second graphical program comprises interconnected graphical objects which specify operation of the second graphical program.

41. The method of claim 1, wherein the first graphical program comprises interconnected icons which specify operation of the first graphical program, and wherein the second graphical program comprises interconnected icons which specify operation of the second graphical program.

42. A computer-implemented method for detecting differences between first and second graphical programs, wherein the method executes on a computer including a display, the method comprising:

creating the first graphical program, wherein the first graphical program comprises first graphical code;

creating the second graphical program, wherein the second graphical program comprises second graphical code;

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

displaying an indication of said differences on the display;

wherein said differences are used to evaluate at least one of the first graphical program and the second graphical program.

43. The method of claim 42,

wherein the first graphical program comprises a first plurality of objects;

wherein the second graphical program comprises a second plurality of objects;

wherein said determining differences comprises determining differences between said first plurality of objects in said first graphical program and said second plurality of objects in said second graphical program.

44. The method of claim 42, wherein said graphical code includes function block icons.

45. The method of claim 42, wherein said graphical code includes interconnected function block icons.

46. The method of claim 42, wherein said creating the second graphical program comprises modifying the first graphical program to create the second graphical program.

47. A computer-implemented method for detecting differences between first and second graphical programs, wherein the method executes on a computer including a display, the method comprising:

creating the first graphical program, wherein the first graphical program comprises first graphical code, wherein the first graphical program comprises a first plurality of objects;

creating the second graphical program, wherein the second graphical program comprises second graphical code, wherein the second graphical program comprises a second plurality of objects;

determining differences between said first plurality of objects in said first graphical program and said second plurality of objects in said second graphical program; and

displaying an indication of said differences on the display;

wherein said differences are used to evaluate at least one of the first graphical program and the second graphical program.

48. A computer-implemented method for detecting differences between first and second graphical programs, wherein the method executes on a computer including a display, the method comprising:

creating the first graphical program, wherein the first graphical program comprises first graphical code, wherein the first graphical program comprises a first plurality of objects;

creating the second graphical program, wherein the second graphical program comprises second graphical code, 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;

wherein said differences are used to evaluate at least one of the first graphical program and the second graphical program.

49. A computer-implemented method for detecting differences between first and second graphical programs, wherein the method executes on a computer including a display, 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:

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;

wherein said differences are used to evaluate at least one of the first graphical program and the second graphical program.

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

a central processing unit (CPU);

a display coupled to the CPU; and

a memory medium coupled to the CPU which stores said first and second graphical programs, wherein each of the said first and second graphical programs comprises graphical code, wherein the memory medium also stores a difference program for detecting differences between said first and second graphical programs;

wherein said CPU is operable to execute said difference program to determine differences between said first graphical program and said second graphical program and to display an indication of said differences on the display;

wherein said differences are used to evaluate at least one of the first graphical program and the second graphical program.

51. The computer system of claim 50, 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 match said first plurality of objects of said first graphical program with said second plurality of objects of said second graphical program to determine differences between said first graphical program and said second graphical program.

52. The computer system of claim 51, wherein said objects include function block icons.

53. The computer system of claim 51, wherein said objects include controls and indicators for displaying data.

54. The computer system of claim 51,

wherein said objects include function block icons;

and

wherein said objects also include data flow paths coupled between said function block icons.

55. The computer system of claim 50, wherein, to display an indication of said differences on the display, the CPU is operable to display at least one of said first and second graphical programs and highlight at least a subset of said differences between said first and second graphical programs.

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

a central processing unit (CPU);

a display coupled to the CPU; and

a memory medium coupled to the CPU which stores said first and second graphical programs, wherein each of the said first and second graphical programs comprises 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 the memory medium also stores a difference program for detecting differences between said first and second graphical programs;

wherein said CPU is operable to execute said difference program to;

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;

wherein said differences are used to evaluate at least one of the first graphical program and the second graphical program.

57. A computer-readable memory medium comprising program instructions for detecting differences between first and second graphical programs, wherein the program instructions execute on a computer including a display, wherein the program instructions are executable to implement:

determining differences between said first graphical program and said second graphical program, wherein said first graphical program and said second gaphical program each comprise graphical code; and

displaying an indication of said differences on the display;

wherein said differences are used to evaluate at least one of the first graphical program and the second graphical program.

58. The memory medium of claim 57, 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 determining differences includes determining differences between said first plurality of objects of said first graphical program and said second plurality of objects of said second graphical program.

59. The memory medium of claim 58, wherein said objects include function block icons.

60. The memory medium of claim 58, wherein said objects include controls and indicators.

61. The memory medium of claim 58,

wherein said objects include functions block icons;

and

wherein said objects also include data flow paths coupled between said function block icons.

62. The memory medium of claim 57, wherein said first and second graphical programs each comprise a block diagram which includes interconnected function icons.

63. The memory medium of claim 57, wherein said first and second graphical programs each include a user interface panel which displays data.

64. The memory medium of claim 57, wherein said displaying said differences includes displaying a textual description of each of said differences.

65. The memory medium of claim 57, wherein said displaying said differences comprises displaying at least one of said first and second graphical programs, wherein said displaying said differences further comprises highlighting at least a subset of said differences between said first and second graphical programs.

66. The memory medium of claim 57, 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 memory medium of claim 57, wherein said first and second graphical programs each comprise a block diagram comprising 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.

68. The memory medium of claim 57, 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.

69. The memory medium of claim 68, wherein said determining differences between said first and second graphical programs includes finding cosmetic differences between said first and second graphical programs, wherein a cosmetic difference is a non-functional difference.

70. The memory medium of claim 57, 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 determining differences includes matching said first plurality of objects of said first graphical program with said second plurality of objects of said second graphical program.

71. The memory medium of claim 70, 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.

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

73. The memory medium of claim 72, 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.

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

75. The memory medium of claim 70, 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.

76. The memory medium of claim 75, wherein each of said 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.

77. The memory medium of claim 70, wherein said first and second graphical programs each comprise a block diagram comprising 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.

78. The memory medium of claim 70, 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.

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

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

81. The memory medium of claim 78, 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.

82. The memory medium of claim 81, wherein said attributes comprise functional attributes and cosmetic attributes;

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

83. The memory medium of claim 78, 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.

84. The memory medium of claim 83, 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.

85. The memory medium of claim 83, 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.

86. The memory medium of claim 70,

wherein said first graphical program comprises a first user interface panel including a subset of said first plurality of objects for displaying one or more of data output and data input;

wherein said second graphical program comprises a second user interface panel including a subset of said second plurality of objects for displaying one or more of data output and data input;

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 differences between said low-level objects using said matching information;

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

87. The memory medium of claim 57,

wherein said differences are useable in determining differences between the first graphical program and the second graphical program.

88. The memory medium of claim 57,

wherein said differences are useable in determining errors in at least one of the first graphical program and the second graphical program.

89. The memory medium of claim 57,

wherein said differences are useable in eliminating errors in at least one of the first graphical program and the second graphical program.

90. The memory medium of claim 57, wherein the program instructions are further executable to implement:

modifying at least one of the first graphical program and the second graphical program to eliminate errors in at least one of the first graphical program and the second graphical program, wherein said modifying is performed in response to said differences.

91. The memory medium of claim 57, wherein the first graphical program comprises interconnected graphical objects which specify operation of the first graphical program, and wherein the second graphical program comprises interconnected graphical objects which specify operation of the second graphical program.

92. The memory medium of claim 57, wherein the first graphical program comprises interconnected icons which specify operation of the first graphical program, and wherein the second graphical program comprises interconnected icons which specify operation of the second graphical program.