/* graph.q: graph operations (Feb 1993 AG); revised 05-08-1993,
   10-26-1993, 11-13-1993, 03-02-2002, 01-30-04 AG */

/* Graphs are represented by the construct graph V E which denotes a graph
   with vertex set V and edges E. E is implemented as a dictionary of (vertex,
   adjacency set) pairs. Undirected graphs are just graphs with a symmetric
   adjacency relation. */

public type Graph = const graph V E;

/* Public operations of this module. */

public mkgraph V E, mkdigraph V E;
public add_edge G E, add_diedge G E;
public rm_edge G E, rm_diedge G E;
public vertices G, edges G;

/* The mkgraph and mkdigraph operations take as arguments a list of vertices
   and a list of edges represented as vertex pairs, and create an undirected
   or directed graph, respectively. */

private edge_dict V;

mkgraph V E		= foldl add_edge (graph (set V) (edge_dict V)) E;
mkdigraph V E		= foldl add_diedge (graph (set V) (edge_dict V)) E;

edge_dict V		= mkdict emptyset V;

/* The add_edge and add_diedge operations add an undirected or directed
   edge to a graph, respectively. */

add_edge (graph V E) (X,Y)
			= foldl add_diedge (graph V E) [(X,Y), (Y,X)];

add_diedge (graph V E) (X,Y)
			= graph V (update E X (insert (E!X) Y));

/* The rm_edge and rm_dedge operations delete an undirected or directed
   edge from a graph, respectively. */

rm_edge (graph V E) (X,Y)
			= foldl rm_diedge (graph V E) [(X,Y), (Y,X)];

rm_diedge (graph V E) (X,Y)
			= graph V (update E X (delete (E!X) Y));
				
/* The following operations retrieve the vertices and edges from a graph,
   respectively. */

vertices (graph V E)	= V;
edges (graph V E)	= E;