A bipartite graph (aka bigraph) is a graph whose vertices can be divided into two disjoint sets such that vertices from one set only connect to the vertices from the other set and not each other. Applications where they arise include resource planning and coding theory.
Questions tagged [bipartite]
378 questions
20
votes
5 answers
Bipartite graph in NetworkX
B.add_nodes_from(a, bipartite=1)
B.add_nodes_from(b, bipartite=0)
nx.draw(B, with_labels = True)
plt.savefig("graph.png")
I am getting the following figure. How can I make it look like a proper bipartite graph?
sheetal_158
- 7,391
- 6
- 27
- 44
19
votes
7 answers
How to find if a graph is bipartite?
I have been trying to understand the bipartite graph. To my understanding it is a graph G which can be divided into two subgraphs U and V.So that intersection of U and V is a null set and union is graph G.
I am trying to find if a graph is bipartite…
user2738777
- 418
- 1
- 5
- 21
19
votes
3 answers
Where are the vertex names in an iGraph graph
My general problem is that I loose the vertex names / labels (not sure about the right word here) when generating a graph using iGraph.
I have an edge list IC_edge_sub of a bipartite network, that looks like the following:
new_individualID…
Henning Piezunka
- 255
- 1
- 3
- 9
14
votes
3 answers
How to plot a bipartite graph in R
How do I plot a network of type bipartite in R? Similar to this:
I have similar data but with weights for both genes and diseases and SARS. This network is an example. I have different kind of attributes. I followed a link here. But due to my…
Pankaj
- 1,296
- 2
- 13
- 23
14
votes
2 answers
Solving a graph game
I've struggled some time with a problem from a programming contest (Andrew Stankevich Contest 21) about a game that goes like follows:
Nick and Peter like to play the following game [...]. They
draw an undirected bipartite graph G on a sheet of…
Niklas B.
- 92,950
- 18
- 194
- 224
12
votes
2 answers
Minimizing number of crossings in a bipartite graph
The following algorithm problem occurred to me while drawing a graph for something unrelated:
We have a plane drawing of a bipartite graph, with the disjoint sets arranged in columns as shown. How can we rearrange the nodes within each column so…
Imre Kerr
- 2,388
- 14
- 34
11
votes
4 answers
Simplest way to plot changes in ranking between two ordered lists in R?
I'm wondering if there is an easy way to plot the changes in position of elements between 2 lists in the form of a directed bipartite graph in R. For example, list 1 and 2 are vectors of character strings, not necessarily containing the same…
dcl
- 929
- 1
- 10
- 22
10
votes
2 answers
Hopcroft–Karp algorithm in Python
I am trying to implement the Hopcroft Karp algorithm in Python using networkx as graph representation.
Currently I am as far as this:
#Algorithms for bipartite graphs
import networkx as nx
import collections
class HopcroftKarp(object):
…
Simon
- 1,521
- 2
- 13
- 20
10
votes
1 answer
Bipartite network graph with ggplot2
I have the following data frame:
structure(list(X1 = structure(c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L,
2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L, 3L, 3L, 3L, 3L, 4L, 4L,
4L, 4L, 4L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 5L, 6L, 6L, 6L
), .Label = c("1", "2",…
Dominik
- 2,753
- 7
- 28
- 32
9
votes
5 answers
How do I implement a Bipartite Graph in Java?
UPDATE
Some answers so far have suggested using an adjacency list. How would an adjacency list look like in Java? ... no pointers right :)
I'm trying to implement a Bipartite Graph in Java to sort into 2 groups information from a file. I found this…
Hristo
- 45,559
- 65
- 163
- 230
8
votes
1 answer
Ego Graph in NetworkX
I have bipartite graph with nodes such as(a1,a2,...a100, m1,m2,...). I want to find the induced subgraph for certain nodes say(a1,a2 and a10). I can do this by using networkx.ego_graph, but it takes one vertex at one time and returns the induced…
ankshukla
- 105
- 2
- 10
8
votes
1 answer
bipartite layout Gephi 0.9.1
my question is awkwardly simple:
how do i plot a bipartite graph in Gephi with a layout like the one you see in the attached image?
I really am not able to find an appropriate layout in Gephi's options
thanks
deltasun
- 314
- 3
- 11
8
votes
1 answer
Plot a bipartite plus line graph comparison
I have to plot a bipartite graph similar to this one:
I have 2 ranked list computed from two different ranking method. I would like to plot this data in order to give a rough qualitative handle on the similarity of 2 ranked lists.
The data I need…
andreapavan
- 697
- 1
- 7
- 24
8
votes
3 answers
Algorithm : Letters and envelopes pairing
Disclaimer : This isn't any kind of homework, the problem just came to my mind while I was going through all the Christmas cards
The problem is given as follows : We've got M envelopes and N letters, each of which is described as a pair of positive…
Danstahr
- 4,190
- 22
- 38
7
votes
1 answer
Solving a Maximum weight bipartite b-matching
My question is regarding the Maximum Weight B-Matching problem.
Bipartite matching problems pair two sets of vertices in a bipartite graph. A maximum weighted bipartite matching (MWM) is defined as a matching where the sum of the values of the…
Sina
- 209
- 1
- 3
- 11