Meta ticket: Finish bipartite graph implementation

[rlmill]

Systematically go through the functions of graph and generic_graph and see which ones, such as add_vertex, need to be overridden in the bipartite graph class so that everything makes sense. Right now, you can add an edge so that the bipartite graph is no longer bipartite.

1. add to __cmp__ to distinguish Bipartite from other graphs
2. loops - this should always be false for bipartite, right? (other functions with "loops" in the name)
3. density - should this reflect "bipartite density"?
4. clear - left & right too?
5. add left_vertices and right_vertices?
6. adjacency_matrix - should this order the vertices a certain way?
7. add_cycle
8. add_path
9. add a function "bipartite_subgraph" to preserve class?
10. bipartite_color, bipartite_sets, is_bipartite

See discussion https://groups.google.com/g/sage-devel/c/yU6nu89M4jU

Open tickets

• Improve add_edge in BipartiteGraph to make it independent from the current coloring #8744 Improve add_edge in BipartiteGraph to make it independent from the current coloring
• Equal hashes for non-isomorphic bipartite graphs with edge labels #33255 equal hashes for non-isomorphic bipartite graphs with edge labels
• Add interface to nauty-genbg (generator of bipartite graphs with given bipartition) #33365 missing interface for nauty-genbg (generating bipartite graphs with given bipartition)

Fixed issues

• Missing copy() method in BipartiteGraph #8329 copy
• BipartiteGraph needs to override methods to add and delete vertices and edges #8330 add_vertex, add_vertices
• BipartiteGraph constructor does not create partitions for dict inputs #8331 BipartiteGraph constructor does not create partitions for dict inputs
• Change BipartiteGraph .left and .right to sets #8421 Change BipartiteGraph .left and .right to sets
• BipartiteGraph add_edge allows bipartite property to be violated #8425 BipartiteGraph add_edge allows bipartite property to be violated
• Add BipartiteGraph to the documentation #8640 add BipartiteGraph to the documentation
• bipartite graph doesn't label a vertex when showing it #10356 bipartite graph doesn't label a vertex when showing it
• BipartiteGraph constructor without *args ignores **kwds #10958 BipartiteGraph constructor without *args ignores **kwds
• BipartiteGraph adding edges between new nodes ignores partition #10959 BipartiteGraph adding edges between new nodes ignores partition
• Bug when taking complement of bipartite graph. #12155 bug when taking complement of bipartite graph
• BipartiteGraph complement #12376 BipartiteGraph complement
• Matchings in Bipartite Graphs #22559 matchings in BipartiteGraph
• Unify behavior of bipartite matchings on labels and multiedges #23265 unify behavior of bipartite matchings on labels and multiedges
• Bipartite graphs should not accept loops #23275 defect: bipartite graphs should not accept loops
• partition input is ignored when casting DiGraph as BipartiteGraph #25065 partition input is ignored when casting DiGraph as BipartiteGraph
• Bipartite graph project_right() projects left #25985 bipartite graph project_right() projects left
• Bug in vertex cover for BipartiteGraph #25988 bug in vertex cover for BipartiteGraph
• clean bipartite_graph.py #26515 clean bipartite_graph.py
• Add method is_bipartite to BipartiteGraph #28198 add method is_bipartite to BipartiteGraph
• BipartiteGraph blindly trusts generic graphs #28897 BipartiteGraph blindly trusts generic graphs
• Memory leak in bipartite_graph (and so in generalised_quadrangle_with_spread) #31313 memory leak in bipartite_graph (and so in generalised_quadrangle_with_spread)
• canonical_label returns incorrect partite sets #33246 canonical_label returns incorrect partite sets
• BipartiteGraph() silently ignores given 'partition' argument #33249 BipartiteGraph() silently ignores given 'partition' argument
• Fix bug in .perfect_matchings() for BipartiteGraph #33260 Fix bug in .perfect_matchings() for BipartiteGraph and ensure that the output is consistent with the partite sets of a given bipartite graph
• .complement() treats bipartite graphs as generic #33261 .complement() treats bipartite graphs as generic
• BipartiteGraph() fails to create graph from graph6 string #33366 BipartiteGraph() fails to create graph from graph6 string
• BipartiteGraph.reduced_adjacency_matrix: accept keyword arguments for matrix constructor #33387 BipartiteGraph.reduced_adjacency_matrix: accept keyword arguments for matrix constructor

Considered invalid or duplicate

• BipartiteGraph override add_vertex() and add_vertices() #8350 BipartiteGraph override add_vertex() and add_vertices()
• Raising exceptions in BipartiteGraph instead of using unreliable methods #10068 raising exceptions in BipartiteGraph instead of using unreliable methods

CC: @sagetrac-brunellus @maxale @tscrim

Component: graph theory

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

[rlmill]

comment:2

 1. add to __cmp__ to distinguish Bipartite from other graphs
 2. loops - this should always be false for bipartite, right? (other functions with "loops" in the name)
 3. density - should this reflect "bipartite density"?
 4. add_vertex - to which side?
 5. add_vertices - what to do with this?
 6. clear - left & right too?
 7. add left_vertices and right_vertices?
 8. complement?
 9. copy
10. add_edge(s)
11. adjacency_matrix - should this order the vertices a certain way?
12. add_cycle
13. add_path
14. add a function "bipartite_subgraph" to preserve class?
15. bipartite_color, bipartite_sets, is_bipartite

[rlmill]

comment:3

Also, the automorphism group/canonical label functions need to be called with the correct partitions.

[rlmill]

comment:4

see #8329

[rlmill]

comment:5

see also #8330

[rlmill]

comment:6

#8331 is also relevant.

[rhinton]

comment:7

And another #8350.

[rhinton]

comment:8

Also #8425.

[dcoudert]

comment:15

Gathering tickets related to BipartiteGraph, open and fixed issues.

[dcoudert]

comment:19

Proposal from #33261#comment:3

Side note: The complete bipartite graph constructor should return a BipartiteGraph object IMO (instead of just a usual Graph).

I tried (for complete, random and random regular bipartite graphs) and it's not an easy task:

• the __repr__ method of BipartiteGraph modifies the name string and so we have to correct several doctests
• algorithms modifying a graph with the addition of vertices fail since the side is not given. We must either implement specific versions for BipartiteGraph or modify these algorithms to work properly with BipartiteGraph.
  So it's not so easy to do

[tscrim]

comment:20

Replying to @dcoudert:

Proposal from #33261#comment:3

Side note: The complete bipartite graph constructor should return a BipartiteGraph object IMO (instead of just a usual Graph).

I tried (for complete, random and random regular bipartite graphs) and it's not an easy task:

Thank you for attempting it.

• the __repr__ method of BipartiteGraph modifies the name string and so we have to correct several doctests

This is minor IMO (although it might be good for the two to be consistent); just annoying to do.

• algorithms modifying a graph with the addition of vertices fail since the side is not given. We must either implement specific versions for BipartiteGraph or modify these algorithms to work properly with BipartiteGraph.

This suggests that there is a compatibility issue between the two classes, which is a bug IMO since BipartiteGraph is a subclass of Graph. We probably need to modify add_vertex and add_edge to be compatible, such as returning a generic graph. Mainly, I am not sure I agree with the behavior of raising an error when the edge does not give a bipartite graph like in #8744 (although without such a complicated thing of recoloring the bipartite graph).

Essentially, IMO subclasses should behave like the base class but with extra features that utilize the special aspects (sometimes known as the "is-a" test).

[dcoudert]

comment:21

BipartiteGraph adds restrictions to Graph and the price to pay is to maintain the partition. When using a BipartiteGraph, some operations may be forbidden (edge contraction, etc.) or done with care (add_vertex, add_path, etc.). Otherwise, the user has to move back to Graph.

[tscrim]

comment:22

Then it should not be a subclass IMO because of a fundamental incompatibility with some common ABC between BipartiteGraph and Graph to explicitly prohibit said methods.

[maxale]

Just added #38618