Cycle_basis giving wrong results in case of multiedges()

[gh-rajat1433]

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

[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])])

[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]]

[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.

[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')]]

[dcoudert]

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

[gh-rajat1433]

Haha it really would be...

[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.

[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.

[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

[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]]

[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.

[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

[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.

[gh-abhayptp]

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:

​b2c82ec	Fixes cycle basis for multiedges
​1a68ce1	Add doctests

[dcoudert]

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.

[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.

[git]

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

​bcc34f9

Make code pep8 compliant

[gh-abhayptp]

Reference added and code made pep8 compliant.

[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.

[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

[git]

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

​adaa2b9

Better implementation

[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')

[git]

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

​2a80f15

Better implementation-2

[gh-abhayptp]

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

[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.

[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())
  

[git]

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

​5956849

Minor changes

[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')]]

[git]

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

​efb6b0c

Minor changes-2

[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')])

[git]

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

​5928a72

Minor changes-3

[dcoudert]

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

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

[gh-rajat1433]

LGTM

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

[dcoudert]

LGTM.