15.4.802  src/lib/graph/uniongraph.pkg

# uniongraph.pkg
#  The union of two graphs.
#
#  -- 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 Union_Graph_View {
        #
        union_view
           :
           ((G1, G2) -> G3)
           ->
           (odg::Digraph(N,E,G1), odg::Digraph(N,E,G2))                 # 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,G3);
    };
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   union_graph_view
    : (weak)  Union_Graph_View                                          # Union_Graph_View      is from   src/lib/graph/uniongraph.pkg
    {   

       fun union_view f (odg::DIGRAPH graph_a, odg::DIGRAPH graph_b)
           =
           {    fun merge_nodes  ns
                    =
                    lms::sort_list_and_drop_duplicates
                        #
                        (\\ ((i, _), (j, _)) =  int::compare (i, j))
                        ns;

                fun merge_node_ids  ns
                    =
                    lms::sort_list_and_drop_duplicates
                        #
                        (\\ (i, j) =  int::compare (i, j))
                        ns;

                fun merge_edges  es
                    =
                    lms::sort_list_and_drop_duplicates
                        #
                        (\\ ((i, j, _), (m, n, _))
                            =
                            if      (i <  m ) LESS;
                            else if (i == m)
                                 if (j <  n ) LESS;
                            else if (j == n ) EQUAL;
                            else                GREATER;   fi; fi;
                            else                GREATER;   fi; fi
                        )
                        es;

                fun allot_node_id ()
                    =
                    int::max (graph_a.capacity (), graph_b.capacity ());

                fun add_node n =  { graph_a.add_node n;   graph_b.add_node n; };
                fun add_edge e =  { graph_a.add_edge e;   graph_b.add_edge e; };

                fun remove_node i
                    =
                    {   graph_a.remove_node i;
                        graph_b.remove_node i;
                    };

                fun set_out_edges e =  { graph_a.set_out_edges e;   graph_b.set_out_edges e; };
                fun set_in_edges  e =  { graph_a.set_in_edges  e;   graph_b.set_in_edges  e; };

                fun garbage_collect ()
                    =
                    {   graph_a.garbage_collect ();
                        graph_b.garbage_collect ();
                    };

                fun nodes () =  merge_nodes (graph_a.nodes()  @  graph_b.nodes ());
                fun edges () =  merge_edges (graph_a.edges()  @  graph_b.edges ());

                fun order () =  length (nodes ());
                fun size  () =  length (edges ());

                fun capacity ()
                    =
                    graph_a.capacity ()
                    +
                    graph_b.capacity ();

                fun out_edges i =  merge_edges (graph_a.out_edges i  @  graph_b.out_edges i);
                fun in_edges  i =  merge_edges (graph_a.in_edges  i  @  graph_b.in_edges  i);

                fun next i =  merge_node_ids  (graph_a.next i  @  graph_b.next i);
                fun prior i =  merge_node_ids  (graph_a.prior i  @  graph_b.prior i);

                fun has_edge e =  graph_a.has_edge e  or  graph_b.has_edge e;
                fun has_node n =  graph_a.has_node n  or  graph_b.has_node n;

                fun node_info n
                    =
                    graph_a.node_info n
                    except
                        _ =  graph_b.node_info n;

                fun entries () =  merge_node_ids (graph_a.entries ()  @  graph_b.entries ());
                fun exits   () =  merge_node_ids (graph_a.exits   ()  @  graph_b.exits   ());

                fun entry_edges i =  merge_edges (graph_a.entry_edges i  @  graph_b.entry_edges i);
                fun exit_edges  i =  merge_edges (graph_a.exit_edges  i  @  graph_b.exit_edges  i);

                fun forall_nodes f =  apply f (nodes ());
                fun forall_edges f =  apply f (edges ());

             #  fun fold_nodes f u =  list::fold_backward f u (nodes ())
             #  fun fold_edges f u =  list::fold_backward f u (edges ())

                odg::DIGRAPH
                  {
                    name            => graph_a.name + "+" + graph_b.name,
                    graph_info      => f (graph_a.graph_info, graph_b.graph_info),
                    allot_node_id,
                    add_node,
                    add_edge,
                    remove_node,
                    set_in_edges,
                    set_out_edges,
                    set_entries     => odg::unimplemented,
                    set_exits       => odg::unimplemented,
                    garbage_collect,
                    nodes,
                    edges,
                    order,
                    size,
                    capacity,
                    out_edges,
                    in_edges,
                    next            => prior,
                    prior            => next,
                    has_edge,
                    has_node,
                    node_info,
                    entries,
                    exits,
                    entry_edges,
                    exit_edges,
                    forall_nodes,
                    forall_edges

               #    fold_nodes      = fold_nodes,
               #    fold_edges      = fold_edges

                  };
           };
    };
end;