search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.32k stars 453 forks source link

Meta ticket: Finish bipartite graph implementation #1941

Open 89c6e537-b2e3-45e6-882d-d4957b74ffe5 opened 16 years ago

89c6e537-b2e3-45e6-882d-d4957b74ffe5 commented 16 years ago

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

Fixed issues

Considered invalid or duplicate

CC: @sagetrac-brunellus @maxale @tscrim

Component: graph theory

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

89c6e537-b2e3-45e6-882d-d4957b74ffe5 commented 16 years ago
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
89c6e537-b2e3-45e6-882d-d4957b74ffe5 commented 16 years ago
comment:3

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

89c6e537-b2e3-45e6-882d-d4957b74ffe5 commented 14 years ago
comment:4

see #8329

89c6e537-b2e3-45e6-882d-d4957b74ffe5 commented 14 years ago
comment:5

see also #8330

89c6e537-b2e3-45e6-882d-d4957b74ffe5 commented 14 years ago
comment:6

8331 is also relevant.

1f45545e-c887-4951-89a2-5b55c4770980 commented 14 years ago
comment:7

And another #8350.

1f45545e-c887-4951-89a2-5b55c4770980 commented 14 years ago
comment:8

Also #8425.

15606e31-f165-4fa5-94d5-bd9bfb0e1636 commented 12 years ago

Description changed:

--- 
+++ 
@@ -1 +1,16 @@
 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. 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
15606e31-f165-4fa5-94d5-bd9bfb0e1636 commented 12 years ago

Description changed:

--- 
+++ 
@@ -6,7 +6,7 @@
 4. #8330: add_vertex, add_vertices
 5. clear - left & right too?
 6. add left_vertices and right_vertices?
-7. complement?
+7. #12376: complement?
 8. #8329: copy
 9. #10959, #8744: add_edge(s)
 10. adjacency_matrix - should this order the vertices a certain way?
dcoudert commented 2 years ago
comment:15

Gathering tickets related to BipartiteGraph, open and fixed issues.

dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -3,14 +3,48 @@
 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
+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](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
+- #33246 `canonical_label` returns incorrect partite sets
+- #33249 `BipartiteGraph()` silently ignores given 'partition' argument
+- #33255 equal hashes for non-isomorphic bipartite graphs with edge labels
+
+
+**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`)
+
+**Considered invalid or duplicate**
+- #8350 `BipartiteGraph` override `add_vertex()` and `add_vertices()`
+- #10068 raising exceptions in `BipartiteGraph` instead of using unreliable methods
+
maxale commented 2 years ago

Description changed:

--- 
+++ 
@@ -19,7 +19,8 @@
 - #33246 `canonical_label` returns incorrect partite sets
 - #33249 `BipartiteGraph()` silently ignores given 'partition' argument
 - #33255 equal hashes for non-isomorphic bipartite graphs with edge labels
-
+- #33260 .perfect_matchings() does not respect partite sets of a given bipartite graph
+- #33261 .complement() treats bipartite graphs as generic

 **Fixed issues**
 - #8329 copy
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -19,7 +19,7 @@
 - #33246 `canonical_label` returns incorrect partite sets
 - #33249 `BipartiteGraph()` silently ignores given 'partition' argument
 - #33255 equal hashes for non-isomorphic bipartite graphs with edge labels
-- #33260 .perfect_matchings() does not respect partite sets of a given bipartite graph
+- #33260 Fix bug in `.perfect_matchings()` for `BipartiteGraph` and ensue that the output is consistent with the partite sets of a given bipartite graph
 - #33261 .complement() treats bipartite graphs as generic

 **Fixed issues**
slel commented 2 years ago

Description changed:

--- 
+++ 
@@ -19,7 +19,7 @@
 - #33246 `canonical_label` returns incorrect partite sets
 - #33249 `BipartiteGraph()` silently ignores given 'partition' argument
 - #33255 equal hashes for non-isomorphic bipartite graphs with edge labels
-- #33260 Fix bug in `.perfect_matchings()` for `BipartiteGraph` and ensue that the output is consistent with the partite sets of a given bipartite graph
+- #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

 **Fixed issues**
dcoudert commented 2 years ago
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:

tscrim commented 2 years ago
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 commented 2 years ago
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 commented 2 years ago
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 commented 2 years ago

Description changed:

--- 
+++ 
@@ -21,6 +21,8 @@
 - #33255 equal hashes for non-isomorphic bipartite graphs with edge labels
 - #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
+- #33365 missing interface for nauty-genbg (generating bipartite graphs with given bipartition)
+- #33366 `BipartiteGraph()` fails to create graph from `graph6` string

 **Fixed issues**
 - #8329 copy
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -23,6 +23,7 @@
 - #33261 .complement() treats bipartite graphs as generic
 - #33365 missing interface for nauty-genbg (generating bipartite graphs with given bipartition)
 - #33366 `BipartiteGraph()` fails to create graph from `graph6` string
+- #33387 `BipartiteGraph.reduced_adjacency_matrix`: accept keyword arguments for matrix constructor

 **Fixed issues**
 - #8329 copy
dcoudert commented 2 years ago

Description changed:

--- 
+++ 
@@ -17,13 +17,9 @@
 **Open tickets**
 - #8744 Improve add_edge in `BipartiteGraph` to make it independent from the current coloring
 - #33246 `canonical_label` returns incorrect partite sets
-- #33249 `BipartiteGraph()` silently ignores given 'partition' argument
 - #33255 equal hashes for non-isomorphic bipartite graphs with edge labels
-- #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
 - #33365 missing interface for nauty-genbg (generating bipartite graphs with given bipartition)
 - #33366 `BipartiteGraph()` fails to create graph from `graph6` string
-- #33387 `BipartiteGraph.reduced_adjacency_matrix`: accept keyword arguments for matrix constructor

 **Fixed issues**
 - #8329 copy
@@ -47,6 +43,10 @@
 - #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`)
+- #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
+- #33387 `BipartiteGraph.reduced_adjacency_matrix`: accept keyword arguments for matrix constructor

 **Considered invalid or duplicate**
 - #8350 `BipartiteGraph` override `add_vertex()` and `add_vertices()`
enjeck commented 2 years ago

Description changed:

--- 
+++ 
@@ -16,10 +16,8 @@

 **Open tickets**
 - #8744 Improve add_edge in `BipartiteGraph` to make it independent from the current coloring
-- #33246 `canonical_label` returns incorrect partite sets
 - #33255 equal hashes for non-isomorphic bipartite graphs with edge labels
 - #33365 missing interface for nauty-genbg (generating bipartite graphs with given bipartition)
-- #33366 `BipartiteGraph()` fails to create graph from `graph6` string

 **Fixed issues**
 - #8329 copy
@@ -43,9 +41,11 @@
 - #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**
maxale commented 1 week ago

Just added #38618