Opened 3 years ago

Closed 3 years ago

# Cycle_basis giving wrong results in case of multiedges()

Reported by: Owned by: gh-rajat1433 gh-rajat1433 major sage-8.8 graph theory cycle dcoudert Abhay Pratap Singh David Coudert, Rajat Mittal N/A 5928a72 5928a728f6f5ff437f01aa383db55e64c6127841

### Description

```sage: G = Graph([(1,2),(2,3),(2,3),(3,4),(1,4),(1,4),(4,5),(5,6),(4,6),(6,7)],multiedges=True)

sage: G.cycle_basis()

getting

[[1, 4], [1, 4]]

```

It should be

```[[5, 6, 4], [2, 3, 4, 1]]
```

### comment:1 Changed 3 years ago by gh-rajat1433

• Owner changed from (none) to gh-rajat1433

I think this discrepency is due to the is_forest function which in turn is calling is_tree function and in it following lines of code is written to return the found cycle:

```            if self.has_multiple_edges():
if output == 'vertex':
return (False, list(self.multiple_edges(sort=True)[0][:2]))
edge1, edge2 = self.multiple_edges(sort=True)[:2]
if edge1[0] != edge2[0]:
return (False, [edge1, edge2])
return (False, [edge1, (edge2[1], edge2[0], edge2[2])])
```

### comment:2 Changed 3 years ago by gh-rajat1433

Problem is due to

```sage: G = Graph([(1,2),(2,3),(2,3),(3,4),(1,4),(1,4),(4,5),(5,6),(4,6),(6,7)],multiedges=True)

sage: w=G.subgraph(edges=[(1,4,None)])
sage: w
Subgraph of (): Multi-graph on 7 vertices
sage: w.edges()
[(1, 4, None), (1, 4, None)]

```

Subgraph is returning with multiple edges instead it should have an edge 1 time(maybe).

Also I am not sure of the definition should the answer for this graph be

```[[5, 6, 4], [2, 3, 4, 1]]
```

OR

```[[5, 6, 4], [2, 3, 4, 1],[1,4],[2,3]]
```
Last edited 3 years ago by gh-rajat1433 (previous) (diff)

### comment:3 follow-up: ↓ 4 Changed 3 years ago by dcoudert

Graphs should be simple and unweighted :P

Concerning `.subgraph`, the result you get is what is documented

```        - ``vertices`` -- a single vertex or an iterable container of vertices,
e.g. a list, set, graph, file or numeric array. If not passed (i.e.,
``None``), defaults to the entire graph.

- ``edges`` -- as with ``vertices``, edges can be a single edge or an
iterable container of edges (e.g., a list, set, file, numeric array,
etc.). By default (``edges=None``), all edges are assumed and the
returned graph is an induced subgraph. In the case of multiple edges,
specifying an edge as `(u,v)` means to keep all edges `(u,v)`,
regardless of the label.
```

There is a mistake in the documentation. It is documented that `output` can be `'vertex'` or `'edges'`, but

```sage: G.cycle_basis(output='edges')
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-19-c82db06774e5> in <module>()
----> 1 G.cycle_basis(output='edges')

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in cycle_basis(self, output)
4556         """
4557         if not output in ['vertex', 'edge']:
-> 4558             raise ValueError('output must be either vertex or edge')
4559
4560         if self.allows_multiple_edges():

ValueError: output must be either vertex or edge
sage: G.cycle_basis(output='edge')
[[(1, 4, None), (4, 1, None)], [(1, 4, None), (4, 1, None)]]
```

I don't know how to fix the issue.

### comment:4 in reply to: ↑ 3 Changed 3 years ago by gh-rajat1433

Graphs should be simple and unweighted :P

but in the examples of cycle_basis following is given: here G is non simple

```For undirected graphs with multiple edges:

sage: G = Graph([(0, 2, 'a'), (0, 2, 'b'), (0, 1, 'c'), (1, 2, 'd')], multiedges=True)
sage: G.cycle_basis()
[[0, 2], [2, 1, 0]]
sage: G.cycle_basis(output='edge')
[[(0, 2, 'a'), (2, 0, 'b')], [(2, 1, 'd'), (1, 0, 'c'), (0, 2, 'a')]]

```

### comment:5 Changed 3 years ago by dcoudert

It was a joke. Our life would be much easier without multiedges...

### comment:6 Changed 3 years ago by gh-rajat1433

Haha it really would be...

### comment:7 Changed 3 years ago by gh-abhayptp

It will work fine if instead of this line in cycle_basis()

```return [self.subgraph(edges=T + [e]).is_forest(certificate=True,
output=output)[1]
for e in self.edge_iterator() if not e in T]
```

we use

```return [Graph(edges=T + [e]).is_forest(certificate=True,
output=output)[1]
for e in self.edge_iterator() if not e in T]
```

Since self.subgraph(e) includes multiple existing copies of e as mentioned above in comment and, if two copies of e = (x,y) are in graph and suppose e got included in T, then there is a cycle including (x,y) always in subgraph(T+[e]), which is returned. So, to avoid that we should use the above method. But it will require extra overhead of creating Graph multiple times, maybe we can use this method only when G has parameter multiedges=True.

Last edited 3 years ago by gh-abhayptp (previous) (diff)

### comment:8 Changed 3 years ago by gh-abhayptp

For, example this works right.

```sage: G = Graph([(1,2),(2,3),(2,3),(3,4),(1,4),(1,4),(4,5),(5,6),(4,6),(6,7)],multiedges=True)
sage: T = G.min_spanning_tree()
sage: [Graph(T + [e],  multiedges=True).is_forest(certificate=True, output='vertex')[1] for e in G.edge_iterator() if not e in T]
[[4, 3, 2, 1], [6, 5, 4]]

```

Though, it will not return some cycle of length 2(resulting from multiple edges between two vertices) when multiple edges e gets included in T because 'if not e in T' evaluates to False then.

### comment:9 Changed 3 years ago by gh-rajat1433

I think the answer should be

```[[5, 6, 4], [2, 3, 4, 1],[1,4],[2,3]]
```

according to definition of cycle_basis. https://en.wikipedia.org/wiki/Cycle_basis

### comment:10 Changed 3 years ago by gh-abhayptp

Yes. I think it fixes this.

```sage: G = Graph([(1,2),(2,3),(2,3),(3,4),(1,4),(1,4),(4,5),(5,6),(4,6),(6,7)],multiedges=True)
sage: T = G.min_spanning_tree()
sage: H = G.copy()
sage: H.delete_edges(T)
sage: [Graph(T + [e],  multiedges=True).is_forest(certificate=True, output='vertex')[1] for e in H.edge_iterator()]
[[1, 4], [2, 3], [4, 3, 2, 1], [6, 5, 4]]
```

### comment:11 Changed 3 years ago by gh-abhayptp

I have sent diff #27563 for it by mistake instead of sending diff on this ticket. Please review it.
I have imported Graph from sage.graphs.graph in cycle_basis() function to create instance of Graph.

Last edited 3 years ago by gh-abhayptp (previous) (diff)

### comment:12 Changed 3 years ago by dcoudert

I suggest to move the branch from #27563 to this ticket and mark #27563 as duplicate. The motivation for that is that the discussion is in this ticket.

• instead of calling `is_forest`, you should call `is_tree`. Indeed, at this point of the code, you know that the graph is connected, so there is no need to check that again in `is_forest`. Actually, method `is_tree` will also check if the graph is connected.
• align `output=output` below `certificate=True`
• add a doctest with the example of this ticket

### comment:13 Changed 3 years ago by gh-rajat1433

@gh-abhayptp can you make the requested changes, then we can move that branch to here. If you require any help let me know.

### comment:14 Changed 3 years ago by gh-abhayptp

• Branch set to u/gh-abhayptp/cycle_basis_giving_wrong_results_in_case_of_multiedges__

### comment:15 Changed 3 years ago by gh-abhayptp

• Commit set to 1a68ce1d896929e27b7dbd2a99dee810bc318dda

There were some extra whitespaces at 4 places in the file which have also been removed. My editor automatically did that :p
I can undo that change if anyone wants.

New commits:

 ​b2c82ec `Fixes cycle basis for multiedges` ​1a68ce1 `Add doctests`
Last edited 3 years ago by gh-abhayptp (previous) (diff)

### comment:16 Changed 3 years ago by dcoudert

• Authors Rajat Mittal deleted
• Reviewers changed from David Coudert to David Coudert, Rajat Mittal

@Rajat: I move your name in the reviewers field. So please double check the proposed solution ;) It passes all tests on my computer.

### comment:17 Changed 3 years ago by gh-abhayptp

• Authors set to Abhay Pratap Singh

### comment:18 Changed 3 years ago by gh-rajat1433

In sage we follow pep8 style: https://www.python.org/dev/peps/pep-0008/

```-            sage: H = Graph([(1,2),(2,3),(2,3),(3,4),(1,4),(1,4),(4,5),(5,6),(4,6),(6,7)],multiedges=True)
-            sage: H.cycle_basis()
-            [[1, 4], [2, 3], [4, 3, 2, 1], [6, 5, 4]]
+            sage: H = Graph([(1, 2), (2, 3), (2, 3), (3, 4), (1, 4), (1, 4), (4, 5), (5, 6), (4, 6), (6, 7)], multiedges=True)
+            sage: H.cycle_basis()
+            [[1, 4], [2, 3], [4, 3, 2, 1], [6, 5, 4]]
```

Also you can add a Wikipedia reference explaining cycle_basis just after its definition

```+        See the :wikipedia:`Cycle_basis` for more information.
```

### comment:19 Changed 3 years ago by git

• Commit changed from 1a68ce1d896929e27b7dbd2a99dee810bc318dda to bcc34f96705c6fe06da61bb4a4d21c59f99e87c2

Branch pushed to git repo; I updated commit sha1. New commits:

 ​bcc34f9 `Make code pep8 compliant`

### comment:21 Changed 3 years ago by gh-rajat1433

```            return [Graph(T + [e], multiedges=True).is_tree(certificate=True,
output=output)[1]
for e in H.edge_iterator()]
```

instead of creating a new graph again and again you can create a single graph from T and then you may add and delete edge e in H.edge_iterator to that graph.

### comment:22 Changed 3 years ago by dcoudert

That's right, you can do something like:

```from sage.graphs.graph import Graph
T = Graph(self.min_spanning_tree(), multiedges=True, format='list_of_edges')
H = self.copy()
H.delete_edges(T.edge_iterator())
L = []
for e in H.edge_iterator():
L.append(T.is_tree(certificate=True, output=output)[1])
T.delete_edge(e)
return L
```

### comment:23 Changed 3 years ago by git

• Commit changed from bcc34f96705c6fe06da61bb4a4d21c59f99e87c2 to adaa2b9fa5885c20e3a31b205fa014174ce2611c

Branch pushed to git repo; I updated commit sha1. New commits:

 ​adaa2b9 `Better implementation`

### comment:24 Changed 3 years ago by gh-rajat1433

Note that T is a list. So you can't use add_edge in that. You need to construct a graph from T first

```T = Graph(self.min_spanning_tree(), multiedges=True, format='list_of_edges')
```

### comment:25 Changed 3 years ago by git

• Commit changed from adaa2b9fa5885c20e3a31b205fa014174ce2611c to 2a80f15e77c93f7bb9cd63fd9bff31ba23051f82

Branch pushed to git repo; I updated commit sha1. New commits:

 ​2a80f15 `Better implementation-2`

### comment:26 Changed 3 years ago by gh-abhayptp

Yeah. I missed that. I don't get why tests went silent. Maybe, I didn't do ./sage -br?

### comment:27 Changed 3 years ago by dcoudert

I usually do `./sage -btp --long src/sage/graphs/generic_graph.py`.

For me this patch is now good to go. Thanks.

@Rajat: if you have no further comments, you can set the ticket to positive review.

### comment:28 Changed 3 years ago by gh-rajat1433

A few improvements:

• Note that Networkx implementation of cycle_basis also does not work for directed graphs so we can check that at the start of the code and return the appropriate error there only.
• A small grammatical error ;)
```-        a dictionary associating an unique vector to each undirected edge::
+        a dictionary associating a unique vector to each undirected edge::
```
• Since the copy parameter of Networkx graph has been deprecated(ticket:27491) you may remove it:
```-        cycle_basis_v = networkx.cycle_basis(self.networkx_graph(copy=False))
+        cycle_basis_v = networkx.cycle_basis(self.networkx_graph())
```

### comment:29 Changed 3 years ago by git

• Commit changed from 2a80f15e77c93f7bb9cd63fd9bff31ba23051f82 to 5956849f9fe9121a63a1936136afd51245bd22f6

Branch pushed to git repo; I updated commit sha1. New commits:

 ​5956849 `Minor changes`

### comment:30 Changed 3 years ago by gh-rajat1433

Just last one 🙂

You may consider adding a test mentioning this ticket:

```+        TESTS:
+
+        :trac:`27538`::
+
+            sage: G= Graph([(1, 2, 'a'),(2, 3, 'b'),(2, 3, 'c'),(3, 4, 'd'),(3, 4, 'e'),(4, 1, 'f')], multiedges=True)
+            sage: G.cycle_basis()
+            [[2, 3], [4, 3, 2, 1], [4, 3, 2, 1]]
+            sage: G.cycle_basis(output='edge')
+            [[(2, 3, 'b'), (3, 2, 'c')],
+             [(4, 3, 'd'), (3, 2, 'b'), (2, 1, 'a'), (1, 4, 'f')],
+             [(4, 3, 'e'), (3, 2, 'b'), (2, 1, 'a'), (1, 4, 'f')]]
```

### comment:31 Changed 3 years ago by git

• Commit changed from 5956849f9fe9121a63a1936136afd51245bd22f6 to efb6b0caec3a7340759526decb1443aaa51561a5

Branch pushed to git repo; I updated commit sha1. New commits:

 ​efb6b0c `Minor changes-2`

### comment:32 Changed 3 years ago by gh-rajat1433

add a line after the definition of cycle_basis:

```-        See the :wikipedia:`Cycle_basis` for more information.
+
```

Notice the changes:

```-            sage: G = DiGraph([(0, 2, 'a'), (0, 1, 'c'), (1, 2, 'd')], multiedges=True)
+            sage: G = DiGraph([(0, 2, 'a'), (0, 1, 'b'), (1, 2, 'c')])
```

### comment:33 Changed 3 years ago by git

• Commit changed from efb6b0caec3a7340759526decb1443aaa51561a5 to 5928a728f6f5ff437f01aa383db55e64c6127841

Branch pushed to git repo; I updated commit sha1. New commits:

 ​5928a72 `Minor changes-3`

### comment:34 Changed 3 years ago by dcoudert

• Status changed from new to needs_review

### comment:35 Changed 3 years ago by dcoudert

This patch is very good now. Thanks to both of you.

I'm now waiting for the patchbot, just in case.

### comment:36 Changed 3 years ago by gh-rajat1433

LGTM

@David: if you have no further comments, we can set the ticket to positive review.

### comment:37 Changed 3 years ago by dcoudert

• Status changed from needs_review to positive_review

LGTM.

### comment:38 Changed 3 years ago by vbraun

• Branch changed from u/gh-abhayptp/cycle_basis_giving_wrong_results_in_case_of_multiedges__ to 5928a728f6f5ff437f01aa383db55e64c6127841
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.