Bipartite graphs

I want to draw something similar to this in latex. How can I do it? I want it to be a directed graph and want to be able to label the vertices.

-

One option would be to use PGF/TikZ; the package is very well documented, and you'll find many examples in the documentation. Another source of examples can be found at TeXample.net

Here's a little example:

\documentclass{book}
\usepackage{tikz}
\usetikzlibrary{positioning,chains,fit,shapes,calc}

\begin{document}

\definecolor{myblue}{RGB}{80,80,160}
\definecolor{mygreen}{RGB}{80,160,80}

\begin{tikzpicture}[thick,
every node/.style={draw,circle},
fsnode/.style={fill=myblue},
ssnode/.style={fill=mygreen},
every fit/.style={ellipse,draw,inner sep=-2pt,text width=2cm},
->,shorten >= 3pt,shorten <= 3pt
]

% the vertices of U
\begin{scope}[start chain=going below,node distance=7mm]
\foreach \i in {1,2,...,5}
\node[fsnode,on chain] (f\i) [label=left: \i] {};
\end{scope}

% the vertices of V
\begin{scope}[xshift=4cm,yshift=-0.5cm,start chain=going below,node distance=7mm]
\foreach \i in {6,7,...,9}
\node[ssnode,on chain] (s\i) [label=right: \i] {};
\end{scope}

% the set U
\node [myblue,fit=(f1) (f5),label=above:$U$] {};
% the set V
\node [mygreen,fit=(s6) (s9),label=above:$V$] {};

% the edges
\draw (f1) -- (s6);
\draw (s6) -- (f2);
\draw (f2) -- (s7);
\draw (s7) -- (f3);
\draw (s8) -- (f3);
\draw (f3) -- (s9);
\draw (s9) -- (f5);
\draw (f5) -- (s6);
\end{tikzpicture}

\end{document}


EDIT: I add a variation of the previous graph (requested in a comment); each vertex will now be a labelled ordered pair. The idea is to use multiple variables in each \foreach construct; the first variable will be used to add a name to each node and to create the labels; the second and third variables will give the first and second coordinates of each ordered pair. The code:

\documentclass{book}
\usepackage{tikz}
\usetikzlibrary{positioning,chains,fit,shapes,calc}

\begin{document}

\definecolor{myblue}{RGB}{80,80,160}
\definecolor{mygreen}{RGB}{80,160,80}

\begin{tikzpicture}[thick,
fsnode/.style={},
ssnode/.style={},
every fit/.style={ellipse,draw,inner sep=5pt,text width=2cm},
->,shorten >= 3pt,shorten <= 3pt
]

% the vertices of U
\begin{scope}[start chain=going below,node distance=7mm]
\foreach \i/\xcoord/\ycoord in {1/6/8,2/5/1,3/-4/7,4/6/9,5/0/-3}
\node[fsnode,on chain,label=left:$t_{\i}$] (f\i) {$(\xcoord,\ycoord)$};
\end{scope}

% the vertices of V
\begin{scope}[xshift=4cm,yshift=-0.5cm,start chain=going below,node distance=7mm]
\foreach \i/\xcoord/\ycoord in {6/0/3,7/1/4,8/-2/1,9/5/9}
\node[ssnode,on chain,label=right:$t_{\i}$] (s\i) {$(\xcoord,\ycoord)$};
\end{scope}

% the set U
\node [myblue,fit=(f1) (f5),label=above:$U$] {};
% the set V
\node [mygreen,fit=(s6) (s9),label=above:$V$] {};

% the edges
\draw (f1) -- (s6);
\draw (s6) -- (f2);
\draw (f2) -- (s7);
\draw (s7) -- (f3);
\draw (s8) -- (f3);
\draw (f3) -- (s9);
\draw (s9) -- (f5);
\draw (f5) -- (s6);
\end{tikzpicture}

\end{document}

-
Thank you very much. This works perfectly. I've one small request. Instead of colored dots if I need a value like $(5,6)$,$(1,2)$ etc. what should I do ? If possible could you please add an answer without editing the first one. It will be helpful for future reference. Thank you – Sunil Apr 6 '11 at 19:39
@Sunil: let me see if I understand: the numbers (1,2,...,8) should not appear; each vertex will be an ordered pair and you don't want the colored dots, but just the ordered pair? – Gonzalo Medina Apr 6 '11 at 19:58
@Gonzalo: Exactly but instead of the numbers I can use any labeling like (t1,t2,...,t9). – Sunil Apr 6 '11 at 20:39
@Sunil: just to be sure, is it something like this what you want? – Gonzalo Medina Apr 6 '11 at 22:40
@Gonzalo: Precisely. – Sunil Apr 7 '11 at 0:06

I come here after the battle but I hope to give some interesting informations.

1. There is a new librairie graphs in the cvs version but I think there is a bug in the documentation you need to replace : \usetikzlibrary{graph} by \usetikzlibrary{ graphs, graphs.standard} without graphs.standardI get an error : $missing An example like your code (I don't get color blue and color green for the two sets) \documentclass[]{scrartcl} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tikz} \thispagestyle{empty} \usetikzlibrary{ graphs, graphs.standard } \begin{document} \definecolor{myblue}{RGB}{80,80,160} \definecolor{mygreen}{RGB}{80,160,80} \begin{tikzpicture} \graph[nodes={draw, circle,fill=myblue}, radius=.5cm, empty nodes, branch down=1 cm, grow right sep=4cm] {subgraph I_nm [V={a, b, c, d, e}, W={1,...,4}]; a -- { 1}; b -- { 1, 2 }; c -- { 2,3, 4 }; e -- { 1,4} }; \end{tikzpicture} \end{document}  The result: 2. I made a package tkz-berge an I think it will be on the ctan servers the next week. I need to finish some tools for the documentation \documentclass[]{scrartcl} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tkz-berge} \thispagestyle{empty} \usetikzlibrary{fit,shapes} \begin{document} \definecolor{myblue}{RGB}{80,80,160} \definecolor{mygreen}{RGB}{80,160,80} \begin{tikzpicture}[every fit/.style={ellipse,draw,inner sep=-2pt,text width=2cm, line width=1pt}] \GraphInit[vstyle=Normal] \SetUpVertex[Math,Lpos=-180,LabelOut] \SetVertexNormal[FillColor=myblue,OuterSep=0pt,TextColor=myblue] \grEmptyPath[form=2,x=0,y=0,RA=2,rotation=90,prefix=U]{5} \SetVertexShade[BallColor=mygreen,OuterSep=0pt] \SetUpVertex[Lpos=0] \SetVertexNormal[FillColor=mygreen,TextColor=mygreen] \grEmptyPath[form=2,x=6,y=0,RA=2,rotation=90,prefix=V]{4} \SetUpEdge[lw=2pt,color=black] \Edges(U4,V3,U3,V2,U1) \Edges(U3,V3,U0,V0,U2,V1) % the set U \node [myblue,fit=(U0) (U4),label=above:\textcolor{myblue}{$U$}] {}; % the set V \node [mygreen,fit=(V0) (V3),label=above:\textcolor{mygreen}{$V$}] {}; \end{tikzpicture} \end{document}  The result is fine but it would be better to draw ellipses in the background before drawing edges - @Sunil : If you want to look at some graphs, the page about tkz-berge is here http://altermundus.com/pages/tkz/berge/index.html – Alain Matthes Apr 6 '11 at 15:45 In fact, my first idea was to provide a solution using your tkz-graph package (which I like so much and I've used before), but since I read elsewhere (at least I undestood so) that it is not available right now, I refrained from doing so and opted for a basic tikz solution. – Gonzalo Medina Apr 6 '11 at 16:42 @Gonzalo Medina The new versions of tkz-graph and tkz-berge are ready for pgf 2.0 and work with pgf 2.1 but I need to correct the documentations. The next versions will be optimize to pgf 2.1 and adapt to pgfkeys. I upload all my work the next week. – Alain Matthes Apr 6 '11 at 19:09 @Altermundus: I'm sorry. I'm not that familiar with drawing in latex and also that was a main reason for me to post a question without a try. All I did was copy @Gonzalo's answer and it worked perfectly. I tried both of your answer but I keep getting error. It's not finding some package I guess. – Sunil Apr 6 '11 at 19:12 @Sunil My english is not very good so perhaps I'm not clear. The first solution needs to work with pgf 2.1 version CVS, you need to download the cvs version to compile this solution. The second solution works only with my package but you need to download the package from my site or to wait 10 or 15 days if you want find it on the ctan servers. – Alain Matthes Apr 6 '11 at 19:27 Here is a mockup using pstricks: \documentclass{article} \usepackage{pst-node}% http://ctan.org/pkg/pst-node \usepackage{multido}% http://ctan.org/pkg/multido \begin{document} \begin{pspicture} % Define nodes/vertices \multido{\i=5+-1}{5}{\pnode(1,\i){U\i}}% Vertices in U \multido{\i=4+-1}{4}{\pnode[0,0.5](4,\i){V\i}}% Vertices in V % Draw vertex set/ellipses \psset{linestyle=solid,linecolor=black,linewidth=1pt,fillstyle=none}% \psellipse[linecolor=blue!80!white](1,3)(1.25,3)% U \psellipse[linecolor=green!40!black](4,3)(1.25,2.5)% V % Vertex set/ellipse labels \rput[u](1,6.5){$U$}% U \rput[u](4,6){$V$}% V % Node/vertex connections/edges \psset{linecolor=black,linewidth=0.5pt}% \psline(U5)(V4) \psline(U4)(V4) \psline(U4)(V3)% \psline(U3)(V2) \psline(U3)(V1)% \psline(U2)(V3)% \psline(U1)(V4) \psline(U1)(V1)% % Draw nodes/vertices and labels \psset{fillstyle=solid}% \multido{\i=5+-1}{5}{% U vertex set \pscircle[fillcolor=blue!80!white](U\i){0.2}% Print vertex \uput{10pt}[l](U\i){$U_\i$}% Print vertex label }% \multido{\i=4+-1}{4}{% V vertex set \pscircle[fillcolor=green!40!black](V\i){0.2}% Print vertex \uput{10pt}[r](V\i){$V_\i\$}% Print vertex label
}%
\end{pspicture}
\end{document}


-
Seems much simple ( at least to understand ). Thank you. – Sunil Sep 27 '11 at 14:03