#8350 closed defect (duplicate)
BipartiteGraph override add_vertex() and add_vertices()
Reported by: | rhinton | Owned by: | rhinton |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | graph theory | Keywords: | BipartiteGraph |
Cc: | rlm, jason | Merged in: | |
Authors: | Ryan Hinton | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
BipartiteGraph? needs to override add_vertex() and add_vertices() to properly partition the vertices.
sage: bg = BipartiteGraph() sage: bg.add_vertex('a') # this vertex should go left or right sage: (bg.left, bg.right) # one of these should contain vertex 'a' ([], [])
Change History (7)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
Forgot to add pointer to mega-ticket #1941.
comment:3 Changed 11 years ago by
I'm not sure part (2) above is good. For example, someone takes their BipartiteGraph bg
, calls graph.is_circular_planar()
(this is one of the currently failing doctests) and gets back a !Graph with exactly the same vertex and edge sets -- but no longer a BipartiteGraph?.
The obvious alternative is to raise an exception when given insufficient information. This means any !Graph algorithms -- like the one in is_circular_planar
may fail when applied to BipartiteGraphs. So the !Graph class will be gradually littered with tests of the object's class like it is now for self._directed
.
At what point is it better to subsume BipartiteGraph as an attribute of !Graph -- like ._directed
? Or should BipartiteGraph not inherit from !Graph at all to avoid this problem?
comment:4 follow-up: ↓ 5 Changed 11 years ago by
rhinton: you bring up a very good point about the organization of the graph classes.
The main point behind the bipartite graph class is that it is represented more efficiently than the normal graphs are, right? That's a storage layer question, which seems like it should be a lower-level thing than the algorithm layer. Maybe in the long run, it would be better to create a backend for bipartite graphs (like the cgraph backend, or the networkx backend).
Since algorithms should only call functions that are in the public interface of the backend, algorithms should just work. We might have to augment the public interface between backends and the graph theory code to handle the extra arguments (like in add_vertex) for different backends, though.
comment:5 in reply to: ↑ 4 Changed 11 years ago by
jason: thanks for the reply, see also my sage-devel post that I was finishing as you posted here. :-)
Replying to jason:
...snip... The main point behind the bipartite graph class is that it is represented more efficiently than the normal graphs are, right? That's a storage layer question, which seems like it should be a lower-level thing than the algorithm layer. Maybe in the long run, it would be better to create a backend for bipartite graphs (like the cgraph backend, or the networkx backend).
No, it's not an issue of efficiency. BipartiteGraph subclasses from Graph and so inherits most of its functionality that way. *Additionally*, the .left and .right attributes indicate the vertex partition. Most of the problems come from adding vertices without specifying a partition (e.g. GenericGraph?.is_circular_planar()), removing vertices without updating the partition (old delete_vertex, see #8330), or assuming everything is either a Graph or DiGraph? (e.g. GenericGraph?.union()).
Since algorithms should only call functions that are in the public interface of the backend, algorithms should just work. We might have to augment the public interface between backends and the graph theory code to handle the extra arguments (like in add_vertex) for different backends, though.
Yes, to a point. Since all Python methods are "virtual", overriding a few methods like delete_vertex and add_vertex will work for many cases. You're right, though, some of the Graph and GenericGraph? code will need to be aware of the BipartiteGraph? case. Or I gave some other options in the sage-devel post. :-)
Thanks! -Ryan
comment:6 Changed 11 years ago by
- Resolution set to duplicate
- Status changed from new to closed
merged with #8330
comment:7 Changed 11 years ago by
- Milestone changed from sage-4.3.4 to sage-duplicate/invalid/wontfix
How about this solution:
1(a). To properly add a vertex to a BipartiteGraph? object, specify keyword left or right as True.
1(b). add_vertices() can use a list for left or right (default right to None). We could also allow left/right to be a single boolean and apply that to every element in the list.