PreviousUpNext

15.4.801  src/lib/graph/undirected-graph-view.pkg

# undirected-graph-view.pkg
#  Undirected graph view.  This makes a graph get undirected.
#
#  -- 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 Undirected_Graph_View {
        #
        undirected_view
           :
           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.
           ->
           odg::Digraph(N,E,G);

    };
end;



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

    package   undirected_graph_view
    : (weak)  Undirected_Graph_View                                     # Undirected_Graph_View is from   src/lib/graph/undirected-graph-view.pkg
    {   

        fun undirected_view (odg::DIGRAPH graph)
            =
            {   fun adjacent_edges i
                    =
                    {   in_edges
                            =
                            map
                                (fn (i, j, e) =  (j, i, e))
                                (graph.in_edges i);

                        out_edges
                            =
                            graph.out_edges i;

                        lms::sort_list_and_drop_duplicates
                            #
                            (fn ((i, j, _), (i', j', _))
                                =
                               if      (i <  i' ) LESS; 
                               else if (i == i')
                                    if (j <  j' ) LESS;
                               else if (j == j' ) EQUAL;
                               else                 GREATER;  fi; fi;
                               else                 GREATER;  fi; fi
                            )
                            (in_edges @ out_edges);
                    };

                fun adjacent_nodes i
                    =
                    {   next  =  graph.next i;
                        prior =  graph.prior i;

                        lms::sort_list_and_drop_duplicates  int::compare  (next @ prior);
                    };

                fun has_edge (i, j)
                    =
                    graph.has_edge (i, j)  or
                    graph.has_edge (j, i);


                odg::DIGRAPH
                  {
                    name            => graph.name,
                    graph_info      => graph.graph_info,
                    allot_node_id   => graph.allot_node_id,
                    add_node        => graph.add_node,
                    add_edge        => graph.add_edge,
                    remove_node     => graph.remove_node,
                    set_in_edges    => graph.set_in_edges,
                    set_out_edges   => graph.set_out_edges,
                    set_entries     => graph.set_exits,
                    set_exits       => graph.set_entries,
                    garbage_collect => graph.garbage_collect,
                    nodes           => graph.nodes,
                    edges           => graph.edges,
                    order           => graph.order,
                    size            => graph.size,
                    capacity        => graph.capacity,
                    out_edges       => adjacent_edges,
                    in_edges        => adjacent_edges,
                    next            => adjacent_nodes,
                    prior           => adjacent_nodes,
                    has_edge,
                    has_node        => graph.has_node,
                    node_info       => graph.node_info,
                    entries         => graph.exits,
                    exits           => graph.entries,
                    entry_edges     => graph.entry_edges,
                    exit_edges      => graph.exit_edges,
                    forall_nodes    => graph.forall_nodes,
                    forall_edges    => graph.forall_edges
                  };
            };                                  # fun undirected_view 
    };
end;


Comments and suggestions to: bugs@mythryl.org

PreviousUpNext