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: |
Description (last modified by )
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.
- add to
__cmp__
to distinguish Bipartite from other graphs - loops - this should always be false for bipartite, right? (other functions with "loops" in the name)
- density - should this reflect "bipartite density"?
- clear - left & right too?
- add left_vertices and right_vertices?
- adjacency_matrix - should this order the vertices a certain way?
- add_cycle
- add_path
- add a function "bipartite_subgraph" to preserve class?
- 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
asBipartiteGraph
- #25985 bipartite graph
project_right()
projects left - #25988 bug in vertex cover for
BipartiteGraph
- #26515 clean
bipartite_graph.py
- #28198 add method
is_bipartite
toBipartiteGraph
- #28897
BipartiteGraph
blindly trusts generic graphs - #31313 memory leak in
bipartite_graph
(and so ingeneralised_quadrangle_with_spread
) - #33246
canonical_label
returns incorrect partite sets - #33249
BipartiteGraph()
silently ignores given 'partition' argument - #33260 Fix bug in
.perfect_matchings()
forBipartiteGraph
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 fromgraph6
string - #33387
BipartiteGraph.reduced_adjacency_matrix
: accept keyword arguments for matrix constructor
Considered invalid or duplicate
Change History (28)
comment:1 Changed 15 years ago by
Milestone: | → sage-2.10.2 |
---|
comment:3 Changed 15 years ago by
Also, the automorphism group/canonical label functions need to be called with the correct partitions.
comment:9 Changed 11 years ago by
Cc: | Lukáš Lánský added |
---|---|
Description: | modified (diff) |
comment:10 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:11 Changed 9 years ago by
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:12 Changed 9 years ago by
Milestone: | sage-6.1 → sage-6.2 |
---|
comment:13 Changed 8 years ago by
Milestone: | sage-6.2 → sage-6.3 |
---|
comment:14 Changed 8 years ago by
Milestone: | sage-6.3 → sage-6.4 |
---|
comment:15 Changed 8 months ago by
Cc: | Max Alekseyev added |
---|---|
Description: | modified (diff) |
Milestone: | sage-6.4 → sage-9.6 |
Summary: | Finish bipartite graph implementation → Meta ticket: Finish bipartite graph implementation |
Type: | defect → task |
Gathering tickets related to BipartiteGraph
, open and fixed issues.
comment:16 Changed 8 months ago by
Description: | modified (diff) |
---|
comment:17 Changed 8 months ago by
Description: | modified (diff) |
---|
comment:18 Changed 8 months ago by
Description: | modified (diff) |
---|
comment:19 follow-up: 20 Changed 8 months ago by
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 usualGraph
).
I tried (for complete, random and random regular bipartite graphs) and it's not an easy task:
- the
__repr__
method ofBipartiteGraph
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 withBipartiteGraph
.
So it's not so easy to do
comment:20 Changed 8 months ago by
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 usualGraph
).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 ofBipartiteGraph
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 withBipartiteGraph
.
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
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
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
Description: | modified (diff) |
---|
comment:24 Changed 7 months ago by
Description: | modified (diff) |
---|
comment:25 Changed 7 months ago by
Description: | modified (diff) |
---|
comment:26 Changed 6 months ago by
Milestone: | sage-9.6 → sage-9.7 |
---|
comment:27 Changed 6 months ago by
Description: | modified (diff) |
---|
comment:28 Changed 5 weeks ago by
Milestone: | sage-9.7 → sage-9.8 |
---|