Hi, Thanks a lot... I will have a try to implement this..
Regards, Mithun On Sat, Aug 28, 2010 at 8:04 AM, Gene <[email protected]> wrote: > 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%[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]<algogeeks%[email protected]> > . > 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.
