4

Im trying to draw the following figure in LaTeX format:

Graph Cuts

My question is how can I draw the curved line passing through the nodes shown in the figure? And how to change the color of the nodes left and right from the curved line. Thx!

\documentclass{article}
\usepackage{tikz}
\usepackage{verbatim}
\usepackage[active,tightpage]{preview}
\PreviewEnvironment{tikzpicture}
\setlength\PreviewBorder{5pt}%
\usetikzlibrary{arrows}

\begin{document}
\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=3cm,
  thick,main node/.style={circle,fill=green!80,draw,font=\sffamily\Large\bfseries}]

  \node[main node] (1) {1};
  \node[main node] (2) [right of=1] {2};
  \node[main node] (3) [right of=2] {3};
  \node[main node] (4) [below left of=1] {4};
  \node[main node] (5) [right of=4] {5};
  \node[main node] (6) [right of=5] {6};
  \node[main node] (7) [below left of=4] {7};
  \node[main node] (8) [right of=7] {8};
  \node[main node] (9) [right of=8] {9};  
  \node[above] (10) [above of=5,node distance=6cm] {$S$};
  \node[below] (11) [below of=5,node distance=6cm] {$T$};

\begin{scope}

  \path[every node/.style={font=\sffamily\Large}]
    (1) edge node {} (4)
    (1) edge node {} (2)
    (2) edge node {} (3)
    (2) edge node {} (5)
    (3) edge node {} (6)
    (4) edge node {} (5)
    (4) edge node {} (7)
    (5) edge node {$n$} (6)
    (5) edge node {} (8)
    (6) edge node {} (9)
    (7) edge node {} (8)
    (8) edge node {} (9)
% Connect the source node with all the nodes
    (10) edge [bend left=-6] node {} (1)    
    (10) edge [bend left=20] node {} (2)
    (10) edge [bend left] node {} (3)
    (10) edge [bend right=30] node {} (4)
    (10) edge [bend right=10] node {} (5)
    (10) edge [bend left] node {} (6)
    (10) edge [bend right] node {} (7)
    (10) edge [bend right] node {} (8)
    (10) edge [bend left=20] node {} (9)
% Connect the sink node with all the nodes  
    (11) edge [bend left=10, dashed] node {} (1)    
    (11) edge [bend right=20, dashed] node {} (2)
    (11) edge [bend right, dashed] node {} (3)
    (11) edge [bend right=-20, dashed] node {} (4)
    (11) edge [bend right=5, dashed] node {} (5)
    (11) edge [bend right=20, dashed] node {} (6)
    (11) edge [bend left, dashed] node {} (7)
    (11) edge [bend right=-10, dashed] node {} (8)
    (11) edge [bend right=10, dashed] node {} (9);
\end{scope}

\end{tikzpicture}
\end{document}
5

I didn't try to optimize loops as percusse but just to draw the curve with hobby tikzlibrary. Points where line pass are fixed using calc tikzlibrary.

Node colors are fixed using an option argument in main node definition. green will be used as default, but can be changed with main node=red option.

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{hobby,calc}
\usepackage{verbatim}
\usepackage[active,tightpage]{preview}
\PreviewEnvironment{tikzpicture}
\setlength\PreviewBorder{5pt}%
\usetikzlibrary{arrows}

\begin{document}
\begin{tikzpicture}[>=stealth', shorten >=1pt, auto, 
    node distance=3cm,
    thick, 
    main node/.style={circle, fill=#1!80, draw, font=\sffamily\Large\bfseries}, 
    main node/.default=green,
    Sline/.style={ultra thick, green!80!black},
    Tline/.style={ultra thick, red!80!black},
]

  \node[main node] (1) {1};
  \node[main node] (2) [right of=1] {2};
  \node[main node=red] (3) [right of=2] {3};
  \node[main node] (4) [below left of=1] {4};
  \node[main node] (5) [right of=4] {5};
  \node[main node=red] (6) [right of=5] {6};
  \node[main node] (7) [below left of=4] {7};
  \node[main node=red] (8) [right of=7] {8};
  \node[main node=red] (9) [right of=8] {9};  
  \node[above] (10) [above of=5,node distance=6cm] {$S$};
  \node[below] (11) [below of=5,node distance=6cm] {$T$};

\begin{scope}

  \path[every node/.style={font=\sffamily\Large}]
    (1) edge node {} (4)
    (1) edge node {} (2)
    (2) edge node {} (3)
    (2) edge node {} (5)
    (3) edge node {} (6)
    (4) edge node {} (5)
    (4) edge node {} (7)
    (5) edge node {$n$} (6)
    (5) edge node {} (8)
    (6) edge node {} (9)
    (7) edge node {} (8)
    (8) edge node {} (9)
% Connect the source node with all the nodes
    (10) edge [bend left=-6, Sline] node {} (1)    
    (10) edge [bend left=20, Sline] node {} (2)
    (10) edge [bend left] node {} (3)
    (10) edge [bend right=30, Sline] node {} (4)
    (10) edge [bend right=10, Sline] node {} (5)
    (10) edge [bend left] node {} (6)
    (10) edge [bend right, Sline] node {} (7)
    (10) edge [bend right] node {} (8)
    (10) edge [bend left=20] node {} (9)
% Connect the sink node with all the nodes  
    (11) edge [bend left=10, dashed] node {} (1)    
    (11) edge [bend right=20, dashed] node {} (2)
    (11) edge [bend right, dashed, Tline] node {} (3)
    (11) edge [bend right=-20, dashed] node {} (4)
    (11) edge [bend right=5, dashed] node {} (5)
    (11) edge [bend right=20, dashed, Tline] node {} (6)
    (11) edge [bend left, dashed] node {} (7)
    (11) edge [bend right=-10, dashed, Tline] node {} (8)
    (11) edge [bend right=10, dashed, Tline] node {} (9);
\end{scope}

\draw[dashed, thick, purple] (7|-11) to[curve through={($(7.center)!0.5!(8.center)$) ($(8.center)!0.5!(5.center)$) ($(5.center)!0.5!(6.center)$) ($(2.center)!0.5!(3.center)$)}] (3|-10); 
\end{tikzpicture}
\end{document}

enter image description here

2
  • and how to make the equivalent lines thicker than the others? for example the lines from S node to nodes 1,2,4,5,7 should have a thicker line than the rest .. and vice versa
    – Kostas
    Apr 17 '15 at 11:51
  • @Kostas this what .styles are for. Look at updated answer with Sline and Tline styles
    – Ignasi
    Apr 17 '15 at 13:46
4

One way is to do lots of loops tediously

\documentclass[tikz]{standalone}
\usetikzlibrary{calc}
\begin{document}
\begin{tikzpicture}[main node/.style={circle,draw,font=\bfseries\sffamily\Large}]
\draw[thick](2.5,1.5)--++(2,3)--++(3,0)--++(-2,-3)--cycle(4,1.5) --++(2,3)(3.5,3)--++(3,0);
\foreach\x[] in{1,2,3}{
  \foreach\y[evaluate={\yi=int((\x-1)*3+\y)}] in{1,2,3}{
    \foreach\z in {1,4,5,7,8}{
      \ifnum\z=\yi\gdef\mycol{blue}\breakforeach\else\gdef\mycol{green}\fi
    }
    \node[main node,fill=\mycol!80] (\yi) at (\x + 1.5*\y,1.5*\x){\yi};
  }
}
\node[above] (10) [above of=5,node distance=6cm] {$S$};
\node[below] (11) [below of=5,node distance=6cm] {$T$};

\foreach \x in {1,...,9}{
\path (10) edge[in=90,out=-90] (\x) (\x) edge[out=-90,in=90,dashed] (11);
}
\draw[ultra thick,dotted] (2.5,0)..controls(5,5) and (4,-1)..([shift={(45:2cm)}]8.center);
\end{tikzpicture}
\end{document}

enter image description here

2
  • and how to make the equivalent lines thicker than the others? for example the lines from S node to nodes 1,2,4,5,7 should have a thicker line than the rest .. and vice versa
    – Kostas
    Apr 17 '15 at 11:52
  • @Kostas Add thick or whatever you wish to the edges in the last foreach loop.
    – percusse
    Apr 17 '15 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.