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}