Opened 13 years ago

Last modified 7 years ago

#1941 new defect

Finish bipartite graph implementation

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

Status badges

Description (last modified by brunellus)

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 (14)

comment:1 Changed 13 years ago by mabshoff

  • Milestone set to sage-2.10.2

comment:2 Changed 13 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 13 years ago by rlm

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

comment:4 Changed 11 years ago by rlm

  • Report Upstream set to N/A

see #8329

comment:5 Changed 11 years ago by rlm

see also #8330

comment:6 Changed 11 years ago by rlm

#8331 is also relevant.

comment:7 Changed 11 years ago by rhinton

And another #8350.

comment:8 Changed 11 years ago by rhinton

Also #8425.

comment:9 Changed 9 years ago by brunellus

  • Cc brunellus added
  • Description modified (diff)

comment:10 Changed 9 years ago by brunellus

  • Description modified (diff)

comment:11 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:12 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:13 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:14 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.