tikz automata edges overlap

Question

I have two states positioned horizontally and need to connect them i.e. A -> B and A <- B, how can I position the edges in a way that they don't overlap and my diagram doesn't become a A <-> B but instead it is visible that one can navigate from one another and be able to place the input message above and below.

 (APPEND_COL) edge[???] node[anchor=east,above,xshift=+3.0em]{delete column} (DELETE_COL)
 (DELETE_COL) edge[???] node[anchor=east,above,xshift=+3.0em]{append column} (APPEND_COL)

I have tried setting ??? to above, below, bend left=20, bend right=20 but none of these produces the intended behavior ...

UPDATE: ok here the full code, and another thing, how can I make the loops left and right not so huge?

\begin{tikzpicture}[->,>=stealth']

 % State: FULL_QR
 \node[initial above,state,anchor=north] (FULL_QR)
 {\begin{tabular}{l}
  Recompute QR \\
 \end{tabular}};

 % State: Append column update
 \node[state,           % layout (defined above)
  below left of=FULL_QR,% Position is to the right of FULL_QR
  node distance=5.0cm,  % distance to FULL_QR
  anchor=south] (APPEND_COL) % posistion relative to the center of the 'box'
 {%
 \begin{tabular}{l}     % content
  Append column \\
  \ \ QR update
 \end{tabular}
 };

 % State: Delete column update
 \node[state,            % layout (defined above)
  below right of=FULL_QR,% Position is to the right of FULL_QR
  node distance=5.0cm,   % distance to FULL_QR
  anchor=south] (DELETE_COL) % posistion relative to the center of the 'box'
 {%
 \begin{tabular}{l}      % content
  Delete column \\
  \ \ QR update
 \end{tabular}
 };

 % State: Append column update
 \node[state,                % layout (defined above)
  below right of=APPEND_COL, % Position is to the bottom of APPEND_COL
  node distance=5.0cm,       % distance to APPEND_COL
  anchor=south] (APPEND_ROW) % posistion relative to the center of the 'box'
 {%
 \begin{tabular}{l}          % content
  Append row \\
  \ \ QR update
 \end{tabular}
 };

 % draw the paths and and print some Text below/above the graph
 \path (FULL_QR) edge[bend right=20] node[anchor=west,above,xshift=-3.0em]{append column} (APPEND_COL)
       (FULL_QR) edge[bend left=20] node[anchor=east,above,xshift=+3.0em]{delete
 column} (DELETE_COL)
       (APPEND_COL) edge[bend right=20]
 node[anchor=west,below,xshift=-3.0em]{append row} (APPEND_ROW)
       (DELETE_COL) edge[bend left=20]
 node[anchor=east,below,xshift=+3.0em]{append row} (APPEND_ROW)
       (APPEND_COL) edge[above]
       node[anchor=west,above,xshift=+0.0em]{delete column} (DELETE_COL)
       (DELETE_COL) edge[below]
       node[anchor=east,below,xshift=+0.0em]{append column} (APPEND_COL)
       (APPEND_COL) edge[loop left] node[anchor=west,above,yshift=+1.5em,xshift=+2.0em]{append column}
       (APPEND_COL) (DELETE_COL) edge[loop right] node[anchor=east,above,yshift=+1.5em,xshift=-2.0em]{delete column}
       (DELETE_COL);

\end{tikzpicture}

Answer 1

Since the connecting lines have opposing directions, you'll have to use bend left=<value> for both lines, not bend left for one and bend right for the other:

    \documentclass{article}

    \usepackage{pgf}
    \usepackage{tikz}
    \usetikzlibrary{arrows,automata}
    \usepackage[latin1]{inputenc}
    \begin{document}
\begin{tikzpicture}[->,>=stealth']

 % State: FULL_QR
 \node[initial above,state,anchor=north] (FULL_QR)
 {\begin{tabular}{l}
  Recompute QR \\
 \end{tabular}};

 % State: Append column update
 \node[state,           % layout (defined above)
  below left of=FULL_QR,% Position is to the right of FULL_QR
  node distance=5.0cm,  % distance to FULL_QR
  anchor=south] (APPEND_COL) % posistion relative to the center of the 'box'
 {%
 \begin{tabular}{l}     % content
  Append column \\
  \ \ QR update
 \end{tabular}
 };

 % State: Delete column update
 \node[state,            % layout (defined above)
  below right of=FULL_QR,% Position is to the right of FULL_QR
  node distance=5.0cm,   % distance to FULL_QR
  anchor=south] (DELETE_COL) % posistion relative to the center of the 'box'
 {%
 \begin{tabular}{l}      % content
  Delete column \\
  \ \ QR update
 \end{tabular}
 };

 % State: Append column update
 \node[state,                % layout (defined above)
  below right of=APPEND_COL, % Position is to the bottom of APPEND_COL
  node distance=5.0cm,       % distance to APPEND_COL
  anchor=south] (APPEND_ROW) % posistion relative to the center of the 'box'
 {%
 \begin{tabular}{l}          % content
  Append row \\
  \ \ QR update
 \end{tabular}
 };

 % draw the paths and and print some Text below/above the graph
 \path (FULL_QR) edge[bend right=20] node[anchor=west,above,xshift=-3.0em]{append column} (APPEND_COL)
       (FULL_QR) edge[bend left=20] node[anchor=east,above,xshift=+3.0em]{delete
 column} (DELETE_COL)
       (APPEND_COL) edge[bend right=20]
 node[anchor=west,below,xshift=-3.0em]{append row} (APPEND_ROW)
       (DELETE_COL) edge[bend left=20]
 node[anchor=east,below,xshift=+3.0em]{append row} (APPEND_ROW)
       (APPEND_COL) edge[above, bend left=5]
       node[anchor=west,above,xshift=+0.0em]{delete column} (DELETE_COL)
       (DELETE_COL) edge[below, bend left=5]
       node[anchor=east,below,xshift=+0.0em]{append column} (APPEND_COL)
       (APPEND_COL) edge[loop left] node[anchor=west,above,yshift=+1.5em,xshift=+2.0em]{append column}
       (APPEND_COL) (DELETE_COL) edge[loop right] node[anchor=east,above,yshift=+1.5em,xshift=-2.0em]{delete column}
       (DELETE_COL);

\end{tikzpicture}


    \end{document}