August 21, 2009

Independent Set, Vertex Cover, and Clique

funes latex

doc.tex

\documentclass{article}
\usepackage[papersize={200mm, 60mm}, text={190mm, 55mm}]{geometry}
\usepackage{subfigure, tikz}

\begin{document}
\begin{figure}[H]
 \centering
 \subfigure[Original Graph]{\input{graph.tex}}
 \quad
 \subfigure[Independent Set]{\input{ind_set.tex}}
 \quad
 \subfigure[Vertex Cover]{\input{vc.tex}}
 \quad
 \subfigure[Clique]{\input{clique.tex}}
 \caption{Relations among Independent Set, Vertex Cover, and Clique}
\end{figure}

\end{document}

graph.tex

\begin{tikzpicture}
  [
    line/.style = {draw=gray, ultra thick},
  ]

  \coordinate (O) at (-.5cm, .3cm);
  % in polar coordinates system
  \coordinate (A) at (  0: 2cm);
  \coordinate (B) at ( 60: 2cm);
  \coordinate (C) at (120: 2cm);
  \coordinate (D) at (180: 2cm);
  \coordinate (E) at (240: 2cm);
  \coordinate (F) at (300: 2cm);

  % edges
  \path[line] (A) -- (B);
  \path[line] (B) -- (C);
  \path[line] (C) -- (D);
  \path[line] (D) -- (E);
  \path[line] (E) -- (F);
  \path[line] (F) -- (A);
  \path[line] (B) -- (O);
  \path[line] (O) -- (F);
  \path[line] (B) -- (D);
  \path[line] (D) -- (F);

  % nodes
  \shade[ball color=gray] (O) circle (4pt);
  \shade[ball color=gray] (A) circle (4pt);
  \shade[ball color=gray] (B) circle (4pt);
  \shade[ball color=gray] (C) circle (4pt);
  \shade[ball color=gray] (D) circle (4pt);
  \shade[ball color=gray] (E) circle (4pt);
  \shade[ball color=gray] (F) circle (4pt);
\end{tikzpicture}

ind_set.tex

\begin{tikzpicture}
  [
    line/.style = {draw=gray, ultra thick},
  ]

  \coordinate (O) at (-.5cm, .3cm);
  % in polar coordinates system
  \coordinate (A) at (  0: 2cm);
  \coordinate (B) at ( 60: 2cm);
  \coordinate (C) at (120: 2cm);
  \coordinate (D) at (180: 2cm);
  \coordinate (E) at (240: 2cm);
  \coordinate (F) at (300: 2cm);

  % edges
  \path[line] (A) -- (B);
  \path[line] (B) -- (C);
  \path[line] (C) -- (D);
  \path[line] (D) -- (E);
  \path[line] (E) -- (F);
  \path[line] (F) -- (A);
  \path[line] (B) -- (O);
  \path[line] (O) -- (F);
  \path[line] (B) -- (D);
  \path[line] (D) -- (F);

  % nodes
  \shade[ball color=blue!80]  (O) circle (4pt);
  \shade[ball color=blue!80]  (A) circle (4pt);
  \shade[ball color=gray] (B) circle (4pt);
  \shade[ball color=blue!80]  (C) circle (4pt);
  \shade[ball color=gray] (D) circle (4pt);
  \shade[ball color=blue!80]  (E) circle (4pt);
  \shade[ball color=gray] (F) circle (4pt);
\end{tikzpicture}

vc.tex

\begin{tikzpicture}
  [
    line/.style = {draw=gray, ultra thick},
  ]

  \coordinate (O) at (-.5cm, .3cm);
  % in polar coordinates system
  \coordinate (A) at (  0: 2cm);
  \coordinate (B) at ( 60: 2cm);
  \coordinate (C) at (120: 2cm);
  \coordinate (D) at (180: 2cm);
  \coordinate (E) at (240: 2cm);
  \coordinate (F) at (300: 2cm);

  % edges
  \path[line] (A) -- (B);
  \path[line] (B) -- (C);
  \path[line] (C) -- (D);
  \path[line] (D) -- (E);
  \path[line] (E) -- (F);
  \path[line] (F) -- (A);
  \path[line] (B) -- (O);
  \path[line] (O) -- (F);
  \path[line] (B) -- (D);
  \path[line] (D) -- (F);

  % nodes
  \shade[ball color=gray] (O) circle (4pt);
  \shade[ball color=gray] (A) circle (4pt);
  \shade[ball color=red ] (B) circle (4pt);
  \shade[ball color=gray] (C) circle (4pt);
  \shade[ball color=red ] (D) circle (4pt);
  \shade[ball color=gray] (E) circle (4pt);
  \shade[ball color=red ] (F) circle (4pt);
\end{tikzpicture}

clique.tex

\begin{tikzpicture}
  [
    line/.style = {draw=gray, ultra thick},
  ]

  \coordinate (O) at (-.5cm, .3cm);
  % in polar coordinates system
  \coordinate (A) at (  0: 2cm);
  \coordinate (B) at ( 60: 2cm);
  \coordinate (C) at (120: 2cm);
  \coordinate (D) at (180: 2cm);
  \coordinate (E) at (240: 2cm);
  \coordinate (F) at (300: 2cm);

  % edges
  \path[line] (A) -- (O);
  \path[line] (A) -- (C);
  \path[line] (A) -- (D);
  \path[line] (A) -- (E);
  \path[line] (B) -- (E);
  \path[line] (B) -- (F);
  \path[line] (C) -- (A);
  \path[line] (C) -- (E);
  \path[line] (C) -- (F);
  \path[line] (C) -- (O);
  \path[line] (D) -- (O);
  \path[line] (E) -- (O);

  % nodes
  \shade[ball color=green] (O) circle (4pt);
  \shade[ball color=green] (A) circle (4pt);
  \shade[ball color=gray]  (B) circle (4pt);
  \shade[ball color=green] (C) circle (4pt);
  \shade[ball color=gray]  (D) circle (4pt);
  \shade[ball color=green] (E) circle (4pt);
  \shade[ball color=gray]  (F) circle (4pt);
\end{tikzpicture}
, , , , , ,
Comments Off on Independent Set, Vertex Cover, and Clique
January 1, 1970

ACRE Learning: subfigure

funes latex

doc.tex

\documentclass[12pt]{beamer}

% color theme
\usetheme{psu}
\usecolortheme[RGB={0,38,93}]{structure}

% For fancy fonts
\usepackage{fontspec}
\defaultfontfeatures{Scale=MatchLowercase, Mapping=tex-text} 
\setmainfont[Ligatures={Common}, Numbers={OldStyle}]{Cambria}
\setsansfont[Scale=0.95]{Candara}
\setromanfont{Cambria}
\setmonofont{Monaco}

\usepackage{subfigure}
\usepackage{tikz}

\begin{document}

\begin{frame}
  \frametitle{Goal of ACRE Learning}
  \begin{figure}[h]
    \centering
    \subfigure[Classifier $c$]{\input{fig1.tex}}
    \quad
    \subfigure[Cost Function $a$]{\input{fig2.tex}}
    \\
    \subfigure[Adversary's Goal]{\input{fig3.tex}}
    \quad
    \subfigure[ACRE Learning]{\input{fig4.tex}}
    \caption{Special Case of 2-Dimensional Feature Vectors}
  \end{figure}
\end{frame}
\end{document}

fig1.tex

\begin{tikzpicture}[scale=.95]
  % classifier
  \filldraw [fill=red!20, draw=black, smooth] (0,0) -- (0cm, 2.6cm) --
  (0.2cm, 2.2cm) -- (0.8cm, 2.0cm) -- (1.2, 2.2cm) -- (1.8cm, 1.6cm)
  -- (2.6cm, 0.4cm) -- (3.5cm, 0cm) -- cycle;
 
  % boundary
  \draw (3.5cm, 0cm) -- (3.5cm, 2.6cm) -- (0cm, 2.6cm);
 
  % markers
  \node at (0.2cm, 0.2cm) {\color{red}+};
  \node at (3.3cm, 2.4cm) {\color{blue}-};
\end{tikzpicture}

fig2.tex

\begin{tikzpicture}[scale=.95]
  % boundary
  \draw (0, 0) -- (0cm, 2.6cm) -- (3.5cm, 2.6cm) -- (3.5cm, 0cm) --
  (0, 0);
 
  % classfier
  \filldraw [fill=red!20, draw=black, smooth] (0,0) -- (0cm, 2.6cm) --
  (0.2cm, 2.2cm) -- (0.8cm, 2.0cm) -- (1.2, 2.2cm) -- (1.8cm, 1.6cm)
  -- (2.6cm, 0.4cm) -- (3.5cm, 0cm) -- cycle;
 
  % cost functions
  \draw (2cm, 1.3cm) ellipse (1cm and .7cm);
  \draw (1.9cm, 1.3cm) ellipse (.8cm and .5cm);
  \draw (1.9cm, 1.3cm) ellipse (.6cm and .2cm);
  \draw (1.8cm, 1.3cm) ellipse (.3cm and .1cm);
  \draw (1.7cm, 1.3cm) ellipse (.12cm and .05cm);
  \draw (2cm, 1.6cm) ellipse (.1cm and .05cm);
\end{tikzpicture}

fig3.tex

\begin{tikzpicture}[scale=.95]
  % boundary
  \draw (0, 0) -- (0cm, 2.6cm) -- (3.5cm, 2.6cm) -- (3.5cm, 0cm) --
  (0, 0);
 
  % classfier
  \filldraw [fill=red!20, draw=black, smooth] (0,0) -- (0cm, 2.6cm) --
  (0.2cm, 2.2cm) -- (0.8cm, 2.0cm) -- (1.2, 2.2cm) -- (1.8cm, 1.6cm)
  -- (2.6cm, 0.4cm) -- (3.5cm, 0cm) -- cycle;
 
  % cost functions
  \draw (2cm, 1.3cm) ellipse (1cm and .7cm);
  \draw (1.9cm, 1.3cm) ellipse (.8cm and .5cm);
  \draw (1.9cm, 1.3cm) ellipse (.6cm and .2cm);
  \draw (1.8cm, 1.3cm) ellipse (.3cm and .1cm);
  \draw (1.85cm, 1.3cm) ellipse (.12cm and .05cm);
  \draw (2cm, 1.6cm) ellipse (.1cm and .05cm);
 
  % star
  \filldraw [orange] (2.05cm, 1.3cm) circle (.05cm);
\end{tikzpicture}

fig4.tex

\begin{tikzpicture}
  [
    scale=.95,
    circle/.style={shape=circle, minimum size=1mm, text centered},
    instance/.style={shape=circle, minimum size=1mm, text centered}
    ]
 
  % boundary
  \draw (0, 0) -- (0cm, 2.6cm) -- (3.5cm, 2.6cm) -- (3.5cm, 0cm) --
  (0, 0);
 
  % cost functions
  \draw (2cm, 1.3cm) ellipse (1cm and .7cm);
  \draw (1.9cm, 1.3cm) ellipse (.8cm and .5cm);
  \draw (1.9cm, 1.3cm) ellipse (.6cm and .2cm);
  \draw (1.8cm, 1.3cm) ellipse (.3cm and .1cm);
  \draw (1.7cm, 1.3cm) ellipse (.12cm and .05cm);
  \draw (2cm, 1.6cm) ellipse (.1cm and .05cm);
 
  % yes-instance
  \node [instance] at (0.5cm, 0.5cm) {\color{red}$x^+$};
  % no-instance
  \node [instance] at (2.5cm, 2.3cm) {\color{blue}$x^-$};
 
  % queries
  \node [circle] at (  2cm,   2cm) {\color{orange}?};
  \node [circle] at (1.5cm, 0.8cm) {\color{orange}?};
  \node [circle] at (2.7cm, 0.5cm) {\color{orange}?};
  \node [circle] at (0.5cm, 2.3cm) {\color{orange}?};
  \node [circle] at (  3cm, 1.5cm) {\color{orange}?};
  \node [circle] at (2.3cm, 1.5cm) {\color{orange}?};
  \node [circle] at (1.7cm, 1.3cm) {\color{orange}?};
\end{tikzpicture}
, , , , ,
Comments Off on ACRE Learning: subfigure