Re: modified-- strongly connected components(SCC)?

Hi Amit,

Amit Gupta wrote: 
then maybe I can get a algorithm
O(V'+E),  V' = (V - Count-of-all-objects-of-type-M).

I do not think this will be possible. Tarjan's algorithm must essentially visit all nodes in a component before that component is even detected. The way I see it is that you have two options for determining whether an SCC has more than 1 object of type M:

1) When an SCC has been fully identified all of its members are on the stack and Tarjan's algorithm proceeds to remove them one by one. At this point you can simply count the number of M objects and either report the component as a match or not.

2) You can maintain a separate count array which counts the number of M's seen in the current component. Unfortunately, this can only be updated in the back-propagation phase of the algorithm so I don't think it gives you anything over option 1 above.

In both cases, all vertices must be visited.

In fact, one thing which I'm unclear about: suppose a cycle which has a nested cycle inside it. This is one SCC. Now, suppose the outer cycle has more than 1 M object, but the inner does not. Then, should the algorithm report the inner cycle as a matching SCC or not?

Cheers,

Dave



-Amit

.

Relevant Pages

  • Re: OT : Approximate / fast math libraries ?
    ... some practical work with the algorithm will tell you the real results. ... It costs no more to calculate doubles than singles except ... depends on the hardware implementations inside the processor and the ... cycle I put into it, along with some additional benefit from hardware ...
    (Fedora)
  • Re: Seed7 programming language and big numbers
    ... where a sequence repeats. ... a record-setting loop cycle length (which is why it's killing ... some tests with the Seed7 version of this algorithm. ... I recieved your C program and started to convert it to Seed7. ...
    (comp.programming)
  • Re: 3n+1 problem
    ... Consider the following algorithm: ... For any two numbers i and j you are to determine the maximum cycle length over ... Sample Input ...
    (comp.lang.lisp)
  • Re: Population count in SSE2, again
    ... and is not as fast as the AMD code. ... IA-64 popcnt instruction. ... Obviously one should be able to get close to 1 byte per cycle ... oneself that the algorithm is mathematically sound. ...
    (comp.lang.asm.x86)
  • Re: Reversible permutation?
    ... > I guess with 256 elements the fractions of rings with respect to possible ... > Could it make a good PRNG? ... > I can see there are some short cycles but using an algorithm that expands 32 ... > it would be possible to map them into a bad cycle. ...
    (sci.crypt)