% 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/graphs/tikzlibrarygraphs.code.tex,v 1.1 2010/10/23 16:35:41 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
}


%
% Keys for using nodes declared outside a graph inside a graph as if
% it were declared there
% 

\tikzset{
  graphs/use existing nodes/.code=\tikz@lib@graph@alltrue
}

\tikzset{
  new set/.code={
    \expandafter\global\expandafter\let\csname tikz@lg@node@set #1\endcsname\pgfutil@empty%
  },
  set/.code={
    \expandafter\def\expandafter\tikz@alias\expandafter{\tikz@alias%
      \expandafter\def\expandafter\pgf@temp\expandafter{\csname tikz@lg@node@set #1\endcsname}%
      \expandafter\expandafter\expandafter\pgfutil@g@addto@macro\expandafter\pgf@temp\expandafter{\expandafter\tikz@lg@do\expandafter{\tikz@fig@name}}%
    }%
  },%
}

\newif\iftikz@lib@graph@all


% 
% Basic options 
%

\tikzset{
  graphs/@nodes styling/.style=,
  graphs/nodes/.style={/tikz/graphs/@nodes styling/.append style={,#1}},
  graphs/@edges styling/.initial=,
  graphs/edges/.style={/tikz/graphs/@edges styling/.append={,#1}},
  graphs/join/.initial=match,
  graphs/connect as/.initial=,
}


% 
% The parser 
%

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

\long\def\tikz@lib@graph@parser@[#1]#2{%
  \scope[graphs/.cd,every graph/.try,#1]%
    \let\tikz@lib@graph@options\pgfutil@empty%
    \let\tikz@lib@graph@node@list\pgfutil@empty%
    \tikz@lib@graph@parse@group{#2}%
    \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@start@group\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%
  }%
}



% 
% Start of a group 
%
\def\tikz@lib@graph@start@group{%
  \pgfutil@ifnextchar[\tikz@lib@graph@start@group@opt{\tikz@lib@graph@start@group@opt[]}%]
}

\def\tikz@lib@graph@start@group@opt[#1]{%
  \pgfkeys{/tikz/graphs/.cd,connect as=,every group/.try,#1}%
  \tikz@lib@graph@main@parser%
}


% 
% 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}%
    \pgfkeys{/tikz/graphs/.cd,#2}%
    \pgfkeysgetvalue{/tikz/graphs/join}\pgf@temp%
    \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{%
  \pgfkeysgetvalue{/tikz/graphs/connect as}\tikz@lib@graph@group@connector
  \expandafter\tikz@lg@do@connector\expandafter{\tikz@lib@graph@group@connector}  
}

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



%
% Handle node
%
\def\tikz@lib@graph@grab@name{%
  \pgfutil@ifnextchar\foreach\tikz@lib@graph@do@foreach\tikz@lib@graph@grab@name@@%
}

\def\tikz@lib@graph@do@foreach\foreach#1in#2#3[\pgf@stop{%
  % Ok, we do a parse on a foreach loop.
  % We have to make sure that we
  \begingroup
    \let\tikz@lib@graph@node@list@saved\pgfutil@empty%
    \foreach #1 in {#2}%
    {%
      \let\tikz@lib@graph@node@list\tikz@lib@graph@node@list@saved%
      \tikz@lib@graph@parse@group{#3}%
      \global\let\tikz@lib@graph@node@list@saved\tikz@lib@graph@node@list%
    }%
    \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@saved}%  
}


\def\tikz@lib@graph@grab@name@@#1[{%
  \tikz@lib@graph@read#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{%
  \let\tikzgraphnodename\tikz@lib@graph@name%
  \tikz@lib@graph@typesetter%
}

\def\tikz@lib@graph@read#1\pgf@stop{%
  \pgfkeys@spdef\tikz@lib@graph@name{#1}%
  \edef\tikz@lib@graph@name{\tikz@lib@graph@path\tikz@lib@graph@name}%
}


\def\tikz@lib@graph@node@opt[#1]#2[\pgf@stop{%
  \ifx\tikz@lib@graph@name\tikz@lib@graph@usetext
    % Ok, make a list of the nodes stored in #1:
    \let\tikz@lg@temp\pgfutil@empty%
    \foreach \tikz@lg@node@name in {#1} {\expandafter\tikz@lib@graph@handle@use\expandafter{\tikz@lg@node@name}}
    % Ok, now add the nodes to the node list
    \expandafter\expandafter\expandafter\def%
    \expandafter\expandafter\expandafter\tikz@lib@graph@node@list%
    \expandafter\expandafter\expandafter{%
      \expandafter\tikz@lib@graph@node@list\tikz@lg@temp}%
    % Then color and initialize them:
    \let\tikz@lg@do\tikz@lib@graph@do@use%
    \tikz@lg@temp%
  \else%
    \expandafter\ifx\csname tikz@lib@graph@def@\tikz@lib@graph@name\endcsname\relax%
      {%
        \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@all%
            \tikzset{/tikz/graph node/.cd,#1}%
          \else%
            \node [name=\tikz@lib@graph@name,/tikz/graph
              node/.cd,/tikz/graphs/@nodes styling,#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}}%
    \else
      % The name of the node is a graph name
      \tikz@lib@graph@handle@graph{#1}%      
    \fi
  \fi%  
}

\def\tikz@lib@graph@handle@use#1{%
  % Is #1 the name of a node set?
  \expandafter\let\expandafter\pgf@temp\csname tikz@lg@node@set #1\endcsname
  \ifx\pgf@temp\relax
    \pgfutil@g@addto@macro\tikz@lg@temp{\tikz@lg@do{#1}}    
  \else%
    \expandafter\pgfutil@g@addto@macro\expandafter\tikz@lg@temp\expandafter{\pgf@temp}
  \fi  
}

\def\tikz@lib@graph@do@use#1{%
  \tikz@lg@init@color{#1}{\tikz@lgc@all@true\tikz@lgc@in@true\tikz@lgc@out@true}%
}

\def\tikz@lib@graph@usetext{use}

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

\tikzset{
  graphs/typeset/.store in=\tikz@lib@graph@typesetter,
  graphs/math nodes/.style={/tikz/graphs/typeset=$\tikzgraphnodename$},
  graphs/empty nodes/.style={/tikz/graphs/typeset=},
  graphs/typeset=\tikzgraphnodename
}


% 
% Handle scope 
%
\def\tikz@lib@graph@scope#1{
  \begingroup
    \let\tikz@lib@graph@node@list\pgfutil@empty%
    \tikz@lib@graph@parse@group{#1}%
    \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}%




% 
% Predefining graphs 
% 

\def\tikzdefgraph#1#2#3{%
  \expandafter\def\csname tikz@lib@graph@def@#1\endcsname{\tikz@lib@graph@do@graph{#2}{#3}}%
}

\def\tikz@lib@graph@handle@graph#1{%
  \begingroup%
    \let\tikz@lib@graph@node@list\pgfutil@empty%
    \tikzset{graphs/.cd,#1}%
    \csname tikz@lib@graph@def@\tikz@lib@graph@name\endcsname%
    \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}% 
}

\def\tikz@lib@graph@do@graph#1#2{%
  #1%
  \tikz@lib@graph@parse@group{#2}%
}

\let\tikz@lib@graph@path\pgfutil@empty

\tikzset{graphs/name/.code={%
    \edef\tikz@lib@graph@path{#1\space\tikz@lib@graph@path}%
  }%
}


%
% 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}%
}




% 
% 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{%
  \pgfkeysgetvalue{/tikz/graphs/@edges styling}\pgf@temp
  \expandafter\tikz@lib@graph@default@new@edge@\expandafter{\pgf@temp}%
}
\def\tikz@lib@graph@default@new@edge@#1#2#3{%
  \pgfkeys{/tikz/graphs/.cd,new edge \pgfkeysvalueof{/tikz/graphs/default edge kind}={#2}{#3}{#1}}%
}

  
% 
% 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 path connector 
%

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

\def\tikz@lib@graph@path@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}%
}



