MATHEMATICA is quite efficient in algos. Directed Acylic Graphs have a number of applications. I need some implementation/guidance for similarity analysis of two or more DAGs.
You can also search for the maximum common subgraph of the two graphs. This is usually done through constructing a derivative graph and finding the maxium clique size of the derivative graph. There are several papers about this, for example:
https://www.comp.nus.edu.sg/~atung/mcs_survey.pdf
If the graphs are not very large you can try a linear programming approach. The idea is this. Suppose you are trying to show graph isomorphism. Form a permutation matrix pMat of variables: restrict all to be between 0 and 1, row and column sums equal 1. Now take the adjacency matrices m1 and m2, and try for constraint satisfaction pMat.m1==m2.pMat. It's actually an ILP of course, but I've had some luck using just the relaxed LP formulation in showing isomorphism (or proving there is no such).
Your case is more difficult in that you do not expect to satisfy the equality constraint. I think maybe you want to minimize the l1 norm of the difference. That involves another set of variables in a matrix of the same shape, call it mDiffs. For the difference diff=pMat.m1-m2.pMat, assign corresponding positions of mDiffs, with the stipulation that mDiffs(i,j)>=both the (i,j) component of diff, and >=its negation. Now the objective is the total of mDiffs.
This may give some idea of how to code this, at least for graphs with not too many vertices (I've had modest success up to several dozen at least). There are refinements that serve to assist the relaxed LP formulation as well but I think this is enough to give an idea of the approach.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs