1097 \end{center} |
1097 \end{center} |
1098 \end{subfigure} |
1098 \end{subfigure} |
1099 \begin{subfigure}[b]{0.55\textwidth} |
1099 \begin{subfigure}[b]{0.55\textwidth} |
1100 \begin{center} |
1100 \begin{center} |
1101 \begin{tikzpicture} |
1101 \begin{tikzpicture} |
1102 \begin{axis}[title={Random ISO, $\delta = 35$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
|
1103 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
|
1104 west},scaled x ticks = false,x tick label style={/pgf/number |
|
1105 format/1000 sep = \space}] |
|
1106 %\addplot+[only marks] table {proteinsOrig.txt}; |
|
1107 \addplot table {randGraph/iso/vf2pIso35_1.txt}; |
|
1108 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
|
1109 {randGraph/iso/vf2ppIso35_1.txt}; |
|
1110 \end{axis} |
|
1111 \end{tikzpicture} |
|
1112 \end{center} |
|
1113 \end{subfigure} |
|
1114 \begin{subfigure}[b]{0.55\textwidth} |
|
1115 \hspace*{-1.5cm} |
|
1116 \begin{tikzpicture} |
|
1117 \begin{axis}[title={Random ISO, $\delta = 45$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
|
1118 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
|
1119 west},scaled x ticks = false,x tick label style={/pgf/number |
|
1120 format/1000 sep = \space}] |
|
1121 %\addplot+[only marks] table {proteinsOrig.txt}; |
|
1122 \addplot table {randGraph/iso/vf2pIso45_1.txt}; |
|
1123 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
|
1124 {randGraph/iso/vf2ppIso45_1.txt}; |
|
1125 \end{axis} |
|
1126 \end{tikzpicture} |
|
1127 \end{subfigure} |
|
1128 \hspace*{-1.5cm} |
|
1129 \begin{subfigure}[b]{0.55\textwidth} |
|
1130 \begin{tikzpicture} |
|
1131 \begin{axis}[title={Random ISO, $\delta = 100$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
1102 \begin{axis}[title={Random ISO, $\delta = 100$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
1132 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
1103 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
1133 west},scaled x ticks = false,x tick label style={/pgf/number |
1104 west},scaled x ticks = false,x tick label style={/pgf/number |
1134 format/1000 sep = \thinspace}] |
1105 format/1000 sep = \thinspace}] |
1135 %\addplot+[only marks] table {proteinsOrig.txt}; |
1106 %\addplot+[only marks] table {proteinsOrig.txt}; |
1136 \addplot table {randGraph/iso/vf2pIso100_1.txt}; |
1107 \addplot table {randGraph/iso/vf2pIso100_1.txt}; |
1137 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
1108 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
1138 {randGraph/iso/vf2ppIso100_1.txt}; |
1109 {randGraph/iso/vf2ppIso100_1.txt}; |
1139 \end{axis} |
1110 \end{axis} |
1140 \end{tikzpicture} |
1111 \end{tikzpicture} |
|
1112 \end{center} |
1141 \end{subfigure} |
1113 \end{subfigure} |
1142 \vspace*{-0.8cm} |
1114 \vspace*{-0.8cm} |
1143 \caption{IND on graphs having an average degree of |
1115 \caption{ISO on random graphs. |
1144 5.}\label{fig:randISO} |
1116 }\label{fig:randISO} |
1145 \end{figure} |
1117 \end{figure} |
1146 |
1118 |
1147 |
1119 |
1148 \subsubsection{Induced subgraph isomorphism} |
1120 \subsubsection{Induced subgraph isomorphism} |
1149 This section presents a comparison of VF2++ and VF2 Plus in the case |
1121 This section presents a comparison of VF2++ and VF2 Plus in the case |
1155 For each chart, a number $0<\rho< 1$ has been fixed, and the following |
1127 For each chart, a number $0<\rho< 1$ has been fixed, and the following |
1156 has been executed 150 times. Generating a large graph $G_{2}$ of an average degree of $\delta$, |
1128 has been executed 150 times. Generating a large graph $G_{2}$ of an average degree of $\delta$, |
1157 choose 10 of its induced subgraphs having $\rho\ |V_{2}|$ nodes, |
1129 choose 10 of its induced subgraphs having $\rho\ |V_{2}|$ nodes, |
1158 and for all the 10 subgraphs find a mapping by using both the graph |
1130 and for all the 10 subgraphs find a mapping by using both the graph |
1159 matching algorithms. The $\delta = 5, 10, 35$ and $\rho = 0.05, 0.1, |
1131 matching algorithms. The $\delta = 5, 10, 35$ and $\rho = 0.05, 0.1, |
1160 0.3, 0.6, 0.8, 0.95$ cases have been examined, see |
1132 0.3, 0.8$ cases have been examined, see |
1161 Figure~\ref{fig:randIND5}, \ref{fig:randIND10} and |
1133 Figure~\ref{fig:randIND5}, \ref{fig:randIND10} and |
1162 \ref{fig:randIND35}. |
1134 \ref{fig:randIND35}. |
1163 |
1135 |
1164 |
1136 |
1165 |
1137 |
1215 \end{center} |
1187 \end{center} |
1216 \end{subfigure} |
1188 \end{subfigure} |
1217 \begin{subfigure}[b]{0.55\textwidth} |
1189 \begin{subfigure}[b]{0.55\textwidth} |
1218 \begin{center} |
1190 \begin{center} |
1219 \begin{tikzpicture} |
1191 \begin{tikzpicture} |
1220 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.6$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
1192 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
1221 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
1193 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
1222 west},scaled x ticks = false,x tick label style={/pgf/number |
1194 west},scaled x ticks = false,x tick label style={/pgf/number |
1223 format/1000 sep = \space}] |
1195 format/1000 sep = \space}] |
1224 %\addplot+[only marks] table {proteinsOrig.txt}; |
1196 %\addplot+[only marks] table {proteinsOrig.txt}; |
1225 \addplot table {randGraph/ind/vf2pInd5_0.6.txt}; |
|
1226 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
|
1227 {randGraph/ind/vf2ppInd5_0.6.txt}; |
|
1228 \end{axis} |
|
1229 \end{tikzpicture} |
|
1230 \end{center} |
|
1231 \end{subfigure} |
|
1232 \begin{subfigure}[b]{0.55\textwidth} |
|
1233 \hspace*{-1.5cm} |
|
1234 \begin{tikzpicture} |
|
1235 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
|
1236 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
|
1237 west},scaled x ticks = false,x tick label style={/pgf/number |
|
1238 format/1000 sep = \space}] |
|
1239 %\addplot+[only marks] table {proteinsOrig.txt}; |
|
1240 \addplot table {randGraph/ind/vf2pInd5_0.8.txt}; |
1197 \addplot table {randGraph/ind/vf2pInd5_0.8.txt}; |
1241 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
1198 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
1242 {randGraph/ind/vf2ppInd5_0.8.txt}; |
1199 {randGraph/ind/vf2ppInd5_0.8.txt}; |
1243 \end{axis} |
1200 \end{axis} |
1244 \end{tikzpicture} |
1201 \end{tikzpicture} |
1245 \end{subfigure} |
1202 \end{center} |
1246 \hspace*{-1.5cm} |
|
1247 \begin{subfigure}[b]{0.55\textwidth} |
|
1248 \begin{tikzpicture} |
|
1249 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.95$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
|
1250 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
|
1251 west},scaled x ticks = false,x tick label style={/pgf/number |
|
1252 format/1000 sep = \thinspace}] |
|
1253 %\addplot+[only marks] table {proteinsOrig.txt}; |
|
1254 \addplot table {randGraph/ind/vf2pInd5_0.95.txt}; |
|
1255 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
|
1256 {randGraph/ind/vf2ppInd5_0.95.txt}; |
|
1257 \end{axis} |
|
1258 \end{tikzpicture} |
|
1259 \end{subfigure} |
1203 \end{subfigure} |
1260 \vspace*{-0.8cm} |
1204 \vspace*{-0.8cm} |
1261 \caption{IND on graphs having an average degree of |
1205 \caption{IND on graphs having an average degree of |
1262 5.}\label{fig:randIND5} |
1206 5.}\label{fig:randIND5} |
1263 \end{figure} |
1207 \end{figure} |
1264 |
1208 |
1265 |
1209 |
1266 \begin{figure}[H] |
1210 \begin{figure} |
1267 \vspace*{-1.5cm} |
1211 \vspace*{-1.5cm} |
1268 \hspace*{-1.5cm} |
1212 \hspace*{-1.5cm} |
1269 \begin{subfigure}[b]{0.55\textwidth} |
1213 \begin{subfigure}[b]{0.55\textwidth} |
1270 \begin{center} |
1214 \begin{center} |
1271 \hspace*{-0.5cm} |
1215 \hspace*{-0.5cm} |
1315 \end{center} |
1259 \end{center} |
1316 \end{subfigure} |
1260 \end{subfigure} |
1317 \begin{subfigure}[b]{0.55\textwidth} |
1261 \begin{subfigure}[b]{0.55\textwidth} |
1318 \begin{center} |
1262 \begin{center} |
1319 \begin{tikzpicture} |
1263 \begin{tikzpicture} |
1320 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.6$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
1264 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
1321 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
1265 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
1322 west},scaled x ticks = false,x tick label style={/pgf/number |
1266 west},scaled x ticks = false,x tick label style={/pgf/number |
1323 format/1000 sep = \space}] |
1267 format/1000 sep = \space}] |
1324 %\addplot+[only marks] table {proteinsOrig.txt}; |
1268 %\addplot+[only marks] table {proteinsOrig.txt}; |
1325 \addplot table {randGraph/ind/vf2pInd10_0.6.txt}; |
|
1326 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
|
1327 {randGraph/ind/vf2ppInd10_0.6.txt}; |
|
1328 \end{axis} |
|
1329 \end{tikzpicture} |
|
1330 \end{center} |
|
1331 \end{subfigure} |
|
1332 \hspace*{-1.5cm} |
|
1333 \begin{subfigure}[b]{0.55\textwidth} |
|
1334 \begin{tikzpicture} |
|
1335 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
|
1336 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
|
1337 west},scaled x ticks = false,x tick label style={/pgf/number |
|
1338 format/1000 sep = \space}] |
|
1339 %\addplot+[only marks] table {proteinsOrig.txt}; |
|
1340 \addplot table {randGraph/ind/vf2pInd10_0.8.txt}; |
1269 \addplot table {randGraph/ind/vf2pInd10_0.8.txt}; |
1341 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
1270 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
1342 {randGraph/ind/vf2ppInd10_0.8.txt}; |
1271 {randGraph/ind/vf2ppInd10_0.8.txt}; |
1343 \end{axis} |
1272 \end{axis} |
1344 \end{tikzpicture} |
1273 \end{tikzpicture} |
1345 \end{subfigure} |
1274 \end{center} |
1346 \begin{subfigure}[b]{0.55\textwidth} |
|
1347 \begin{tikzpicture} |
|
1348 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.95$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
|
1349 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
|
1350 west},scaled x ticks = false,x tick label style={/pgf/number |
|
1351 format/1000 sep = \thinspace}] |
|
1352 %\addplot+[only marks] table {proteinsOrig.txt}; |
|
1353 \addplot table {randGraph/ind/vf2pInd10_0.95.txt}; |
|
1354 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
|
1355 {randGraph/ind/vf2ppInd10_0.95.txt}; |
|
1356 \end{axis} |
|
1357 \end{tikzpicture} |
|
1358 \end{subfigure} |
1275 \end{subfigure} |
1359 \vspace*{-0.8cm} |
1276 \vspace*{-0.8cm} |
1360 \caption{IND on graphs having an average degree of |
1277 \caption{IND on graphs having an average degree of |
1361 10.}\label{fig:randIND10} |
1278 10.}\label{fig:randIND10} |
1362 \end{figure} |
1279 \end{figure} |
1363 |
1280 |
1364 |
1281 |
1365 |
1282 |
1366 \begin{figure}[H] |
1283 \begin{figure} |
1367 \vspace*{-1.5cm} |
1284 \vspace*{-1.5cm} |
1368 \hspace*{-1.5cm} |
1285 \hspace*{-1.5cm} |
1369 \begin{subfigure}[b]{0.55\textwidth} |
1286 \begin{subfigure}[b]{0.55\textwidth} |
1370 \begin{center} |
1287 \begin{center} |
1371 \begin{tikzpicture} |
1288 \begin{tikzpicture} |
1413 \end{center} |
1330 \end{center} |
1414 \end{subfigure} |
1331 \end{subfigure} |
1415 \begin{subfigure}[b]{0.55\textwidth} |
1332 \begin{subfigure}[b]{0.55\textwidth} |
1416 \begin{center} |
1333 \begin{center} |
1417 \begin{tikzpicture} |
1334 \begin{tikzpicture} |
1418 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.6$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
1335 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
1419 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
1336 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
1420 west},scaled x ticks = false,x tick label style={/pgf/number |
1337 west},scaled x ticks = false,x tick label style={/pgf/number |
1421 format/1000 sep = \space}] |
1338 format/1000 sep = \space}] |
1422 %\addplot+[only marks] table {proteinsOrig.txt}; |
1339 %\addplot+[only marks] table {proteinsOrig.txt}; |
1423 \addplot table {randGraph/ind/vf2pInd35_0.6.txt}; |
|
1424 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
|
1425 {randGraph/ind/vf2ppInd35_0.6.txt}; |
|
1426 \end{axis} |
|
1427 \end{tikzpicture} |
|
1428 \end{center} |
|
1429 \end{subfigure} |
|
1430 \hspace*{-1.5cm} |
|
1431 \begin{subfigure}[b]{0.55\textwidth} |
|
1432 \begin{tikzpicture} |
|
1433 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
|
1434 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
|
1435 west},scaled x ticks = false,x tick label style={/pgf/number |
|
1436 format/1000 sep = \space}] |
|
1437 %\addplot+[only marks] table {proteinsOrig.txt}; |
|
1438 \addplot table {randGraph/ind/vf2pInd35_0.8.txt}; |
1340 \addplot table {randGraph/ind/vf2pInd35_0.8.txt}; |
1439 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
1341 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
1440 {randGraph/ind/vf2ppInd35_0.8.txt}; |
1342 {randGraph/ind/vf2ppInd35_0.8.txt}; |
1441 \end{axis} |
1343 \end{axis} |
1442 \end{tikzpicture} |
1344 \end{tikzpicture} |
1443 \end{subfigure} |
1345 \end{center} |
1444 \begin{subfigure}[b]{0.55\textwidth} |
|
1445 \begin{tikzpicture} |
|
1446 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.95$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid |
|
1447 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north |
|
1448 west},scaled x ticks = false,x tick label style={/pgf/number |
|
1449 format/1000 sep = \thinspace}] |
|
1450 %\addplot+[only marks] table {proteinsOrig.txt}; |
|
1451 \addplot table {randGraph/ind/vf2pInd35_0.95.txt}; |
|
1452 \addplot[mark=triangle*,mark size=1.8pt,color=red] table |
|
1453 {randGraph/ind/vf2ppInd35_0.95.txt}; |
|
1454 \end{axis} |
|
1455 \end{tikzpicture} |
|
1456 \end{subfigure} |
1346 \end{subfigure} |
1457 \vspace*{-0.8cm} |
1347 \vspace*{-0.8cm} |
1458 \caption{IND on graphs having an average degree of |
1348 \caption{IND on graphs having an average degree of |
1459 35.}\label{fig:randIND35} |
1349 35.}\label{fig:randIND35} |
1460 \end{figure} |
1350 \end{figure} |