15.4.769  src/lib/graph/graph-is-cyclic.pkg

#
# Tests if a graph is cyclic
#
# -- Allen Leung

# Compiled by:
#     src/lib/graph/graphs.lib


stipulate
    package odg =  oop_digraph;                                         # oop_digraph   is from   src/lib/graph/oop-digraph.pkg
    package bts =  bit_set;                                             # bit_set               is from   src/lib/graph/bit-set.pkg
herein


    package  graph_is_cyclic
    : (weak) Graph_Is_Cyclic                                            # Graph_Is_Cyclic       is from   src/lib/graph/graph-is-cyclic.api
    {
        exception CYCLIC;


        # Cyclic test

        fun is_cyclic (odg::DIGRAPH ggg)
            = 
            {   nnn     =  ggg.capacity (); 
                visited =  bts::create nnn;
                done    =  bts::create nnn;

                fun dfs i
                    =
                    if (bts::mark_and_test (visited, i))
                        #
                        if  (not (bts::contains (done, i)))
                             raise exception CYCLIC;
                        fi;
                    else 
                        dfs_succ (ggg.out_edges i);
                        bts::set (done, i);
                    fi

                also
                fun dfs'(i, _)
                    =
                    dfs i

                also
                fun dfs_succ [] =>   ();

                    dfs_succ((_, j, _) ! es)
                        =>
                        {   dfs j;
                            dfs_succ es;
                        };
                end;

                {   ggg.forall_nodes dfs';
                    FALSE;
                }
                except
                    CYCLIC = TRUE;
            };
    };
end;