Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007
Team Mouse Trap - M7
The final milestone required us to analyze and merge two genealogy trees simultaneously. These requirements made us to put our GUI design to the test, as reusing code became a necessity for such features.
The actual specifications of the assignment were as follows:
- Provide the ability to look at two maps simultaneously.
- Give the user a way to designate Persons from the two maps as the same individual, thus beginning or continuing the process of merging the two open maps.
- Provide the ability to automatically compare two maps, looking for Persons from each map who may represent the same individual.
- Create a ranking of such matches, for all pairs above some threshhold of "closeness."
- Provide an interface that allows the user to approve matches before you incorporate the information from two matched Person objects in a merged map.
- Finally (and most importantly) generate some kind of interface or visualization that illustrates the merged tree. The user has to be able to move around representations of Persons, see the relationships, and somehow discern which nodes are merged, and which nodes are from which maps and are NOT merged. You should also support the user unmerging nodes and merging nodes that your algorithm didn't merge.
One of the most difficult aspect of this assignment was to actually utilize our previous GUI implementation to work with the new one. Thus, the MVC paradigm was imperative in the design process for this assignment.
Another difficult aspect was determining how to match people, as many problems arise when matching people's relationship information, as described later in the document.
The way we approached the problem was to divide the tasks into separate, and entirely different sections such that all people were able to work with as little conflict as possible.
First, we decided that someone should be doing the comparison algorithm, which would automatically generate a score report when comparing one person to a list of persons. This is somewhat similar to your search engines, which return a list of documents matching the search specifications in order of relativity, ignoring those below a thresh hold of “closeness”.
Second, we devised a GUI that would utilize our previous visualization code. This required very little added code, as we used the same window for the previous assignments, and just called it twice to create the new merging window. For examples of what this looked like will be presented later in this document.
Lastly, we had to create some type of merging algorithm that would merge one person with another, centered on a certain person. That is, any information missing on the centered person would be the only information used from the other person. The most difficult part of this design was figuring out how exactly would we reuse the components to do the above. After that was determined, the actual coding wasn't all that bad.
Visualization of the Merged Trees
We decided that it would be best to load a completely new window pertaining to any action of merging. This would allow easy separation of merge operations and the resulting merger. As before, the user would load up the main program and the current working tree. When the user wishes to load the tree to compare to the current tree, the merge window will appear as follows:
When the user attempts to manually merge, another GUI appears. This GUI utilizes many of the same visualization components as previous visualizations, adding to code reuse.
The idea here is that the user will take any two people on the left (representing the two previous trees) and merge or add them directly to the right, given that they are unflagged. The rightmost window represents the resulting merged tree. The people that were used to merge will now be flagged, allowing the user see who he has already used to merge.
If a Person already exists from a merge (in the right list), a window will appear asking the user how another merged person will be added relative to that merger. This allows people to manually build up a tree, merge by merge.
The user is able to undo any actions, which removes the last user and unflags the appropriate users.
To compare two people and to determine if they are similar, we simply compared various attributes and scored attributes if they were equal. People’s last names were compared using soundex, a government standard for matching last names based on sound, rather than actual spelling. For example, Smyth and Smith will have the same soundex pattern, because they sound alike. More information on soundex may be found here:
The most difficult aspect of this project was creating a way for the user to interact with the two maps, and displaying them properly. We solved this by the approach above, utilizing our older visualization code in very efficient ways. Instead of recoding anything, we simply redesigned the view template and reused our visualization widget by placing it in the template twice.
Moreover, merging was also difficult, especially the automatic merging because certain non-specific relations exist. That is, relations like child, sibling, or spouse – each of which you may have multiples of, rather than a mother and father, which have direct correlations. It is then the job of the comparison algorithm to match those correctly during the automatic merging process.
One of the major problems that we have is with the undo feature. Using it after merges still leaves the connections present, but only takes out the people on the merge list. The solution is simply cloning each person before adding him or her to the new merged list, while saving each list after each operation. This would solve the problem of using the same reference for the people, list after list.
UML class diagram [NOTE: remove ".x" from end of filename]
Squeak .st source files