% Copyright 2010 by Till Tantau
%
% This file may be distributed and/or modified
%
% 1. under the LaTeX Project Public License and/or
% 2. under the GNU Public License.
%
% See the file doc/generic/pgf/licenses/LICENSE for more details.

\ProvidesFileRCS[v\pgfversion] $Header: /cvsroot/pgf/pgf/generic/pgf/frontendlayer/tikz/libraries/tikzlibrarygraphs.code.tex,v 1.3 2010/09/27 14:35:05 tantau Exp $


% 
% Interface keys 
%

\tikzset{
  graphs/new edge directed/.code n args={3}{\path (#1) edge[->,#3] (#2);},
  graphs/new edge undirected/.code n args={3}{\path (#1) edge[-,#3] (#2);},
  graphs/new edge bidirected/.code n args={3}{\path (#1) edge[<->,#3] (#2);},
  graphs/new edge back directed/.style n args={3}{new edge directed={#2}{#1}{#3}},
  graphs/default edge kind/.initial=undirected
}



\def\tikz@lib@graph@parser{%
  \pgfutil@ifnextchar[{\tikz@lib@graph@parser@}{\tikz@lib@graph@parser@[]}%]
}

\long\def\tikz@lib@graph@parser@[#1]#2{%
  \pgfutil@ifnextchar[{\tikz@lib@graph@parser@opt[#1]{#2}}{\tikz@lib@graph@parser@opt[#1]{#2}[]}%]
}

\long\def\tikz@lib@graph@parser@opt[#1]#2[#3]{%
  \scope[#1]%
    \let\tikz@lib@graph@options\pgfutil@empty%
    \let\tikz@lib@graph@node@list\pgfutil@empty%
    \tikz@lib@graph@parse@group{#2}[#3]%
    \let\tikz@lg@do=\tikz@lib@graph@cleanup%
    \tikz@lib@graph@node@list%
  \endscope%
  \tikz@lib@graph@parser@done%
}




\long\def\tikz@lib@graph@parse@group#1{%
  \let\tikz@lib@graph@group@c\pgfutil@empty%
  \let\tikz@lib@graph@group@cont\pgfutil@empty%
  \let\tikz@lib@graph@group@conta\pgfutil@empty%
  \tikz@lib@graph@par#1\par\pgf@stop@eogroup%
}



% 
% Remove \par 
%

\long\def\tikz@lib@graph@par#1\par{%
  \pgfutil@ifnextchar\pgf@stop@eogroup{%
    \expandafter\tikz@lib@graph@encloser\tikz@lib@graph@group@c#1[}{%
    \expandafter\def\expandafter\tikz@lib@graph@group@c\expandafter{\tikz@lib@graph@group@c#1}%
    \tikz@lib@graph@par%
  }%
}


% 
% Replace ...[...]... by ...[{...}]...
% 
\def\tikz@lib@graph@encloser#1[{%
  \pgfutil@ifnextchar\pgf@stop@eogroup{%
    \expandafter\tikz@lib@graph@semi\tikz@lib@graph@group@cont#1;%
  }{%
    \expandafter\def\expandafter\tikz@lib@graph@group@cont\expandafter{\tikz@lib@graph@group@cont#1[}%]
    \tikz@lib@graph@encloser@cont%
  }%
}

\def\tikz@lib@graph@encloser@cont#1]#2[{%
  \pgfutil@ifnextchar\pgf@stop@eogroup{%
    \expandafter\tikz@lib@graph@semi\tikz@lib@graph@group@cont{#1}]#2;}{%
    \expandafter\def\expandafter\tikz@lib@graph@group@cont\expandafter{\tikz@lib@graph@group@cont{#1}]#2[}%
    \tikz@lib@graph@encloser@cont}%
}


% 
% Replace ; by , 
%

\def\tikz@lib@graph@semi#1;{%
  \pgfutil@ifnextchar\pgf@stop@eogroup{%
    \expandafter\tikz@lib@graph@main@parser\tikz@lib@graph@group@conta#1,}{%
    \expandafter\def\expandafter\tikz@lib@graph@group@conta\expandafter{\tikz@lib@graph@group@conta#1,}%
    \tikz@lib@graph@semi%
  }%
}



% 
% Main parse 
%

\def\tikz@lib@graph@main@parser#1,{%
  \begingroup%
    \let\tikz@lib@graph@stored@actions\pgfutil@empty%
    \let\tikz@lib@graph@node@list\pgfutil@empty% reset
    \tikz@lib@graph@parse@one#1-\pgf@stop@eodashes%
}


\def\tikz@lib@graph@parse@one{%
  \pgfutil@ifnextchar\bgroup\tikz@lib@graph@scope\tikz@lib@graph@node%
}




% A normal node

\def\tikz@lib@graph@node#1-{%
  % Detect trailing <
  \tikz@lib@graph@@node#1<\pgf@stop%
}

\def\tikz@lib@graph@@node#1<#2\pgf@stop%
{
  % 
  % #1 will be a node (not a group)
  % 
  % Syntax: node name [options]
  % 
  % Grab node name
  \tikz@lib@graph@grab@name#1[\pgf@stop%
  \tikz@lib@graph@stored@actions%
  \pgfutil@ifnextchar\pgf@stop@eodashes{%
    \tikz@lib@graph@graph@done%
  }{%
    % 
    % Now, get arrow kind 
    % 
    \def\pgf@test{#2}%
    \ifx\pgf@test\pgfutil@empty%
      \expandafter\tikz@lib@graph@no@back@arrow%
    \else%
      \expandafter\tikz@lib@graph@back@arrow%
    \fi%
  }%
}

\def\tikz@lib@graph@no@back@arrow{%
  \pgfutil@ifnextchar>\tikz@lib@graph@forward@arrow{%
    \pgfutil@ifnextchar-\tikz@lib@graph@undirected@arrow{%
      \PackageError{graphs library}{One of the arrow types <-, --, ->, or <-> expected}{}%
      \tikz@lib@graph@undirected@arrow%
    }%
  }%
}

\def\tikz@lib@graph@undirected@arrow-{%
  \def\tikz@lib@graph@arrow@type{undirected}%
  \tikz@lib@graph@after@arrow%
}

\def\tikz@lib@graph@forward@arrow>{%
  \def\tikz@lib@graph@arrow@type{directed}%
  \tikz@lib@graph@after@arrow%
}

\def\tikz@lib@graph@bi@arrow>{%
  \def\tikz@lib@graph@arrow@type{bidirected}%
  \tikz@lib@graph@after@arrow%
}

\def\tikz@lib@graph@back@arrow{%
  \pgfutil@ifnextchar>{\tikz@lib@graph@bi@arrow}{%
    \def\tikz@lib@graph@arrow@type{back directed}%
    \tikz@lib@graph@after@arrow%
  }%
}

\def\tikz@lib@graph@after@arrow{%
  \pgfutil@ifnextchar[{\tikz@lib@graph@after@arrow@opt}{\tikz@lib@graph@after@arrow@opt[]}%]
}

\def\tikz@lib@graph@after@arrow@opt[#1]{%
  % 
  % Ok, first recolor 
  % 
  \pgfkeys{/tikz/graph node/recolor in by=in''}
  \pgfkeys{/tikz/graph node/recolor out by=out'}
  % Save action for next node
  \expandafter\def\expandafter\tikz@lib@graph@stored@actions\expandafter{%
    \expandafter\tikz@lib@graph@joiner\expandafter{\tikz@lib@graph@arrow@type}{#1}}%
  \tikz@lib@graph@parse@one%
}

\def\tikz@lib@graph@joiner#1#2{%
  \pgfkeys{/tikz/graph node/recolor in by=in'}
  \pgfkeys{/tikz/graph node/recolor in'' by=in}
  {%
    \pgfkeyssetvalue{/tikz/graphs/default edge kind}{#1}%
    \def\pgf@temp{#2}%
    \ifx\pgf@temp\pgfutil@empty%
      \pgfkeysgetvalue{/tikz/join connector}\pgf@temp%
    \fi%
    \expandafter\tikz@lg@do@connector\expandafter{\pgf@temp}%
  }%
  \pgfkeys{/tikz/graph node/!in',/tikz/graph node/!out'}
}

\def\tikz@lib@graph@graph@done\pgf@stop@eodashes{%
    % Get node list outside...
    \expandafter%  
  \endgroup%
  \expandafter\expandafter\expandafter\def%
  \expandafter\expandafter\expandafter\tikz@lib@graph@node@list%
  \expandafter\expandafter\expandafter{\expandafter\tikz@lib@graph@node@list\tikz@lib@graph@node@list}%
  \pgfutil@ifnextchar\pgf@stop@eogroup%
  \tikz@lib@graph@graph@group@done%
  \tikz@lib@graph@main@parser%
}

\def\tikz@lib@graph@graph@group@done\pgf@stop@eogroup[#1]{%
  {%
    \def\pgf@temp{#1}%
    \ifx\pgf@temp\pgfutil@empty%
      \pgfkeysgetvalue{/tikz/connector}\pgf@temp%
    \fi%
    \expandafter\tikz@lg@do@connector\expandafter{\pgf@temp}  
  }%
}

\def\tikz@lg@do@connector#1{%
  \tikzset{/tikz/connectors/.cd,#1}
}



%
% Handle node
%
\def\tikz@lib@graph@grab@name#1[{%
  \tikz@lib@graph@paren@check#1\pgf@stop%
  \let\tikz@lib@graph@as\tikz@lib@graph@as@default%
  \pgfutil@ifnextchar\pgf@stop{%
    \ifx\tikz@lib@graph@name\pgfutil@empty%
    \else
      \expandafter\tikz@lib@graph@noskip%
    \fi%
  }{\tikz@lib@graph@node@opt[}%
}
\def\tikz@lib@graph@noskip{\tikz@lib@graph@node@opt[][}%]

\def\tikz@lib@graph@as@default{%
  \expandafter\tikz@lib@graph@typesetter\tikz@lib@graph@name\pgf@stop%
}

\newif\iftikz@lib@graph@is@reference

\def\tikz@lib@graph@paren@check{%
  \pgfutil@ifnextchar({\tikz@lib@graph@paren@read}{\tikz@lib@graph@noparen@read}%)
}
\def\tikz@lib@graph@paren@read(#1)#2\pgf@stop{%
  \pgfkeys@spdef\tikz@lib@graph@name{#1}%
  \tikz@lib@graph@is@referencetrue%
}
\def\tikz@lib@graph@noparen@read#1\pgf@stop{%
  \pgfkeys@spdef\tikz@lib@graph@name{#1}%
  \tikz@lib@graph@is@referencefalse%
}


\def\tikz@lib@graph@node@opt[#1]#2[\pgf@stop{%
  {%
    \edef\tikz@lib@graph@node@list{\noexpand\tikz@lg@do{\tikz@lib@graph@name}}%
    \tikz@lg@if@local@node{\tikz@lib@graph@name}%
    {\tikzset{/tikz/graph node/.cd,in,out,#1}}%
    {%
      \tikz@lg@init@color{\tikz@lib@graph@name}{\tikz@lgc@all@true\tikz@lgc@in@true\tikz@lgc@out@true}%
      \iftikz@lib@graph@is@reference%
        \tikzset{/tikz/graph node/.cd,#1}%
      \else%
        \node [name=\tikz@lib@graph@name,/tikz/graph node/.cd,#1] {\tikz@lib@graph@as};%
      \fi%
    }%
  }%
  \expandafter\expandafter\expandafter\def%
  \expandafter\expandafter\expandafter\tikz@lib@graph@node@list%
  \expandafter\expandafter\expandafter{%
    \expandafter\tikz@lib@graph@node@list\expandafter\tikz@lg@do\expandafter{\tikz@lib@graph@name}}%
}


\def\tikz@lib@graph@typeset@def#1 as #2\pgf@stop{
  \def\tikz@lib@graph@typesetter#1\pgf@stop{#2}
}

\tikzset{
  graph typeset/.code=\tikz@lib@graph@typeset@def#1\pgf@stop,
  math graph nodes/.style={graph typeset=#1 as $#1$},
}

\def\tikz@lib@graph@typesetter#1\pgf@stop{#1}


% 
% Handle scope 
%
\def\tikz@lib@graph@scope#1{%
  \pgfutil@ifnextchar[{\tikz@lib@graph@scope@opt{#1}}{\tikz@lib@graph@scope@opt{#1}[]}%]
}

\def\tikz@lib@graph@scope@opt#1[#2]{%
  \begingroup
    \let\tikz@lib@graph@node@list\pgfutil@empty%
    \tikz@lib@graph@parse@group{#1}[#2]%
    \expandafter%  
  \endgroup%
  \expandafter\expandafter\expandafter\def%
  \expandafter\expandafter\expandafter\tikz@lib@graph@node@list%
  \expandafter\expandafter\expandafter{\expandafter\tikz@lib@graph@node@list\tikz@lib@graph@node@list}%
  \tikz@lib@graph@stored@actions%
  \pgfutil@ifnextchar-{\tikz@lib@graph@scope@minus}{%
    \pgfutil@ifnextchar<{\tikz@lib@graph@scope@less}{%
      \PackageError{graphs library}{One of the arrow types <-, --, ->,
        or <-> expected}{}%
    }%
  }%
}

\def\tikz@lib@graph@scope@minus-{
  \pgfutil@ifnextchar>\tikz@lib@graph@forward@arrow{%
    \pgfutil@ifnextchar-\tikz@lib@graph@undirected@arrow{%
      \pgfutil@ifnextchar\pgf@stop@eodashes\tikz@lib@graph@graph@done{%
        \PackageError{graphs library}{One of the arrow types <-, --, ->, or <-> expected}{}%
        \tikz@lib@graph@undirected@arrow%
      }%
    }%
  }%
}

\def\tikz@lib@graph@scope@less<-{\tikz@lib@graph@back@arrow}%


%
% Colors
% 

\tikzset{
  graph node/.unknown/.code={%
    \let\tikz@key\pgfkeyscurrentname% 
    \pgfkeys{/tikz/\tikz@key={#1}}%
  },
  graph node/as/.code=\def\tikz@lib@graph@as{#1}%
}


\tikzset{%
  new graph color/.style={%
    /utils/exec=\expandafter\newif\csname iftikz@lgc@#1@\endcsname,
    graph node/#1/.code={%
      \edef\tikz@lg@col{\expandafter\noexpand\csname tikz@lgc@#1@true\endcsname}%
      \let\tikz@lg@do\tikz@lg@colorize%
      \tikz@lib@graph@node@list%
    },
    graph node/!#1/.code={%
      \edef\tikz@lg@old@col{\expandafter\noexpand\csname tikz@lgc@#1@true\endcsname}%
      \def\tikz@lg@new@col{}%
      \let\tikz@lg@do\tikz@lg@change@color%
      \tikz@lib@graph@node@list%
    },
    graph node/recolor #1 by/.code={%
      \edef\tikz@lg@old@col{\expandafter\noexpand\csname tikz@lgc@#1@true\endcsname}%
      \edef\tikz@lg@new@col{\expandafter\noexpand\csname tikz@lgc@##1@true\endcsname}%
      \let\tikz@lg@do\tikz@lg@change@color%
      \tikz@lib@graph@node@list%
    },
    graph node/not #1/.style=!#1,
  },
  new graph color=in,
  new graph color=in',
  new graph color=in'',
  new graph color=out,
  new graph color=out',
  new graph color=all
}

\def\tikz@lg@init@color#1#2{%
  \expandafter\gdef\csname tikz@lgc@#1\endcsname{#2}%
}

\def\tikz@lib@graph@cleanup#1{%
  \expandafter\global\expandafter\let\csname tikz@lgc@#1\endcsname\relax%
}

\def\tikz@lg@colorize#1{%
  \expandafter\let\expandafter\pgf@temp\csname tikz@lgc@#1\endcsname%
  \expandafter\expandafter\expandafter\def%
  \expandafter\expandafter\expandafter\pgf@temp%
  \expandafter\expandafter\expandafter{%
    \expandafter\tikz@lg@col\pgf@temp}%
  \expandafter\global\expandafter\let\csname tikz@lgc@#1\endcsname\pgf@temp%
}

\def\tikz@lg@change@color#1{%
  \def\tikz@lg@temp@save{#1}%
  \let\tikz@lg@collect\pgfutil@empty%
  \expandafter\let\expandafter\pgf@temp\csname tikz@lgc@#1\endcsname%
  \expandafter\tikz@lg@change@check\pgf@temp\pgf@stop%
}
\def\tikz@lg@change@check#1{%
  \ifx#1\pgf@stop%
    \tikz@lg@change@write@back%
  \else%
    \def\pgf@temp{#1}%
    \ifx\pgf@temp\tikz@lg@old@col%
      \expandafter\tikz@lg@change@add\expandafter{\tikz@lg@new@col}% Found!
    \else%
      \tikz@lg@change@add{#1}%
    \fi%
    \expandafter\tikz@lg@change@check
  \fi%
}
\def\tikz@lg@change@add#1{%
  \expandafter\def\expandafter\tikz@lg@collect\expandafter{\tikz@lg@collect#1}%
}

\def\tikz@lg@change@write@back{%
  \expandafter\global\expandafter\let\csname tikz@lgc@\tikz@lg@temp@save\endcsname\tikz@lg@collect%
}



\def\tikz@lg@if@has@color#1#2#3#4{%
  {%
    \csname tikz@lgc@#1\endcsname%
    \expandafter\let\expandafter\pgf@temp\csname iftikz@lgc@#2@\endcsname%
    \ifx\pgf@temp\relax%
      \tikz@lib@reset@temp%
    \fi%
    \pgf@temp%
      \global\tikz@color@testtrue%
    \else%
      \global\tikz@color@testfalse%
    \fi%
  }%
  \iftikz@color@test#3\else#4\fi%
}
\newif\iftikz@color@test

\def\tikz@lg@if@local@node#1#2#3{\expandafter\ifx\csname tikz@lgc@#1\endcsname\relax#3\else#2\fi}

\def\tikz@lib@reset@temp{\let\pgf@temp\iffalse}



%
% Color functions
%

% Do something for all nodes having a certain color
%
% #1 = the color name
% #2 = a macro
% 
% Description:
% 
% For each node having color #1, the macro #2 will be called. This
% macro should take a single parameter, which will be set 
% to the node's name.

\def\tikzlibgraphforeachcolorednode#1#2{%
  \expandafter\def\expandafter\iftikz@lib@graph@color@picker\expandafter{\csname iftikz@lgc@#1@\endcsname}%
  \let\tikz@lib@graph@action#2%
  \let\tikz@lg@do\tikz@lg@pick%
  \tikz@lib@graph@node@list%  
}
\def\tikz@lg@pick#1{
  {%
    \csname tikz@lgc@#1\endcsname%
    \iftikz@lib@graph@color@picker
      \global\tikz@color@testtrue%
    \else%
      \global\tikz@color@testfalse%
    \fi%
  }%
  \iftikz@color@test\tikz@lib@graph@action{#1}\fi%
}


% Prepare a color 
%
% #1 is the color name
% #2 is a counter
% #3 is a prefix
% 
% Description:
% 
% You can call this function inside a connector. It will do the
% following: First, its counts how many nodes exist that have color
% #1. This number is stored in the counter passed as #2. Furthermore,
% let <name> be the name of the <i>-th vertex that has color #1. Then, a
% macro called \#3<i> will store <name>. For instance, if #1 is "red"
% and the third red node is called foo and if #3 is "bar", then a
% macro called "\bar3" is set to "foo" as if you had said
% "\expandafter\def\csname bar3\endcsname{foo}".
% 
% The bottom line of all this is that after a preparation you can
% easily iterate over nodes having a certain color. If you wish to
% iterate over a single color, it will be quicker and easier to call
% \tikzlibgraphforeachcolorednode, but if you need to iterate over two
% colors simultaneously, it will be better to first prepare the color.

\def\tikzlibgraphpreparecolor#1#2#3{%
  \let\tikz@lib@graph@count#2%
  \def\tikz@lib@graph@prefix{#3}%
  \tikzlibgraphforeachcolorednode{#1}\tikz@lib@graph@prepare%
}

\def\tikz@lib@graph@prepare#1{%
  \advance\tikz@lib@graph@count by1\relax%
  \expandafter\def\csname \tikz@lib@graph@prefix\the\tikz@lib@graph@count\endcsname{#1}%
}



% 
% Connectors
% 

\let\tikz@lib@graph@connector\relax

\tikzset{
  connector/.initial=,
  join connector/.initial=match,
}


% 
% The bipartite connector 
%

\tikzset{
  connectors/bipartite/.code 2 args={
    \def\tikz@lg@shoreb{#2}%
    \tikzlibgraphforeachcolorednode{#1}\tikz@lib@graph@bipartite@outer
  },
  connectors/bipartite/.default={out'}{in'}
}

\def\tikz@lib@graph@bipartite@outer#1{%
  \def\tikz@lib@graph@from{#1}%
  {%
    \tikzlibgraphforeachcolorednode{\tikz@lg@shoreb}\tikz@lib@graph@bipartite@inner%
  }%
}

\def\tikz@lib@graph@bipartite@inner#1{%
  \def\pgf@temp{#1}%
  \ifx\pgf@temp\tikz@lib@graph@from\else%
    \tikz@lib@graph@default@new@edge{\tikz@lib@graph@from}{#1}%
  \fi%
}

\def\tikz@lib@graph@default@new@edge#1#2{%
  \pgfkeys{/tikz/graphs/.cd,new edge \pgfkeysvalueof{/tikz/graphs/default edge kind}={#1}{#2}{}}%
}

  
% 
% The clique connector 
%

\tikzset{
  connectors/clique/.code={
    \tikzlibgraphpreparecolor{#1}\c@pgf@counta{tikz@lg}%
    \tikz@lg@clique@loop%
  },
  connectors/clique/.default=all
}

\def\tikz@lg@clique@loop{%
  \ifnum\c@pgf@counta=0\relax%
  \else
    \c@pgf@countb=\c@pgf@counta\relax%
    \tikz@lg@clique@loop@inner%
    \advance\c@pgf@counta by-1\relax%
    \expandafter\tikz@lg@clique@loop%
  \fi%
}

\def\tikz@lg@clique@loop@inner{%
  \advance\c@pgf@countb by-1\relax%
  \ifnum\c@pgf@countb>0\relax%
    \tikz@lib@graph@default@new@edge{\csname tikz@lg\the\c@pgf@counta\endcsname}{\csname tikz@lg\the\c@pgf@countb\endcsname}%
    \expandafter\tikz@lg@clique@loop@inner%
  \fi%
}


% 
% The list connector 
%

\tikzset{
  connectors/list/.code={%
    \let\tikz@lg@prev\relax%
    \tikzlibgraphforeachcolorednode{#1}\tikz@lib@graph@list@do%
  },
  connectors/list/.default=all
}

\def\tikz@lib@graph@list@do#1{%
  \ifx\tikz@lg@prev\relax%
  \else%
    \tikz@lib@graph@default@new@edge{\tikz@lg@prev}{#1}%
  \fi
  \def\tikz@lg@prev{#1}%
}


% 
% The cycle connector 
%

\tikzset{
  connectors/cycle/.code={%
    \let\tikz@lg@prev\relax%
    \let\tikz@lg@first\relax%
    \tikzlibgraphforeachcolorednode{#1}\tikz@lib@graph@cycle@do%
    \ifx\tikz@lg@first\relax%
    \else%
      \tikz@lib@graph@default@new@edge{\tikz@lg@prev}{\tikz@lg@first}%
    \fi%
  },
  connectors/cycle/.default=all
}

\def\tikz@lib@graph@cycle@do#1{%
  \ifx\tikz@lg@prev\relax%
    \def\tikz@lg@prev{#1}%
    \let\tikz@lg@first\tikz@lg@prev%
  \else%
    \tikz@lib@graph@default@new@edge{\tikz@lg@prev}{#1}%
    \def\tikz@lg@prev{#1}%
  \fi%
}




% 
% The match connector 
%

\tikzset{
  connectors/match/.code 2 args={
    {%
      \tikzlibgraphpreparecolor{#1}\c@pgf@counta{tikz@lg}
      \c@pgf@countb=0\relax%
      \let\tikz@lg@prev\relax
      \tikzlibgraphforeachcolorednode{#2}\tikz@lib@graph@match@do%
      \tikz@lib@graph@match@rest%
    }%
  },
  connectors/match/.default={out'}{in'}
}

\def\tikz@lib@graph@match@do#1{%
  \advance\c@pgf@countb by1\relax%
  \ifnum\c@pgf@countb>\c@pgf@counta\relax%
    \c@pgf@countb=\c@pgf@counta\relax%
  \fi%
  \tikz@lib@graph@default@new@edge{\csname tikz@lg\the\c@pgf@countb\endcsname}{#1}%
  \def\tikz@lg@prev{#1}%
}

\def\tikz@lib@graph@match@rest{%
  \ifnum\c@pgf@countb<\c@pgf@counta\relax%
    \advance\c@pgf@countb by1\relax%
    \tikz@lib@graph@default@new@edge{\csname tikz@lg\the\c@pgf@countb\endcsname}{\tikz@lg@prev}%
    \expandafter\tikz@lib@graph@match@rest%
  \fi%
}



% 
% The butterfly connector 
%

\tikzset{
  connectors/butterfly/.code={
    {}{%
      \pgfkeys{/tikz/connectors/butterfly/.cd,#1}%
      \ifnum\pgfkeysvalueof{/tikz/connectors/butterfly/level}=0\relax%
        \pgfkeysalso{/tikz/connectors/match={\pgfkeysvalueof{/tikz/connectors/butterfly/from}}{\pgfkeysvalueof{/tikz/connectors/butterfly/to}}}%
      \else%
        {%
          \tikzlibgraphpreparecolor{\pgfkeysvalueof{/tikz/connectors/butterfly/from}}\c@pgf@counta{tikz@lg}
          \c@pgf@countb=0\relax%
          \tikzlibgraphforeachcolorednode{\pgfkeysvalueof{/tikz/connectors/butterfly/to}}\tikz@lib@graph@butterfly@do%
        }%
        \iftikz@butterfly@prime\else\pgfkeysalso{/tikz/connectors/match={\pgfkeysvalueof{/tikz/connectors/butterfly/from}}{\pgfkeysvalueof{/tikz/connectors/butterfly/to}}}\fi%
      \fi%
    }%
  },
  connectors/butterfly/.default=,
  connectors/butterfly/level/.initial=1,
  connectors/butterfly/from/.initial=out',
  connectors/butterfly/to/.initial=in',
  connectors/butterfly'/.code={%
    {}{\tikz@butterfly@primetrue\pgfkeysalso{butterfly={#1}}}},
  connectors/butterfly'/.default=,
}

\newif\iftikz@butterfly@prime

\def\tikz@lib@graph@butterfly@do#1{%
  \advance\c@pgf@countb by1\relax%
  % Compute other side...
  \c@pgf@countc=\pgfkeysvalueof{/tikz/connectors/butterfly/level}\relax%
  {%
    % Computer countb mod (2level)
    \count0=\c@pgf@countc\relax%
    \multiply\count0 by2\relax%
    \count1=\c@pgf@countb\relax%
    \advance\count1 by-1\relax%
    \count2=\count1\relax%
    \count3=\count1\relax%
    \divide\count1 by\count0\relax%
    \multiply\count1 by\count0\relax%
    \advance\count2 by-\count1\relax%
    % count0 = 2*level
    % count2 = countb mod (2level) (starting with 0)
    % count1 = countb - count2 (starting with 0)
    \ifnum\count2<\c@pgf@countc\relax%
      \advance\count3 by \c@pgf@countc\relax%
    \else%
      \advance\count3 by -\c@pgf@countc\relax%
    \fi%
    \expandafter%
  }%
  \expandafter\c@pgf@countc\the\count3\relax%
  \advance\c@pgf@countc by1\relax%
  \ifnum\c@pgf@countc>\c@pgf@counta\relax%
    \c@pgf@countc=\c@pgf@counta\relax%
  \fi%
  \tikz@lib@graph@default@new@edge{\csname tikz@lg\the\c@pgf@countc\endcsname}{#1}%
}
