\input cwebmac



\def\title{RANDOM2}


\N{1}{1}Random graphs.
This is a short program for generating inputs for Sedgewick s programs in {\it
Algorithms in C\/} (Parts~1--4), Section~1.3.  The user should use the
command-line options {\tt -nN -nM -sS} to ask for a random graph with~{\tt N}
vertices and~{\tt M} edges.  The quantity~{\tt S} is used as the seed for the
random number generator.

\Y\B\8\#\&{include} \.{"gb\_graph.h"}\C{ we use the {\sc GB\_\,GRAPH} data
structures }\6
\8\#\&{include} \.{"gb\_rand.h"}\C{ for the random graph generation routine }\6
\8\#\&{include} \.{"gb\_sort.h"}\C{ for SGB's sorting routine }\6
\8\#\&{include} \.{"gb\_flip.h"}\C{ for SGB's random number generator }\7
\X3:Declarations\X\6
\X2:The program\X\par
\fi

\M{2}\B\X2:The program\X${}\E{}$\6
\&{int} \\{main}(\&{int} \\{argc}${},\39{}$\&{char} ${}{*}\\{argv}[\,]){}$\1\1%
\2\2\6
${}\{{}$\5
\1\&{Graph} ${}{*}\|g;{}$\6
\&{unsigned} \&{long} \|n${}\K\T{10};{}$\6
\&{unsigned} \&{long} \|m${}\K\T{20};{}$\6
\&{long} \\{seed}${}\K\T{0};{}$\7
\X7:Scan the command-line options\X;\6
${}\|g\K\\{random\_graph}(\|n,\39\|m,\39\T{0},\39\T{0},\39\T{0},\39\NULL,\39%
\NULL,\39\T{1},\39\T{1},\39\\{seed});{}$\6
\X4:Create the linked list representing the edges of \PB{\|g}\X;\6
\X5:Sort and output the pairs of endpoints of edges\X;\6
\&{return} \T{0};\C{ normal exit }\6
\4${}\}{}$\2\par
\U1.\fi

\M{3}\B\X3:Declarations\X${}\E{}$\6
\&{typedef} \&{struct} \&{node\_struct} ${}\{{}$\1\6
\&{long} \\{key};\C{ a numeric quantity, assumed nonnegative }\6
\&{struct} \&{node\_struct} ${}{*}\\{link}{}$;\C{ the next node on a list }\6
\&{long} \|u${},{}$ \|w;\C{ the vertex names }\2\6
${}\}{}$ \&{node};\7
\&{node} ${}{*}\\{ll\_edges}\K\NULL{}$;\C{ pointer to the beginning of the
linked list of                         edge clones }\par
\U1.\fi

\M{4}\B\X4:Create the linked list representing the edges of \PB{\|g}\X${}\E{}$\6
\&{if} ${}(\|g\E\NULL){}$\1\5
${}\\{printf}(\.{"Something\ went\ wron}\)\.{g\ (panic\ code\ \%ld)!\\}\)%
\.{n"},\39\\{panic\_code});{}$\2\6
\&{else}\5
${}\{{}$\1\6
\&{register} \&{Vertex} ${}{*}\|v{}$;\C{ current vertex being visited }\7
\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$
${}\|v\PP){}$\5
${}\{{}$\1\6
\&{register} \&{Arc} ${}{*}\|a{}$;\C{ current arc from \PB{\|v} }\7
\&{for} ${}(\|a\K\|v\MG\\{arcs};{}$ \|a; ${}\|a\K\|a\MG\\{next}){}$\1\6
\&{if} ${}(\|a\MG\\{tip}>\|v){}$\5
${}\{{}$\1\6
\&{register} \&{node} ${}{*}\|p\K{}$\\{malloc}(\&{sizeof} ${}{*}\|p);{}$\7
${}\|p\MG\|u\K\\{atoi}(\|v\MG\\{name});{}$\6
${}\|p\MG\|w\K\\{atoi}(\|a\MG\\{tip}\MG\\{name});{}$\6
${}\|p\MG\\{key}\K\\{gb\_next\_rand}(\,);{}$\6
${}\|p\MG\\{link}\K\\{ll\_edges};{}$\6
${}\\{ll\_edges}\K\|p;{}$\6
\4${}\}{}$\2\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U2.\fi

\M{5}\B\X5:Sort and output the pairs of endpoints of edges\X${}\E{}$\6
\\{gb\_linksort}(\\{ll\_edges});\6
\X6:Output the pairs\X\par
\U2.\fi

\M{6}\B\X6:Output the pairs\X${}\E{}$\6
${}\{{}$\5
\1\&{int} \|j;\6
\&{node} ${}{*}\|p;{}$\7
\&{for} ${}(\|j\K\T{127};{}$ ${}\|j\G\T{0};{}$ ${}\|j\MM){}$\1\6
\&{for} ${}(\|p\K{}$(\&{node} ${}{*}){}$ \\{gb\_sorted}[\|j]; \|p; ${}\|p\K\|p%
\MG\\{link}){}$\1\5
${}\\{printf}(\.{"\ \%ld\ \%ld\\n"},\39\|p\MG\|u,\39\|p\MG\|w);{}$\2\2\6
\4${}\}{}$\2\par
\U5.\fi

\M{7}\B\X7:Scan the command-line options\X${}\E{}$\6
\&{while} ${}(\MM\\{argc}){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"-n\%lu"},\39{\AND}\|n)\E%
\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"-m\%lu"},\39{\AND}\|m)%
\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"-s\%ld"},\39{\AND}%
\\{seed})\E\T{1}){}$\1\5
;\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Usage:\ \%s\ [-nN][-mM}\)\.{][-sS]\\n"},\39%
\\{argv}[\T{0}]);{}$\6
\&{return} ${}{-}\T{2};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U2.\fi

\N{1}{8}Index.
\fi


\inx
\fin
\con
