Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

A bipartite graph is a graph whose vertices can be divided into two disjoint sets. Given two lists: {1, 2, 3} and {x, y, z}, where some of the elements are connected:

{{1, x}, {1, y}, {1, z},{2, x}, {2, y}, {3, x}}

I want to draw a bipartite graph with the numbers {1, 2, 3} on one side, the letters {x, y, z} on the other, and with edges connecting those which are paired together. How can I draw such a graph?

Furthermore, how can one generate bipartite graphs? All I was able to find in the Mathematica documentation is BipartiteGraphQ that tests whether or not a graph is bipartite. I found nothing on how to generate one. Is there a way to do this without the Combinatorica` package?

share|improve this question
    
Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2)Read the FAQs! 3) When you see good Q&A, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. ALSO, remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign` –  chris Nov 23 '12 at 19:56
    
Do you need to draw (visualize) an existing graph or do you need to generate a new one? These are two different problems. –  Szabolcs Nov 26 '12 at 0:09
add comment

3 Answers

up vote 5 down vote accepted

One way is to specify VertexCoordinates:

g=Graph[{1 <-> x, 1 <-> y, 
  1 <-> z, 2 <-> x, 2 <-> y,
  3 <-> x}, 
 VertexCoordinates -> {{0, 2}, {1, 2}, {1, 1}, {1, 0}, {0, 1}, {0, 
    0}}]

bipartite graph

Note that the vertices {v1, v2, ...} are given in the order returned by VertexList.

VertexList[g]
(* {1, x, y, z, 2, 3} *)

Update

To automatize a bit the generation of bipartite graphs the way you want you could use this function:

bipartiteGraph[elements_List] := Module[{g1, el, c1, c2, cc, vrt},
  g1 = Graph[
    MapThread[
     UndirectedEdge, {Sort[elements][[All, 1]], 
      Sort[elements][[All, 2]]}]];
  el = VertexList[g1];
  c1 = Transpose[{Select[el, IntegerQ], 
     Table[{0, i}, {i, 1, 0, -1/(Length[Select[el, IntegerQ]] - 1)}]}];
  c2 = Transpose[{Complement[el, Select[el, IntegerQ]], 
     Table[{1, i}, {i, 1, 
       0, -1/(Length[Complement[el, Select[el, IntegerQ]]] - 1)}]}];
  cc = Join[c1, c2];
  vrt = cc[[Table[Position[cc, el[[i]]], {i, Length[cc]}][[All, 1, 
       1]], 2]];
  Graph[MapThread[
    UndirectedEdge, {Sort[elements][[All, 1]], 
     Sort[elements][[All, 2]]}], VertexCoordinates -> vrt, 
   VertexLabels -> "Name", VertexLabelStyle -> 16, 
   ImagePadding -> 20]
  ]

bipartiteGraph[{{1, x}, {1, y}, {1, z},{2, x}, {2, y}, {3, x}}]

bipartite graph

bipartiteGraph[{{4, p}, {1, x}, {1, y}, {1, z}, {2, x}, {2, y}, {3, x}, {4, r}}]

bipartite graph

GraphicsGrid[Partition[
  Table[bipartiteGraph[
  Union[Transpose[{RandomInteger[{1, 4}, 8], 
   RandomChoice[CharacterRange["a", "d"], 8]}]]], {16}], 4]]

grid of bipartite graphs

share|improve this answer
    
Thanks VLC! That is definitely helpful, but what if I dont want to manually type out the links and the coordinates? I vary the amount of vertices on each side, and the connections are randomly generated from trial to trial. As you can tell, I am new at this... Thanks again for your help! –  Pancholp Nov 23 '12 at 18:45
    
@Pancholp Please, see update. –  VLC Nov 25 '12 at 21:57
    
That is immensely helpful! Thank you! –  Pancholp Nov 26 '12 at 0:55
    
@Pancholp Glad to be of some help. –  VLC Nov 26 '12 at 6:51
add comment

This is a bit different approach. A balanced bipartite graph (where the two vertex sets have the same cardinality, $N$) can be represented as an adjacency matrix, where the rows and columns of the matrix stand for the left and right side vertices, respectively. This approach generates a random adjacency matrix and translates it to edges, representing left nodes as $(1, 2, ..., N)$ and right nodes as $(N+1, N+2, ..., 2N)$. Letters are only used for labelling right-side vertices.

n = 5; (* node number of ONE side of the graph *)
m = RandomInteger[{0, 1}, {n, n}];

adjacencyToEdge[m_List] := Module[{n = Length@m}, 
   DeleteCases[Flatten@Table[If[m[[i, j]] == 1, i -> n + j], {i, n}, {j, n}], Null]];

Row@{
  Graph[Range[2 n], adjacencyToEdge@m, 
   VertexCoordinates -> Join[
     Table[{0, 1 - i/n}, {i, n}], Table[{1, 1 - i/n}, {i, Length@m}]], 
   VertexLabels -> Join[
     Thread[Range@n -> Range@n], 
     Thread[Range[n + 1, 2 n] -> Take[CharacterRange["a", "z"], n]]], 
   ImagePadding -> 10, VertexLabelStyle -> 16, ImageSize -> 300],
  MatrixForm@m}

Mathematica graphics

Note that even unconnected nodes are placed at the correct position (which GraphLayout -> "BipartiteEmbedding" won't do).

share|improve this answer
add comment

Edit 2

In version 9, you can use BipartiteEmbedding:

Graph[{3, 2, 1, z, y, x}, {1 \[DirectedEdge] x, 1 \[DirectedEdge] y, 1 \[DirectedEdge] z, 2 \[DirectedEdge] x, 2 \[DirectedEdge] y, 3 \[DirectedEdge] x}, 
GraphLayout -> "BipartiteEmbedding" , 
VertexLabels -> "Name", ImagePadding -> 15, VertexLabelStyle -> 16]

The order of the vertices in the vertex list determines where they will appear in the graph (although Mathematica figures out the left right distinction).

bipartite3


Edit 1:

This is more direct than my earlier attempt. (You can find my earlier response in the edit history.)

Obtain the coordinates that Mathematica would use to plot a Turan graph that is bipartite:

TuranGraph[6, 2];
vc= AbsoluteOptions[%, VertexCoordinates]

{{0., -0.359017}, {0., 0.}, {0., 0.359017}, {1., -0.359017}, {1., 0.}, {1., 0.359017}}

Make a list of the left and right vertices. You reverse them each because Mathematica draws Turan graphs from the bottom up. You need the vertexList to ensure that the graph is laid out correctly. edges are simply the edges of the bipartite graph (which you obtained earlier).

leftvertices = Reverse@{1, 2, 3};
rightvertices = Reverse@{x, y, z};
edges={1 \[DirectedEdge] x, 1 \[DirectedEdge] y, 1 \[DirectedEdge] z, 2 \[DirectedEdge] x, 2 \[DirectedEdge] y, 3 \[DirectedEdge] x}

Graph the bipartite graph:

Graph[Join[leftvertices, rightvertices], edges, VertexLabels -> "Name", ImagePadding -> 15, 
VertexCoordinates -> {{0., -0.359017}, {0., 0.}, {0., 0.359017}, {1., -0.359017}, 
{1., 0.}, {1., 0.359017}}]

graph

Note: for some reason, the vertex coordinates are not properly used if vc is used instead of the actual list.

share|improve this answer
    
Thanks David! I will give this approach a shot as well! –  Pancholp Nov 24 '12 at 12:59
    
Note that if any of the nodes is unconnected, Mathematica places it at the bottom of the figure as a singleton when using "BipartiteEmbedding" (and not specifying vertex coordinates manually), yielding thus an ugly graph where vertex positions are messed up. –  István Zachar Mar 14 '13 at 14:34
    
I suppose so. But a true bipartite graph should have no singletons. –  David Carraher Mar 14 '13 at 15:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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