Graphs and partial orders

In graph.diesel:

Basic graph ADT. A graph is a set of nodes, and each node has a set of in edges and a set of out edges. Clients can just provide concrete subclasses of graph_node, implementing = and hash, or they can subclass graph_edge and/or graph also.

extend module Stdlib;

module Graph;
abstract class graph_node[Node <= graph_node[Node,Edge],
                                 Edge <= graph_edge[Node,Edge]]
                                        isa hashable[graph_node[Node,Edge]];
  field in_edges(:graph_node[`Node,`Edge]):m_set[Edge];
  field out_edges(:graph_node[`Node,`Edge]):m_set[Edge];
abstract class graph_node[Node <= graph_node[Node]]
                                isa graph_node[Node, graph_edge[Node]],
                                    hashable[graph_node[Node]];
abstract class graph_edge[Node <= graph_node[Node,Edge],
                                 Edge <= graph_edge[Node,Edge]]
                                        isa comparable[graph_edge[Node,Edge]];
  var field from_node(:graph_edge[`Node,`Edge]):Node;
  var field to_node(:graph_edge[`Node,`Edge]):Node;
  fun add_edge(e:`Edge <= graph_edge[`Node,`Edge]):void;
  fun remove_edge(e:`Edge <= graph_edge[`Node,`Edge]):void;
class graph_edge[Node <= graph_node[Node]]
                                isa graph_edge[Node, graph_edge[Node]],
                                    comparable[graph_edge[Node]];
  fun new_graph_edge(f:`Node <= graph_node[Node], t:Node):graph_edge[Node];
class graph[Node <= graph_node[Node,Edge],
                   Edge <= graph_edge[Node,Edge]];
  fun add_node(g:graph[`Node,`Edge], node:Node):void;
  fun remove_node(g:graph[`Node,`Edge], node:Node):void;
  fun add_edge(g:graph[`Node,`Edge], e:Edge):void;
  fun remove_edge(g:graph[`Node,`Edge], e:Edge):void;
  fun print_header(g:graph[`Node,`Edge]):string;
  fun print_headers(g:graph[`Node,`Edge]):string;
  fun new_graph[Node <= graph_node[Node,`Edge]]():graph[Node,Edge];

end module Graph;

In partial-order.diesel:

Partial order graph type. Supports downwards and upwards traversals. Clients can just provide concrete subclasses of partial_order_node, implementing =, hash, and <.

extend module Stdlib;

module PartialOrder;
abstract class partial_order_node[Node <= partial_order_node[Node,Edge],
                                         Edge <= partial_order_edge[Node,Edge]]
                isa graph_node[Node, Edge],
                    hashable[partial_order_node[Node,Edge]],
                    partially_ordered[partial_order_node[Node,Edge]];
  fun up_edges(t:partial_order_node[`Node,`Edge]):set[Edge];
  fun down_edges(t:partial_order_node[`Node,`Edge]):set[Edge];
  fun is_top(t:partial_order_node[`Node,`Edge]):bool;
  fun is_bottom(t:partial_order_node[`Node,`Edge]):bool;
  fun up_nodes_do(t:partial_order_node[`Node,`Edge],
                         bl:&(Node):void):void;
  fun down_nodes_do(t:partial_order_node[`Node,`Edge],
                           bl:&(Node):void):void;
  fun order_print_string(t:partial_order_node[`Node,`Edge]):string;
abstract class partial_order_node[Node <= partial_order_node[Node]]
                isa partial_order_node[Node, partial_order_edge[Node]],
                    hashable[partial_order_node[Node]],
                    partially_ordered[partial_order_node[Node]];
abstract class partial_order_edge[Node <= partial_order_node[Node,Edge],
                                         Edge <= partial_order_edge[Node,Edge]]
                                        isa graph_edge[Node,Edge];
  fun down_node(e:partial_order_edge[`Node,`Edge]):Node;
  fun up_node(e:partial_order_edge[`Node,`Edge]):Node;
class partial_order_edge[Node <= partial_order_node[Node]]
                isa partial_order_edge[Node, partial_order_edge[Node]];
  fun new_partial_order_edge(down:`Node <= partial_order_node[Node],
                                    up:Node):partial_order_edge[Node];
abstract class partial_order[Node <= partial_order_node[Node,Edge],
                                    Edge <= partial_order_edge[Node,Edge]]
                                                isa graph[Node, Edge];
  field tops(:partial_order[`Node,`Edge]):m_set[Node];
  field bottoms(:partial_order[`Node,`Edge]):m_set[Node];
  fun add_partial_order_edges(t:partial_order[`Node,`Edge]):void;
  fun top_down_do(t:partial_order[`Node,`Edge], cl:&(Node):void):void;
  fun bottom_up_do(t:partial_order[`Node,`Edge], cl:&(Node):void):void;
  fun ordered_strictly_below(t:partial_order[`Node,`Edge],
                                    n1:Node, n2:Node):bool;
  fun ordered_below(t:partial_order[`Node,`Edge],
                           n1:Node, n2:Node):bool;
  fun ordered_strictly_above(t:partial_order[`Node,`Edge],
                                    n1:Node, n2:Node):bool;
  fun ordered_above(t:partial_order[`Node,`Edge],
                           n1:Node, n2:Node):bool;
  fun clear_marks(g:partial_order[`Node,`Edge]):void;
  fun new_partial_order_edge(:partial_order[`Node,`Edge],
                                    down:Node, up:Node):Edge;
class partial_order[Node <= partial_order_node[Node]]
                isa partial_order[Node, partial_order_edge[Node]];
  fun new_partial_order[Node <= partial_order_node[Node]](
        ):partial_order[Node];

end module PartialOrder;