I have a task of comparing two organisation charts. These chart objects are desc

Question

I have a task of comparing two organisation charts. These chart objects are described as a set of nodes (people) where each has a unique ID field and a parent ID field (pointing to another node's unique ID). For simplicity we can assume that there's only one node without a parent ID (head of the organisation) and that no node can reference itself. So it's essentially a tree of all the people in the organisation. Comparison should produce two lists - people who left the organisation, people who joined, and people who have changed their position in the organisation. Leavers and joiners are trivial, but I don't know how to proceed with people who changed their position. I need some ideas on how to proceed with identifying people who really moved within the chart from those who only have new parent IDs

Explanation / Answer

As stated, I think this is a minimum edit distance problem. Encode your graph in some canonical order (e.g. breadth-first, with tokens at each level sorted by id) with a token for each node and a token for each parent. You want the minimum edit distance between that encoding and the encoding of the new tree.

Minimum edit distance counts insertion, deletion, and substitution. Seems to map naturally to your problem.

If what you really have is an org. chart where there are various jobs that define the org chart with people who fill the jobs, then you have two different problems. You need to define your graph in terms of the jobs, and the min. edit distance algorithm is applicable to that. You then need to encode who has which job, and the encoding will make finding people who changed jobs trivial.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.