[SOLVED] CS251 Project 4 Computing Graph and Tree-path Properties

Introduction

In this project you will write functions to determine various graph properties and perform explorations on trees. Graphs and trees will be represented by either adjacency lists or adjacency matrices, they will be undirected or directed, and the properties will range from simple checks to recursive traversals. The techniques you will use are common in graph problems you will encounter in later courses.

Learning Objectives

• Explain the advantages and disadvantages of the different graph representations using concrete examples.
• Demonstrate effective use of graph and tree traversal strategies. ● Perform basic linear-time operations on a directed acyclic graph.
• Apply recursion to tree computations. In particular, to a tree problem in which an objective function is maximized.

Definitions and Notations

Assume graph G = (V, E) has n vertices and m edges with V = {0,1,2, … , n-1}. All graphs are simple graphs. Note that (u,v) represents an undirected edge or the edge from u to v in a directed graph. Do not make any assumption about the connectivity of a given graph.

Problems will specify which graph representation to use:

Adjacency Matrix M

• M of size n x n
• M[u][v] = 1 if (u,v) is an edge of graph G and M[u][v] = 0 otherwise. For undirected graphs, M[u][v] = 1 implies M[v][u] = 1.

Adjacency lists

• An array A of size n; A[u] points to the list of vertices incident to vertex u.
• For directed graphs, the adjacency list of vertex u contains the vertices of the outgoing edges.
• For undirected graphs, edge (u,v) has u in v’s list and v in u’s list.
• Vertices do not necessarily have to be in the sorted order in the list

For all problems:

• If the running time is given, your report needs to explain how it is achieved by your implementation.
• If the running time is not given, give the worst-case time bound your implementation achieves along with a brief implementation in the report.
• You can use an auxiliary array of size n if needed. Give a brief explanation what it is used for in the report.
• The graphs may or may not be connected.
• The graphs are always simple

1. File IO and Graph representation.

ListGraph

Implement a ListGraph class. The class should contain a read(String filepath) function and a readWeighted(String filepath) function. These functions will read the graph from the input file and then store it in an adjacency list representation.

You have to come up with your own linked list and write your own node class. Imports are not allowed. The node class should be inside the same file as ListGraph.

public static ListGraph read(String filepath) throws IOException {}

This function reads the unweighted graph stored at the given file path into memory.

vertices are indexed from 0 to . The𝑛lines of the file are indexed starting from 1, ● Line 1 of the file contains a single integer specifying the number of vertices. The as in IntelliJ. 𝑛 − 1

• For each integer such thatof the file is a space-separated ● For undirected graphs, if an        then    will be present on line           , and

list of all vertices 𝑢𝑣 such that         𝑢 − 𝑣                   the𝑢 𝑣graph.                     𝑢

will also be present on line   .

• If𝑢 vertex 𝑢 has no outgoing edges,𝑣 line 2 + 𝑢 will be empty.

public static ListGraph readWeighted(String filepath) throws IOException {} This function reads the weighted graph stored at the given file path into memory. The file specification is identical to the unweighted case, except:

• Line 2 is now a space-separated list of integers specifying the weights of vertices ●    The vertices𝑛 − in1 the out-neighbourhood of vertex 𝑢 are now specified on line 3 + 𝑢.

through           , respectively.                  𝑛                                                                          0

MatrixGraph

Implement a MatrixGraph class. This class should contain a read(String filepath) function. This function will read the graph from the input file and then store it in an adjacency matrix representation.

public static MatrixGraph read(String filepath) throws IOException {}

This function reads the unweighted graph stored at the given file path into memory. The file specification is identical to the ListGraph.read case except that it uses the matrix representation to store the graph in place of the list.

1.   Undirected Graph Properties

Tree-check

G is an undirected n-vertex graph represented by adjacency lists. Determine in O(n) time whether G is a tree. public static boolean treeCheck(ListGraph a)

Counting triangles

G is an undirected n-vertex graph represented by an adjacency matrix. Count the number of distinct triangles in G in O(n³) time. Vertices x, y, and z form a triangle if the edges (x,y), (y, z), and (z,x) are in G. Note: triangle(x,y,z) = triangle(z,x,y). public static int countTriangles(MatrixGraph a)

Clustering coefficient of a vertex

G is an undirected n-vertex graph represented by adjacency lists. Given a vertex u, determine u’s clustering coefficient. The clustering coefficient is defined below.

Assume an edge between vertices u and v means that u and v are friends. The clustering coefficient of u is the fraction of pairs of friends of u that are friends with each other. If a vertex has k friends, the clustering coefficient is 0 when none of the k friends are friends with each other; it is 1 when all k friends are friends with each other (i.e., they form a complete graph on k vertices).

More formally, when vertex u has degree d(u), the clustering coefficient of u is 2×(𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠(𝑑(𝑢 𝑥)× 𝑎𝑛𝑑(𝑑( 𝑢𝑦) 𝑜𝑓−1 𝑢) 𝑤𝑖𝑡ℎ 𝑒𝑑𝑔𝑒 (𝑥,𝑦) 𝑖𝑛 𝐸)

The graph shown below gives the clustering coefficient for each vertex. Vertex A has 4 neighbors. Four vertices can have at most ⁴C₂ = 6 edges between them. For vertex A, 3 pairs of neighbors are friends with each other. A’s clustering coefficient is thus 3/6 = 0.5.

Compute the clustering coefficient of a vertex u in O(n²) time. As noted above, you can use an auxiliary array of size n during the computation. You are not supposed to convert the adjacency list representation of the graph into its adjacency matrix representation. public static double vertexClusterCoeff(ListGraph a, int u)

Clustering coefficient of G

The global clustering coefficient of a graph is defined as the average of the n clustering coefficients of its vertices. Compute in O(n³) time.

public static double graphClusterCoeff(ListGraph a

2.   Directed Graph Properties

Compute in-degrees

G is an n-vertex directed graph represented by adjacency lists. Determine in O(n+m) time the indegrees of all the vertices in the graph. Return an array inDeg where inDeg[u] represents the in-degree of vertex u.

public static int[] computeInDegrees(ListGraph a)

DAG-check

G is an n-vertex directed graph represented by adjacency lists. Determine in O(n+m) time whether G is a directed acyclic graph (DAG). If G is a DAG, determine the number of sources and number of sinks.

dagCheck(adjList A) returns a pair of integers (in0, out0), where in0 represents the number of sources and out0 represents the number of sinks. If G is not a DAG, the output should be

(-1,-1).

public static int[] dagCheck(ListGraph a)

3.   Recursive Tree Exploration

Given is an n-node free tree T=(V,E) with V = {0,1,2,3 …., n-1}. We assume n>2. The tree is represented by adjacency lists. Every node v has a positive integer weight w(v).

You are asked to determine the cost of a max-weight path P in tree T which has the following properties:

1. The path P is between two leaves of T.
2. Selected nodes on path P get marked. The sum of the weights of the marked nodes on P is the weight of the path.
3. Path P cannot contain two marked nodes that are adjacent. We call a path with no adjacent marked nodes a valid path.
4. Path P has maximum weight; i.e., the sum of the weights of the marked nodes on P is a maximum over all possible valid paths between any two leaves in T.

Consider the tree shown in Figure 1.The green edges between leaves x and y form a valid path as no two marked (green) nodes are adjacent. The cost of the path is 215 and it is a max-weight path.

We note that a path in which marked and unmarked nodes alternate is a valid path. However, in a max-weight path marked and unmarked nodes do not necessarily alternate. This occurs in the path from x to y where the node x is marked and the next two nodes on the max-weight path are not marked. For instance, in Figure 1, this allows the nodes with weights 30 and 35 to be marked, while leaving the two vertices with weight 5 unmarked.

Figure 2 shows three trees that are chains in which the patterns of which nodes are marked vary. The max-weight path does not necessarily alternate nodes and does not need to include the leaf nodes. Note that in a max-weight path there will never be three consecutive unmarked nodes between two marked nodes (as the weights are positive, the middle unmarked node should always be included).

The goal is to find the cost of a max-weight path in T (a tree can contain more than one max-weight path). The algorithm for finding the cost of a max-weight path needs to have O(n) time complexity and use the recursive formulation described below.

We describe in section 3.1 a recursive approach for determining which nodes to mark when tree T is a linear chain. In 3.2 we extend the approach to finding the cost of a max-weight path in an arbitrary tree. Make sure you understand the approach for a chain before working on the tree.

Input Format

For the input, you will use the method readWeighted(String filepath)you implemented in ListGraph to read in a Graph as a ListGraph containing int []weight indicating the weight of each node weight[i]. You need to implement functions named maxWeightChain, maxWeightTree. The return type should be an integer that is the value of the maximum weighted path.

3.1.  Determining the max-weight in a chain

Given is a chain C on n nodes represented by adjacency lists. Let s be one of the two leaves of chain C. The max-weight for chain C is computed in O(n) time using the recursive approach described below. Note that you do not need to determine the nodes on the chain contributing to the max-weight.

The chain exploration should start from a leaf node. During recursion, the nodes having a child-parent relationship reflect the recursive calls made (as done in DFS).

Let (u,v) be an edge on the chain. The recursive call made with v as an argument from node u returns three values: in(v), out1(v) and out2(v):

• in(v): the max-weight achievable when node v is marked (i.e., w(v) is included)
• out1(v): the max-weight achievable when node v is not marked and the child of v is marked.
• out2(v): the max-weight achievable when neither node v nor the child of v are marked.

Node u uses the values of in(v), out1(v) and out2(v) to determine in(u), out1(u) and out2(u). We illustrate this in Figure 3 for one of the chains shown in Figure 2. The triples next to each node represent the three values the node returns.

• Node f is a leaf and in(f) = w(f) = 100 and the two out-values are 0. Node f returns the triple (100,0,0). This defines the base case of the recursion.
• Node e receives (100,0,0) and sets in(e) = w(e) =30 and out1(e) = in(f) =100; out2(e) remains 0. Node e returns the triple (30,100,0).
• Work through the triples for nodes d to a on your own and understand what solutions they represent.
• Finally, node s receives (415, 310, 400). The quantity 400 represents out2(a), the max-weight achievable in the chain from node a to f that does not include w(a)=15 and w(b)=10. Node s determines its triple to return using the rules stated in Figure 3. The value out2(a) = 400 is used to determine in(s) = 445 = 45+400 which represents the solution marking nodes s, c and f.

Let u1 and u2 be the two leaves in the chain. If the initial call is made with leaf u1 then, in(u1) = w(u1), out1(u1) = out2(u1) = 0, and the final returned weight will be max(in(u2),out1(u2)).

Let (u,v) be an edge in the chain. The recursive call made by u receives in(v), out1(v) and out2(v). The three values node u returns are:

1. in(u) = w(u) + max{out1(v), out2(v)}
2. out1(u) = in(v)
3. out2(u) = out1(v)

When node u is marked, we add to its weight the maximum of the two subsolutions we determined (and return the value in in(u)). When node u is not marked, we return two values reflecting that we either have node v marked (out1(u)) or the second node adjacent to v marked

(out2(u)).

Write function public static int maxWeightChain(ListGraph a) using the recursive approach described above.

3.2.  Determining the max-weight in a tree

Given a tree T, use a recursive tree exploration approach to determine the cost of the max-weight path in O(n) time. You do not need to find the vertices on the path (there can be more than one such path).

The tree exploration finding the cost of a max-weight path can start at any node s. The final cost returned will be the same for any start node, but some intermediate entries computed at nodes will be different.

The tree exploration has similarities with a DFS exploration on an undirected graph: at node u, all nodes v adjacent to u are considered and a call to v is made if v has not been visited. Make sure you understand the three entries, the call to maxWeightChain returns before reading on.

When the tree exploration starts at a vertex s, the path of max-weight may include node s (see Figure 4(a)). The max weight path can also be between two leaves in a subtree rooted at a node adjacent to the start node. If the start node is node s’, as shown in Figure 4(b), the path is in the subtree rooted at node s (and the path is found in the call made by s’ on s).

This means a recursive call made by node u on its neighbor node v needs to return information about the cost of a path in the subtree rooted at node v (this subtree includes all nodes that are reachable from v through a path that does not pass through u). To correctly compute max-weight, a call returns 4 entries on the subtree explored.

Assume there is an edge from node u to v, and u discovers v. The recursive call from v returns four entries related to the subtree rooted at node v:

1. L2: max-weight of a path in the subtree rooted at node v. The two end nodes of the path are leaves in the subtree rooted at v. The path can include node v. The cost of this path could be the final max-weight cost of the tree.
2. in: max-weight of a path in the subtree rooted at node v from node v to a leaf node. Node v is marked.
3. out1: max-weight of a path in the subtree rooted at node v from node v to a leaf node. Node v is not marked. The node adjacent to v on the path is marked.
4. out2: max-weight of a path in the subtree rooted at node v from node v to a leaf node. Node v and the node adjacent to v on the path are not marked.

Consider the tree shown in Figure 5. The exploration starts at node s and we show the 4-tuple returned by calls to nodes v1, u1, and u2. We show arrows on edges to reflect the calls made.

When we refer to a subtree rooted at a node u we always refer to the tree rooted at node u as the recursive call is made to u. Figure 5 shows the subtree rooted at node v2 shaded assuming v2 is called from s.

In the example tree, node s considers its four adjacent nodes in the order v1, v2, v3, and v4:

• Node v1 represents a subtree consisting of the single node v1 having weight 80. It returns (L2, L1.in, L1.out1, L1.out2) = (0, 80, 0, 0). L2=0 as there exists no path between two leaves, marking node v1 results in L1.in=80, and the subtree rooted at v1 contains no other nodes that could contribute to L1.out1 and L1.out2. See Figure 5.
• Node v2 is the root of a subtree containing 10 nodes. Hence, v2 makes two recursive calls: to u1 and u2.

○    Node u1 returns (L2, L1.in, L1.out1, L1.out2) = (0, 45, 22, 0).

○    Node u2 returns (L2, L1.in, L1.out1, L1.out2) = (95, 60, 75, 50).

○       Node v2 combines these values and returns (L2, L1.in, L1.out1, L1.out2) = (157, 135, 60, 75). The process of combining values returned is described below.

• Node v3 makes two recursive calls, each one to a single node subtree. It returns (L2, L1.in, L1.out1, L1.out2) = (37, 10, 22, 0), as shown in Figure 6.
• Node v4 makes two recursive calls and, after combining the two 4-tuples returns (L2, L1.in, L1.out1, L1.out2) = (105, 80, 45, 65).

Node s combines the four 4-tuple received from the 4 recursive calls (one 4-tuple from each recursive call). If node s is the root of the tree T and not a leaf, L2(s) is returned as L2(s) is the weight of the max-weighted path. However, when the start node s is a leaf in tree T, max{L2(s), L1.in(s), L1.out1(s)} is returned, which is the cost of the max-weighted path in T.

In Figure 6, we show the other 3 values as well. These values are relevant when the start node s is a leaf in the tree.

We say that u is an ancestor of v (and v is a descendant of u) if u has been called but not returned at the time when v is called. The root of the tree is the ancestor of all other vertices in the tree.

If v has been called from u then u is the parent of v and v is a child of u. This relationship holds only when (u,v) belongs to E.

Naturally, a parent is an ancestor and a child is a descendant.

In the following we sketch how a node u invoking recursive calls on its k children v1, v2, …, vj manages the 4-tuples it receives from each child. There is no need to store all k 4-tuples. As a 4-tuple is received by u, updates to u’s 4-tuple are made.

Before making any call, node u initializes its 4-tuple (L2, L1.in, L1.out1, L1.out2) = (0,0,0,0). Note that when it is clear from the context which node the L-values belong to, we use them as L2, L1.in, etc. If it may not be clear, we use the notation L2(u), L1.in(u) , etc.

Assume node vj returns to u the 4-tuple (L2, L1.in, L1.out1, L1.out2). See Figure 7 for an illustration:

• L2(vj) is the blue path in the subtree rooted at vj
• in(vj) is the black path from a leaf to node vj (vj is marked)
• out1(vj) is the red path (red node is marked and vj is not marked)
• out2(vj) is the green path (one green node is not marked and one is marked, vj is not marked)

Figure 7

We describe how node u updates its already determined 4-tuple after receiving the 4-tuple from node vj. Note that the description below uses no additional variables about previously computed entries and hence the order in which entries are updated is important. Do not change the order if you use it in your implementation. If you are making changes, make sure to address all aspects of correctness.

Updating L2. Updating L2 means determining the best path between two leaves in the subtree rooted at node u now allowing that the path can go through node u to a leaf in the subtree rooted at vi for i in {1,…,j}.

The new value L2 of u is the maximum of 5 quantities:

L2(u) = max {

L2(u),	previously found best path in the subtree rooted at node u
L2(vi),	best path in the subtree rooted at node vi

L1.in(u) + max{L1.out1(vi), L1.out2(vi)},

first part of the path going through node u, node u marked, and the second part of the path is in the subtree rooted at vi.

L1.out1(u) + max{L1.in(vi), L1.out1(vi)},

first part of the path going through node u, node u not marked, and the second part of the path is in subtree rooted at vi.

L1.out2(u) + L1.in(vi),

first part of the path going through node u, node u and its

neighbor on that path are not marked, vi is marked, and the second part of the path is in the subtree rooted at vi.

}

Updating the other three entries of the 4-tuple. These updates are done after L2(u) has been updated:

●	L1.in(u) =	max {L1.in(u), w(u) + max {L1.out1(vi), L1.out2(vi)}}
●	L1.out1(u) =	max{ L1.out1(u), L1.in(vi)}
●	L1.out2(u) =	max {L1.out2(u), L1.out1(vi)}

Try to think why are the entries above being updated as such. Try to think of cases in terms of inclusion and exclusion of the node in the path.

Base Case:

The node is a leaf.

For a leaf v , set (L2, L1.in, L1.out1, L1.out2) = (0, w(v), 0, 0).

Write function public static int maxWeightTree(ListGraph a) using the recursive approach described above.

Project Structure

You are required to implement the following files:

• java ● MatrixGraph.java ●     UndirectedCheck.java.
• java
• java

ListGraph.java:

You need to implement the following functions:

public static ListGraph read(String filepath) throws IOException {} public static ListGraph readWeighted(String filepath) throws IOException {}

MatrixGraph.java:

You need to implement the following functions:

public static MatrixGraph read(String filepath) throws IOException {}

UndirectedCheck.java:

You need to implement the following functions:

public static boolean treeCheck(ListGraph a) public static int countTriangles(MatrixGraph a) public static double vertexClusterCoeff(ListGraph a, int u) public static double graphClusterCoeff(ListGraph a)

DirectedCheck.java:

You need to implement the following functions: public static int[] computeInDegrees(ListGraph a) public static int[] dagCheck(ListGraph a)

MaxWeight.java:

You need to implement the following functions:

public static int maxWeightChain(ListGraph a) public static int maxWeightTree(ListGraph a)

Testing your code

We provide a set of JUnit tests for the functionality in this project at GraphTest.java. Before running the tests, download and extract data.zip from BrightSpace, and change line 14 of GraphTest to point to the extracted directory.

Report

You are required to submit a report.

• The report should describe for each problem in sections 1 and 2 the approach you used and how the stated time complexity is achieved. The description given for each problem should be brief and not repeat material covered in class.
• For the two problems in section 3 describe any variations you made to the given description. Clearly address why your code achieves O(n) time.
• The final paragraph of the report should address two questions:

○    Which of the problems was the most interesting? Address why.

○           Which of the problems was the most challenging one to complete? Address why.

The overall report guidelines and expectations are:

• The report needs to be typed (use LaTeX or Word).
• Your name (Last, First), your Purdue email, and your section number (LE1@4:30 or LE2@1:30) need to be on top of page 1.
• The RC statement needs to be given for each problem in section 1, 2 and 3. It should be the first line(s) before the description.
• The suggested length of the report is up to 2 pages, with font size 12 and 1.5 spacing. If you have additional supporting material you can include it as an Appendix (which has no page limit). However, only your report will be graded. The appendix may be consulted by the grader for additional information.
• Reports are uploaded to Gradescope and code is uploaded to Vocareum.

Grading

The expected grading rubric is given below. ●       Coding part (85 points)

○    Tree-check, Counting triangles, Clustering coefficient (vertex and graph), in-degrees, DAG-check. (30 Points)

○    Recursive exploration on a tree: max-weight on a chain; max-weight on an arbitrary tree (55 Points)

• Overall quality of the report (15 points)

■    Quality and conciseness of writing

■    Logical flow of arguments for each problem

■    Clear explanation of running times your code achieves for each of the eight problems

Submission

• To Vocareum (everything should be inside the src folder):
  • Java

○    UndirectedCheck.Java

○    MaxWeight.Java

○ ListGraph.Java ○ MatrixGraph.Java

• To Gradescope:
  • pdf

Note:

• Additional imports are not allowed. (other than the ones in the starter code)
• No other file uploads are allowed. Only those files will be compiled. If you have to write a new Java Class, please do so in one of the files above.
• If for some reason you do not see the src folder under the work folder on Vocareum, please make a new src folder.
• This has been explained on Piazza already so you can refer to it there. ● Please go to office hours for additional help.