01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
package algs41;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac GraphClient.java
 *  Execution:    java GraphClient graph.txt
 *  Dependencies: Graph.java
 *
 *  Typical graph-processing code.
 *
 *  % java GraphClient tinyG.txt
 *  13 13
 *  0: 6 2 1 5
 *  1: 0
 *  2: 0
 *  3: 5 4
 *  4: 5 6 3
 *  5: 3 4 0
 *  6: 0 4
 *  7: 8
 *  8: 7
 *  9: 11 10 12
 *  10: 9
 *  11: 9 12
 *  12: 11 9
 *
 *  vertex of maximum degree = 4
 *  average degree           = 2
 *  number of self loops     = 0
 *
 *************************************************************************/

public class XGraphClient {

  // show edges (twice)
  public static void show (Graph G) {
    for (int v = 0; v < G.V(); v++)
      for (int w : G.adj(v))
        StdOut.println(v + "-" + w);
  }

  // degree of v
  public static int degree(Graph G, int v) {
    int degree = 0;
    for (int w : G.adj(v)) degree++;
    return degree;
  }

  // maximum degree
  public static int maxDegree(Graph G) {
    int max = 0;
    for (int v = 0; v < G.V(); v++)
      if (degree(G, v) > max)
        max = degree(G, v);
    return max;
  }

  // average degree
  public static int avgDegree(Graph G) {
    // each edge incident on two vertices
    return 2 * G.E() / G.V();
  }

  // number of self-loops
  public static int numberOfSelfLoops(Graph G) {
    int count = 0;
    for (int v = 0; v < G.V(); v++)
      for (int w : G.adj(v))
        if (v == w) count++;
    return count/2;   // self loop appears in adjacency list twice
  }

  public static void main(String[] args) {
    args = new String[] { "data/tinyG.txt" };
    In in = new In(args[0]);
    Graph G = GraphGenerator.fromIn (in);
    //StdOut.println(G);
    //show (G);

    StdOut.println("degree of 4 = " + degree(G, 4));
    StdOut.println("vertex of maximum degree = " + maxDegree(G));
    StdOut.println("average degree           = " + avgDegree(G));
    StdOut.println("number of self loops     = " + numberOfSelfLoops(G));

  }

}