bipartite graph doesn't label a vertex when showing it

[jasongrout]

In Sage 4.6, I see

sage: a=BipartiteGraph(matrix(2,2,[1,0,1,0]))
sage: a.show()

gives a graph where vertex "1" is not labeled (see attached picture).

Component: graph theory

Author: Geoffrey Ehrman, Douglas McNeil

Reviewer: Nathann Cohen

Merged: sage-4.7.1.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/10356

[51b33c04-92b8-44c2-9e6f-69d65854572a]

comment:1

Attachment: sage0.png

It looks like there's a bigger problem here:

sage: a=BipartiteGraph(matrix(2,2,[1,0,1,0]))
sage: a
Bipartite graph on 3 vertices
sage: a.vertices()
[0, 2, 3]

It can't be a coincidence that the missing vertex in a.vertices() is also the vertex missing a label. Of course, this may raise the question of why the fourth vertex is being drawn in the first place; however, I don't know enough about how graphs are drawn to be certain of that.

[51b33c04-92b8-44c2-9e6f-69d65854572a]

comment:2

The problem seems to be that the reduced adjacency matrix code does the following:

else:
    for ii in range(ncols):
        for jj in range(nrows):
            if arg1[jj][ii] != 0:
                self.add_edge((ii, jj + ncols))

This is fine if the graph is has no isolated vertices. However, any graphs with isolated vertices will cause the similar problems:

sage: n = matrix(4,4,[1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0])
[1 1 1 1]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
sage: g = BipartiteGraph(n)
sage: g
Bipartite graph on 5 vertices
sage: g.left, g.right
(set([0, 1, 2, 3]), set([4, 5, 6, 7]))

[56048686-9665-4c5e-973e-6c3add3aa805]

comment:3

Attachment: trac_10356_fix_bipartite_graphs_isolated_vertex_reduced_adjacency_matrix.patch.gz

It looks to me like gbe did all the hard work! Patch attached, which simply makes sure that the vertices are directly added to the graph, instead of relying on the side effect of adding an edge to the vertex. This fixes the label problem too.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Reviewer: Nathann Cohen

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Author: Geoffrey Ehrman, Douglas McNeil

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:4

To the point. And good to go ! :-)

Nathann

[jdemeyer]

Merged: sage-4.7.1.alpha0