Bipartite graphs¶

This module implements bipartite graphs.

AUTHORS:

Robert L. Miller (2008-01-20): initial version
Ryan W. Hinton (2010-03-04): overrides for adding and deleting vertices and edges

class sage.graphs.bipartite_graph.BipartiteGraph(data=None, partition=None, check=True, *args, **kwds)¶

Bases: sage.graphs.graph.Graph

Bipartite graph.

INPUT:

data – can be any of the following:
1. Empty or None (creates an empty graph).
2. An arbitrary graph.
3. A reduced adjacency matrix.
  
  A reduced adjacency matrix contains only the non-redundant portion of the full adjacency matrix for the bipartite graph. Specifically, for zero matrices of the appropriate size, for the reduced adjacency matrix H, the full adjacency matrix is [[0, H'], [H, 0]]. The columns correspond to vertices on the left, and the rows correspond to vertices on the right.
4. A file in alist format.
  
  The alist file format is described at http://www.inference.phy.cam.ac.uk/mackay/codes/alist.html
5. From a NetworkX bipartite graph.
partition – (default: None); a tuple defining vertices of the left and right partition of the graph. Partitions will be determined automatically if partition is None.
check – boolean (default: True); if True, an invalid input partition raises an exception. In the other case offending edges simply won’t be included.
loops – ignored; bipartite graphs cannot have loops
multiedges – boolean (default: None); whether to allow multiple edges
weighted – boolean (default: None); whether graph thinks of itself as weighted or not. See self.weighted()

Note

All remaining arguments are passed to the Graph constructor

EXAMPLES:

No inputs or None for the input creates an empty graph:

sage: B = BipartiteGraph()
sage: type(B)
<class 'sage.graphs.bipartite_graph.BipartiteGraph'>
sage: B.order()
0
sage: B == BipartiteGraph(None)
True

From a graph: without any more information, finds a bipartition:

sage: B = BipartiteGraph(graphs.CycleGraph(4))
sage: B = BipartiteGraph(graphs.CycleGraph(5))
Traceback (most recent call last):
...
ValueError: input graph is not bipartite
sage: G = Graph({0: [5, 6], 1: [4, 5], 2: [4, 6], 3: [4, 5, 6]})
sage: B = BipartiteGraph(G)
sage: B == G
True
sage: B.left
{0, 1, 2, 3}
sage: B.right
{4, 5, 6}
sage: B = BipartiteGraph({0: [5, 6], 1: [4, 5], 2: [4, 6], 3: [4, 5, 6]})
sage: B == G
True
sage: B.left
{0, 1, 2, 3}
sage: B.right
{4, 5, 6}

If a Graph or DiGraph is used as data, you can specify a partition using partition argument. Note that if such graph is not bipartite, then Sage will raise an error. However, if one specifies check=False, the offending edges are simply deleted (along with those vertices not appearing in either list). We also lump creating one bipartite graph from another into this category:

sage: P = graphs.PetersenGraph()
sage: partition = [list(range(5)), list(range(5, 10))]
sage: B = BipartiteGraph(P, partition)
Traceback (most recent call last):
...
TypeError: input graph is not bipartite with respect to the given partition

sage: B = BipartiteGraph(P, partition, check=False)
sage: B.left
{0, 1, 2, 3, 4}
sage: B.show()

sage: G = Graph({0: [5, 6], 1: [4, 5], 2: [4, 6], 3: [4, 5, 6]})
sage: B = BipartiteGraph(G)
sage: B2 = BipartiteGraph(B)
sage: B == B2
True
sage: B3 = BipartiteGraph(G, [list(range(4)), list(range(4, 7))])
sage: B3
Bipartite graph on 7 vertices
sage: B3 == B2
True

sage: G = Graph({0: [], 1: [], 2: []})
sage: part = (list(range(2)), [2])
sage: B = BipartiteGraph(G, part)
sage: B2 = BipartiteGraph(B)
sage: B == B2
True

sage: d = DiGraph(6)
sage: d.add_edge(0, 1)
sage: part=[[1, 2, 3], [0, 4, 5]]
sage: b = BipartiteGraph(d, part)
sage: b.left
{1, 2, 3}
sage: b.right
{0, 4, 5}

From a reduced adjacency matrix:

sage: M = Matrix([(1,1,1,0,0,0,0), (1,0,0,1,1,0,0),
....:             (0,1,0,1,0,1,0), (1,1,0,1,0,0,1)])
sage: M
[1 1 1 0 0 0 0]
[1 0 0 1 1 0 0]
[0 1 0 1 0 1 0]
[1 1 0 1 0 0 1]
sage: H = BipartiteGraph(M); H
Bipartite graph on 11 vertices
sage: H.edges()
[(0, 7, None),
 (0, 8, None),
 (0, 10, None),
 (1, 7, None),
 (1, 9, None),
 (1, 10, None),
 (2, 7, None),
 (3, 8, None),
 (3, 9, None),
 (3, 10, None),
 (4, 8, None),
 (5, 9, None),
 (6, 10, None)]

sage: M = Matrix([(1, 1, 2, 0, 0), (0, 2, 1, 1, 1), (0, 1, 2, 1, 1)])
sage: B = BipartiteGraph(M, multiedges=True, sparse=True)
sage: B.edges()
[(0, 5, None),
 (1, 5, None),
 (1, 6, None),
 (1, 6, None),
 (1, 7, None),
 (2, 5, None),
 (2, 5, None),
 (2, 6, None),
 (2, 7, None),
 (2, 7, None),
 (3, 6, None),
 (3, 7, None),
 (4, 6, None),
 (4, 7, None)]

sage: F.<a> = GF(4)
sage: MS = MatrixSpace(F, 2, 3)
sage: M = MS.matrix([[0, 1, a + 1], [a, 1, 1]])
sage: B = BipartiteGraph(M, weighted=True, sparse=True)
sage: B.edges()
[(0, 4, a), (1, 3, 1), (1, 4, 1), (2, 3, a + 1), (2, 4, 1)]
sage: B.weighted()
True

From an alist file:

sage: file_name = os.path.join(SAGE_TMP, 'deleteme.alist.txt')
sage: fi = open(file_name, 'w')
sage: _ = fi.write("7 4 \n 3 4 \n 3 3 1 3 1 1 1 \n 3 3 3 4 \n\
                    1 2 4 \n 1 3 4 \n 1 0 0 \n 2 3 4 \n\
                    2 0 0 \n 3 0 0 \n 4 0 0 \n\
                    1 2 3 0 \n 1 4 5 0 \n 2 4 6 0 \n 1 2 4 7 \n")
sage: fi.close()
sage: B = BipartiteGraph(file_name)
sage: B.is_isomorphic(H)
True

From a NetworkX bipartite graph:

sage: import networkx
sage: G = graphs.OctahedralGraph()
sage: N = networkx.make_clique_bipartite(G.networkx_graph())
sage: B = BipartiteGraph(N)

add_edge(u, v=None, label=None)¶

Add an edge from \(u\) to \(v\).

INPUT:

u – the tail of an edge.
v – (default: None); the head of an edge. If v=None, then attempt to understand u as a edge tuple.
label – (default: None); the label of the edge (u, v).

The following forms are all accepted:

G.add_edge(1, 2)
G.add_edge((1, 2))
G.add_edges([(1, 2)])
G.add_edge(1, 2, 'label')
G.add_edge((1, 2, 'label'))
G.add_edges([(1, 2, 'label')])

See add_edge() for more detail.

This method simply checks that the edge endpoints are in different partitions. If a new vertex is to be created, it will be added to the proper partition. If both vertices are created, the first one will be added to the left partition, the second to the right partition.

add_edges(edges, loops=True)¶

Add edges from an iterable container.

INPUT:

edges – an iterable of edges, given either as (u, v) or (u, v, label).
loops – ignored

See add_edges() for more detail.

This method simply checks that the edge endpoints are in different partitions. If a new vertex is to be created, it will be added to the proper partition. If both vertices are created, the first one will be added to the left partition, the second to the right partition.

EXAMPLES:

sage: bg = BipartiteGraph()
sage: bg.add_vertices([0, 1, 2], left=[True, False, True])
sage: bg.add_edges([(0, 1), (2, 1)])
sage: bg.add_edges([[0, 2]])
Traceback (most recent call last):
...
RuntimeError: edge vertices must lie in different partitions

Loops will raise an error:

sage: bg.add_edges([[0, 3], [3, 3]])
Traceback (most recent call last):
...
RuntimeError: edge vertices must lie in different partitions

add_vertex(name=None, left=False, right=False)¶

Create an isolated vertex. If the vertex already exists, then nothing is done.

INPUT:

name – (default: None); name of the new vertex. If no name is specified, then the vertex will be represented by the least non-negative integer not already representing a vertex. Name must be an immutable object and cannot be None.
left – boolean (default: False); if True, puts the new vertex in the left partition.
right – boolean (default: False); if True, puts the new vertex in the right partition.

Obviously, left and right are mutually exclusive.

As it is implemented now, if a graph \(G\) has a large number of vertices with numeric labels, then G.add_vertex() could potentially be slow, if name is None.

OUTPUT:

If name is None, the new vertex name is returned. None otherwise.

EXAMPLES:

sage: G = BipartiteGraph()
sage: G.add_vertex(left=True)
0
sage: G.add_vertex(right=True)
1
sage: G.vertices()
[0, 1]
sage: G.left
{0}
sage: G.right
{1}

add_vertices(vertices, left=False, right=False)¶

Add vertices to the bipartite graph from an iterable container of vertices.

Vertices that already exist in the graph will not be added again.

INPUT:

vertices – sequence of vertices to add.
left – (default: False); either True or sequence of same length as vertices with True/False elements.
right – (default: False); either True or sequence of the same length as vertices with True/False elements.

Only one of left and right keywords should be provided. See the examples below.

EXAMPLES:

sage: bg = BipartiteGraph()
sage: bg.add_vertices([0, 1, 2], left=True)
sage: bg.add_vertices([3, 4, 5], left=[True, False, True])
sage: bg.add_vertices([6, 7, 8], right=[True, False, True])
sage: bg.add_vertices([9, 10, 11], right=True)
sage: bg.left
{0, 1, 2, 3, 5, 7}
sage: bg.right
{4, 6, 8, 9, 10, 11}

allow_loops(new, check=True)¶

Change whether loops are permitted in the (di)graph

Note

This method overwrite the allow_loops() method to ensure that loops are forbidden in BipartiteGraph.

INPUT:

new – boolean

EXAMPLES:

sage: B = BipartiteGraph()
sage: B.allow_loops(True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in bipartite graphs

bipartition()¶

Return the underlying bipartition of the bipartite graph.

EXAMPLES:

sage: B = BipartiteGraph(graphs.CycleGraph(4))
sage: B.bipartition()
({0, 2}, {1, 3})

complement()¶

Return a complement of this graph.

EXAMPLES:

sage: B = BipartiteGraph({1: [2, 4], 3: [4, 5]})
sage: G = B.complement(); G
Graph on 5 vertices
sage: G.edges(labels=False)
[(1, 3), (1, 5), (2, 3), (2, 4), (2, 5), (4, 5)]

delete_vertex(vertex, in_order=False)¶

Delete vertex, removing all incident edges.

Deleting a non-existent vertex will raise an exception.

INPUT:

vertex – a vertex to delete.
in_order – boolean (default False); if True, deletes the \(i\)-th vertex in the sorted list of vertices, i.e. G.vertices()[i].

EXAMPLES:

sage: B = BipartiteGraph(graphs.CycleGraph(4))
sage: B
Bipartite cycle graph: graph on 4 vertices
sage: B.delete_vertex(0)
sage: B
Bipartite cycle graph: graph on 3 vertices
sage: B.left
{2}
sage: B.edges()
[(1, 2, None), (2, 3, None)]
sage: B.delete_vertex(3)
sage: B.right
{1}
sage: B.edges()
[(1, 2, None)]
sage: B.delete_vertex(0)
Traceback (most recent call last):
...
ValueError: vertex (0) not in the graph

sage: g = Graph({'a': ['b'], 'c': ['b']})
sage: bg = BipartiteGraph(g)  # finds bipartition
sage: bg.vertices()
['a', 'b', 'c']
sage: bg.delete_vertex('a')
sage: bg.edges()
[('b', 'c', None)]
sage: bg.vertices()
['b', 'c']
sage: bg2 = BipartiteGraph(g)
sage: bg2.delete_vertex(0, in_order=True)
sage: bg2 == bg
True

delete_vertices(vertices)¶

Remove vertices from the bipartite graph taken from an iterable sequence of vertices.

Deleting a non-existent vertex will raise an exception.

INPUT:

vertices – a sequence of vertices to remove

EXAMPLES:

sage: B = BipartiteGraph(graphs.CycleGraph(4))
sage: B
Bipartite cycle graph: graph on 4 vertices
sage: B.delete_vertices([0, 3])
sage: B
Bipartite cycle graph: graph on 2 vertices
sage: B.left
{2}
sage: B.right
{1}
sage: B.edges()
[(1, 2, None)]
sage: B.delete_vertices([0])
Traceback (most recent call last):
...
ValueError: vertex (0) not in the graph

is_bipartite(certificate=False)¶

Check whether the graph is bipartite.

This method always returns True as first value, plus a certificate when certificate == True.

INPUT:

certificate – boolean (default: False); whether to return a certificate. If set to True, the certificate returned is a proper 2-coloring of the vertices.

See also

EXAMPLES:

Maximum matching in a cycle graph:

sage: G = BipartiteGraph(graphs.CycleGraph(10))
sage: G.matching()
[(0, 1, None), (2, 3, None), (4, 5, None), (6, 7, None), (8, 9, None)]

The size of a maximum matching in a complete bipartite graph using Eppstein:

sage: G = BipartiteGraph(graphs.CompleteBipartiteGraph(4,5))
sage: G.matching(algorithm="Eppstein", value_only=True)
4

matching_polynomial(algorithm='Godsil', name=None)¶

Compute the matching polynomial.

The matching polynomial is defined as in [God1993], where \(p(G, k)\) denotes the number of \(k\)-matchings (matchings with \(k\) edges) in \(G\) :

\[\mu(x)=\sum_{k \geq 0} (-1)^k p(G,k) x^{n-2k}\]

INPUT:

algorithm – string (default: "Godsil"); either “Godsil” or “rook”; “rook” is usually faster for larger graphs
name – string (default: None); name of the variable in the polynomial, set to \(x\) when name is None

EXAMPLES:

sage: BipartiteGraph(graphs.CubeGraph(3)).matching_polynomial()
x^8 - 12*x^6 + 42*x^4 - 44*x^2 + 9

sage: x = polygen(QQ)
sage: g = BipartiteGraph(graphs.CompleteBipartiteGraph(16, 16))
sage: bool(factorial(16) * laguerre(16, x^2) == g.matching_polynomial(algorithm='rook'))
True

Compute the matching polynomial of a line with \(60\) vertices:

sage: from sage.functions.orthogonal_polys import chebyshev_U
sage: g = next(graphs.trees(60))
sage: chebyshev_U(60, x/2) == BipartiteGraph(g).matching_polynomial(algorithm='rook')
True

The matching polynomial of a tree is equal to its characteristic polynomial:

sage: g = graphs.RandomTree(20)
sage: p = g.characteristic_polynomial()
sage: p == BipartiteGraph(g).matching_polynomial(algorithm='rook')
True

plot(*args, **kwds)¶

Override Graph’s plot function, to illustrate the bipartite nature.

EXAMPLES:

sage: B = BipartiteGraph(graphs.CycleGraph(20))
sage: B.plot()
Graphics object consisting of 41 graphics primitives

project_left()¶

Project self onto left vertices. Edges are 2-paths in the original.

EXAMPLES:

sage: B = BipartiteGraph(graphs.CycleGraph(20))
sage: G = B.project_left()
sage: G.order(), G.size()
(10, 10)

project_right()¶

Project self onto right vertices. Edges are 2-paths in the original.

EXAMPLES:

sage: B = BipartiteGraph(graphs.CycleGraph(20))
sage: G = B.project_right()
sage: G.order(), G.size()
(10, 10)

reduced_adjacency_matrix(sparse=True)¶

Return the reduced adjacency matrix for the given graph.

A reduced adjacency matrix contains only the non-redundant portion of the full adjacency matrix for the bipartite graph. Specifically, for zero matrices of the appropriate size, for the reduced adjacency matrix H, the full adjacency matrix is [[0, H'], [H, 0]].

INPUT:

sparse – boolean (default: True); whether to return a sparse matrix

EXAMPLES:

Bipartite graphs that are not weighted will return a matrix over ZZ:

sage: M = Matrix([(1,1,1,0,0,0,0), (1,0,0,1,1,0,0),
....:             (0,1,0,1,0,1,0), (1,1,0,1,0,0,1)])
sage: B = BipartiteGraph(M)
sage: N = B.reduced_adjacency_matrix()
sage: N
[1 1 1 0 0 0 0]
[1 0 0 1 1 0 0]
[0 1 0 1 0 1 0]
[1 1 0 1 0 0 1]
sage: N == M
True
sage: N[0,0].parent()
Integer Ring

Multi-edge graphs also return a matrix over ZZ:

sage: M = Matrix([(1,1,2,0,0), (0,2,1,1,1), (0,1,2,1,1)])
sage: B = BipartiteGraph(M, multiedges=True, sparse=True)
sage: N = B.reduced_adjacency_matrix()
sage: N == M
True
sage: N[0,0].parent()
Integer Ring

Weighted graphs will return a matrix over the ring given by their (first) weights:

sage: F.<a> = GF(4)
sage: MS = MatrixSpace(F, 2, 3)
sage: M = MS.matrix([[0, 1, a+1], [a, 1, 1]])
sage: B = BipartiteGraph(M, weighted=True, sparse=True)
sage: N = B.reduced_adjacency_matrix(sparse=False)
sage: N == M
True
sage: N[0,0].parent()
Finite Field in a of size 2^2

save_afile(fname)¶

Save the graph to file in alist format.

Saves this graph to file in David MacKay’s alist format, see http://www.inference.phy.cam.ac.uk/mackay/codes/data.html for examples and definition of the format.

EXAMPLES:

sage: M = Matrix([(1,1,1,0,0,0,0), (1,0,0,1,1,0,0),
....:             (0,1,0,1,0,1,0), (1,1,0,1,0,0,1)])
sage: M
[1 1 1 0 0 0 0]
[1 0 0 1 1 0 0]
[0 1 0 1 0 1 0]
[1 1 0 1 0 0 1]
sage: b = BipartiteGraph(M)
sage: file_name = os.path.join(SAGE_TMP, 'deleteme.alist.txt')
sage: b.save_afile(file_name)
sage: b2 = BipartiteGraph(file_name)
sage: b.is_isomorphic(b2)
True

to_undirected()¶

Return an undirected Graph (without bipartite constraint) of the given object.

EXAMPLES:

sage: BipartiteGraph(graphs.CycleGraph(6)).to_undirected()
Cycle graph: Graph on 6 vertices

vertex_cover(algorithm='Konig', value_only=False, reduction_rules=True, solver=None, verbosity=0)¶

Return a minimum vertex cover of self represented by a set of vertices.

A minimum vertex cover of a graph is a set \(S\) of vertices such that each edge is incident to at least one element of \(S\), and such that \(S\) is of minimum cardinality. For more information, see Wikipedia article Vertex_cover.

Equivalently, a vertex cover is defined as the complement of an independent set.

As an optimization problem, it can be expressed as follows:

\[\begin{split}\mbox{Minimize : }&\sum_{v\in G} b_v\\ \mbox{Such that : }&\forall (u,v) \in G.edges(), b_u+b_v\geq 1\\ &\forall x\in G, b_x\mbox{ is a binary variable}\end{split}\]

INPUT:

algorithm – string (default: "Konig"); algorithm to use among:
- "Konig" will compute a minimum vertex cover using Konig’s algorithm (Wikipedia article Kőnig%27s_theorem_(graph_theory))
- "Cliquer" will compute a minimum vertex cover using the Cliquer package
- "MILP" will compute a minimum vertex cover through a mixed integer linear program
- "mcqd" will use the MCQD solver (http://www.sicmm.org/~konc/maxclique/), and the MCQD package must be installed
value_only – boolean (default: False); if set to True, only the size of a minimum vertex cover is returned. Otherwise, a minimum vertex cover is returned as a list of vertices.
reduction_rules – (default: True); specify if the reductions rules from kernelization must be applied as pre-processing or not. See [ACFLSS04] for more details. Note that depending on the instance, it might be faster to disable reduction rules. This parameter is currently ignored when algorithm == "Konig".
solver – (default: None); specify a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method sage.numerical.mip.MixedIntegerLinearProgram.solve() of the class sage.numerical.mip.MixedIntegerLinearProgram.
verbosity – non-negative integer (default: 0); set the level of verbosity you want from the linear program solver. Since the problem of computing a vertex cover is \(NP\)-complete, its solving may take some time depending on the graph. A value of 0 means that there will be no message printed by the solver. This option is only useful if algorithm="MILP".

EXAMPLES:

On the Cycle Graph:

sage: B = BipartiteGraph(graphs.CycleGraph(6))
sage: len(B.vertex_cover())
3
sage: B.vertex_cover(value_only=True)
3

The two algorithms should return the same result:

sage: g = BipartiteGraph(graphs.RandomBipartite(10, 10, .5))
sage: vc1 = g.vertex_cover(algorithm="Konig")
sage: vc2 = g.vertex_cover(algorithm="Cliquer")
sage: len(vc1) == len(vc2)
True

Bipartite graphs¶

Previous topic

Next topic

This Page