Opened 3 years ago

Closed 3 years ago

#25994 closed defect (fixed)

Blocks_and_cut_vertices - bug with directed graphs and Boost interface

Reported by: meghanamreddy Owned by:
Priority: minor Milestone: sage-8.4
Component: graph theory Keywords: connectivity, biconnected components, boost, bc tree, gsoc2018
Cc: dcoudert, dimpase Merged in:
Authors: Meghana M Reddy Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 7c76517 (Commits, GitHub, GitLab) Commit: 7c7651780e24db88d8a8be7063b9775e10f52d5e
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (6)

comment:1 Changed 3 years ago by meghanamreddy

  • Branch set to u/meghanamreddy/25994_boost_interface

comment:2 Changed 3 years ago by git

  • Commit set to 7c7651780e24db88d8a8be7063b9775e10f52d5e

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

​7c76517Fixed the bug and added an example related to the bug.

comment:3 Changed 3 years ago by dcoudert

  • Reviewers set to David Coudert

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

comment:4 Changed 3 years ago by meghanamreddy

  • Status changed from new to needs_review

comment:5 Changed 3 years ago by dcoudert

  • Status changed from needs_review to positive_review

LGTM.

comment:6 Changed 3 years ago by vbraun

  • Branch changed from u/meghanamreddy/25994_boost_interface to 7c7651780e24db88d8a8be7063b9775e10f52d5e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.