PreviousUpNext

15.4.782  src/lib/graph/oop-digraph.pkg

## oop-digraph.pkg
#
#  A generic directed graph data package.  
#  Implemented in an ``object oriented style''
#
#  All Mythryl compiler backend lowhalf graphs
#  are based on this interface.

#  -- Allen Leung
#
# For a production instantiation of this framework see:
#
#     src/lib/compiler/back/low/mcg/machcode-controlflow-graph-g.pkg

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

# Here we define only an api and a few convenience functions.
# For a full implementation see:
#
#     src/lib/graph/digraph-by-adjacency-list.pkg
#
package   oop_digraph
: (weak)  Oop_Digraph                                   # Oop_Digraph   is from   src/lib/graph/oop-digraph.api
{
    exception BAD_GRAPH  String;
    exception SUBGRAPH;
    exception NOT_FOUND;
    exception UNIMPLEMENTED;
    exception READ_ONLY;     
    exception NOT_SINGLE_ENTRY;
    exception NOT_SINGLE_EXIT;

    fun unimplemented _ = raise exception UNIMPLEMENTED;

    Node_Id = Int; 

    Node(N) = (Node_Id, N);
    Edge(E) = (Node_Id, Node_Id, E);
                                                        # "Digraph" == "Directed_Graph".
    Digraph (N,E,G)                                     # Here N,E,G stand stead for the types of client-package-supplied records associated with (respectively) nodes, edges and graphs.
        =
        DIGRAPH  Graph_Methods(N,E,G)
        withtype
            Graph_Methods (N,E,G)
              =
              { name:             String,
                graph_info:       G,

                # Inserting/removing nodes and edges:
                #
                allot_node_id:    Void -> Node_Id,
                add_node:         Node(N) -> Void,
                add_edge:         Edge(E) -> Void, 
                remove_node:      Node_Id -> Void,
                #
                set_out_edges:    (Node_Id, List(Edge(E))) -> Void,
                set_in_edges:     (Node_Id, List(Edge(E))) -> Void,
                #
                set_entries:      List(Node_Id) -> Void,
                set_exits:        List(Node_Id) -> Void,

                garbage_collect:  Void -> Void,

                nodes:            Void -> List(Node(N)),
                edges:            Void -> List(Edge(E)),
                #
                order:            Void -> Int,
                size:             Void -> Int,
                capacity:         Void -> Int,
                #
                next:             Node_Id -> List( Node_Id ),
                prior:            Node_Id -> List( Node_Id ),
                #
                out_edges:        Node_Id -> List( Edge(E) ),
                in_edges:         Node_Id -> List( Edge(E) ),
                #
                has_edge:        (Node_Id, Node_Id) -> Bool,
                has_node:         Node_Id -> Bool,
                #
                node_info:        Node_Id -> N,
                #
                entries:          Void -> List(Node_Id),
                exits:            Void -> List(Node_Id),
                #
                entry_edges:      Node_Id -> List(Edge(E)),
                exit_edges:       Node_Id -> List(Edge(E)),

                # Iterators:
                # 
                forall_nodes:    (Node(N) -> Void) -> Void,
                forall_edges:    (Edge(E) -> Void) -> Void
              };


    fun remove_all_edges (DIGRAPH graph) (i, j)
        =
        graph.set_out_edges (i, list::filter (\\ (_, k, _) =  k == j) (graph.out_edges i));


    fun remove_all_edges' (DIGRAPH graph) (i, j, p)
        =
        graph.set_out_edges (i, list::filter (\\ (_, k, e) =  k == j and p e) 
                            (graph.out_edges i));


    fun remove_edge (DIGRAPH graph) (i, j)
        =
        graph.set_out_edges (i, filter (graph.out_edges i))
        where
            fun filter [] =>  [];

                filter ((e as (_, k, _)) ! es)
                    => 
                    j == k   ??              es
                             ::   e ! filter es;
            end;
        end;


    fun remove_edge' (DIGRAPH graph) (i, j, p)
        =
        graph.set_out_edges (i, filter (graph.out_edges i))
        where
            fun filter [] => [];

                filter((e as (_, k, e')) ! es)
                    => 
                    if (j == k and p e')             es;
                    else                  e ! filter es;
                    fi;
            end;
        end;

};



Comments and suggestions to: bugs@mythryl.org

PreviousUpNext