%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% A student asked me to show how I would write the 
%% connected-components presented in class.  Here it is.
%% Two important points.
%%
%%   1. I am working with the algorithm shown in class.  There
%%      is no attempt to use a better algorithm.
%%
%%   2. Since the question was about how I would write it,
%%      that is what I have done.
%%
%% This is written in Cinnameg, a programming language.  Most
%% of this is comments, like this.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Package connectedComponents

%% Goal: Find the connected components in a graph.
%%
%% connectedComponents(g) yields a set of the connected components
%% of g.

===============================================================
%%                  Some types
===============================================================

Abbrev 
  Vertex = Integer;            %% (A vertex is an integer.)

  Edge   = {Vertex};           %% (An edge is a set of vertices.)

  Graph  = ({Vertex}, {Edge})  %% (A graph is a pair (V,E), where
                               %% V is a set of vertices and E is
                               %% a set of edges.)
%Abbrev

===============================================================
%%                  Notational conventions
===============================================================

Assume
 u,v,w       : Vertex;         %% u, v and w have type Vertex
 g           : Graph;          %% g has type Graph
 vertices, vs: {Vertex};       %% vertices and vs have type {Vertex}
 edges       : {Edge}          %% edges has type {Edge}
%Assume

===============================================================
%%                  neighborhood
===============================================================

Expect neighborhood: (Vertex, {Edge}) -> {Vertex}.

%% neighborhood(v, edges) is the set of all neighbors of
%% vertex v, based on the given set of edges.

%% Algorithm: Look at all edges that contain v.  Put the
%% other vertex from that edge into the neighborhood set.

Define neighborhood(v, edges) = {u | {(=v),u} from edges}.

Example
  neighborhood(2, {{1,2}, {2,3}, {3,4}}) = {1,3}
%Example

===============================================================
%%               Removing vertices from a graph
===============================================================

Expect - : (Graph, {Vertex}) -> Graph.

%% g - vs is the graph obtained from g by removing all of the
%% vertices in set vs, as well as all edges that are incident
%% on members of vs.

%% Algorithm: graph g is ordered pair (vertices, edges).
%%
%% The new set of vertices is (vertices -\ vs), where
%% A -\ B is the set of all members of A that are not in B.
%%
%% The new set of edges are those in the old set (edges)
%% that only contain vertices in the new set of vertices.

%% Notation: The bar at the end of the first line means to do the
%% definitions (Let...) that occur after the bar before 
%% computing the answer that comes before the bar.

Define (vertices, edges) - vs = (newVertices, newEdges) |
  Let newVertices = vertices -\ vs.
  Let newEdges    = {{u,v} | {u,v} from edges, 
                             u `in` newVertices,
                             v `in` newVertices}.
%Define

Example
  ({1,2,3,4}, {{1,2}, {1,3}, {2,3}, {3,4}}) - {2} = 
     ({1,3,4}, {{1,3}, {3,4}})
%Example

===============================================================
%%               oneConnectedComponent
===============================================================

Expect oneConnectedComponent: Graph -> {Vertex}.

%% oneConnectedComponent(g) yields a connected component of g,
%% as a set of vertices.

%% Algorithm:
%% Function f takes a set of vertices s and extends it by 
%% adding all vertices that are neighbors of a vertex in s.
%% For example, for graph 
%%
%%     1 ----- 2 ----- 3 ----- 4
%%             |       |
%%             5       6
%%
%%        f({1})           = {1,2},
%%        f({1,2})         = {1,2,3,5},
%%        f({1,2,3,5})     = {1,2,3,4,5,6}
%%        f({1,2,3,4,5,6}) = {1,2,3,4,5,6}.
%%
%% Notice that set {1,2,3,4,5,6} is a *fixed-point* of f.
%% A fixed-point of a function f is a value x so that f(x) = x.
%%
%% Function fixp is from the library.
%% Expression (fixp f i) yields a fixed-point of f found by
%% computing sequence i, f(i), f(f(i)), f(f(f(i))), ... until
%% two consecutive values are equal.
%%
%% Notation: 
%% A \/ B is the union of sets A and B.
%% {x & A} is the same as {x} \/ A.  So it is A with additional 
%% member x.
%%
%% The graph parameter is shown as a pair containing a set of 
%% vertices and a set of edges.

Define
  oneConnectedComponent(({v & ?}, edges)) 
    = fixp f {v} |
        Define f(vs) = vs \/ {u | w from vs, 
                                  u from neighborhood(w,edges)}.
%Define

===============================================================
%%                 connectedComponents
===============================================================

Expect connectedComponents: Graph -> {{Vertex}}.

%% connectedComponents(g) yields a set of the connected components
%% of graph g.  That it, it yields a set of sets of vertices.

Define
  ------------------------------------------------------------
  %% A graph with no vertices has no connected components.

  case connectedComponents(({},?)) = {}

  ------------------------------------------------------------
  %% For a graph with at least one vertex, find one connected
  %% component, remove it from the graph, and find the remaining
  %% connected components.  Put all of the connected components
  %% together.

  case connectedComponents(g) = {c} \/ connectedComponents(g - c) |
    Let c = oneConnectedComponent(g).
  ------------------------------------------------------------
%Define

Example
  connectedComponents(({1,2,3,4,5,6}, {{1,2}, {2,3}, {4,5}})) =
    {{1,2,3}, {4,5}, {6}}
%Example

%Package