Ticket #1941 (new defect)

Opened 5 years ago

Last modified 17 months ago

Finish bipartite graph implementation

Reported by: rlm Owned by: rlm
Priority: major Milestone: sage-5.11
Component: graph theory Keywords:
Cc: brunellus Work issues:
Report Upstream: N/A Reviewers:
Authors: Merged in:
Dependencies: Stopgaps:

Description (last modified by brunellus) (diff)

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. #8330: add_vertex, add_vertices
  5. clear - left & right too?
  6. add left_vertices and right_vertices?
  7. #12376: complement?
  8. #8329: copy
  9. #10959, #8744: add_edge(s)
  10. adjacency_matrix - should this order the vertices a certain way?
  11. add_cycle
  12. add_path
  13. add a function "bipartite_subgraph" to preserve class?
  14. bipartite_color, bipartite_sets, is_bipartite

Change History

comment:1 Changed 5 years ago by mabshoff

  • Milestone set to sage-2.10.2

comment:2 Changed 5 years ago by rlm

 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 5 years ago by rlm

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

comment:4 Changed 3 years ago by rlm

  • Report Upstream set to N/A

see #8329

comment:5 Changed 3 years ago by rlm

see also #8330

comment:6 Changed 3 years ago by rlm

#8331 is also relevant.

comment:7 Changed 3 years ago by rhinton

And another #8350.

comment:8 Changed 3 years ago by rhinton

Also #8425.

comment:9 Changed 17 months ago by brunellus

  • Cc brunellus added
  • Description modified (diff)

comment:10 Changed 17 months ago by brunellus

  • Description modified (diff)
Note: See TracTickets for help on using tickets.