Opened 13 years ago

Closed 13 years ago

#7671 closed enhancement (fixed)

strongly_connected_components in c_graphs

Reported by: Nathann Cohen Owned by: Robert Miller
Priority: major Milestone: sage-4.3.4
Component: graph theory Keywords:
Cc: Merged in: sage-4.3.4.alpha0
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Nathann Cohen)

The function strongly_connected_components uses Networkx for the moment. As c_graphs are to become the standard implementation of graphs in Sage, this function should be rewritten in Cython.

This functions should be able to return two types of data :

  • A list of lists : as the function connected_components
  • A digraph whose vertices are [immutable Sets representing a set of vertices defining a strongly connected components] and such that there is an edge between A and B if there is an arc from one vertex of A to one vertex of B.

This because, the graph strongly connected components is acyclic, which is sometimes useful.

Nathann

Attachments (1)

trac_7671.patch (6.0 KB) - added by Nathann Cohen 13 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 13 years ago by Nathann Cohen

Description: modified (diff)

comment:2 Changed 13 years ago by Nathann Cohen

Description: modified (diff)

comment:3 Changed 13 years ago by Nathann Cohen

Status: newneeds_review

Done here, with small other things :-)

Nathann

comment:4 Changed 13 years ago by Robert Miller

Typo: "conaitning"

comment:5 Changed 13 years ago by Robert Miller

Authors: Nathann Cohen
Reviewers: Robert Miller
Status: needs_reviewpositive_review

All tests pass. Works for me, if the typo gets fixed

Changed 13 years ago by Nathann Cohen

Attachment: trac_7671.patch added

comment:6 Changed 13 years ago by Nathann Cohen

Done !

comment:7 Changed 13 years ago by Minh Van Nguyen

Merged in: sage-4.3.4.alpha0
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.