Opened 9 years ago

Closed 9 years ago

#7671 closed enhancement (fixed)

strongly_connected_components in c_graphs

Reported by: ncohen Owned by: rlm
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:

Description (last modified by ncohen)

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 ncohen 9 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:3 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

Done here, with small other things :-)

Nathann

comment:4 Changed 9 years ago by rlm

Typo: "conaitning"

comment:5 Changed 9 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

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

Changed 9 years ago by ncohen

comment:6 Changed 9 years ago by ncohen

Done !

comment:7 Changed 9 years ago by mvngu

  • Merged in set to sage-4.3.4.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.