Blocks_and_cut_vertices - bug with directed graphs and Boost interface

[meghanamreddy]

While using the Boost interface to compute the blocks and cut vertices, the output is wrong if the input is a directed graph.

sage: from sage.graphs.connectivity import blocks_and_cut_vertices
sage: rings = graphs.CycleGraph(10)
sage: rings.merge_vertices([0, 5])
sage: blocks_and_cut_vertices(rings, algorithm="Tarjan_Boost")
([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0])

sage: from sage.graphs.connectivity import blocks_and_cut_vertices
sage: rings = graphs.CycleGraph(10)
sage: rings.merge_vertices([0, 5])
sage: rings = rings.to_directed()
sage: blocks_and_cut_vertices(rings, algorithm="Tarjan_Boost")
([[0, 1, 4, 2, 3, 6, 7, 8, 9], [0, 6, 9, 7, 8]], [0, 9, 8, 6, 7])

If the input graph is a directed graph, the blocks and cut vertices are computed on the underlying simple graph.

CC: @dcoudert @dimpase

Component: graph theory

Keywords: connectivity, biconnected components, boost, bc tree, gsoc2018

Author: Meghana M Reddy

Branch/Commit: 7c76517

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/25994

[meghanamreddy]

Branch: u/meghanamreddy/25994_boost_interface

[sagetrac-git]

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

7c76517

Fixed the bug and added an example related to the bug.

[sagetrac-git]

Commit: 7c76517

[dcoudert]

comment:3

Is this patch ready for review ? if so, set it to needs review.

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:5

LGTM.

[vbraun]

Changed branch from u/meghanamreddy/25994_boost_interface to 7c76517