Java- Data Structures and Analysis

profilebrinco
homework5.zip
Home>Computer Science homework help>Java- Data Structures and Analysis

homework5/~$cial Graphs.docx

homework5/Graph.java

homework5/Graph.java

// UMUC CMSC 350 
// Class Graph - Defines an undirected graph
// Adapted by Ioan from:
// Liang - Introduction to Java Programming, 9th Edition (Code Examples of Chapter 30 Graphs and Applications)
// Source code of the examples available at: 
// http://www.cs.armstrong.edu/liang/intro9e/examplesource.html

import  java . util . * ;

public   class   Graph < V >   {
   protected   List < V >  vertices  =   new   ArrayList < V > ();   // Store vertices
   protected   List < List < Integer >>  neighbors  =   new   ArrayList < List < Integer >> ();   // Adjacency lists

   /** Construct an empty graph */
   protected   Graph ()   {
   }
  
   /** Construct a graph from edges and vertices stored in arrays */
   protected   Graph ( int [][]  edges ,  V []  vertices )   {
     for   ( int  i  =   0 ;  i  <  vertices . length ;  i ++ )
       this . vertices . add ( vertices [ i ]);
    
    createAdjacencyLists ( edges ,  vertices . length );
   }

   /** Construct a graph from edges and vertices stored in List */
   protected   Graph ( List < Edge >  edges ,   List < V >  vertices )   {
   for   ( int  i  =   0 ;  i  <  vertices . size ();  i ++ )
     this . vertices . add ( vertices . get ( i ));
      
  createAdjacencyLists ( edges ,  vertices . size ());
   }

   /** Construct a graph for integer vertices 0, 1, 2 and edge list */
   protected   Graph ( List < Edge >  edges ,   int  numberOfVertices )   {
     for   ( int  i  =   0 ;  i  <  numberOfVertices ;  i ++ )  
      vertices . add (( V )( new   Integer ( i )));   // vertices is {0, 1, ...}
    
    createAdjacencyLists ( edges ,  numberOfVertices );
   }

   /** Construct a graph from integer vertices 0, 1, and edge array */
   protected   Graph ( int [][]  edges ,   int  numberOfVertices )   {
     for   ( int  i  =   0 ;  i  <  numberOfVertices ;  i ++ )  
      vertices . add (( V )( new   Integer ( i )));   // vertices is {0, 1, ...}
    
    createAdjacencyLists ( edges ,  numberOfVertices );
   }
  
   /** Create adjacency lists for each vertex */
   private   void  createAdjacencyLists ( int [][]  edges ,   int  numberOfVertices )   {
     // Create a linked list
     for   ( int  i  =   0 ;  i  <  numberOfVertices ;  i ++ )   {
      neighbors . add ( new   ArrayList < Integer > ());
     }

     for   ( int  i  =   0 ;  i  <  edges . length ;  i ++ )   {
       int  u  =  edges [ i ][ 0 ];
       int  v  =  edges [ i ][ 1 ];
      neighbors . get ( u ). add ( v );
     }
   }

   /** Create adjacency lists for each vertex */
   private   void  createAdjacencyLists ( List < Edge >  edges ,   int  numberOfVertices )   {
     // Create a linked list for each vertex
     for   ( int  i  =   0 ;  i  <  numberOfVertices ;  i ++ )   {
      neighbors . add ( new   ArrayList < Integer > ());
     }

     for   ( Edge  edge :  edges )   {
      neighbors . get ( edge . u ). add ( edge . v );
     }
   }

   /** Return the number of vertices in the graph */
   public   int  getSize ()   {
     return  vertices . size ();
   }

   /** Return the vertices in the graph */
   public   List < V >  getVertices ()   {
     return  vertices ;
   }

   /** Return the object for the specified vertex */
   public  V getVertex ( int  index )   {
     return  vertices . get ( index );
   }

   /** Return the index for the specified vertex object */
   public   int  getIndex ( V v )   {
     return  vertices . indexOf ( v );
   }

   /** Return the neighbors of the specified vertex */
   public   List < Integer >  getNeighbors ( int  index )   {
     return  neighbors . get ( index );
   }

   /** Return the degree for a specified vertex */
   public   int  getDegree ( int  v )   {
     return  neighbors . get ( v ). size ();
   }

   /** Print the edges */
   public   void  printEdges ()   {
     for   ( int  u  =   0 ;  u  <  neighbors . size ();  u ++ )   {
       System . out . print ( getVertex ( u )   +   " ("   +  u  +   "): " );
       for   ( int  j  =   0 ;  j  <  neighbors . get ( u ). size ();  j ++ )   {
         System . out . print ( "("   +  u  +   ", "   +
          neighbors . get ( u ). get ( j )   +   ") " );
       }
       System . out . println ();
     }
   }

   /** Clear graph */
   public   void  clear ()   {
    vertices . clear ();
    neighbors . clear ();
   }
  
   /** Add a vertex to the graph */   
   public   void  addVertex ( V vertex )   {
    vertices . add ( vertex );
    neighbors . add ( new   ArrayList < Integer > ());
   }

   /** Add an edge to the graph */   
   public   void  addEdge ( int  u ,   int  v )   {
    neighbors . get ( u ). add ( v );
    neighbors . get ( v ). add ( u );
   }
  
   /** DFS Graph Traversal */
   /** Obtain a DFS List of vertices starting from vertex v */
   /** Original code modified to return List (instead of Tree)*/
   public   List < Integer >  dfs ( int  v )   {
     List < Integer >  searchOrder  =   new   ArrayList < Integer > ();
     int []  parent  =   new   int [ vertices . size ()];
     for   ( int  i  =   0 ;  i  <  parent . length ;  i ++ )
      parent [ i ]   =   - 1 ;   // Initialize parent[i] to -1

     // Mark visited vertices
     boolean []  isVisited  =   new   boolean [ vertices . size ()];

     // Recursively search
    dfs ( v ,  parent ,  searchOrder ,  isVisited );

     // Return a search tree
     return  searchOrder ;
   }

   /** Recursive method for DFS search */
   private   void  dfs ( int  v ,   int []  parent ,   List < Integer >  searchOrder ,   boolean []  isVisited )   {
     // Store the visited vertex
    searchOrder . add ( v );
    isVisited [ v ]   =   true ;   // Vertex v visited

     for   ( int  i  :  neighbors . get ( v ))   {
       if   ( ! isVisited [ i ])   {
        parent [ i ]   =  v ;   // The parent of vertex i is v
        dfs ( i ,  parent ,  searchOrder ,  isVisited );   // Recursive search
       }
     }
   }
  
   /** BFS Graph Traversal */
   /** Obtain a BFS List of vertices starting from vertex v */
   /** Original code modified to return List (instead of Tree)*/
   public   List < Integer >  bfs ( int  v )   {
     List < Integer >  searchOrder  =   new   ArrayList < Integer > ();
     int []  parent  =   new   int [ vertices . size ()];
     for   ( int  i  =   0 ;  i  <  parent . length ;  i ++ )
      parent [ i ]   =   - 1 ;   // Initialize parent[i] to -1

    java . util . LinkedList < Integer >  queue  =
       new  java . util . LinkedList < Integer > ();   // list used as a queue
     boolean []  isVisited  =   new   boolean [ vertices . size ()];
    queue . offer ( v );   // Enqueue v
    isVisited [ v ]   =   true ;   // Mark it visited

     while   ( ! queue . isEmpty ())   {
       int  u  =  queue . poll ();   // Dequeue to u
      searchOrder . add ( u );   // u searched
       for   ( int  w  :  neighbors . get ( u ))   {
         if   ( ! isVisited [ w ])   {
          queue . offer ( w );   // Enqueue w
          parent [ w ]   =  u ;   // The parent of w is u
          isVisited [ w ]   =   true ;   // Mark it visited
         }
       }
     }
     return  searchOrder ;
   }
 
   /** Edge inner class inside the Graph class */
   public   static   class   Edge   {
     public   int  u ;   // Starting vertex of the edge
     public   int  v ;   // Ending vertex of the edge

     /** Construct an edge for (u, v) */
     public   Edge ( int  u ,   int  v )   {
       this . u  =  u ;
       this . v  =  v ;
     }
   }
}

homework5/Social Graphs.docx

Social Graphs - An Application of Graphs

1. Specification

The concept of Social Graph was introduced by M. Zuckerberg at the first Facebook F8 conference in 2007 when he introduced the Facebook platform to model relationships among internet users.

Part 1

Consider the attached file Graph.java which defines a generic undirected Graph class. Design and implement a class SocialGraph (in a separate source file SocialGraph.java) which extends the class Graph. In a social graph, the vertices (graph nodes) represent people names while the un-directed edges represent the acquaintance relationships between them. Class SocialGraph should define constructor(s) and enhance the behavior of the class Graph by defining the following social graphs’ specific methods:

 normalizedDegreeOfCentrality calculates and returns the normalized degree of centrality for a given vertex v. The required value is calculated as: degree(v) / (n-1) where degree(v) represents the number of vertex incident edges and n represents the number of graph vertices. For social graphs, a high degree of centrality for a person v reflects his/her dominant position in the group or his/her social interaction skills.

 numberOfTrianglesIncidentToVertex, calculates and returns the number of triangles incident to vertex v. The algorithm below calculates the number of triangles incident for all graph vertices (V is the set of vertices, E is the set of edges):

foreach v in V foreach pair of vertices (p, q) in AdjacencyList(v) if (p, q) is in E then add 1 to triangles[v]

 listOfTrianglesIncidentToVertex calculates and returns the list of triangles incident to vertex v. A triangle should be specified by its vertices.

 clusterIndividual for a given vertex v, calculates and returns the percentage indicating how close its neighbors are to make a complete graph and is calculated as: [(number of edges connecting v's neighbor vertices) / (number of edges, potentially connecting v's neighbor vertices)] * 100 where: - the number of edges connecting v’s neighbor vertices is equal to the number of triangles incident to vertex v - the number of edges, potentially connecting v's neighbor vertices is calculated as: [degree(v) * (degree(v) - 1)] / 2

The value of cluster individual measures how close wrapped are the persons in the social graph around the given person.

 averageClustering for the social graph is calculated as (the sum applies to all vertices v in V): (1 / n) * ∑ clusterIndividual (v) This value indicates the overall density of the social graph.

 isDirectAcquaintance determines whether two persons supplied as parameters are / are not direct connected.

 isIndirectAcquaintance determines whether two persons supplied as parameters can establish social contact through a chain of transitive acquaintance relationships (in terms of graphs it means that there is a path between the two nodes representing the two persons).

Additional (helper) methods and / or instance variables may be defined as necessary.

Part 2

Design and implement a driver program TestSocialGraph (in a separate source file TestSocialGraph.java) for testing the methods implemented in Part 1. The driver program should build a social graph from an input file data.txt. After building the social graph, in a loop, the program should invite the user to select for execution one of the following operations: (1) normalizedDegreeOfCentrality, (2) numberOfTrianglesIncidentToVertex, (3) listOfTrianglesIncidentToVertex, (4) clusterIndividual, (5) averageClustering, (6) isIndirectAcquaintance, (7) isIndirectAcquaintance, (8) addVertex, (9) addEdge, (10) printEdges and (0) exit the loop and the program. As a result of each operation execution, relevant information should be displayed to the user. For example, as a result of invoking clusterIndividual method, the cluster individual value for the given person should be displayed.

An example of the data input file content, its format and the corresponding social graph layout is shown in the attached file SocialGraph_Example.pdf.

The programs should compile without errors.

Notes. 1. You may consider that there are no errors in the input file structure. 2. If an operation requires additional information, the user will be prompted to enter it. 3. The input file (a simple .txt file) should be generated by the students using a simple text editor such as Notepad. 4. Person names (instead of indices) should be used in I/O operations involved by the user interface.

2. Submission Requirements

Submit the following before the due date listed in the Calendar:

1. All .java source files and the input file data.txt. The source code should use Java code conventions and appropriate code layout (white space management and indents) and comments.

2. The solution description document <YourSecondName>_FP (.pdf or .doc / .docx) containing: (2.1) assumptions, main design decisions, error handling, (2.2) test plan, test cases and two relevant screenshots, (2.3) lessons learned and (2.4) possible improvements. The size of the document file (including the screenshots) should be of three pages, single spaced, font size 10.

homework5/SocialGraph_Example.pdf

This file contains an example and explanations regarding the input file content for the Final Project.

Below please find an example of input file content:

john;peter;mary;susan;george;debbie;tom;bill;

# 0 1 2

1 0 2

2 0 1 3 4 6

3 2 4 5

4 2 3

5 3 6

6 2 5 7

7 6

The correspondent social graph is shown in the figure below.

The list of person names in the first part of the file (until the # separator) defines the vertices while the last part of the file (after the # separator) defines for each vertex its associated adjacent vertices (the vertices are represented by their index in the list of vertices, starting from index 0). Considering the example, in the list of names john has index 0, peter has index 1, etc. The file line 0 1 2 in the second part of the file reads: “the incident edges to vertex 0 are the edges (0, 1) and (0, 2)” or its equivalent “the adjacent vertices to vertex john are the vertices peter and mary”.

tom

0

john

1

mary

2

susan

3

george 4

bill

debbie

peter

6

7

5