001package algs41; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac GraphClient.java 005 * Execution: java GraphClient graph.txt 006 * Dependencies: Graph.java 007 * 008 * Typical graph-processing code. 009 * 010 * % java GraphClient tinyG.txt 011 * 13 13 012 * 0: 6 2 1 5 013 * 1: 0 014 * 2: 0 015 * 3: 5 4 016 * 4: 5 6 3 017 * 5: 3 4 0 018 * 6: 0 4 019 * 7: 8 020 * 8: 7 021 * 9: 11 10 12 022 * 10: 9 023 * 11: 9 12 024 * 12: 11 9 025 * 026 * vertex of maximum degree = 4 027 * average degree = 2 028 * number of self loops = 0 029 * 030 *************************************************************************/ 031 032public class XGraphClient { 033 034 // show edges (twice) 035 public static void show (Graph G) { 036 for (int v = 0; v < G.V(); v++) 037 for (int w : G.adj(v)) 038 StdOut.println(v + "-" + w); 039 } 040 041 // degree of v 042 public static int degree(Graph G, int v) { 043 int degree = 0; 044 for (int w : G.adj(v)) degree++; 045 return degree; 046 } 047 048 // maximum degree 049 public static int maxDegree(Graph G) { 050 int max = 0; 051 for (int v = 0; v < G.V(); v++) 052 if (degree(G, v) > max) 053 max = degree(G, v); 054 return max; 055 } 056 057 // average degree 058 public static int avgDegree(Graph G) { 059 // each edge incident on two vertices 060 return 2 * G.E() / G.V(); 061 } 062 063 // number of self-loops 064 public static int numberOfSelfLoops(Graph G) { 065 int count = 0; 066 for (int v = 0; v < G.V(); v++) 067 for (int w : G.adj(v)) 068 if (v == w) count++; 069 return count/2; // self loop appears in adjacency list twice 070 } 071 072 public static void main(String[] args) { 073 args = new String[] { "data/tinyG.txt" }; 074 In in = new In(args[0]); 075 Graph G = GraphGenerator.fromIn (in); 076 //StdOut.println(G); 077 //show (G); 078 079 StdOut.println("degree of 4 = " + degree(G, 4)); 080 StdOut.println("vertex of maximum degree = " + maxDegree(G)); 081 StdOut.println("average degree = " + avgDegree(G)); 082 StdOut.println("number of self loops = " + numberOfSelfLoops(G)); 083 084 } 085 086}