15.4.755  src/lib/graph/acyclic-graph.pkg

# acyclic-graph.pkg
#
# Acyclic subgraph adaptor.  This takes a linear order of node id
# return a view in which only the edges (and nodes) consistent with
# the linear order is visible.
#
# -- Allen Leung

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



#                   "It is by the goodness of God that in our country
#                    we have those three unspeakably precious things:
#                    freedom of speech, freedom of conscience, and
#                    the prudence never to practice either."
#
#                                          -- Mark Twain,
#                                             More Tramps Abroad



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

    api Acyclic_Subgraph_View {
        #
        # Acyclic node induced subgraph 
        #
        acyclic_view
            :
            List( odg::Node_Id )
            ->    odg::Digraph(N,E,G)                                           # Here N,E,G represent the types of the client-package-supplied records associated with (respectively) nodes, edges and graphs.
            ->    odg::Digraph(N,E,G);
    };
end;

stipulate
   package odg =  oop_digraph;                                                  # oop_digraph           is from   src/lib/graph/oop-digraph.pkg
   package a   =  sparse_rw_vector;                                             # sparse_rw_vector              is from   src/lib/src/sparse-rw-vector.pkg
   package s   =  subgraph_p_view;                                              # subgraph_p_view               is from   src/lib/graph/subgraph-p.pkg
herein

    package  acyclic_subgraph_view
    : (weak) Acyclic_Subgraph_View                                              # Acyclic_Subgraph_View         is from   src/lib/graph/acyclic-graph.pkg
    {
       fun acyclic_view nodes (graph as odg::DIGRAPH g)
           =
           s::subgraph_p_view nodes node_p edge_p graph
           where
               ord = a::make_rw_vector (g.capacity (),-1);

               fun order (i,[])      =>   ();
                   order (i, n ! ns) =>   {   a::set (ord, n, i);
                                              order (i+1, ns);
                                          };
               end;

               order (0, nodes);

               fun node_p i
                   =
                   a::get (ord, i) >= 0; 

               fun edge_p (i, j)
                   = 
                   {   i = a::get (ord, i);

                       i >= 0 and i < a::get (ord, j);
                   };

           end;
    };

end;