# Ticket #8350(closed defect: duplicate)

Opened 3 years ago

Reported by: Owned by: rhinton rhinton major sage-duplicate/invalid/wontfix graph theory BipartiteGraph rlm, jason N/A Ryan Hinton

### 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

### comment:1 Changed 3 years ago by rhinton

1(a). To properly add a vertex to a BipartiteGraph? object, specify keyword left or right as True.

```sage: bg = BipartiteGraph()
sage: bg.add_vertex('a', left=True)  # new syntax
sage: bg.left
['a']
```

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.

```sage: bg = BipartiteGraph()
sage: bg.add_vertices(['a', 'b', 'c'], left=[True, False, True])
```
1. With no specific instruction, add_vertex will convert the current BipartiteGraph? back to a Graph. (Is this allowed/possible?)
```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'>
```

### comment:2 Changed 3 years ago by rhinton

Forgot to add pointer to mega-ticket #1941.

### comment:3 Changed 3 years ago by rhinton

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 3 years ago by jason

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 3 years ago by rhinton

jason: thanks for the reply, see also my sage-devel post that I was finishing as you posted here. :-)

...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 3 years ago by rhinton

• Status changed from new to closed
• Resolution set to duplicate

merged with #8330

### comment:7 Changed 3 years ago by mvngu

• Milestone changed from sage-4.3.4 to sage-duplicate/invalid/wontfix
Note: See TracTickets for help on using tickets.