Sage: Ticket #8350: BipartiteGraph override add_vertex() and add_vertices()
https://trac.sagemath.org/ticket/8350
<p>
<a class="missing wiki">BipartiteGraph?</a> needs to override add_vertex() and add_vertices() to properly partition the vertices.
</p>
<pre class="wiki">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'
([], [])
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/8350
Trac 1.1.6rhintonWed, 24 Feb 2010 18:13:32 GMT
https://trac.sagemath.org/ticket/8350#comment:1
https://trac.sagemath.org/ticket/8350#comment:1
<p>
How about this solution:
</p>
<p>
1(a). To properly add a vertex to a <a class="missing wiki">BipartiteGraph?</a> object, specify keyword left or right as True.
</p>
<pre class="wiki">sage: bg = BipartiteGraph()
sage: bg.add_vertex('a', left=True) # new syntax
sage: bg.left
['a']
</pre><p>
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.
</p>
<pre class="wiki">sage: bg = BipartiteGraph()
sage: bg.add_vertices(['a', 'b', 'c'], left=[True, False, True])
</pre><ol start="2"><li> With no specific instruction, add_vertex will convert the current <a class="missing wiki">BipartiteGraph?</a> back to a Graph. (Is this allowed/possible?)
<pre class="wiki">sage: g = BipartiteGraph()
sage: g.add_vertex('a') # no left/right specified, so revert to a Graph
sage: g
Graph on 1 vertex
sage: type(g)
<class 'sage.graphs.graph.Graph'>
</pre></li></ol>
TicketrhintonWed, 24 Feb 2010 18:15:08 GMT
https://trac.sagemath.org/ticket/8350#comment:2
https://trac.sagemath.org/ticket/8350#comment:2
<p>
Forgot to add pointer to mega-ticket <a class="new ticket" href="https://trac.sagemath.org/ticket/1941" title="defect: Finish bipartite graph implementation (new)">#1941</a>.
</p>
TicketrhintonFri, 26 Feb 2010 15:50:17 GMT
https://trac.sagemath.org/ticket/8350#comment:3
https://trac.sagemath.org/ticket/8350#comment:3
<p>
I'm not sure part (2) above is good. For example, someone takes their BipartiteGraph <code>bg</code>, calls <code>graph.is_circular_planar()</code> (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 <a class="missing wiki">BipartiteGraph?</a>.
</p>
<p>
The obvious alternative is to raise an exception when given insufficient information. This means any !Graph algorithms -- like the one in <code>is_circular_planar</code> 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 <code>self._directed</code>.
</p>
<p>
At what point is it better to subsume BipartiteGraph as an attribute of !Graph -- like <code>._directed</code>? Or should BipartiteGraph not inherit from !Graph at all to avoid this problem?
</p>
TicketjasonFri, 26 Feb 2010 16:46:22 GMT
https://trac.sagemath.org/ticket/8350#comment:4
https://trac.sagemath.org/ticket/8350#comment:4
<p>
rhinton: you bring up a very good point about the organization of the graph classes.
</p>
<p>
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).
</p>
<p>
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.
</p>
TicketrhintonFri, 26 Feb 2010 17:19:17 GMT
https://trac.sagemath.org/ticket/8350#comment:5
https://trac.sagemath.org/ticket/8350#comment:5
<p>
jason: thanks for the reply, see also my sage-devel post that I was finishing as you posted here. :-)
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8350#comment:4" title="Comment 4">jason</a>:
</p>
<blockquote class="citation">
<p>
...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).
</p>
</blockquote>
<p>
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. <a class="missing wiki">GenericGraph?</a>.is_circular_planar()), removing vertices without updating the partition (old delete_vertex, see <a class="closed ticket" href="https://trac.sagemath.org/ticket/8330" title="defect: BipartiteGraph needs to override methods to add and delete vertices ... (closed: fixed)">#8330</a>), or assuming everything is either a Graph or <a class="missing wiki">DiGraph?</a> (e.g. <a class="missing wiki">GenericGraph?</a>.union()).
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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 <a class="missing wiki">GenericGraph?</a> code will need to be aware of the <a class="missing wiki">BipartiteGraph?</a> case. Or I gave some other options in the sage-devel post. :-)
</p>
<p>
Thanks! -Ryan
</p>
TicketrhintonTue, 02 Mar 2010 02:56:17 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/8350#comment:6
https://trac.sagemath.org/ticket/8350#comment:6
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>duplicate</em>
</li>
</ul>
<p>
merged with <a class="closed ticket" href="https://trac.sagemath.org/ticket/8330" title="defect: BipartiteGraph needs to override methods to add and delete vertices ... (closed: fixed)">#8330</a>
</p>
TicketmvnguTue, 02 Mar 2010 11:11:05 GMTmilestone changed
https://trac.sagemath.org/ticket/8350#comment:7
https://trac.sagemath.org/ticket/8350#comment:7
<ul>
<li><strong>milestone</strong>
changed from <em>sage-4.3.4</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
Ticket