\manpage {graph} {} {Graphs} 
 
\definition
An instance $G$ of the data type $graph$ consists of a list $V$  of nodes
and a list $E$  of edges ($node$ and $edge$ are item types). A pair of nodes 
$(v,w) \in V\times V$ is associated with every edge $e\in E$; $v$ is called 
the {\em source} of $e$ and $w$ is called the {\em target} of $e$. Two lists 
of edges are associated with every node $v$: the list
$out\_edges(v) = \{\ e \in E\ | source(e) = v\ \}$ of edges starting in $v$, 
and the list $in\_edges(v) = \{\ e \in E\ | target(e) = v\ \}$ of
edges ending in $v$. Distinct graphs have disjoint node and edge sets. 
A graph with empty node list is called {\em empty}.

A graph is either {\em directed} or {\em undirected}; the main difference
between directed and undirected edges is the definition of {\em adjacent}. 
Undirected graphs are the subject of section \ref{Undirected Graphs}. 
In a directed graph an edge is adjacent to its source and in an undirected 
graph it is adjacent to its source and sink. In a directed graph a node $w$ 
is adjacent to a node $v$ if there is an edge $(v,w) \in E$; in an undirected 
graph $w$ is adjacent to $v$ if there is an edge $(v,w)$ or $(w,v)$ in the 
graph. The {\em adjacency list} of a node $v$ is the list of edges adjacent 
to $v$; more precisely, for directed graphs the adjacency list of $v$ is 
equal to $out\_edges(v)$ and for undirected graphs it is the concatenation
of $out\_edges(v)$ and $in\_edges(v)$. 

The value of a variable of type node is either the node of some graph, or the
special value nil (which is distinct from all nodes), or is undefined (before the first assignment to the variable). A corresponding statement is true for
the variables of type edge.
 
\creation G 
 
\create { }
   { creates an object $G$ of type $graph$ and initializes it to
            the empty directed graph.  }
 
 
\operations 1.9 4.7 
 
       
\bigskip
{\bf a) Access operations} 
 
\op  int outdeg {(node\ v)}
           {  returns the outdegree of node $v$, i.e., the number of
            edges starting at $v$ ($|out\_edges(v)|$.  }
 
 
\op  int indeg {(node\ v)}
           {  returns the indegree of node $v$, i.e., the number of
            edges ending at $v$ ($|in\_edges(v)|$.  }
 
 
\op  int degree {(node\ v)}
           {  returns the indegree of node $v$, i.e., the number of
            edges starting or ending at $v$.  }
 
 
\op  node source {(edge\ e)}
           {  returns the source node of edge $e$. }
 
 
\op  node target {(edge\ e)}
           {  returns the target node of edge $e$. }
 
 
\op  node opposite {(node\ v, \ edge\ e)}
           {  returns a node of edge $e$ different from $v$ (returns $v$
            if $e$ has source and target equal to $v$) .  }
 
 
\op  int  number\_of\_nodes {()}
           {  returns the number of nodes in $G$.  }
 
 
\op  int  number\_of\_edges {()}
           {  returns the number of edges in $G$.  }
 
 
\op  list\<edge\> all\_edges {()}
           {  returns the list $E$ of all edges of $G$.  }
 
 
\op  list\<node\> all\_nodes {()}
           {  returns the list $V$ of all nodes of $G$.  }
 
 
\op  list\<edge\> adj\_edges {(node\ v)}
           {  returns the list of all edges adjacent to $v$.  }
 
 
\op  list\<edge\> in\_edges {(node\ v)}
           {  returns the list of all edges ending at $v$.  }
 
 
\op  list\<node\> adj\_nodes {(node\ v)}
           {  returns the list of all nodes adjacent to $v$.  }
 
 
\op  node first\_node {()}
           {  returns the first node in $V$.  }
 
 
\op  node last\_node {()}
           {  returns the last node in $V$.  }
 
 
\op  node choose\_node {()}
           {  returns a node of $G$ (nil if $G$ is empty).  }
 
 
\op  node succ\_node {(node\ v)}
           {  returns the successor of node $v$ in $V$
	      (nil if it does not exist).  }
 
 
\op  node pred\_node {(node\ v)}
           {  returns the predecessor of node $v$ in $V$
	      (nil if it does not exist).  }
 
 
\op  edge first\_edge {()}
           {  returns the first edge in $E$.  }
 
 
\op  edge last\_edge {()}
           {  returns the last edge in $E$.  }
 
 
\op  edge choose\_edge {()}
           {  returns an edge of $G$ (nil if $G$ is empty).  }
 
 
\op  edge succ\_edge {(edge\ e)}
           {  returns the successor of edge $e$ in $E$
	      (nil if it does not exist).  }
 
 
\op  edge pred\_edge {(edge\ e)}
           {  returns the predecessor of edge $e$ in $E$
	      (nil if it does not exist).  }
 
 
\op  edge first\_adj\_edge {(node\ v)}
           {  returns the first edge in the adjacency list of $v$.  }
 
 
\op  edge last\_adj\_edge {(node\ v)}
           {  returns the last edge in the adjacency list of $v$.  }
 
 
\op  edge adj\_succ {(edge\ e)}
           {  returns the successor of edge $e$ in the
              adjacency list of node $source(e)$
	      (nil if it does not exist).  }
 
 
\op  edge adj\_pred {(edge\ e)}
           {  returns the predecessor of edge $e$ in the
              adjacency list of node $source(e)$
	      (nil if it does not exist).  }
 
 
\op  edge cyclic\_adj\_succ {(edge\ e)}
           {  returns the cyclic successor of edge $e$ in the
              adjacency list of node $source(e)$.  }
 
 
\op  edge cyclic\_adj\_pred {(edge\ e)}
           {  returns the cyclic predecessor of edge $e$ in the
	      adjacency list of node $source(e)$.  }
 
 
\op  edge first\_in\_edge {(node\ v)}
           {  returns the first edge of $in\_list(v)$.  }
 
 
\op  edge last\_in\_edge {(node\ v)}
           {  returns the last edge of $in\_list(v)$.  }
 
 
\op  edge in\_succ {(edge\ e)}
           {  returns the successor of edge $e$ in $in\_list(target(e))$
              (nil if it does not exist).  }
 
 
\op  edge in\_pred {(edge\ e)}
           {  returns the predecessor of edge $e$ in $in\_list(target(e))$
              (nil if it does not exist).  }
 
 
\op  edge cyclic\_in\_succ {(edge\ e)}
           {  returns the cyclic successor of edge $e$ in
              $in\_list(target(e))$ (nil if it does not exist).  }
 
 
\op  edge cyclic\_in\_pred {(edge\ e)}
           {  returns the cyclic predecessor of edge $e$ in
              $in\_list(target(e))$ (nil if it does not exist).  }
 
 
       
\bigskip
{\bf b) Update operations} 
 
\op  node new\_node {()}
           {  adds a new node to $G$ and returns it.  }
 
 
\op  edge new\_edge {(node\ v, \ node\ w)}
           {  adds a new edge $(v,w)$ to \var\ by appending it to
                $out\_list(v)$ and to $in\_list(w)$, and returns it. }
 
 
\opl edge new\_edge {(edge\ e, \ node\ w, \ int\ dir=after)}
           {  adds a new edge $(source(e),w)$ to \var\ by inserting it
               before ($dir$=before) or after ( $dir$= after) edge $e$ into 
               $out\_list(source(e))$ and appending it to $in\_list(w)$, 
               and returns it. Here $before$ and $after$ are predefined
               integer constants.  }
 
 
\opl edge new\_edge {(edge\ e1, \ edge\ e2, \ int\ d1=after, \ int\ d2=after)}
           {  adds a new edge $(source(e1),target(e2))$ to \var\ by
               inserting it before (if $d1$=before) or after (if $d1$= after) 
               edge $e1$ into $out\_list(source(e1))$ and before 
               (if $d2$=before) or after (if $d2$= after) edge $e2$ into 
               $in\_list(target(e2))$, and returns it.  } 
 
 
\op  void hide\_edge {(edge\ e)}
           {  removes edge $e$ from $out\_list(source(e))$ and
               from $in\_list(target(e))$, but leaves it in the
               list of all edges $E$.  }
 
 
\op  void restore\_edge {(edge\ e)}
           {  restores $e$ by re-inserting into $out\_list(source(e))$
               and into $in\_list(taret(e))$. \precond $e$ must have been
               removed by a call of hide\_edge before.  }
 
 
\op  void del\_node {(node\ v)}
           {  deletes $v$ and all edges starting or ending at $v$
	      from $G$.  }
 
 
\op  void del\_edge {(edge\ e)}
           {  deletes the edge $e$ from $G$.  }
 
 
\op  void del\_all\_nodes {()}
           {  deletes all nodes from $G$.  }
 
 
\op  void del\_all\_edges {()}
           {  deletes all edges from $G$.  }
 
 
\op  edge rev\_edge {(edge\ e)}
           {  reverses the edge $e = (v,w)$ by removing it from $G$
              and inserting the edge $(w,v)$ into $G$; returns the 
              reversed edge.  }
 
 
\op  graph\& rev {()}
           {  all edges in $G$ are reversed.  }
 
 
\opl void sort\_nodes {(int\ (*cmp)(const\ node\&,\ const\ node\&))}
           {  the nodes of $G$ are sorted according to the
	      ordering defined by the comparing function
	      $cmp$. Subsequent executions of forall\_nodes
	      step through the nodes in this order.
	      (cf.~TOPSORT1 in section \ref{Graph and network algorithms}).  }
 
 
\opl void sort\_edges {(int\ (*cmp)(const\ edge\&,\ const\ edge\&))}
           {  the edges of $G$ and all out\_lists (but not the in\_lists)
              are sorted according to the
	      ordering defined by the comparing function
	      $cmp$. Subsequent executions of forall\_edges
	      step through the edges in this order.
              (cf.~TOPSORT1 in section \ref{Graph and network algorithms}).  }
 
 
\opl void sort\_nodes {( node\_array\<T\>\ A)}
           {  the nodes of $G$ are sorted according to the entries of
              node\_array $A$ (cf. section \ref{Node Arrays})
	      \precond $T$ must be linearly ordered.  }
 
 
\opl void sort\_nodes {( edge\_array\<T\>\ A)}
           {  the edges of $G$ are sorted according to the entries of
              edge\_array $A$ (cf. section \ref{Edge Arrays})
	      \precond $T$ must be linearly ordered.  }
 
 
\op  list\<edge\> insert\_reverse\_edges {()}
           {  for every edge $(v,w)$ in $G$ the reverse edge $(w,v)$
              is inserted into $G$. Returns the list of all inserted 
              edges is returned. }
 
 
\op  void make\_undirected {()}
           {  make $G$ undirected.  }
 
 
\op  void make\_directed {()}
           {  make $G$ directed.  }
 
 
\op  void clear {()}
           {  makes $G$ the empty graph.  }
 
 

\bigskip
{\bf c) Iterators}

With the adjacency list of every node $v$ a list iterator, 
called the adjacency iterator of $v$, is associated (cf. section \ref{Linear Lists}). There 
are operations to initialize, move, and read these iterators.  
 
\op  void init\_adj\_iterator {(node\ v)}
           {  sets the adjacency iterator of $v$ to undefined.  }
 
 
\opl bool next\_adj\_edge {(edge\&\ e, node\ v)}
           {  moves the adjacency iterator of $v$ forward by one edge
             (to the first item of $adj\_list(v)$ if it was undefined) 
             and returns $G$.current\_adj\_edge($e,v$). }
 
 
\opl bool current\_adj\_edge {(edge\&\ e, node\ v)}
           {  if the adjacency iterator of $v$ is defined assign the
             corresponding edge to $e$ and return true, otherwise,
             return false. }
 
 
\opl bool next\_adj\_node {(node\&\ w, node\ v)}
           {  if $G$.next\_adj\_edge($e$, $v$) = true assign
	     $target(e)$ to $w$ and return true else return false. }
 
 
\opl bool current\_adj\_node {(node\&\ w, node\ v)}
           {  if $G$.current\_adj\_edge($e$, $v$) = true then assign
	     $target(e)$ to $w$ and return true, else return false.  }
 
 
\op  void reset {()}
           {  sets all iterators in $G$ to undefined.  }
 
 

\bigskip
{\bf d) I/O Operations} 
 
\opl void write {(ostream\&\ O\ =\ cout)}
           {  writes $G$ to the output stream $O$. }
 
 
\op  void write {(string\ s)}
           {  writes $G$ to the file with name $s$. }
 
 
\opl int read {(istream\&\ I\ =\ cin)}
           {  reads a graph from the input stream $I$ and assigns
              it to \var.  }
 
 
\op  int read {(string\ s)}
           {  reads a graph from the file with name $s$ and assigns
              it to \var.  }
 
 
\opl void print\_node {(node\ v, \ ostream\&\ O\ =\ cout)}
           {  prints node $v$ on the output stream $O$.  }
 
 
\opl void print\_edge {(edge\ e, \ ostream\&\ O\ =\ cout)}
           {  prints edge $e$ on the output stream $O$. If \var\
              is directed $e$ is represented by an arrow 
              pointing from source to target. If \var\ is undirected
              $e$ is printed as an undirected line segment.  }
 
 
\opl void print {(string\ s, \ ostream\&\ O\ =\ cout)}
           {  pretty-prints $G$ with header line $s$ on the output
              stream $O$.  }
 
 
\op  void print {(ostream\&\ O)}
           {  pretty-prints $G$ on the output stream $O$.  }
 
 
\op  void print {()}
           {  pretty-prints $G$ on the standard ouput stream $cout$.  }
 
 
            
\bigskip
{\bf e) Iteration} 
 
            
\bigskip
{\bf forall\_nodes}($v,G$)\\ 
$\{$ ``the nodes of $G$ are successively assigned to $v$" $\}$ 
 
            
\bigskip
{\bf forall\_edges}($v,G$)\\
$\{$ ``the edges of $G$ are successively assigned to $e$" $\}$ 
 
            
\bigskip
{\bf Forall\_nodes}($v,G$)\\
$\{$ ``the nodes of $G$ are successively assigned to $v$ in reverse order" $\}$ 
 
            
\bigskip
{\bf Forall\_edges}($v,G$)\\ 
$\{$ ``the edges of $G$ are successively assigned to $e$ in reverse order" $\}$ 
 

\bigskip
{\bf forall\_out\_edges}($e,w$)\\
$\{$ ``the edges of $out\_list(w)$ are successively assigned to $e$" $\}$ 
 

\bigskip
{\bf forall\_in\_edges}($e,w$)\\
$\{$ ``the edges of $in\_list(w)$ are successively assigned to $e$" $\}$ 
 

\bigskip
{\bf forall\_inout\_edges}($e,w$)\\
$\{$ ``the edges of $out\_list(w)$ and $in\_list(w)$ are successively assigned to $e$" $\}$ 
 

\bigskip
{\bf forall\_adj\_edges}($e,w$)\\
$\{$ ``the edges adjacent to node $w$ are successively assigned to $e$" $\}$ 
 

\bigskip
{\bf forall\_adj\_nodes}($v,w$)\\
$\{$ ``the nodes adjacent to node $w$ are successively assigned to v" $\}$ 
 
\implementation
Graphs are implemented by doubly linked adjacency lists. Most operations 
take constant time, except for all\_nodes, all\_edges, del\_all\_nodes,
del\_all\_edges, clear, write, and read which take time $O(n+m)$, where 
$n$ is the current number of nodes and $m$ is the current number of edges. 
The space requirement is $O(n+m)$.
 
\manpage {GRAPH} {vtype,etype} {Parameterized Graphs}
 
\definition 
A parameterized graph $G$ is a graph whose nodes and edges contain additional
(user defined) data. Every node contains an element of a data type $vtype$, 
called the node type of $G$ and every edge contains an element of a data type 
$etype$ called the edge type of $G$. We use $\<v,w,y\>$ to denote an edge 
$(v,w)$ with information $y$ and $\<x\>$ to denote a node with information $x$.

All operations defined on instances of the data type $graph$ are also defined on
instances of any parameterized graph type \name. For 
parameterized graphs there are additional operations to access or update the 
information associated with its nodes and edges.  
Instances of a parameterized graph type can be used wherever an instance 
of the data type $graph$ can be used, e.g., in assignments and as 
arguments to functions with formal parameters of type $graph\&$. 
If a function $f(graph\&\ G)$ is called with an argument $Q$ of type 
\name\ then inside $f$ only the basic graph structure of $Q$ (the
adjacency lists) can be accessed. The node and edge entries are hidden.
This allows the design of generic graph algorithms, i.e., algorithms accepting
instances of any parametrized graph type as argument.
 
\creation G 
 
\create { }
   { creates an instance \var\ of type \name\ and initializes it to
            the empty graph.  }
 
 
\operations 1.5 4.5 
 
\op  vtype inf {(node\ v)}
           {  returns the information of node $v$  }
 
 
\op  etype inf {(edge\ e)}
           {  returns the information of edge $e$  }
 
 
\op  void assign {(node\ v, vtype\ x)}
           {  makes $x$ the information of node $v$  }
 
 
\op  void assign {(edge\ e, etype\ x)}
           {  makes $x$ the information of edge $e$  }
 
 
\op  node new\_node {(vtype\ x)}
           {  adds a new node $\<x\>$ to $G$ and returns it }
 
 
\op  node   new\_node {()}
           {  adds a new node $\<vdef\>$ to $G$ and returns it. Here,
           $vdef$ is the default value of type $vtype$. }
 
 
\opl edge new\_edge {(node\ v, \ node\ w, \ etype\ a)}
           {  adds a new edge $\<v,w,a\>$ to $G$ by appending
           it to the adjacency list of $v$ and the in-list of 
           $w$ and returns it.  }
 
 
\opl edge new\_edge {(node\ v, \ node\ w)}
           {  adds a new edge $\<v,w,edef\>$ to $G$ by
	   appending it to the adjacency list of $v$ and
           the in-list of $w$ and returns it. Here, $edef$ 
           is the default value of type $etype$. }
 
 
\opl edge new\_edge {(edge\ e, \ node\ w, \ etype\ a)}
           {  adds a new edge $\<source(e),w,a\>$ to $G$ by appending it
           to the adjacency list of $source(e)$ and the in-list of 
           $w$ and returns it.  }
 
 
\opl edge new\_edge {(edge\ e, \ node\ w)}
           {  adds a new edge $\<source(e),w,edef\>$ to $G$ by appending
           it to the adjacency list of $source(e)$ and the in-list of 
           $w$ and returns it. Here, $edef$ is the default value of 
           type $etype$. }
 
 
\opl edge new\_edge {(edge\ e, \ node\ w, \ etype\ a, \ int\ dir)}
           {  adds a new edge $\<source(e),w,x\>$ to $G$
	   by inserting it after ($dir$=after) or before ($dir$
	   =before) edge $e$ into the adjacency list of
	   $source(e)$ and appending it to the in-list of $w$.
           Returns the new edge. }
 
 
\op  void sort\_nodes {()}
           {  the nodes of $G$ are sorted according to their
           contents.\\
           \precond $vtype$ is linearly ordered. }
 
 
\op  void sort\_edges {()}
           {  the edges of $G$ are sorted according to their
	   contents.\\ 
           \precond $etype$ is linearly ordered. }
 
 
\op  void write {(string\ fname)}
           {  writes $G$ to the file with name $fname$. The
           output functions $Print(vtype,ostream)$ and
           $Print(etype,ostream)$ (cf. section 1.6) must
           be defined. }
 
 
\op  int read {(string\ fname)}
           {  reads $G$ from the file with name $fname$. The
	   input functions $Read(vtype,istream)$ and 
	   $Read(etype,istream)$ (cf.~section 1.6) must
	   be defined. Returns error code\\
	   1 \quad if file $fname$ does not exist\\
	   2 \quad if graph is not of type \name\\
	   3 \quad if file $fname$ does not contain a graph\\
	   0 \quad otherwise. }
 
 

\bigskip
{\bf Operators} 
 
\arrop vtype\&  {node\ v}
         {  returns a reference to $G$.inf($v$). }
 
 
\arrop etype\&  {edge\ e}
         {  returns a reference to $G$.inf($e$). }
 
 
\implementation
Parameterized graphs are derived from directed graphs. All additional 
operations for manipulating the node and edge entries take constant
time.
 
