This algorithm you describe is a brute force search. There are no heuristics in play if you consider all permutations of the vertices of the second graph. The heuristic I proposed is to eliminate all permutations that would equate vertices with different degree. The adjacency matrix comparison would be certain to fail for these cases, so it's best never even to try.
Here's an algorithm: Let the graphs be G and H. Let Vg be a partition of the set of vertices of G into subsets. Within each subset, all vertices have identical in- and out-degree. You can do the partitioning easily in O(n) time if you have the right graph data structure for G and H. Assume each subset in Vg is labeled with the associated in- and out-degree values. Let Vh be the same kind of labeled partition of the vertices of H. If Vg and Vh are of different size or have different subset labels, the graphs are not isomorphic. You're done. Otherwise compute all permutations of each subset in Vh. As you proposed, use these permutations to re-order the adjacency matrix of H. Compare each reordered matrix with G's. If identical, you have found an isomorphism. If you never find an identical pair of matrices, G and H are not isomorphic. Of course if your graph is sparse, constructing and comparing adjacency matrices is expensive (O(n^2) can be much bigger than O(m)). You'd want to use adjacency lists or similar in this case. The heuristic of in- and out-degree can be very helpful or useless depending on the graph. If each vertex has different degree, then there will only be one permutation to consider, so the algorithm is linear time. If all vertices have identical degree, then of course you'll be checking O(n!) permutations. On Aug 27, 2:55 pm, Mithun A V <[email protected]> wrote: > Hi, > > Thanks for the reply. > > Could you please give an algorithm. > When i searched, i got the info that the heuristic approach is as follows. > Assume we have to accept the graphs using adjacency matrix. > > Keep the first graph in tact. > Take the second graph and change it by changing the vertices(permutation of > rows/columns of the matrix) > If we get a matrix that is equal to the first graph at any stage, the > graph is isomorphic. > I would like to get a somewhat detailed algorithm for this procedure. > > Regards, > Mithun > > > > > > On Fri, Aug 27, 2010 at 10:28 PM, Gene <[email protected]> wrote: > > A lot depends on whether the graphs have any labels to anchor a > > search. Some labelings allow for linear time comparison. For > > example, it's easy to compare two deterministic finite automata in > > linear time. > > > If you have no labels at all, then the only heuristic available is to > > partition vertices into equivalence classes based on in/out-degree. > > The classes must be identical in both graphs, or they're trivially not > > isomorphic. If the classes are the same, then check all possible 1-1 > > mappings of vertices between members of like class pairs drawn from > > the two graphs. Generating 1-1 mappings for sets of size n is > > equivalent to generating all permutations of a sequence of size n. > > Just label one set of vertices 1,2,..n. Construct successive > > permutations of 1..n and apply these as labels to the other set of > > vertices. Then check that all the edges in the first graph exist (or > > not) under the hypthesized labeling in the second graph. > > > On Aug 27, 9:18 am, Mithun <[email protected]> wrote: > > > Hi, > > > > I have to write a program in c or cpp to check whether 2 given > > > graphs(given in adjacency matrix or list) are isomorphic.. > > > Could any please help me? > > > I am not worried about the running time..So even the heuristic > > > approach will do.. > > > > Thanks > > > Mithun > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<algogeeks%2bunsubscr...@googlegroups > > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Regards, > > Mithun -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
