Strongly Connected Components (flexible) (GIT_SCC)

Definition

An instance algorithm of class GIT_SCC<Out,In,It,OutSt,InSt,NSt,Mark> is an implementation of an algorithm that computes the strongly connected components.

Iterator version: There is an iterator version of this algorithm: SCC_It. Usage is similar to that of node iterators without the ability to go backward in the sequence and only a graph is allowed at creation time. Method compnumb() returns the component number of the current node.

Creation

GIT_SCC<Out,In,It,OutSt,InSt,NSt,Mark>	algorithm(OutSt ost, InSt ist, Mark ma, Out oai, It it, In iai);
		creates an instance algorithm of this class bound to the stack st and data accessor ma.

Preconditions:

• Out is an adjacency iterator that iterates over the outgoing edges of a fixed vertex
• In is an adjacency iterator that iterates over the incoming edges of a fixed vertex
• OutSt is stack parameterized with items of type Out
• InSt is stack parameterized with items of type In
• Mark is a data accessor that has access to a boolean value that is associated with each node of the graph

Operations

int

algorithm.state()

returns the internal state.

• NEXT_OUT =first phase,
• NEXT_ORDER =order phase,
• NEXT_IN=second phase,
• NEXT_DONE =algorithm finished

void

algorithm.finish_algo()

executes the algorithm until finished() is true.

bool

algorithm.finished()

returns true if the algorithm is finished.

InSt&

algorithm.in_stack()

gives direct access to the internal stack of incoming adjacency iterators.

In

algorithm.in_current()

returns the current iterator of the internal stack of incoming adjacency iterators.

OutSt&

algorithm.out_stack()

gives direct access to the internal stack of outgoing adjacency iterators.

Out

algorithm.out_current()

returns the current iterator of the internal stack of outgoing adjacency iterators.

itnodetype

algorithm.current_node()

returns the current node.

int

algorithm.compnumb()

returns the component number of the fixed node of the current iterator if current state is NEXT_IN.

()

Performs one iteration of the core loop of the algorithm.

Implementation

Each operation requires constant time. The algorithm has running time ${\cal O}(\hbox{$\vert\,V\,\vert$ }+\hbox{$\vert\,E\,\vert$ })$.