#27538 closed defect (fixed)

Cycle_basis giving wrong results in case of multiedges()

Reported by: gh-rajat1433 Owned by: gh-rajat1433
Priority: major Milestone: sage-8.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) 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 14 months 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 14 months 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 14 months ago by gh-rajat1433 (previous) (diff)

comment:3 follow-up: Changed 14 months 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 14 months ago by gh-rajat1433

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 14 months ago by dcoudert

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

comment:6 Changed 14 months ago by gh-rajat1433

Haha it really would be...

comment:7 Changed 14 months 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 14 months ago by gh-abhayptp (previous) (diff)

comment:8 Changed 14 months 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 14 months 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 14 months 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 14 months 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 14 months ago by gh-abhayptp (previous) (diff)

comment:12 Changed 14 months 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.

Some comments on the branch:

  • 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 14 months 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 14 months ago by gh-abhayptp

  • Branch set to u/gh-abhayptp/cycle_basis_giving_wrong_results_in_case_of_multiedges__

comment:15 Changed 14 months ago by gh-abhayptp

  • Commit set to 1a68ce1d896929e27b7dbd2a99dee810bc318dda

Added doctests and made the required changes.
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:

b2c82ecFixes cycle basis for multiedges
1a68ce1Add doctests
Last edited 14 months ago by gh-abhayptp (previous) (diff)

comment:16 Changed 14 months ago by dcoudert

  • Authors Rajat Mittal deleted
  • 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 14 months ago by gh-abhayptp

  • Authors set to Abhay Pratap Singh

comment:18 Changed 14 months 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 14 months ago by git

  • Commit changed from 1a68ce1d896929e27b7dbd2a99dee810bc318dda to bcc34f96705c6fe06da61bb4a4d21c59f99e87c2

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

bcc34f9Make code pep8 compliant

comment:20 Changed 14 months ago by gh-abhayptp

Reference added and code made pep8 compliant.

comment:21 Changed 14 months 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 14 months 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():
    T.add_edge(e)
    L.append(T.is_tree(certificate=True, output=output)[1])
    T.delete_edge(e)
return L

comment:23 Changed 14 months ago by git

  • Commit changed from bcc34f96705c6fe06da61bb4a4d21c59f99e87c2 to adaa2b9fa5885c20e3a31b205fa014174ce2611c

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

adaa2b9Better implementation

comment:24 Changed 14 months 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 14 months ago by git

  • Commit changed from adaa2b9fa5885c20e3a31b205fa014174ce2611c to 2a80f15e77c93f7bb9cd63fd9bff31ba23051f82

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

2a80f15Better implementation-2

comment:26 Changed 14 months 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 14 months 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 14 months 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 14 months ago by git

  • Commit changed from 2a80f15e77c93f7bb9cd63fd9bff31ba23051f82 to 5956849f9fe9121a63a1936136afd51245bd22f6

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

5956849Minor changes

comment:30 Changed 14 months 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 14 months ago by git

  • Commit changed from 5956849f9fe9121a63a1936136afd51245bd22f6 to efb6b0caec3a7340759526decb1443aaa51561a5

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

efb6b0cMinor changes-2

comment:32 Changed 14 months ago by gh-rajat1433

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 14 months ago by git

  • Commit changed from efb6b0caec3a7340759526decb1443aaa51561a5 to 5928a728f6f5ff437f01aa383db55e64c6127841

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

5928a72Minor changes-3

comment:34 Changed 14 months ago by dcoudert

  • Status changed from new to needs_review

comment:35 Changed 14 months 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 14 months ago by gh-rajat1433

LGTM

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

comment:37 Changed 14 months ago by dcoudert

  • Status changed from needs_review to positive_review

LGTM.

comment:38 Changed 14 months 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.