Opened 3 years ago
Closed 3 years ago
#27538 closed defect (fixed)
Cycle_basis giving wrong results in case of multiedges()
Reported by:  ghrajat1433  Owned by:  ghrajat1433 

Priority:  major  Milestone:  sage8.8 
Component:  graph theory  Keywords:  cycle 
Cc:  dcoudert  Merged in:  
Authors:  Abhay Pratap Singh  Reviewers:  David Coudert, Rajat Mittal 
Report Upstream:  N/A  Work issues:  
Branch:  5928a72 (Commits, GitHub, GitLab)  Commit:  5928a728f6f5ff437f01aa383db55e64c6127841 
Dependencies:  Stopgaps: 
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]]
Change History (38)
comment:1 Changed 3 years ago by
 Owner changed from (none) to ghrajat1433
comment:2 Changed 3 years ago by
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 (): Multigraph 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]]
comment:3 followup: ↓ 4 Changed 3 years ago by
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) <ipythoninput19c82db06774e5> in <module>() > 1 G.cycle_basis(output='edges') /Users/dcoudert/sage/local/lib/python2.7/sitepackages/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
Replying to dcoudert:
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
It was a joke. Our life would be much easier without multiedges...
comment:6 Changed 3 years ago by
Haha it really would be...
comment:7 Changed 3 years ago by
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.
comment:8 Changed 3 years ago by
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
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
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
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.
comment:12 Changed 3 years ago by
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.
Some comments on the branch:
 instead of calling
is_forest
, you should callis_tree
. Indeed, at this point of the code, you know that the graph is connected, so there is no need to check that again inis_forest
. Actually, methodis_tree
will also check if the graph is connected.  align
output=output
belowcertificate=True
 add a doctest with the example of this ticket
comment:13 Changed 3 years ago by
@ghabhayptp 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
 Branch set to u/ghabhayptp/cycle_basis_giving_wrong_results_in_case_of_multiedges__
comment:15 Changed 3 years ago by
 Commit set to 1a68ce1d896929e27b7dbd2a99dee810bc318dda
comment:16 Changed 3 years ago by
 Reviewers changed from David Coudert to David Coudert, Rajat Mittal
Please add your real name in the Author field.
@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
comment:18 Changed 3 years ago by
In sage we follow pep8 style: https://www.python.org/dev/peps/pep0008/
 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
 Commit changed from 1a68ce1d896929e27b7dbd2a99dee810bc318dda to bcc34f96705c6fe06da61bb4a4d21c59f99e87c2
Branch pushed to git repo; I updated commit sha1. New commits:
bcc34f9  Make code pep8 compliant

comment:20 Changed 3 years ago by
Reference added and code made pep8 compliant.
comment:21 Changed 3 years ago by
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
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(): T.add_edge(e) L.append(T.is_tree(certificate=True, output=output)[1]) T.delete_edge(e) return L
comment:23 Changed 3 years ago by
 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
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
 Commit changed from adaa2b9fa5885c20e3a31b205fa014174ce2611c to 2a80f15e77c93f7bb9cd63fd9bff31ba23051f82
Branch pushed to git repo; I updated commit sha1. New commits:
2a80f15  Better implementation2

comment:26 Changed 3 years ago by
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
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
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
 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
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
 Commit changed from 5956849f9fe9121a63a1936136afd51245bd22f6 to efb6b0caec3a7340759526decb1443aaa51561a5
Branch pushed to git repo; I updated commit sha1. New commits:
efb6b0c  Minor changes2

comment:32 Changed 3 years ago by
add a line after the definition of cycle_basis:
 See the :wikipedia:`Cycle_basis` for more information. + + 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
 Commit changed from efb6b0caec3a7340759526decb1443aaa51561a5 to 5928a728f6f5ff437f01aa383db55e64c6127841
Branch pushed to git repo; I updated commit sha1. New commits:
5928a72  Minor changes3

comment:34 Changed 3 years ago by
 Status changed from new to needs_review
comment:35 Changed 3 years ago by
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
LGTM
@David: if you have no further comments, we can set the ticket to positive review.
comment:38 Changed 3 years ago by
 Branch changed from u/ghabhayptp/cycle_basis_giving_wrong_results_in_case_of_multiedges__ to 5928a728f6f5ff437f01aa383db55e64c6127841
 Resolution set to fixed
 Status changed from positive_review to closed
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: