Lines Matching refs:Tarjan
37 //------------------------------Tarjan-----------------------------------------
39 struct Tarjan {
44 Tarjan *_parent; // Parent in DFS
45 Tarjan *_label; // Used for LINK and EVAL
46 Tarjan *_ancestor; // Used for LINK and EVAL
47 Tarjan *_child; // Used for faster LINK and EVAL
48 Tarjan *_dom; // Parent in dominator tree (immediate dom)
49 Tarjan *_bucket; // Set of vertices with given semidominator
51 Tarjan *_dom_child; // Child in dominator tree
52 Tarjan *_dom_next; // Next in dominator tree
56 Tarjan *EVAL(void);
57 void LINK( Tarjan *w, Tarjan *tarjan0 );
65 // constructed. This is the Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
71 // Setup mappings from my Graph to Tarjan's stuff and back
72 // Note: Tarjan uses 1-based arrays
73 Tarjan *tarjan = NEW_RESOURCE_ARRAY(Tarjan,_num_blocks+1);
75 // Tarjan's algorithm, almost verbatim:
89 // and hack the Tarjan algorithm below to be robust in the presence of
98 // Tarjan is using 1-based arrays, so these are some initialize flags
104 Tarjan *w = &tarjan[i]; // Get vertex from DFS
110 Tarjan *vx = &tarjan[b->_pre_order];
111 Tarjan *u = vx->EVAL();
126 for( Tarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {
127 Tarjan *u = vx->EVAL();
134 Tarjan *w = &tarjan[i];
140 Tarjan *w = &tarjan[_broot->_pre_order];
145 for( i=1; i<=_num_blocks;i++){// For all Tarjan vertices
146 Tarjan *t = &tarjan[i]; // Handy access
147 Tarjan *tdom = t->_dom; // Handy access to immediate dominator
170 Tarjan *_tarjan;
173 Block_Stack(Tarjan *tarjan, int size) : _tarjan(tarjan) {
179 Tarjan *t = &_tarjan[pre_order]; // Fast local access
264 uint PhaseCFG::DFS( Tarjan *tarjan ) {
295 void Tarjan::COMPRESS()
307 Tarjan *Tarjan::EVAL() {
314 void Tarjan::LINK( Tarjan *w, Tarjan *tarjan0 ) {
315 Tarjan *s = w;
328 Tarjan *tmp = s; s = _child; _child = tmp;
337 void Tarjan::setdepth( uint stack_size ) {
338 Tarjan **top = NEW_RESOURCE_ARRAY(Tarjan*, stack_size);
339 Tarjan **next = top;
340 Tarjan **last;
350 Tarjan *t = *next; // next tarjan from stack
354 Tarjan *dom_child = t->_dom_child;
403 // Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
406 // Setup mappings from my Graph to Tarjan's stuff and back
407 // Note: Tarjan uses 1-based arrays
418 // Tarjan's algorithm, almost verbatim:
423 // Tarjan is using 1-based arrays, so these are some initialize flags
496 for( i=1; i<dfsnum; i++ ) { // For all Tarjan vertices