Ticket #2423 (accepted defect)

Opened 11 years ago

Last modified 6 years ago

SCC/topsort_prefix

Reported by: jberry Owned by: gemacke
Priority: low Milestone: 1.2
Version: 1.0 Severity: normal
Keywords: Cc: eldorado-graph@…

Description

The strongly connected components algorithm typically finds one large scc per connected component on the Cray "fancy graph"s (power law). The other scc's are single vertex scc's. The "topsort prefix" and "topsort suffix" algorithms in TopSort?.cpp are designed to find these leading and trailing vertices not involved in any cycle. However, the number of vertices in the (topsort_prefix union topsort_suffix) doesn't match the number of singleton scc's. Any vertex not in a cycle should be a singleton scc and in (topsort_prefix union topsort_suffix).

Change History

comment:1 Changed 11 years ago by jberry

  • bug_group Eldorado deleted

comment:2 Changed 6 years ago by gemacke

  • Version unspecified deleted

Getting rid of unspecified version. Changing to <blank> as the unknown version.

comment:3 Changed 6 years ago by gemacke

  • component Eldorado deleted

comment:4 Changed 6 years ago by gemacke

  • Owner changed from jberry to gemacke
  • Status changed from new to accepted

I'm not sure if this is still a problem. I'm accepting it for now until I have time to look into this further.

comment:5 Changed 6 years ago by gemacke

  • Priority changed from high to low

comment:6 Changed 6 years ago by gemacke

  • Version set to 1.1
  • Milestone set to 1.0

comment:7 Changed 6 years ago by gemacke

  • Version changed from 1.1 to 1.0
  • Milestone changed from 1.0 to 1.1

comment:8 Changed 6 years ago by gemacke

  • Milestone changed from 1.1 to 1.2
Note: See TracTickets for help on using tickets.