graphs_tarjan.h

Go to the documentation of this file.

#ifndef TARJAN_H_
#define TARJAN_H_
 
 /*   ____                 _             _____          _             _      */
 /*  / ___|_ __ __ _ _ __ | |__  ___ _  |_   _|_ _ _ __(_) __ _ _ __ ( )___  */
 /* | |  _| '__/ _` | '_ \| '_ \/ __(_)   | |/ _` | '__| |/ _` | '_ \|// __| */
 /* | |_| | | | (_| | |_) | | | \__ \_    | | (_| | |  | | (_| | | | | \__ \ */
 /*  \____|_|_ \__,_| .__/|_| |_|___(_)   |_|\__,_|_| _/ |\__,_|_| |_| |___/ */
 /*    / \  | | __ _|_|__  _ __(_) |_| |__  _ __ ___ |__/                    */
 /*   / _ \ | |/ _` |/ _ \| '__| | __| '_ \| '_ ` _ \                        */
 /*  / ___ \| | (_| | (_) | |  | | |_| | | | | | | | |                       */
 /* /_/   \_\_|\__, |\___/|_|  |_|\__|_| |_|_| |_| |_|                       */
 /*            |___/                                                         */
 
//#define DEBUG_TARJAN
 
 
#include "type_partitions.h"
#include "graphs.h"
#include <stdbool.h>
 
/***********************/
/* Classical algorithm */
/***********************/

parti* tarjan(graph* g 
);

parti* ltarjan(lgraph* g, 
    bool* alph 
);

parti* dtarjan(dgraph* g, 
    bool* alph, 
    bool ismor      
);
 

parti* dualdtarjan(dgraph* g1, 
    dgraph* g2, 
    bool* alph, 
    bool ismor 
);
 
 
/**************************/
/*+ Computations on SCCS +*/
/**************************/
 

dgraph* dgraph_extract(dgraph* g, 
    parti* P, 
    uint* inv, 
    uint j 
);

void dgraph_compute_alph_scc(dgraph* g, 
    parti* sccs, 
    uint scc, 
    bool* alph 
);
 

bool dgraph_common_alph_loop(dgraph* g, 
    parti* sccs, 
    uint* inv_sccs, 
    uint q1, 
    uint q2, 
    bool* alph 
);
 

void dgraph_discard_nonscc_edges(dgraph* g, 
    parti* sccs 
);

dgraph* dgraph_copy_discard_nonscc_edges(dgraph* g, 
    parti* sccs 
);
 

bool dgraph_ntrivial_loop(dgraph* g, 
    parti* sccs, 
    uint q 
);
 
 
 
#endif // TARJAN_H_