§1  RANDOM2  RANDOM GRAPHS 1

1. Random graphs. This is a short program for generating inputs for Sedgewick s programs in Algorithms in C (Parts 1–4), Section 1.3. The user should use the command-line options -nN -nM -sS to ask for a random graph with N vertices and M edges. The quantity S is used as the seed for the random number generator. #include /∗ we use the GB GRAPH data structures ∗/ #include /∗ for the random graph generation routine ∗/ #include /∗ for SGB’s sorting routine ∗/ #include /∗ for SGB’s random number generator ∗/

⟨ Declarations 3 ⟩ ⟨ The program 2 ⟩

2. ⟨ The program 2 ⟩ ≡ int main(int argc, char ∗argv [ ]) { Graph ∗g;

unsigned long n = 10; unsigned long m = 20; long seed = 0; ⟨ Scan the command-line options 7 ⟩; g = random graph(n, m, 0, 0, 0, Λ, Λ, 1, 1, seed ); ⟨ Create the linked list representing the edges of g 4 ⟩; ⟨ Sort and output the pairs of endpoints of edges 5 ⟩; return 0; /∗ normal exit ∗/

}

This code is used in section 1.

3. ⟨ Declarations 3 ⟩ ≡

typedef struct node struct { long key ; /∗ a numeric quantity, assumed nonnegative ∗/ struct node struct ∗link ; /∗ the next node on a list ∗/ long u, w; /∗ the vertex names ∗/

} node; node ∗ll edges = Λ; /∗ pointer to the beginning of the linked list of edge clones ∗/

This code is used in section 1.

2  RANDOM GRAPHS  RANDOM2 §4

4. ⟨ Create the linked list representing the edges of g 4 ⟩ ≡ if (g ≡ Λ) printf ( ␣ ␣ ␣ ␣ ␣ , panic code); else {

register Vertex ∗v; /∗ current vertex being visited ∗/ for (v = g vertices ; v < g vertices + g n; v^{++}) {

register Arc ∗a; /∗ current arc from v ∗/

for (a = v arcs ; a; a = a next )

if (a tip > v) { register node ∗p = malloc(sizeof ∗p); p u = atoi (v name); p w = atoi (a tip name); p key = gb next rand ( ); p link = ll edges ; ll edges = p;

} }

}

This code is used in section 2.

5. ⟨ Sort and output the pairs of endpoints of edges 5 ⟩ ≡ gb linksort (ll edges ); ⟨ Output the pairs 6 ⟩

This code is used in section 2.

6. ⟨ Output the pairs 6 ⟩ ≡

{ int j; node ∗p; for (j = 127; j ≥ 0; j^{−})

for (p = (node ∗) gb sorted [j]; p; p = p link ) printf ( ␣ ␣ , p u, p w); }

This code is used in section 5.

7. ⟨ Scan the command-line options 7 ⟩ ≡

while (^{−}argc) { if (sscanf (argv [argc], , &n) ≡ 1) ; else if (sscanf (argv [argc], , &m) ≡ 1) ; else if (sscanf (argv [argc], , &seed ) ≡ 1) ; else {

fprintf (stderr , ␣ ␣ , argv [0]);

return −2; }

}

This code is used in section 2.

§8  RANDOM2  INDEX 3

8. Index.

a: \underline{4}. arcs : 4. argc: \underline{2}, 7. argv : \underline{2}, 7. atoi : 4. fprintf : 7. g: \underline{2}. gb linksort : 5. gb next rand : 4. gb sorted : 6. j: \underline{6}. key : \underline{3}, 4. link : \underline{3}, 4, 6. ll edges : \underline{3}, 4, 5. m: \underline{2}. main: \underline{2}. malloc: 4. n: \underline{2}. name: 4. next : 4. node: \underline{3}, 4, 6. node struct: \underline{3}. p: \underline{4}, \underline{6}. panic code: 4. printf : 4, 6. random graph: 2. seed : \underline{2}, 7. sscanf : 7. stderr : 7. tip: 4. u: \underline{3}. v: \underline{4}. vertices : 4. w: \underline{3}.

⟨ Create the linked list representing the edges of g 4 ⟩ Used in section 2.

⟨ Declarations 3 ⟩ Used in section 1.

⟨ Output the pairs 6 ⟩ Used in section 5. ⟨ Scan the command-line options 7 ⟩ Used in section 2. ⟨ Sort and output the pairs of endpoints of edges 5 ⟩ Used in section 2.

⟨ The program 2 ⟩ Used in section 1.

RANDOM2

Section Page

Random graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3