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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
