%---TeX-start-of-header---
\documentclass[titlepage]{article}
\usepackage{figi,mathematica,alltt}
%\mmanobreak

\newenvironment{implementation}%
  {\footnotesize\textbf{Implementation notes: }}{\bigskip}

\begin{comment}

\begin{mathematica}
<<tek.m;
\end{mathematica}

\begin{mathematica}
SetOptions["stdout", PageWidth->100];
zero = 0.00001;
ohide = DisplayFunction->Identity;
oshow = DisplayFunction -> $DisplayFunction;
ojoin = PlotJoined -> True;
oall = PlotRange->All;
osurf = HiddenSurface->False;
deg = N[Degree];
pi = N[Pi];
\end{mathematica}

\begin{mathematica}
<<DiscreteMath`Combinatorica`
\end{mathematica}

\end{comment}

\begin{document}
\psfiginit
%---TeX-end-of-header---

\author{Tomasz J.\ Cholewo}
\title{{\Large Design and Analysis of Computer Algorithms, EE619}\\[1cm]
Programming Project \#1: Euler Circuits}
\maketitle
\tableofcontents
%====================================================================
\newpage
\section{Listings of \Mma{} Functions}

\subsection{Connectivity and undirectionality tests}

Function \texttt{depthfirstsearch[adj, start]} performs a recursive
depth-first search of a graph represented by an adjacency list \texttt{adj}
starting from vertex \texttt{start}, and returns a list of vertices in the
order in which they were encountered. An empty list is returned for an
empty graph.
\begin{mathematica}
depthfirstsearch[{}, _] := {};
depthfirstsearch[adj_List, start_Integer] := Module[
  { visited = {},                     (* list of already traversed vertices *)
    dfsnum = Table[0, {Length[adj]}], (* array for marking vertices as visited *)
    cnt = 1 },                        (* number of a current vertex *)
  dfs[v_Integer] := (                 (* subfunction definition *)
      dfsnum[[v]] = cnt++;            (* label the vertex as visited *)
      AppendTo[visited, v];           (* add it to list *)
      Scan[ (If[ dfsnum[[#]] == 0, dfs[#] ])&, adj[[v]] ]
                                      (* call dfs for all unvisited vertices on
                                         the adjacency list of vertex v *)
  ); (* end dfs *)
  dfs[start];                         (* start the dfs recursions *)
  visited                             (* return list of visited vertices as a result *)
];
\end{mathematica}
\begin{implementation}
  \verb+Module+ construct creates a block structure with statically
  scoped local variables defined in a list being its first argument.
  The basic \Mma{} data structure is a list.  It enables expressing many
  problems in a natural, terse way.  Variable \texttt{dfsnum}
  functioning here as an array is also a list.  When a given graph
  consists of a single vertex, then a list consisting of this vertex is
  returned.
\end{implementation}

Predicate \texttt{connectedQ[adj]} determines if a graph is connected by
testing if a number of vertices visited in a depth-first search started
at an arbitrary vertex and a number of all vertices in this graph are
equal.
\begin{mathematica}
connectedQ[adj_List] := Length[ depthfirstsearch[adj, 1] ] == Length[adj];
\end{mathematica}
\begin{implementation}
  One can count vertices of a graph represented by adjacency lists by
  simply counting the number of these lists.  Function
  \texttt{depthfirstsearch} is more general than it is necessary here
  because it also stores numbers of visited vertices.  With this
  definition graphs empty and consisting of a single vertex are
  considered connected.
\end{implementation}

Predicate \texttt{undirectedQ} in a rather baroque functional style
tests for undirectionality of a graph \texttt{adj}.
\begin{mathematica}
undirectedQ[adj_List] := And @@ MapIndexed[ Function[{li, v},
    And @@ ((Count[ adj[[#]], v[[1]] ] == 1)& /@ li) ], adj];
\end{mathematica}
\begin{implementation}
  It works by checking if for each edge $(v,w)$ on an adjacency list of
  a vertex $v$ there exists the edge $(w,v)$ on adjacency list of a
  vertex $w$.  It is obviously not optimally designed because each edges
  is checked twice. \verb+x /@ y+ means \verb+Map[x, y]+, i.e., creating
  a list by running a function \texttt{x} on each element of a list
  \texttt{y}, and \verb+x @@ y+ means \verb+Apply[x, y]+, i.e.,
  evaluating a function \texttt{x} with arguments taken from a list
  \texttt{y}.  Shortly, the result is true only if for all entries on
  each vertex'es list a predicate testing if an edge exists also on the
  tail vertex'es list returns true.  From \verb+And[{}] == {}+ property
  it follows that empty and single-vertex graphs are recognized as
  undirected.
\end{implementation}

\subsection{Euler circuit test and algorithm}

Predicate \texttt{eulerianQ[adj]} checks whether a graph has Eulerian
circuit by testing if it is undirected, connected and if all its
vertices have even degrees.
\begin{mathematica}
eulerianQ[adj_List] := undirectedQ[adj] && connectedQ[adj] &&
    Apply[ And, Map[ EvenQ[ Length[#] ]&, adj ] ];
\end{mathematica}
\begin{implementation}
  The second part of this statement first creates a list of logical
  values saying if the length of a list for each vertex is even by
  mapping \verb+EvenQ @ Length+ function on the adjacency lists. Then
  this list becomes an argument to the logical \verb+And+ operation.
  Somehow arbitrarily this definition is also working for empty and
  single-vertex graphs.
\end{implementation}

Function \texttt{euler[adj, start, mode]} returns a list of edges
describing Eulerian circuit in the graph given by adjacency list
\texttt{adj} starting and ending on vertex \texttt{start}.  If optional
argument \texttt{mode} with value \texttt{Debug} is supplied then the
function prints out a detailed report of its progress.  The function
call is returned unevaluated if a ciruit does not exist.  For empty
and single-vertex graphs an empty list is returned.
\begin{mathematica}
euler[{}, ___] := {};
euler[adj_List /; eulerianQ[adj], start_Integer, mode_:Silent] := Module[
  { a = adj,                     (* local copy of the adjacency list *)
    ind = "" },                  (* indentation (spaces) for pretty-printing *)
  visit[v_Integer] := Module[    (* local subfunction *)
    { pathout = {},              (* part of a circuit leading to a deadend/start vertex *)
      w },                       (* tail of a current edge *)
    If[mode === Debug,           (* print the call identification *)
      Print[ind, "visit(", v, ")"];
      ind = ind <> "  "
    ];
    While[ Length[a[[v]]] > 0,   (* while there are any undeleted edges in adjacency list of vertex v *)
      w = a[[v, 1]];             (* tail of an untraversed edge *)
      If[mode === Debug,         (* identify edge and way-out path *)
        Print[ind, "while ", v, ": w = ", w, ", pathout = ", pathout];
      ];
      a[[v]] = DeleteCases[a[[v]], w];  (* remove edge (v,w) from a[v] *)
      a[[w]] = DeleteCases[a[[w]], v];  (* and from a[w] *)
      pathout = Join[{{v, w}}, visit[w], pathout]
                  (* the essence of algorithm, see explanation below *)
    ]; (* While *)
    If[mode === Debug,            (* print return value *)
      ind = StringDrop[ind, -2];
      Print[ind, "return ", v, " = ", pathout];
    ];
    pathout                       (* return path leading to a deadend *)
  ]; (* visit *)
  visit[start]                    (* start the algorithm on selected vertex *)
]; (* euler *)
\end{mathematica}
The basic idea of the algorithm, as explained in class, is to go as far
as possible in the depth-first search, marking already traversed edges
as old.  When a deadend is met it means that it is a vertex where
the search for the current cycle started, because only that vertex has
an odd degree.  To use all edges, not only these laying on this main
depth-first search cycle we have to backtrack from each deadend found
and start recursively a new cycle search on each vertex having any
untraversed edges adjacent and then patch this cycle in the correct
position in the circuit.

This approach can be implemented by noticing that for a given starting
vertex we can find a part of a desired circuit by joining any
untraversed edge with the cycle to be found by the same procedure called
on a tail of this edge.  There can still be some edges untraversed after
the first edge is traversed, but we can notice that this first part must
lead to a deadend (i.e., vertex where the search started), so this part
must come last in the resulting circuit.  Next parts will be cycles
returning to the same vertex and as such should be prepended to the
whole circuit.

Whole problem in explaining this comes from the fact that mentally there
are two different levels of recursion: one for the depth-first search and
other for backtracking to unused edges, but only one procedure realizing
both, because backtracking is implemented as the \texttt{While} loop.

\begin{implementation}
  I chose not to keep information about new and old edges (see
  Pidgin--Pascal formulation) because it would be much more cumbersome
  and ineffective.  Instead I simply keep a copy of adjacency lists (one
  is not allowed to modify formal parameters) and each time a new edge
  is encountered it is moved from there to pathout list.  This way it is
  possible to ``prove'' the stop property of this program: there is a
  finite number of edges on the input, in each step one of them is
  removed, so it must stop in finite time.  The domain of this function
  is restricted to adjacency lists which pass \texttt{eulerianQ} test.
  Argument \texttt{mode} is optional and its default value is set to
  \texttt{Silent}.
\end{implementation}
%====================================================================
\newpage
\section{Tests}
\subsection{Test data}

For test purposes five undirected graphs are defined in the form of
adjacency lists:
\begin{description}
\item[g1:] The ``class'' example graph.
\begin{mathematica}
g1 = {{2, 9}, {1, 3, 7, 10}, {2, 4, 5, 6}, {3, 5}, {3, 4}, {3, 7},
      {2, 6, 8, 9}, {7, 9}, {1, 7, 8, 10}, {2, 9}};
\end{mathematica}

\item[g2:] The ``class'' example disconnected by substituting edges $(2,3)$
  and $(6,3)$ by $(2,8)$ and $(6,8)$, accordingly.
\begin{mathematica}
g2 = {{2, 9}, {1, 7, 8, 10}, {4, 5}, {3, 5}, {3, 4}, {7, 8},
      {2, 6, 8, 9}, {2, 6, 7, 9}, {1, 7, 8, 10}, {2, 9}};
\end{mathematica}

\item[g3:] The ``class'' example with edge $(7,9)$ removed.
\begin{mathematica}
g3 = {{2, 9}, {1, 3, 7, 10}, {2, 4, 5, 6}, {3, 5}, {3, 4}, {3, 7},
      {2, 6, 8}, {7, 9}, {1, 8, 10}, {2, 9}};
\end{mathematica}
These three graphs are shown in figure~\ref{g1}.
\figwiii{g1}{g2}{g3}{Test graphs: (a)~\texttt{g1} -- ``class'' example;
  (b)~\texttt{g2} -- similar to \texttt{g1} but disconnected;
  (c)~\texttt{g3} -- \texttt{g1} with edge $(7,9)$ removed.}


\item[g4:] A simple six-vertex graph.
\begin{mathematica}
g4 = {{2, 6}, {1, 3, 4, 6}, {2, 4}, {2, 3, 5, 6}, {4, 6}, {1, 2, 4, 5}};
\end{mathematica}
\item[g5:] A rather complicated twelve-vertex graph.
\begin{mathematica}
g5 = {{2, 8}, {1, 3, 4, 5, 11, 12}, {2, 4, 6, 7}, {2, 3, 6, 7}, {2, 6, 7, 8},
      {3, 4, 5, 7}, {3, 4, 5, 6}, {1, 5, 9, 10, 11, 12}, {8, 10},
      {8, 9, 11, 12}, {2, 8, 10, 12}, {2, 8, 10, 11}};
\end{mathematica}
These two graphs are presented in figure~\ref{g4}.
\figii{g4}{g5}{Test graphs: (a)~\texttt{g4}; (b)~\texttt{g5}.}
\end{description}


Diagrams were created by a function \texttt{showadj[adj]} which
plots a graph given by adjacency lists \texttt{adj} using circular
embedding.  It uses two functions from \textit{Combinatorica} package.
\begin{mathematica}
showadj[adj_List] := ShowLabeledGraph[ FromAdjacencyLists[adj] ];
\end{mathematica}

\begin{comment}
\begin{mathematica}
Display["g1.eps", showadj[g1], "EPS"];
\end{mathematica}
\begin{mathematica}
Display["g2.eps", showadj[g2], "EPS"];
\end{mathematica}
\begin{mathematica}
Display["g3.eps", showadj[g3], "EPS"];
\end{mathematica}
\begin{mathematica}
Display["g4.eps", showadj[g4], "EPS"];
\end{mathematica}
\begin{mathematica}
Display["g5.eps", showadj[g5], "EPS"];
\end{mathematica}
\end{comment}

To facilitate the testing a list of all test adjacency lists is defined.
It allows performing different operations on a whole set with simple map
function.
\begin{mathematica}
g = {g1, g2, g3, g4, g5};
\end{mathematica}

Using it one can present the test graphs in (I hope not overly) fancy tabular way.
\begin{mathematica}
g // TableForm[#, TableHeadings->{Table["g" <> ToString[i] <> ":    ",
  {i, 5}], Table["v" <> ToString[i], {i, 12}]}, TableSpacing->{2,2}]&
.
//TableForm=          v1  v2  v3  v4  v5  v6  v7  v8  v9  v10  v11  v12
                          1   2               2       1
                          3   4               6       7
                      2   7   5   3   3   3   8   7   8   2
             g1:      9   10  6   5   4   7   9   9   10  9


                          1                   2   2   1
                          7                   6   6   7
                      2   8   4   3   3   7   8   7   8   2
             g2:      9   10  5   5   4   8   9   9   10  9


                          1   2
                          3   4               2       1
                      2   7   5   3   3   3   6   7   8   2
             g3:      9   10  6   5   4   7   8   9   10  9


                          1       2       1
                          3       3       2
                      2   4   2   5   4   4
             g4:      6   6   4   6   6   5


                          1                       1
                          3                       5
                          4   2   2   2   3   3   9       8    2    2
                          5   4   3   6   4   4   10      9    8    8
                      2   11  6   6   7   5   5   11  8   11   10   10
             g5:      8   12  7   7   8   7   6   12  10  12   12   11
\end{mathematica}

\subsection{Supplementary functions' tests}

Mapping the function \texttt{depthfirstsearch} reveals that graph ``g2''
is not connected because not all ten vertices were visited.
\begin{mathematica}
Map[ depthfirstsearch[#, 1]&, g] // TableForm
.
//TableForm= 1   2   3   4   5   6   7    8   9   10

             1   2   7   6   8   9   10

             1   2   3   4   5   6   7    8   9   10

             1   2   3   4   5   6

             1   2   3   4   6   5   7    8   9   10   11   12
\end{mathematica}

This result is shown explicitly by the \texttt{connectedQ} function
(\verb+x /@ y+ is a handy notation for \verb+Map[x, y]+):
\begin{mathematica}
connectedQ /@ g
.
= {True, False, True, True, True}
\end{mathematica}

All test graphs are undirected:
\begin{mathematica}
undirectedQ /@ g
.
= {True, True, True, True, True}
\end{mathematica}

Let us test for existence of Euler ciruits. Graphs \texttt{g2} and
\texttt{g3} are disqualified because of lack of connectivity and
existence of odd vertex degrees, accordingly:
\begin{mathematica}
eulerianQ /@ g
.
= {True, False, False, True, True}
\end{mathematica}

\subsection{Euler circuit function's test}
Running the main function \texttt{euler} on the test graphs gives the following
lists of edges:
\begin{mathematica}
euler[#, 1]& /@ g // TableForm[#, TableDepth->1]&
.
             {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 3}, {3, 6}, {6, 7}, {7, 2}, {2, 10}, {10, 9},
//TableForm= >   {9, 7}, {7, 8}, {8, 9}, {9, 1}}

             euler[{{2, 9}, {1, 7, 8, 10}, {4, 5}, {3, 5}, {3, 4}, {7, 8}, {2, 6, 8, 9},
             >    {2, 6, 7, 9}, {1, 7, 8, 10}, {2, 9}}, 1]

             euler[{{2, 9}, {1, 3, 7, 10}, {2, 4, 5, 6}, {3, 5}, {3, 4}, {3, 7}, {2, 6, 8}, {7, 9},
             >    {1, 8, 10}, {2, 9}}, 1]

             {{1, 2}, {2, 3}, {3, 4}, {4, 2}, {2, 6}, {6, 4}, {4, 5}, {5, 6}, {6, 1}}

             {{1, 2}, {2, 3}, {3, 4}, {4, 2}, {2, 5}, {5, 6}, {6, 3}, {3, 7}, {7, 4}, {4, 6},
             >   {6, 7}, {7, 5}, {5, 8}, {8, 9}, {9, 10}, {10, 8}, {8, 11}, {11, 2}, {2, 12},
             >   {12, 10}, {10, 11}, {11, 12}, {12, 8}, {8, 1}}
\end{mathematica}
If a graph does not have a circuit then the function returns
unevaluated, in accordance with a general \Mma{} behavior.
Edge list representation allows representing the circuit in the form of
a directed graph.  The results are shown in figure~\ref{g1e}.
\figwiii{g1e}{g4e}{g5e}{Euler circuits of graphs (a)~\texttt{g1},
  (b)~\texttt{g4}, and (c)~\texttt{g5}.}

\begin{comment}
\begin{mathematica}
Display[#[[2]] <> ".eps", ShowLabeledGraph[ FromOrderedPairs[euler[#[[1]], 1],
  (FromOrderedPairs[#[[1]]]) [[2]] ], Directed], "EPS" ]& /@
  {{g1, "g1e"}, {g4, "g4e"}, {g5, "g5e"}};
.
MapAt::part: Part {2, 6, 8, 9} of {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, <<8>>,
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}} does not exist.

MapAt::part: Part {2, 3, 5, 6} of {{0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0},
     <<2>>, {0, 0, 0, 0, 0, 0}} does not exist.

MapAt::part: Part {1, 5, 9, 10, 11, 12} of
    {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, <<10>>, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}
     does not exist.

General::stop: Further output of MapAt::part will be suppressed during this calculation.
\end{mathematica}
\end{comment}

When only a list of visited vertices is needed, one can use the
following simple operation extracting the head vertex from each edge
(example for graph \texttt{g4}):
\begin{mathematica}
#[[1]]& /@ euler[g4, 1]
.
= {1, 2, 3, 4, 2, 6, 4, 5, 6}
\end{mathematica}
Or, if it is necessary to have the start vertex repeated at the end of
the list:
\begin{mathematica}
Append[ #, #[[1]] ]&  [ #[[1]]& /@ euler[g4, 1] ]
.
= {1, 2, 3, 4, 2, 6, 4, 5, 6, 1}
\end{mathematica}
\begin{implementation}
The above statements use anonymous functions (denoted by trailing
\verb+&+) with an argument accesible by the \verb+#+ symbol.
\end{implementation}

Let us take a closer look at the inner working of the function
\texttt{euler} for graph \texttt{g4} (the simplest, but not trivial case):
\begin{mathematica}
euler[g4, 1, Debug]
.
visit(1)
  while 1: w = 2, pathout = {}
  visit(2)
    while 2: w = 3, pathout = {}
    visit(3)
      while 3: w = 4, pathout = {}
      visit(4)
        while 4: w = 2, pathout = {}
        visit(2)
          while 2: w = 6, pathout = {}
          visit(6)
            while 6: w = 1, pathout = {}
            visit(1)
            return 1 = {}
            while 6: w = 4, pathout = {{6, 1}}
            visit(4)
              while 4: w = 5, pathout = {}
              visit(5)
                while 5: w = 6, pathout = {}
                visit(6)
                return 6 = {}
              return 5 = {{5, 6}}
            return 4 = {{4, 5}, {5, 6}}
          return 6 = {{6, 4}, {4, 5}, {5, 6}, {6, 1}}
        return 2 = {{2, 6}, {6, 4}, {4, 5}, {5, 6}, {6, 1}}
      return 4 = {{4, 2}, {2, 6}, {6, 4}, {4, 5}, {5, 6}, {6, 1}}
    return 3 = {{3, 4}, {4, 2}, {2, 6}, {6, 4}, {4, 5}, {5, 6}, {6, 1}}
  return 2 = {{2, 3}, {3, 4}, {4, 2}, {2, 6}, {6, 4}, {4, 5}, {5, 6}, {6, 1}}
return 1 = {{1, 2}, {2, 3}, {3, 4}, {4, 2}, {2, 6}, {6, 4}, {4, 5}, {5, 6}, {6, 1}}

= {{1, 2}, {2, 3}, {3, 4}, {4, 2}, {2, 6}, {6, 4}, {4, 5}, {5, 6}, {6, 1}}
\end{mathematica}
The function skips over the small $(6,4,5,6)$ cycle and after reaching the
dead end 1, which can be only the point where the cycle searching started
(only there the degree of the vertex will be not even) it backtraces to
the last vertex having some adjacent unvisited edges (6 in this case)
where it stores the way out in the \texttt{cycle} variable.  After visting this
small cycle both parts of a circuit are patched together and the
algorithm tries to find some more unvisited edges by backtracing.
During this process the already visited edges are being stacked at the
beginning of the circuit.

On the ``class'' example the algorithm operates in the following way
(starting vertex is chosen to maximize number of successful backtraces):
\begin{mathematica}
euler[g1, 6, Debug]
.
visit(6)
  while 6: w = 3, pathout = {}
  visit(3)
    while 3: w = 2, pathout = {}
    visit(2)
      while 2: w = 1, pathout = {}
      visit(1)
        while 1: w = 9, pathout = {}
        visit(9)
          while 9: w = 7, pathout = {}
          visit(7)
            while 7: w = 2, pathout = {}
            visit(2)
              while 2: w = 10, pathout = {}
              visit(10)
                while 10: w = 9, pathout = {}
                visit(9)
                  while 9: w = 8, pathout = {}
                  visit(8)
                    while 8: w = 7, pathout = {}
                    visit(7)
                      while 7: w = 6, pathout = {}
                      visit(6)
                      return 6 = {}
                    return 7 = {{7, 6}}
                  return 8 = {{8, 7}, {7, 6}}
                return 9 = {{9, 8}, {8, 7}, {7, 6}}
              return 10 = {{10, 9}, {9, 8}, {8, 7}, {7, 6}}
            return 2 = {{2, 10}, {10, 9}, {9, 8}, {8, 7}, {7, 6}}
          return 7 = {{7, 2}, {2, 10}, {10, 9}, {9, 8}, {8, 7}, {7, 6}}
        return 9 = {{9, 7}, {7, 2}, {2, 10}, {10, 9}, {9, 8}, {8, 7}, {7, 6}}
      return 1 = {{1, 9}, {9, 7}, {7, 2}, {2, 10}, {10, 9}, {9, 8}, {8, 7}, {7, 6}}
    return 2 = {{2, 1}, {1, 9}, {9, 7}, {7, 2}, {2, 10}, {10, 9}, {9, 8}, {8, 7}, {7, 6}}
    while 3: w = 4, pathout = {{3, 2}, {2, 1}, {1, 9}, {9, 7}, {7, 2}, {2, 10}, {10, 9}, {9, 8},
>    {8, 7}, {7, 6}}
    visit(4)
      while 4: w = 5, pathout = {}
      visit(5)
        while 5: w = 3, pathout = {}
        visit(3)
        return 3 = {}
      return 5 = {{5, 3}}
    return 4 = {{4, 5}, {5, 3}}
  return 3 = {{3, 4}, {4, 5}, {5, 3}, {3, 2}, {2, 1}, {1, 9}, {9, 7}, {7, 2}, {2, 10}, {10, 9},
>    {9, 8}, {8, 7}, {7, 6}}
return 6 = {{6, 3}, {3, 4}, {4, 5}, {5, 3}, {3, 2}, {2, 1}, {1, 9}, {9, 7}, {7, 2}, {2, 10},
>    {10, 9}, {9, 8}, {8, 7}, {7, 6}}

= {{6, 3}, {3, 4}, {4, 5}, {5, 3}, {3, 2}, {2, 1}, {1, 9}, {9, 7}, {7, 2}, {2, 10}, {10, 9},
>    {9, 8}, {8, 7}, {7, 6}}
\end{mathematica}


%====================================================================
%====================================================================
\section{Discussion}

\subsection{Pidgin--Pascal Programs}

\begin{alltt}
procedure dfs(v);
begin
  \textit{mark v as old};
  \textit{add v to visited list};
  for \textit{all new vertices w on adjacency list of v} do
    dfs(w);
end;

function depthfirstsearch(v);
begin
  visited := {};
  \textit{mark all vertices as new};
  dfs(v);
  return visited;
end;
\end{alltt}

\begin{alltt}
function connectedQ(g);
begin
  return (\textit{length of depthfirstsearch(g) list is equal to the number of all vertices});
end;
\end{alltt}

\begin{alltt}
function undirectedQ(g);
begin
  result := True;
  for each vertex v do
    for \textit{each vertex w on the adjacency list of vertex v} do
      result := result and \textit{vertex v exists on adjacency list of vertex w};
  return result;
end;
\end{alltt}


\begin{alltt}
function eulerianQ(g);
begin
  return (undirectedQ(g) and connectedQ(g) and \textit{all vertex degrees are even});
end;
\end{alltt}

\begin{alltt}
function visit(v);
begin
  pathout := {};
  for \textit{all edges (v,w) adjacent to v and marked as new} do begin
    \textit{mark edge (v,w) as old};
    pathout := concatenation of (v,w), visit(w) and pathout;
  end;
  return pathout;
end;

function euler(v);
begin
  \textit{mark all edges as new};
  return visit(v);
end;
\end{alltt}

\subsection{Efficiency}
In the main proposed algorithm (function \texttt{euler}) each edge is
visited at most once, so its complexity can be estimated as $\Theta(m)$,
where $m$ is a number of edges of a graph.  The auxiliary predicates
have also $\Theta(n)$ complexity, though e.g., \texttt{undirectedQ}
predicate ``visits'' each edge twice.

High level languages like \Mma{} are usually not used where efficiency is a
crucial issue.  \Mma{} language is interpreted, not compiled, but availabilty
of over 900 optimized builtin functions causes that many tasks are performed
quite quickly.

For me, the biggest advantage of using it is a possibility of creating
documents like this one, integrating working ``live'' code which can be
evaluated at any time, its description and graphics results.  Whole data
about this project is contained in a single file.  It is possible thanks
to the Emacs editor \TeX/\Mma{} mode interfacing directly with \Mma{}
and producing ready-to-compile \TeX{} scripts.
%====================================================================
%====================================================================

\end{document}

\begin{mathematica}
  cyclegraph[l_List, Graph[e_,v_]] := FromOrderedPairs[ Table[{l[[i]],
    l[[ Mod[i, Length[l]] + 1 ]]}, {i, Length[l]}], v ];
\end{mathematica}

\begin{mathematica}
edgecount[adj_List] := Apply[ Plus, Map[ Length, g1adjacencylist ] ] / 2;
\end{mathematica}
\begin{mathematica}
g4
.
= {{2, 6}, {1, 3, 4, 6}, {2, 4}, {2, 3, 5, 6}, {4, 6}, {1, 2, 4, 5}}
\end{mathematica}
\begin{mathematica}
Count[g4[[2]], 7]
.
= 0
\end{mathematica}
\begin{mathematica}
g4
.
= {{2, 6}, {1, 3, 4, 6}, {2, 4}, {2, 3, 5, 6}, {4, 6}, {1, 2, 4, 5}}
\end{mathematica}

\begin{mathematica}
eulerianQ[ {{2, 6}, {1, 3, 4, 6}, {2, 4}, {2, 3, 5, 6}, {4}, {1, 2, 4, 5}}]
.
= False
\end{mathematica}