Mercuriallemon-vf2 / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
damecco.tex
changeset 10 1e4a79cd8332
parent 9 2ad9aa6d7f63
child 11 e73184c3928f
equal deleted inserted replaced
8:1942b1d71a41 9:b98d12a52724 
  1501 For each chart, a number $0<\rho< 1$ has been fixed and the following
 
  1501 For each chart, a number $0<\rho< 1$ has been fixed and the following
 
  1502 has been executed 150 times. Generating a large graph $G_{large}$,
 
  1502 has been executed 150 times. Generating a large graph $G_{large}$,
 
  1503 choose 10 of its induced subgraphs having $\rho\ |V_{large}|$ nodes,
 
  1503 choose 10 of its induced subgraphs having $\rho\ |V_{large}|$ nodes,
 
  1504 and for all the 10 subgraphs find a mapping by using both the graph
 
  1504 and for all the 10 subgraphs find a mapping by using both the graph
 
  1505 matching algorithms.  The $\delta = 5, 10, 35$ and $\rho = 0.05, 0.1,
 
  1505 matching algorithms.  The $\delta = 5, 10, 35$ and $\rho = 0.05, 0.1,
 
  1506 0.3, 0.6, 0.8, 0.95$ cases have been examined (see
 
  1506 0.3, 0.6, 0.8, 0.95$ cases have been examined, see
 
  1507 Figure~\ref{fig:randIND5}, \ref{fig:randIND10} and
 
  1507 Figure~\ref{fig:randIND5}, \ref{fig:randIND10} and
 
  1508 \ref{fig:randIND35}, and for each $\delta$, a cumulative chart is
 
  1508 \ref{fig:randIND35}.
 
  1509 given as well, which excludes $\rho = 0.05$ and $0.1$ for the sake of
 
       
  1510 perspicuity (see Figure~\ref{fig:randIND5Sum}, \ref{fig:randIND10Sum}
 
       
  1511 and \ref{fig:randIND35Sum}).
 
       
  1512 
  1509 
  1513 
  1510 
  1514 
  1511 
  1515 
  1512 
  1516 
  1513 
  1609 \vspace*{-0.8cm}
 
  1606 \vspace*{-0.8cm}
 
  1610 \caption{IND on graphs having an average degree of
 
  1607 \caption{IND on graphs having an average degree of
 
  1611   5.}\label{fig:randIND5}
 
  1608   5.}\label{fig:randIND5}
 
  1612 \end{figure}
 
  1609 \end{figure}
 
  1613 
  1610 
  1614 \begin{figure}[H]
 
       
  1615 \begin{center}
 
       
  1616 \hspace*{-2cm}
 
       
  1617 \begin{tikzpicture}
 
       
  1618 \begin{axis}[title={Rand IND Summary, $\delta = 5$, $\rho = 0.3, 0.6, 0.8, 0.95$},height=17cm,width=16cm,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},line width=0.8pt,grid
 
       
  1619 =major,mark size=1pt, legend style={at={(0,1)},anchor=north
 
       
  1620   west},scaled x ticks = false,x tick label style={/pgf/number
 
       
  1621   format/1000 sep = \thinspace}]
 
       
  1622 %\addplot+[only marks] table {proteinsOrig.txt};
 
       
  1623 \addplot[mark=*,mark size=1.5pt,color=blue] table
 
       
  1624         {randGraph/ind/vf2pInd5_0.3.txt}; \addplot[mark=triangle*,mark
 
       
  1625           size=1.8pt,color=red] table
 
       
  1626         {randGraph/ind/vf2ppInd5_0.3.txt}; \addplot[mark=*,mark
 
       
  1627           size=1.5pt,color=blue] table
 
       
  1628         {randGraph/ind/vf2pInd5_0.6.txt}; \addplot[mark=triangle*,mark
 
       
  1629           size=1.8pt,color=red] table
 
       
  1630         {randGraph/ind/vf2ppInd5_0.6.txt}; \addplot[mark=*,mark
 
       
  1631           size=1.5pt,color=blue] table
 
       
  1632         {randGraph/ind/vf2pInd5_0.8.txt}; \addplot[mark=triangle*,mark
 
       
  1633           size=1.8pt,color=red] table
 
       
  1634         {randGraph/ind/vf2ppInd5_0.8.txt}; \addplot[mark=*,mark
 
       
  1635           size=1.5pt,color=blue] table
 
       
  1636         {randGraph/ind/vf2pInd5_0.95.txt};
 
       
  1637         \addplot[mark=triangle*,mark size=1.8pt,color=red] table
 
       
  1638                 {randGraph/ind/vf2ppInd5_0.95.txt};
 
       
  1639 \end{axis}
 
       
  1640 \end{tikzpicture}
 
       
  1641 \end{center}
 
       
  1642 \vspace*{-0.8cm}
 
       
  1643 \caption{Cummulative chart for $\delta=5$.}\label{fig:randIND5Sum}
 
       
  1644 \end{figure}
 
       
  1645 
       
  1646 
       
  1647 
  1611 
  1648 \begin{figure}[H]
 
  1612 \begin{figure}[H]
 
  1649 \vspace*{-1.5cm}
 
  1613 \vspace*{-1.5cm}
 
  1650 \hspace*{-1.5cm}
 
  1614 \hspace*{-1.5cm}
 
  1651 \begin{subfigure}[b]{0.55\textwidth}
 
  1615 \begin{subfigure}[b]{0.55\textwidth}
 
  1741 \vspace*{-0.8cm}
 
  1705 \vspace*{-0.8cm}
 
  1742 \caption{IND on graphs having an average degree of
 
  1706 \caption{IND on graphs having an average degree of
 
  1743   10.}\label{fig:randIND10}
 
  1707   10.}\label{fig:randIND10}
 
  1744 \end{figure}
 
  1708 \end{figure}
 
  1745 
  1709 
  1746 \begin{figure}[H]
 
       
  1747 \begin{center}
 
       
  1748 \hspace*{-2cm}
 
       
  1749 \begin{tikzpicture}
 
       
  1750 \begin{axis}[title={Rand IND Summary, $\delta = 10$, $\rho = 0.3, 0.6, 0.8, 0.95$},height=17cm,width=16cm,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},line width=0.8pt,grid
 
       
  1751 =major,mark size=1pt, legend style={at={(0,1)},anchor=north
 
       
  1752   west},scaled x ticks = false,x tick label style={/pgf/number
 
       
  1753   format/1000 sep = \thinspace}]
 
       
  1754 %\addplot+[only marks] table {proteinsOrig.txt};
 
       
  1755 \addplot[mark=*,mark size=1.5pt,color=blue] table
 
       
  1756         {randGraph/ind/vf2pInd10_0.3.txt};
 
       
  1757         \addplot[mark=triangle*,mark size=1.8pt,color=red] table
 
       
  1758                 {randGraph/ind/vf2ppInd10_0.3.txt};
 
       
  1759                 \addplot[mark=*,mark size=1.5pt,color=blue] table
 
       
  1760                         {randGraph/ind/vf2pInd10_0.6.txt};
 
       
  1761                         \addplot[mark=triangle*,mark
 
       
  1762                           size=1.8pt,color=red] table
 
       
  1763                                 {randGraph/ind/vf2ppInd10_0.6.txt};
 
       
  1764                                 \addplot[mark=*,mark
 
       
  1765                                   size=1.5pt,color=blue] table
 
       
  1766                                         {randGraph/ind/vf2pInd10_0.8.txt};
 
       
  1767                                         \addplot[mark=triangle*,mark
 
       
  1768                                           size=1.8pt,color=red] table
 
       
  1769                                                 {randGraph/ind/vf2ppInd10_0.8.txt};
 
       
  1770                                                 \addplot[mark=*,mark
 
       
  1771                                                   size=1.5pt,color=blue]
 
       
  1772                                                 table
 
       
  1773                                                 {randGraph/ind/vf2pInd10_0.95.txt};
 
       
  1774                                                 \addplot[mark=triangle*,mark
 
       
  1775                                                   size=1.8pt,color=red]
 
       
  1776                                                 table
 
       
  1777                                                 {randGraph/ind/vf2ppInd10_0.95.txt};
 
       
  1778 \end{axis}
 
       
  1779 \end{tikzpicture}
 
       
  1780 \end{center}
 
       
  1781 \vspace*{-0.8cm}
 
       
  1782 \caption{Cummulative chart for $\delta=10$.}\label{fig:randIND10Sum}
 
       
  1783 \end{figure}
 
       
  1784 
       
  1785 
  1710 
  1786 
  1711 
  1787 \begin{figure}[H]
 
  1712 \begin{figure}[H]
 
  1788 \vspace*{-1.5cm}
 
  1713 \vspace*{-1.5cm}
 
  1789 \hspace*{-1.5cm}
 
  1714 \hspace*{-1.5cm}
 
  1878 \vspace*{-0.8cm}
 
  1803 \vspace*{-0.8cm}
 
  1879 \caption{IND on graphs having an average degree of
 
  1804 \caption{IND on graphs having an average degree of
 
  1880   35.}\label{fig:randIND35}
 
  1805   35.}\label{fig:randIND35}
 
  1881 \end{figure}
 
  1806 \end{figure}
 
  1882 
  1807 
  1883 \begin{figure}[H]
 
       
  1884 \begin{center}
 
       
  1885 \hspace*{-2cm}
 
       
  1886 \begin{tikzpicture}
 
       
  1887 \begin{axis}[title={Rand IND Summary, $\delta = 35$, $\rho = 0.3, 0.6, 0.8, 0.95$},height=17cm,width=16cm,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},line width=0.8pt,grid
 
       
  1888 =major,mark size=1pt, legend style={at={(0,1)},anchor=north
 
       
  1889   west},scaled x ticks = false,x tick label style={/pgf/number
 
       
  1890   format/1000 sep = \thinspace}]
 
       
  1891 %\addplot+[only marks] table {proteinsOrig.txt};
 
       
  1892 \addplot[mark=*,mark size=1.5pt,color=blue] table
 
       
  1893         {randGraph/ind/vf2pInd35_0.3.txt};
 
       
  1894         \addplot[mark=triangle*,mark size=1.8pt,color=red] table
 
       
  1895                 {randGraph/ind/vf2ppInd35_0.3.txt};
 
       
  1896                 \addplot[mark=*,mark size=1.5pt,color=blue] table
 
       
  1897                         {randGraph/ind/vf2pInd35_0.6.txt};
 
       
  1898                         \addplot[mark=triangle*,mark
 
       
  1899                           size=1.8pt,color=red] table
 
       
  1900                                 {randGraph/ind/vf2ppInd35_0.6.txt};
 
       
  1901                                 \addplot[mark=*,mark
 
       
  1902                                   size=1.5pt,color=blue] table
 
       
  1903                                         {randGraph/ind/vf2pInd35_0.8.txt};
 
       
  1904                                         \addplot[mark=triangle*,mark
 
       
  1905                                           size=1.8pt,color=red] table
 
       
  1906                                                 {randGraph/ind/vf2ppInd35_0.8.txt};
 
       
  1907                                                 \addplot[mark=*,mark
 
       
  1908                                                   size=1.5pt,color=blue]
 
       
  1909                                                 table
 
       
  1910                                                 {randGraph/ind/vf2pInd35_0.95.txt};
 
       
  1911                                                 \addplot[mark=triangle*,mark
 
       
  1912                                                   size=1.8pt,color=red]
 
       
  1913                                                 table
 
       
  1914                                                 {randGraph/ind/vf2ppInd35_0.95.txt};
 
       
  1915 \end{axis}
 
       
  1916 \end{tikzpicture}
 
       
  1917 \end{center}
 
       
  1918 \vspace*{-0.8cm}
 
       
  1919 \caption{Cummulative chart for $\delta=35$.}\label{fig:randIND35Sum}
 
       
  1920 \end{figure}
 
       
  1921 
  1808 
  1922 Based on these experiments, VF2++ is faster than VF2 Plus and able to
 
  1809 Based on these experiments, VF2++ is faster than VF2 Plus and able to
 
  1923 handle really large graphs in milliseconds. Note that when $IND$ was
 
  1810 handle really large graphs in milliseconds. Note that when $IND$ was
 
  1924 considered and the small graphs had proportionally few nodes ($\rho =
 
  1811 considered and the small graphs had proportionally few nodes ($\rho =
 
  1925 0.05$, or $\rho = 0.1$), then VF2 Plus produced some inefficient node
 
  1812 0.05$, or $\rho = 0.1$), then VF2 Plus produced some inefficient node
lemon-vf2