PreviousUpNext

15.4.786  src/lib/graph/revgraph.pkg

#
#  The transpose of a graph
#
#  -- Allen Leung

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

stipulate
    package odg =  oop_digraph;                                         # oop_digraph   is from   src/lib/graph/oop-digraph.pkg
herein
    api Reversed_Graph_View {
        #
        rev_view:  odg::Digraph(N,E,G) -> odg::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.
    };
end;


stipulate
    package odg =  oop_digraph;                                         # oop_digraph   is from   src/lib/graph/oop-digraph.pkg
herein
    package   reversed_graph_view
    : (weak)  Reversed_Graph_View                                       # Reversed_Graph_View   is from   src/lib/graph/revgraph.pkg
    {
        fun rev_view (odg::DIGRAPH graph)
            =
            {   fun swap  f (i, j, e) =  f (j, i, e);
                fun swap' f (i, j)    =  f (j, i);
                fun swap'' (i, j, e)  =  (j, i, e);

                fun flip es
                    =
                    map' es (fn (i, j, e) = (j, i, e));

                odg::DIGRAPH
                  {
                    name            => graph.name,
                    graph_info      => graph.graph_info,
                    allot_node_id   => graph.allot_node_id,
                    add_node        => graph.add_node,
                    add_edge        => swap graph.add_edge,
                    remove_node     => graph.remove_node,
                    set_in_edges    => fn (j, es) = graph.set_out_edges (j, flip es),
                    set_out_edges   => fn (i, es) = graph.set_in_edges (i, flip es),
                    set_entries     => graph.set_exits,
                    set_exits       => graph.set_entries,
                    garbage_collect => graph.garbage_collect,
                    nodes           => graph.nodes,
                    edges           => .{ map swap'' (graph.edges ()); },
                    order           => graph.order,
                    size            => graph.size,
                    capacity        => graph.capacity,
                    out_edges       => fn i = map swap'' (graph.in_edges i),
                    in_edges        => fn i = map swap'' (graph.out_edges i),
                    next            => graph.prior,
                    prior            => graph.next,
                    has_edge        => swap' graph.has_edge,
                    has_node        => graph.has_node,
                    node_info       => graph.node_info,
                    entries         => graph.exits,
                    exits           => graph.entries,
                    entry_edges     => graph.exit_edges,
                    exit_edges      => graph.entry_edges,
                    forall_nodes    => graph.forall_nodes,
                    forall_edges    => fn f = graph.forall_edges (swap f)

              #      fold_nodes      => graph.fold_nodes,
              #      fold_edges      => fn f = fn u = graph.fold_edges (fn ((i, j, e), l) = f((j, i, e), l)) u
                  };
            };
    };
end;


Comments and suggestions to: bugs@mythryl.org

PreviousUpNext