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
TESTS:
sage: B = graphs.CompleteBipartiteGraph(7, 9)
sage: loads(dumps(B)) == B
True
sage: B = BipartiteGraph(graphs.CycleGraph(4))
sage: B == B.copy()
True
sage: type(B.copy())
<class 'sage.graphs.bipartite_graph.BipartiteGraph'>
-
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:- Empty or
None
(creates an empty graph). - An arbitrary graph.
- A reduced adjacency matrix.
- A file in alist format.
- From a NetworkX bipartite graph.
- Empty or
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 alist file format is described at http://www.inference.phy.cam.ac.uk/mackay/codes/alist.html
partition
– (default:None
) a tuple defining vertices of the left and right partition of the graph. Partitions will be determined automatically ifpartition``=``None
.check
– (default:True
) ifTrue
, an invalid input partition raises an exception. In the other case offending edges simply won’t be included.
Note
All remaining arguments are passed to the
Graph
constructorEXAMPLES:
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): ... TypeError: 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}
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 specifiescheck=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 = [range(5), 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, [range(4), range(4,7)]) sage: B3 Bipartite graph on 7 vertices sage: B3 == B2 True :: sage: G = Graph({0:[], 1:[], 2:[]}) sage: part = (range(2), [2]) sage: B = BipartiteGraph(G, part) sage: B2 = BipartiteGraph(B) sage: B == B2 True
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 == 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)
TESTS:
Make sure we can create a
BipartiteGraph
with keywords but no positional arguments (trac ticket #10958).sage: B = BipartiteGraph(multiedges=True) sage: B.allows_multiple_edges() True
Ensure that we can construct a
BipartiteGraph
with isolated vertices via the reduced adjacency matrix (trac ticket #10356):sage: a=BipartiteGraph(matrix(2,2,[1,0,1,0])) sage: a Bipartite graph on 4 vertices sage: a.vertices() [0, 1, 2, 3] sage: g = BipartiteGraph(matrix(4,4,[1]*4+[0]*12)) sage: g.vertices() [0, 1, 2, 3, 4, 5, 6, 7] sage: sorted(g.left.union(g.right)) [0, 1, 2, 3, 4, 5, 6, 7]
-
add_edge
(u, v=None, label=None)¶ Adds an edge from
u
andv
.INPUT:
u
– the tail of an edge.v
– (default:None
) the head of an edge. Ifv=None
, then attempt to understandu
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
Graph.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.
TEST:
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_edge(0,2) Traceback (most recent call last): ... RuntimeError: Edge vertices must lie in different partitions. sage: bg.add_edge(0,3); list(bg.right) [1, 3] sage: bg.add_edge(5,6); 5 in bg.left; 6 in bg.right True True
-
add_vertex
(name=None, left=False, right=False)¶ Creates 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 beNone
.left
– (default:False
) ifTrue
, puts the new vertex in the left partition.right
– (default:False
) ifTrue
, puts the new vertex in the right partition.
Obviously,
left
andright
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 isNone
.OUTPUT:
- If
name``=``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}
TESTS:
Exactly one of
left
andright
must be true:sage: G = BipartiteGraph() sage: G.add_vertex() Traceback (most recent call last): ... RuntimeError: Partition must be specified (e.g. left=True). sage: G.add_vertex(left=True, right=True) Traceback (most recent call last): ... RuntimeError: Only one partition may be specified.
Adding the same vertex must specify the same partition:
sage: bg = BipartiteGraph() sage: bg.add_vertex(0, right=True) sage: bg.add_vertex(0, right=True) sage: bg.vertices() [0] sage: bg.add_vertex(0, left=True) Traceback (most recent call last): ... RuntimeError: Cannot add duplicate vertex to other partition.
-
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
) eitherTrue
or sequence of same length asvertices
withTrue
/False
elements.right
– (default:False
) eitherTrue
or sequence of the same length asvertices
withTrue
/False
elements.
Only one of
left
andright
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}
TEST:
sage: bg = BipartiteGraph() sage: bg.add_vertices([0,1,2], left=True) sage: bg.add_vertices([0,1,2], left=[True,True,True]) sage: bg.add_vertices([0,1,2], right=[False,False,False]) sage: bg.add_vertices([0,1,2], right=[False,False,False]) sage: bg.add_vertices([0,1,2]) Traceback (most recent call last): ... RuntimeError: Partition must be specified (e.g. left=True). sage: bg.add_vertices([0,1,2], left=True, right=True) Traceback (most recent call last): ... RuntimeError: Only one partition may be specified. sage: bg.add_vertices([0,1,2], right=True) Traceback (most recent call last): ... RuntimeError: Cannot add duplicate vertex to other partition. sage: (bg.left, bg.right) ({0, 1, 2}, set())
-
bipartition
()¶ Returns the underlying bipartition of the bipartite graph.
EXAMPLE:
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)¶ Deletes vertex, removing all incident edges. Deleting a non-existent vertex will raise an exception.
INPUT:
vertex
– a vertex to delete.in_order
– (defaultFalse
) ifTrue
, this 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): ... RuntimeError: 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): ... RuntimeError: Vertex (0) not in the graph.
-
load_afile
(fname)¶ Loads into the current object the bipartite graph specified in the given file name. This file should follow David MacKay’s alist format, see http://www.inference.phy.cam.ac.uk/mackay/codes/data.html for examples and definition of the format.
EXAMPLE:
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() sage: B.load_afile(file_name) Bipartite graph on 11 vertices sage: B.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: B2 = BipartiteGraph(file_name) sage: B2 == B True
-
matching_polynomial
(algorithm='Godsil', name=None)¶ Computes the matching polynomial.
If \(p(G, k)\) denotes the number of \(k\)-matchings (matchings with \(k\) edges) in \(G\), then the matching polynomial is defined as [Godsil93]:
\[\mu(x)=\sum_{k \geq 0} (-1)^k p(G,k) x^{n-2k}\]INPUT:
algorithm
- a string which must be either “Godsil” (default) or “rook”; “rook” is usually faster for larger graphs.name
- optional string for the variable name in the polynomial.
EXAMPLE:
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 graphs 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
TESTS:
sage: g = BipartiteGraph(matrix.ones(4,3)) sage: g.matching_polynomial() x^7 - 12*x^5 + 36*x^3 - 24*x sage: g.matching_polynomial(algorithm="rook") x^7 - 12*x^5 + 36*x^3 - 24*x
-
plot
(*args, **kwds)¶ Overrides Graph’s plot function, to illustrate the bipartite nature.
EXAMPLE:
sage: B = BipartiteGraph(graphs.CycleGraph(20)) sage: B.plot() Graphics object consisting of 41 graphics primitives
-
project_left
()¶ Projects
self
onto left vertices. Edges are 2-paths in the original.EXAMPLE:
sage: B = BipartiteGraph(graphs.CycleGraph(20)) sage: G = B.project_left() sage: G.order(), G.size() (10, 10)
-
project_right
()¶ Projects
self
onto right vertices. Edges are 2-paths in the original.EXAMPLE:
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]]
.This method supports the named argument ‘sparse’ which defaults to
True
. When enabled, the returned matrix will be sparse.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
TESTS:
sage: B = BipartiteGraph() sage: B.reduced_adjacency_matrix() [] sage: M = Matrix([[0,0], [0,0]]) sage: BipartiteGraph(M).reduced_adjacency_matrix() == M True sage: M = Matrix([[10,2/3], [0,0]]) sage: B = BipartiteGraph(M, weighted=True, sparse=True) sage: M == B.reduced_adjacency_matrix() True
-
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.
EXAMPLE:
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 == b2 True
TESTS:
sage: file_name = os.path.join(SAGE_TMP, 'deleteme.alist.txt') sage: for order in range(3, 13, 3): ....: num_chks = int(order / 3) ....: num_vars = order - num_chks ....: partition = (range(num_vars), range(num_vars, num_vars+num_chks)) ....: for idx in range(100): ....: g = graphs.RandomGNP(order, 0.5) ....: try: ....: b = BipartiteGraph(g, partition, check=False) ....: b.save_afile(file_name) ....: b2 = BipartiteGraph(file_name) ....: if b != b2: ....: print("Load/save failed for code with edges:") ....: print(b.edges()) ....: break ....: except Exception: ....: print("Exception encountered for graph of order "+ str(order)) ....: print("with edges: ") ....: g.edges() ....: raise
-
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