Undirected graph Java

undirected graph java implementation and undirected graph longest path algorithm
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 4.1 UNDIRECTED GRAPHS introduction ‣ graph API ‣ depth-first search ‣ Algorithms FOUR TH EDITION breadth-first search ‣ connected components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu challenges ‣4.1 UNDIRECTED GRAPHS introduction ‣ graph API ‣ depth-first search ‣ Algorithms breadth-first search ‣ connected components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu challenges ‣Undirected graphs Graph. Set of vertices connected pairwise by edges. Why study graph algorithms? Thousands of practical applications. Hundreds of graph algorithms known. Interesting and broadly useful abstraction. Challenging branch of computer science and discrete math. 3Border graph of 48 contiguous United States 4Protein-protein interaction network Reference: Jeong et al, Nature Review Genetics 5Map of science clickstreams http://www.plosone.org/article/info:doi/10.1371/journal.pone.0004803 610 million Facebook friends "Visualizing Friendships" by Paul Butler 8The evolution of FCC lobbying coalitions “The Evolution of FCC Lobbying Coalitions” by Pierre de Vries in JoSS Visualization Symposium 2010 9The Spread of Obesity in a Large Social Network Over 32 Years educational level; the ego’s obesity status at the ing both their weights. We estimated these mod- previous time point (t); and most pertinent, the els in varied ego–alter pair types. 25 alter’s obesity status at times t and t + 1. We To evaluate the possibility that omitted vari- used generalized estimating equations to account ables or unobserved events might explain the as- for multiple observations of the same ego across sociations, we examined how the type or direc- 26 examinations and across ego–alter pairs. We tion of the social relationship between the ego assumed an independent working correlation and the alter affected the association between the 26,27 structure for the clusters. ego’s obesity and the alter’s obesity. For example, The use of a time-lagged dependent variable if unobserved factors drove the association be- (lagged to the previous examination) eliminated tween the ego’s obesity and the alter’s obesity, serial correlation in the errors (evaluated with a then the directionality of friendship should not 28 Lagrange multiplier test ) and also substantial- have been relevant. ly controlled for the ego’s genetic endowment and We evaluated the role of a possible spread in any intrinsic, stable predisposition to obesity. The smoking-cessation behavior as a contributor to use of a lagged independent variable for an alter’s the spread of obesity by adding variables for the 25 weight status controlled for homophily. The smoking status of egos and alters at times t and key variable of interest was an alter’s obesity at t + 1 to the foregoing models. We also analyzed time t + 1. A significant coefficient for this vari- the role of geographic distance between egos able would suggest either that an alter’s weight and alters by adding such a variable. Framingham heart study affected an ego’s weight or that an ego and an We calculated 95% confidence intervals by sim- alter experienced contemporaneous events affect- ulating the first difference in the alter’s contem- Figure 1. Largest Connected Subcomponent of the Social Network in the Framingham Heart Study in the Year 2000. Each circle (node) represents one person in the data set. There are 2200 persons in this subcomponent of the social network. Circles with red borders denote women, and circles with blue borders denote men. The size of each circle is proportional to the person’s body-mass index. The interior color of the circles indicates the person’s obesity status: yellow denotes an obese person (body-mass index, ≥30) and green denotes a nonobese person. The colors of the ties between the nodes indicate the relationship between them: purple denotes a friendship or marital tie and orange denotes a familial tie. “The Spread of Obesity in a Large Social Network over 32 Years” by Christakis and Fowler in New England Journal of Medicine, 2007 10 373 n engl j med 357;4 www.nejm.org july 26, 2007The Internet as mapped by the Opte Project http://en.wikipedia.org/wiki/Internet 11Graph applications graph vertex edge telephone, computer fiber optic cable communication gate, register, processor wire circuit joint rod, beam, spring mechanical stock, currency transactions financial intersection street transportation class C network connection internet board position legal move game person friendship social relationship neuron synapse neural network protein protein-protein interaction protein network atom bond molecule 12Graph terminology Path. Sequence of vertices connected by edges. Cycle. Path whose first and last vertices are the same. Two vertices are connected if there is a path between them. vertex edge cycle of length 5 path of length 4 vertex of degree 3 connected components Anatomy of a graph 13Some graph-processing problems problem description s-t path Is there a path between s and t ? shortest s-t path What is the shortest path between s and t ? cycle Is there a cycle in the graph ? Euler cycle Is there a cycle that uses each edge exactly once ? Hamilton cycle Is there a cycle that uses each vertex exactly once ? connectivity Is there a way to connect all of the vertices ? biconnectivity Is there a vertex whose removal disconnects the graph ? planarity Can the graph be drawn in the plane with no crossing edges ? graph isomorphism Do two adjacency lists represent the same graph ? Challenge. Which graph problems are easy? difficult? intractable? 144.1 UNDIRECTED GRAPHS introduction ‣ graph API ‣ depth-first search ‣ Algorithms breadth-first search ‣ connected components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu challenges ‣Graph representation Graph drawing. Provides intuition about the structure of the graph. two drawings of the same graph Two drawings of the same graph Caveat. Intuition can be misleading. 16 Two drawings of the same graphGraph representation Vertex representation. This lecture: use integers between 0 and V – 1. Applications: convert between names and integers with symbol table. A 0 B C G 1 2 6 symbol table D E 3 4 F 5 parallel self-loop edges Anomalies. Anomalies 17Graph API public class public class Graph Graph Graph(int V) Graph(int V) create an empty graph with V vertices Graph(In in) Graph(In in) create a graph from input stream void addEdge(int v, int w) addEdge(int v, int w) add an edge v-w IterableInteger adj(int v) adj(int v) vertices adjacent to v int V() V() number of vertices int E() E() number of edges In in = new In(args0); read graph from input stream Graph G = new Graph(in); for (int v = 0; v G.V(); v++) print out each for (int w : G.adj(v)) edge (twice) StdOut.println(v + "-" + w); 18Graph API: sample client Graph input format. % java Test tinyG.txt tinyG.txt mediumG.txt V V 0-6 13 250 E E 13 1273 0-2 0 5 244 246 0-1 4 3 239 240 0-5 0 1 238 245 1-0 9 12 235 238 6 4 233 240 2-0 5 4 232 248 3-5 0 2 231 248 3-4 229 249 11 12 ⋮ 228 241 9 10 226 231 0 6 12-11 ... 7 8 12-9 (1261 additional lines) 9 11 5 3 Input format for Graph constructor (two examples) In in = new In(args0); read graph from input stream Graph G = new Graph(in); for (int v = 0; v G.V(); v++) print out each for (int w : G.adj(v)) edge (twice) StdOut.println(v + "-" + w); 19Typical graph-processing code public class public class Graph Graph Graph(int V) Graph(int V) create an empty graph with V vertices Graph(In in) Graph(In in) create a graph from input stream void addEdge(int v, int w) addEdge(int v, int w) add an edge v-w IterableInteger adj(int v) adj(int v) vertices adjacent to v int V() V() number of vertices int E() E() number of edges // degree of vertex v in graph G public static int degree(Graph G, int v) int degree = 0; for (int w : G.adj(v)) degree++; return degree; 20Set-of-edges graph representation Maintain a list of the edges (linked list or array). 0 0 1 0 2 1 2 6 0 5 0 6 3 4 3 4 3 5 4 5 5 4 6 7 8 9 10 9 10 9 11 7 8 9 12 11 12 11 12 Q. How long to iterate over vertices adjacent to v ? 21