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

4 次查看（过去 30 天）
DEEPAK P
DEEPAK P 2017-4-25
评论： DEEPAK P 2017-4-26
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
  3 个评论
显示 1更早的评论
DEEPAK P
DEEPAK P 2017-4-25
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

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

Christine Tobler
Christine Tobler 2017-4-25
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.

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by