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]> > . > 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.
