Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uupsi!sunic!cs.umu.se!jan
From: jan@cs.umu.se (Jan T}ngring)
Newsgroups: comp.theory
Subject: Re: GRAPH ISOMORPHISMS !
Summary: Sicstus prolog program
Message-ID: <1991May6.191221.15788@cs.umu.se>
Date: 6 May 91 19:12:21 GMT
References: <1991Apr24.002002.9063@grape.ecs.clarkson.edu> <1991Apr28.201043.1@csc.anu.edu.au>
Sender: jan@cs.umu.se
Organization: Dep. of Info.Proc, Umea Univ., Sweden
Lines: 69

In article <1991Apr28.201043.1@csc.anu.edu.au> bdm659@csc.anu.edu.au writes:
>
>Given two isomorphic graphs G and H, "fix" one
>vertex v of G by sticking a large clique onto it, making G(v).   Then try
>sticking a clique of the same size onto each vertex of H in turn until one
>is found, say w, for which the extended graph H(w) is isomorphic to G(v).
>Then there must be an isomorphism from G to H taking v onto w.  Continue
>in the same way using G(v) and H(w) until an entire isomrphism is found.
>The whole process takes O(n^2) isomomorphism tests, where G and H have
>n vertices.
>
>>       Narsim.

The following beautiful sicstus prolog program implements the
above algorithm:

-----------------cut here--------------------------------

/* ---------------- support ----------------- */

selected(N, [N|L], L).
selected(N, [M|LNL], [M|LL]):- selected(N, LNL, LL).

perm([], []).
perm(LNL, [N|LL]):- selected(N, LNL, Perm), perm(Perm, LL).

equal(L1, L2):- perm(L1, L2).

/*-----------------isomorphic------------------------- */

isomorphic([], []).
isomorphic([(V,N1)|S1], G2):-
    selected((V,N2), G2, S2) -> equal(N1, N2),
    isomorphic(S1, S2).


/* The third line of isomorphic is equivalent to:
    (selected((V,N2), G2, S2), !, equal(N1, N2)),
*/

-----------------cut here--------------------------------


If G1 and G2 are isomorphic then isomorfic(G1, G2) shows the
corresponding corners.

G1 & G2 are undirected graphs represented as adjacency sets
(lists). An edge between corners a and b should have an entry
in the adjacency lists of both a and b. There is no control
made that the input data is consistent in this respect. (It
should be trivial to write a predicate converting from a
briefer notation)

The program cunningly uses prolog built-in unification, so
the corners of G1 must be constants and the corners of G2
must be variables. Check your prolog-manual for conventions
on names, as they may differ. In the example below, variables
have a leading capital letter.

Example, input:
    G1 = [(a,[b,e,f]), (b,[a,c,g,e])...],
    G2 = [(A, [B,C,G]),...],
    isomorphic(G1, G2).
output:
    A = a, B = d, C = h,...


	/JanneT
	jan@cs.umu.se