-- Copyright 1993-1998, by the Cecil Project
-- Department of Computer Science and Engineering, University of Washington
-- See the LICENSE file for license information.

(-- 
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.
--)

abstract object graph_node[Node <= graph_node[Node,Edge],
			   Edge <= graph_edge[Node,Edge]]
		isa comparable[graph_node[Node,Edge]];
  field in_edges (@:graph_node[`Node,`Edge]):m_set[Edge]
						:= new_list_set[Edge]();
  field out_edges(@:graph_node[`Node,`Edge]):m_set[Edge]
						:= new_list_set[Edge]();

  signature table_key(graph_node[`Node,`Edge]):string;


abstract object 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;

  method =(e1@:graph_edge[`Node,`Edge], e2@:graph_edge[Node,Edge]):bool { 
    e1 == e2 | { e1.from_node == e2.from_node & { e1.to_node == e2.to_node } } }

  method add_edge(e@graph_edge[`Node,`Edge]:`Edge <= graph_edge[`Node,`Edge]
		  ):void {
    e.from_node.out_edges.add(e);
    e.to_node.in_edges.add(e);
  }
  method remove_edge(e@graph_edge[`Node,`Edge]:`Edge <= graph_edge[`Node,`Edge]
		     ):void {
    e.from_node.out_edges.remove(e);
    e.to_node.in_edges.remove(e);
  }


abstract object graph[Node <= graph_node[Node,Edge],
		      Edge <= graph_edge[Node,Edge]];
  var field nodes(@:graph[`Node,`Edge]):m_removable_table[string,Node]
  		:= new_hash_table[string,Node]();

  method add_node(g@:graph[`Node,`Edge], node:Node):void {
    g.nodes.store(node.table_key, node);
  }
  method remove_node(g@:graph[`Node,`Edge], node:Node):void {
    g.nodes.remove_key(node.table_key);
    void
  }

  method add_edge(g@:graph[`Node,`Edge], e:Edge):void {
    e.add_edge;
  }
  method remove_edge(g@:graph[`Node,`Edge], e:Edge):void {
    e.remove_edge;
  }

  method print_header(g@:graph[`Node,`Edge]):string {
    "graph of " || g.nodes.length.print_string || " nodes\n" }
  method print_headers(g@:graph[`Node,`Edge]):string {
    let var s:string := "";
    do(g.nodes, &(n:Node){
      s := s || n.print_string || "\n";
    });
    s }

  method print_string(g@:graph[`Node,`Edge]):string {
    g.print_header || g.print_headers }

  method print(g@:graph[`Node,`Edge]):void {
    g.print_header.print;
    do(g.nodes, &(n:Node){
      n.print_string.print_line;
    });
  }