Navigation

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(*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 (finds a bipartition).
    3. A graph and a bipartition.
    4. A reduced adjacency matrix.
    5. A file in alist format.
    6. From a NetworkX bipartite 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]].

The alist file format is described at http://www.inference.phy.cam.ac.uk/mackay/codes/alist.html

EXAMPLES:

  1. 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

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

    sage: B = BipartiteGraph(graphs.CycleGraph(4))
sage: B = BipartiteGraph(graphs.CycleGraph(5))
...
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
set([0, 1, 2, 3])
sage: B.right
set([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
set([0, 1, 2, 3])
sage: B.right
set([4, 5, 6])

  3. From a graph and a partition. Note that if the input 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 = [range(5), range(5,10)]
sage: B = BipartiteGraph(P, partition)
...
TypeError: Input graph is not bipartite with respect to the given partition!

sage: B = BipartiteGraph(P, partition, check=False)
sage: B.left
set([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

  1. 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

  1. From an alist file:

    sage: file_name = 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

  2. 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)

Adds an edge from u and v.

INPUT:

  • u – the tail of an edge.
  • v – (default: None) the head of an edge. If v=None, then attempt to add the edge (u, u).
  • 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.

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)
...
RuntimeError: Edge vertices must lie in different partitions.
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 be None.
  • left – (default: False) if True, puts the new vertex in the left partition.
  • right – (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.

EXAMPLES:

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

TESTS:

Exactly one of left and right must be true:

sage: G = BipartiteGraph()
sage: G.add_vertex()
...
RuntimeError: Partition must be specified (e.g. left=True).
sage: G.add_vertex(left=True, right=True)
...
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)
...
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.

INPUTS:

  • 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
set([0, 1, 2, 3, 5, 7])
sage: bg.right
set([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])
...
RuntimeError: Partition must be specified (e.g. left=True).
sage: bg.add_vertices([0,1,2], left=True, right=True)
...
RuntimeError: Only one partition may be specified.
sage: bg.add_vertices([0,1,2], right=True)
...
RuntimeError: Cannot add duplicate vertex to other partition.
sage: (bg.left, bg.right)
(set([0, 1, 2]), set([]))
bipartition()

Returns the underlying bipartition of the bipartite graph.

EXAMPLE:

sage: B = BipartiteGraph(graphs.CycleGraph(4))
sage: B.bipartition()
(set([0, 2]), set([1, 3]))
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 – (default False) if True, 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
set([2])
sage: B.edges()
[(1, 2, {}), (2, 3, {})]
sage: B.delete_vertex(3)
sage: B.right
set([1])
sage: B.edges()
[(1, 2, {})]
sage: B.delete_vertex(0)
...
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
set([2])
sage: B.right
set([1])
sage: B.edges()
[(1, 2, {})]
sage: B.delete_vertices([0])
...
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 = 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
plot(*args, **kwds)

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

EXAMPLE:

sage: B = BipartiteGraph(graphs.CycleGraph(20))
sage: B.plot()
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 = SAGE_TMP + 'deleteme.alist.txt'
sage: b.save_afile(file_name)
sage: b2 = BipartiteGraph(file_name)
sage: b == b2
True

TESTS:

sage: file_name = 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()
...           except:
...               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

Previous topic

Directed graphs

Next topic

Cliquer : routines for finding cliques in graphs

This Page

Navigation

© Copyright 2005--2010, The Sage Development Team. Created using Sphinx 0.6.3.