Opened 15 years ago

Last modified 5 weeks ago

#1941 new task

Meta ticket: Finish bipartite graph implementation

Reported by: Robert Miller Owned by: Robert Miller
Priority: major Milestone: sage-9.8
Component: graph theory Keywords:
Cc: Lukáš Lánský, Max Alekseyev, Travis Scrimshaw Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Enjeck Cleopatra)

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

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

Fixed issues

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

Considered invalid or duplicate

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

Change History (28)

comment:1 Changed 15 years ago by Michael Abshoff

Milestone: sage-2.10.2

comment:2 Changed 15 years ago by Robert Miller

 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

comment:3 Changed 15 years ago by Robert Miller

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

comment:4 Changed 13 years ago by Robert Miller

Report Upstream: N/A

see #8329

comment:5 Changed 13 years ago by Robert Miller

see also #8330

comment:6 Changed 13 years ago by Robert Miller

#8331 is also relevant.

comment:7 Changed 13 years ago by Ryan Hinton

And another #8350.

comment:8 Changed 13 years ago by Ryan Hinton

Also #8425.

comment:9 Changed 11 years ago by Lukáš Lánský

Cc: Lukáš Lánský added
Description: modified (diff)

comment:10 Changed 11 years ago by Lukáš Lánský

Description: modified (diff)

comment:11 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:12 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:13 Changed 8 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:14 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:15 Changed 8 months ago by David Coudert

Cc: Max Alekseyev added
Description: modified (diff)
Milestone: sage-6.4sage-9.6
Summary: Finish bipartite graph implementationMeta ticket: Finish bipartite graph implementation
Type: defecttask

Gathering tickets related to BipartiteGraph, open and fixed issues.

comment:16 Changed 8 months ago by Max Alekseyev

Description: modified (diff)

comment:17 Changed 8 months ago by David Coudert

Description: modified (diff)

comment:18 Changed 8 months ago by Samuel Lelièvre

Description: modified (diff)

comment:19 Changed 8 months ago by David Coudert

Cc: Travis Scrimshaw added

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

comment:20 in reply to:  19 Changed 8 months ago by Travis Scrimshaw

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

comment:21 Changed 8 months ago by David Coudert

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.

comment:22 Changed 8 months ago by Travis Scrimshaw

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.

comment:23 Changed 8 months ago by Max Alekseyev

Description: modified (diff)

comment:24 Changed 7 months ago by David Coudert

Description: modified (diff)

comment:25 Changed 7 months ago by David Coudert

Description: modified (diff)

comment:26 Changed 6 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:27 Changed 6 months ago by Enjeck Cleopatra

Description: modified (diff)

comment:28 Changed 5 weeks ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.