This Python code tries to compute dominators for a given graph. It (tries to) implement the Algorithm GD, Version 2 in "Finding Dominators via Disjoint Set Union" by Wojciech Fraczak, Loukas Georgiadis, Andrew Miller and Robert E. Tarjan. See http://arxiv.org/abs/1310.2118 for the article.
Note that the implementation is not working for the attached data. Needs more work.
- dominators.py:
- The implementation. Run it with downloading UnionFInd.py and LCA.py described as below. It reads *.json files in the same directory.
- OrderedUnionFind.py:
- A wrapper of UnionFind. It always unifies into the first argument.
- UnionFind.py and LCA.py:
- Required external libraries which are not in the repository. Download it as described below.
- *.json:
- Data files. edges.json is edges in the original graph, parents.json is p() in the DFS spanning tree (root=0) and postorder.json represents a bottom-up order.
- RESULT.txt:
- A dominator result for the data files. You can see some dominators are "None" (e.g. for node 13) which are failing to compute at this time.
Note that it is a slow implementation because it uses naive Python lists to represent sets "same", "out" and "in". It can be faster by replacing them by singly-circular linked lists.
It uses the following libraries for disjoint set union and least common ancestors.
- Union-find:
- LCA (least common ancestors):
It assumes Python 2.7.