Warshall Algorithm

To construct transitive closure on a graph more efficiently

• Recursive Conditions => We use recursion and have a complexity Θ(n3)
  • new_arc_list(for some intermediary_node)source_node to destination_node = 1 if there is a path from source_node to destination_node where all the intermediary nodes are between(1,.., intermediary_node)
  • new_arc_list(for some intermediary_node) source_node to destination_node = 0 otherwise

    //Copy of the initial graph
   NEW_ARC_LIST =INITIAL_ARC_LIST
   
    //In the copy. Loop through all the mediatory nodes
    for(INTERMEDIARY_NODE = 1,2,...,NUMBER_OF_NODES)
      
        // Loop through each pair of nodes
      
        // Loop through all the source nodes
        for(SOURCE_NODE = 1,2,...,NUMBER_OF_NODES)
            
            // Loop through all the destination nodes
            for(DESTINATION_NODE = 1,2,...,NUMBER_OF_NODES)
                
                // If there is NO arc from source_node to destination_node, 
                // if there is an arc from source_node to intermediary_node and 
                // from intermediary_node to destination_node.
                if(NEW_ARC_LIST[SOURCE_NODE, DESTINATION_NODE].doNotExist())
                    if(NEW_ARC_LIST[SOURCE_NODE,INTERMEDIARY_NODE].isPresent() 
                        and NEW_ARC_LIST[INTERMEDIARY_NODE, DESTINATION_NODE].isPresent())
                        
                        NEW_ARC_LIST.append((SOURCE_NODE, DESTINATION_NODE) or
                            (SOURCE_NODE,INTERMEDIARY_NODE) + (INTERMEDIARY_NODE,DESTINATION_NODE) ) )
    
    return NEW_ARC_LIST