how can i use graph edit distance for n number of nodes

i am doing my project on Graph based representation of handwritten Devanagari word images. i want to use the graph edit distance to match the graph. i have created GXL file. i want some code to find graph edit distance for n number of nodes in a graph. please help me. thanks in advance.

this is my graph image

[Eng. Fredius Magige]

Hi other option; tell us coordinates of all nodes,and propose longest route thanks

[DEEPAK P]

clc;
clear all;
close all;
X=imread('d1.png');
figure,imshow(X)

b = imresize(X,[100,100]);
si = size(b,1);
sj = size(b,2);
%figure;imshow(b);

% Binarization
th = graythresh(b);
I = im2bw(b,th);
% %thinning
kl=bwmorph(~I,'thin',inf);
figure,imshow(kl)
%figure,
R(:,:)=kl(:,:);
%grid size 
t1=5;
D=100;
 I=1;
U1=t1;
J=1;
U2=t1;
E=1;
t2=D/t1;
%Z=1;
for iir=1:t2
    for jjr=1:t2
 B(I:U1,J:U2)=R(I:U1,J:U2);
%  vc=sum(B(I:U1,J:U2));
%  Fd=sum(vc);
 [x,y]=find(B==1);
 CX=mean(x);
 CY=mean(y);
 CXXX(E)=CX;
 CYYY(E)=CY;
 CXX(iir,jjr)=CX;
 CYY(iir,jjr)=CY;

   T(I:U1,J:U2)=B(I:U1,J:U2);
      J=J+t1;
    U2=U2+t1;
  E=E+1;
   clear B x y 

      end

I=I+t1;
U1=U1+t1;
J=1;
  U2=t1;

end
%plot and grid
%figure,imshow(R)
hold on
M10 = size(R,1);
N10 = size(R,2);

a=t1; 
b=t1; 
for k = 1:a:M10
    x = [1 N10]; 
   y = [k k]; 
   plot(x,y,'Color','white');
    set(findobj('Tag','MyGrid'),'Visible','on')
end
for k = 1:b:N10 
    x = [k k]; 
    y = [1 M10];
    plot(x,y,'Color','white');
    set(findobj('Tag','MyGrid'),'Visible','on')
end
z = imread('empty.jpg');
r = imresize(z,[100,100]);
figure,imshow(r);
hold on
plot(CYY,CXX,'g*')
%line(CYY,CXX)
%CC=bwconncomp(CXX,4)

hold off
%node neighbourhoood analyssis
N1=t2;
for I2=1:N1
    for J2=1:N1
        %last row
       if(I2>=N1)
             W1=CXX(I2,J2);
           W2=CXX(I2-1,J2);
           W3=CYY(I2,J2);
           W4=CYY(I2-1,J2);    
           W6=[W1,W2];
           W7=[W3,W4];
           line(W7,W6);
           if(J2>=N1)
               Z=CXX(I2,J2);
           else
           if (CXX(I2,J2+1)>1)&& ((CYY(I2,J2+1)>1))
            TXX=CXX(I2,J2);
            TYY=CXX(I2,J2+1);
               TTX=CYY(I2,J2);
               TTY=CYY(I2,J2+1);

              IY=[TXX,TYY];
              IIY=[TTX,TTY];
              line(IIY,IY);
             end
             end
         else
             if(J2>=N1);
               W1=CXX(I2,J2);
             W2=CXX(I2+1,J2);
             W3=CYY(I2,J2);
             W4=CYY(I2+1,J2);    
             W6=[W1,W2];
             W7=[W3,W4];
             line(W7,W6);
             else   
                 if (CXX(I2,J2+1)>1)&& ((CYY(I2,J2+1)>1))
              TXX=CXX(I2,J2);
              TYY=CXX(I2,J2+1);
                 TTX=CYY(I2,J2);
                 TTY=CYY(I2,J2+1);

              IY=[TXX,TYY];
              IIY=[TTX,TTY];
              line(IIY,IY);

           end
           if (CXX(I2+1,J2)>1)&& ((CYY(I2+1,J2)>1))
             W1=CXX(I2,J2);
             W2=CXX(I2+1,J2);
             W3=CYY(I2,J2);
             W4=CYY(I2+1,J2);    
             W6=[W1,W2];
             W7=[W3,W4];
             line(W7,W6);
             J2=J2+1

           end
          end
      end
      end
  end

      A=zeros(t2,t2);   
      ttt=1;
      c5=1;
     for rt=1:t2
        for  rt1=1:t2
            if(CXX(rt,rt1)>1)
                A(rt,rt1)=ttt
                B(c5)=ttt
            end
            ttt=ttt+1;
            c5=c5+1;
        end
     end

g=1;
jk=1;
um=t2-1;
um1=t2;
for iir=1:t2
    for jjr=1:t2
        if(A(iir,jjr)>=0)
            BB(jk)=0;
                       DD(g)=0;
                      FF(g)=0;
                      HH(g)=0;
        end
        if(A(iir,jjr)>=1)
          if(iir==um1)&&(jjr==1)
             GG(g)=A(iir,jjr);
            HH(g)=A(iir-1,jjr); 
            BB(jk)=A(iir,jjr+1);
            DD(g)=0;
          else
              if(iir==um1)&&(jjr>1)&&(jjr<=um)
               FF(g)=A(iir,jjr-1); 
                BB(jk)=A(iir,jjr+1);
                HH(g)=A(iir-1,jjr);
              else

                if(iir==um1)&&(jjr==um1)
                    HH(g)=A(iir-1,jjr);
                    FF(g)=A(iir,jjr-1);
                    DD(g)=0;
                    BB(jk)=0;
                else

          if(iir==1)&&(jjr==um1)
              FF(g)=A(iir,jjr-1);
              DD(g)=A(iir+1,jjr);
              BB(jk)=0;

          else
              if(iir>=1)&&(iir<=um)&&(jjr==um1)
               HH(g)=A(iir-1,jjr);
               DD(g)=A(iir+1,jjr);
              FF(g)=A(iir,jjr-1);
              BB(jk)=0;
              else
                if(iir==1)&&(jjr==1)
                  BB(jk)=A(iir,jjr+1);  
                  DD(g)=A(iir+1,jjr);
                else
                if(iir==1)&&(jjr>=1)&&(jjr<=um)  
                FF(g)=A(iir,jjr-1);    
                DD(g)=A(iir+1,jjr); 
                  BB(jk)=A(iir,jjr+1);
                else
                 if(iir>1)&&(iir<=um)&&(jjr==1)   
                  HH(g)=A(iir-1,jjr);
                  DD(g)=A(iir+1,jjr);
                  BB(jk)=A(iir,jjr+1);
                 else
                     if(iir>1)&&(iir<=um)&&(jjr>1)&&(jjr<=um) 
                         BB(jk)=A(iir,jjr+1);
                     DD(g)=A(iir+1,jjr);
                     HH(g)=A(iir-1,jjr);
                      FF(g)=A(iir,jjr-1);
                     end
                    end
                  end
                end
              end
           end
         end
                end
   end
          end
      g=g+1;
      jk=jk+1;
      end

end
adj=zeros(t2*t2);
H9=size(adj);
Y=1;
for ll=1:1
        for ii=1:H9(1,1)
            for jj=1:H9(1,1)
                if (ii>=4)
                    if (jj==DD(1,Y))
                    adj(ii,jj)=1;
                end
                if (jj==FF(1,Y))
                    adj(ii,jj)=1;
                end
                if (jj==BB(1,Y))
                    adj(ii,jj)=1;
                end
                if (jj==HH(1,Y))
                    adj(ii,jj)=1;
                end
                else
                if (jj==BB(1,Y))
                    adj(ii,jj)=1;
                end
                if (jj==DD(1,Y))
                    adj(ii,jj)=1;
                end
                if (jj==FF(1,Y))
                    adj(ii,jj)=1;
                end
                if (jj==HH(1,Y))
                    adj(ii,jj)=1;
                end
                end
            end
            Y=Y+1;
        end

end   

M = adj;
M(~any(M,2),:) = []; % remove zero rows
M(:,~any(M,1)) = []; % remove zero columns
X = CXX'; % transpose
Y = CYY'; % transpose
X = X(:); % x vector
Y = Y(:); % y vector
X(isnan(X)) = []; % remove Nan
Y(isnan(Y)) = [];
G = graph(M); % graph
plot(G,'k','Xdata',X,'Ydata',Y,'MarkerSize',15,'NodeLabel',{});% plot

this my code i am tried yet please run this code i have stored my coordinates in CXX and CYY

[DEEPAK P]

my input image

Answer 1

[Christine Tobler]

I'm afraid MATLAB does not provide functionality for computing the Graph Edit Distance. I took a look at the wikipedia page, which gives a high-level definition and some ideas of algorithms used for computing it.

The suggested exact solution on the wikipedia page sounds prohibitively expensive if you were to try to store the "edit graph" (a graph where each node corresponds to a graph, and each edge corresponds to one of the operations addnode, rmnode, addedge, rmedge). You would need to somehow store this graph implicitly for an efficient algorithm.

You might have more luck looking into the two suggested approximation algorithms, and trying to implement one of these in MATLAB. (Note I have not looked at these papers - this may not be practical either).

Also take a look at this stackoverflow post, which recommends some software for this problem.

[DEEPAK P]

please suggest any other method for matching graphs

[Steven Lord]

You want to tell if two graphs are isomorphic?

[DEEPAK P]

no sir i want to match the two graphs using graph edit distance.