代做Data Structures | C语言代写 | 代做Algorithm | Assignment – 这是一个利用C语言的代写，涉及数据结构方面的知识综合应用，对算法理解有要求
CS130A Programming assignment 2
1 Description
The focus of this assignment will be on graphs. Graphs are structures that can model pair-wise relations between entities and are used in various real-world applications, like internet routing, data organization, flow of computation etc. In the following problems, your graphs have nodes connected by weighted undirected edges.
1.1 Part 1
The first part of the assignment is focused on the diameter, radius and centre of a graph. Eccentricity of a node:The eccentricity of a node v is the maximum distance from v to another vertex. Diameter: The diameter is the greatest eccentricity of the nodes of a graph, or the greatest distance between any pair of nodes. One method to do so is to find the shortest paths between each pair of vertices and then choose the largest one. Radius:The radius of a graph is the minimum eccentricity between any two nodes, which is the minimum of the maximum distances between node pairs in the graph. Center:The center of the graph is the set of all vertices u where the greatest distance to other vertices v is minimal. Equivalently, it is the set of vertices with distances equal to the graphs radius. To find the central vertices, find the vertices with lowest eccentricity.
1.1.1 Input
The input to the first part of the assignment is a weighted undirected graph G. The input of the program is a text file with each line describing an edge, with a starting node, an ending node and the weight on the edge. The input file namedpa 2 _ip 1 .txtcontains k lines denoting k edges in the graph. Each of the lines denote the starting node, the ending node and the weight of the edge between these nodes.
6 1 2 2 1 6 3 2 3 1 3 4 2 4 5 3 5 6 1
1.1.2 Output
The output file namedpa 2 _op 1 .txtis expected to have exactly three lines, the diameter, radius and centre node. The first line being the diameter of the graph, the second line being the radius of the graph and the third line being the set of nodes forming the centre.
6 5 1 4
1.2 Part 2
The second part of the assignment is focused on shortest paths within a graph, and correspondingly path centrality of nodes. The path centrality(or betweenness centrality) of a node measures the extent to which a node lies on shortest paths between other nodes. Hence, to measure the path centrality of a node, count the number of times this node is present in the shortest paths of a pair of nodes, and normalize it by the total number of shortest paths for the node pair in computation. Do so for all node pairs and sum the values.
1.2.1 Input
The input to the first part of the assignment is a weighted undirected graph G. The input of the program is a text file with each line describing an edge, with a starting node, an ending node and the weight on the edge. The input file namedpa 2 _ip 2 .txtcontains k lines denoting k edges in the graph. Each of the lines denote the starting node, the ending node and the weight of the edge between these nodes.
6 1 2 2 1 6 3 2 3 1 3 4 2 4 5 3 5 6 1
1.2.2 Output
Two separate output files are required for this assignment. The first output file namedpa 2 _op 2 _ 1 .txtis expected to be a distribution of lengths of shortest paths between all pairs of vertices in one file, ordered according to nodes. For example:
1 2 2 1 3 3 1 4 5 1 5 4 1 6 3 2 3 1 2 4 3 2 5 6 2 6 5 3 4 2 3 5 5 3 6 6 4 5 3 4 6 4 5 6 1
The second output file namedpa 2 _op 2 _ 2 .txtis required to have a list of nodes in ascending order of path centralities, along with the number of shortest paths passing through these nodes.For example:
2 2. 3 2. 1 2 4 2
6 1.
5 1.
1.3 Part 3
In this part of the assignment, You will employ a different approach in finding the shortest path between nodes. Dijkstras Algorithm which you have used in the previous parts finds the shortest path between two source and destination by finding the next closest node from source until it reaches the destination node. In some cases, this might result in visiting nodes that are not on the shortest path. To avoid this, you now need to implement an algorithm that expands the search by finding nodes one forward from the source and one backward from the destination node, stopping when the two meet in the middle. In the above example, assume root 1 to be source and root 2 to be destination. You can see
Figure 1: Sample Graph with bi-directional search
search initiated from source and destination meeting at common node.
1.3.1 Input
The input of the program is a text file namedpa 2 _ip 3 .txtwith each line describing an edge, with a starting node, an ending node and the weight on the edge. The first line of the input file contains an integer k denoting the number of edges in the graph. The following k lines denote k edges in the graph. Each of the lines denote the starting node, the ending node and the weight of the edge between these nodes. The last line contains two nodes, being the nodes from which your search should begin.
6 1 2 2 1 6 3 2 3 1 3 4 2 4 5 3 5 6 1 1 5
1.3.2 Output
The output of the program is expected to be a single output file namedpa 2 _op 3 .txt, having exactly three lines. The first line must contain the source node and the sequence of nodes visited during the bidirectional search. The second line must contain the destination node and the se- quence of nodes visited from the destination node during the bidirectional search. The third line is expected to have the sequence of nodes visited from source to destination using unidirectional search. Essentially, your output format must look like: Source_Node Node1 Node2 Node3 Node Destination_Node Node7 Node5 Node Source_Node Node1 Node2 Node3 Node4 Node5 Node7 Destination_Node
Sample output: 1 6 5 6 1 5 6
1.4 Part 4
In this assignment, you will essentially find the centroid of three given points in a graph network. The centroid of three points in a Network is the point that is at the least distance from all three points. Given three points, if you consider a hypothetical triangle with these three points as the vertices, your job is to find the point closest to all three vertices, called the centroid.
You will be given a weighted graph, and the focus of the assignment is to come with an algo- rithm to efficiently find the point closest to each of the vertices. A brute-force method would be to find the distances from all three sources serially, and find the smallest distances. However, a more efficient method would be to implement a tri-directional search. More specifically, you should use a modified version of Dijkstras algorithm in such a way that there is a simultaneous radial expansion from the 3 source nodes, and the centroid then would be the first node for whom the triple search overlaps. You are free to use any combination of Data Structures and algorithms to efficiently store, traverse and solve the problem.
In the given network, if the given three points are (A,B,C), and the weight on all of the edges is
Figure 2: Sample Graph with Centroid
one, the centroid of triangle ABC is point M, which is one unit away from nodes A and B and two units away from C, thus making the total distance equal to 1+1+2=4. Similarly, point M1 can also be a centroid, being two units away from nodes A and B, and one
unit away from C. This makes the total distance equal to 2+2+1=5. Hence, M is the desired centroid.
1.4.1 Input
The input of the program is a text file namedpa 2 _ip 4 .txtwith each line describing an edge, with a starting node, an ending node and the weight on the edge. The first line of the input file contains an integer k denoting the number of edges in the graph. The following k lines denote k edges in the graph. Each of the lines denote the starting node, the ending node and the weight of the edge between these nodes. The last line contains three nodes, being the nodes from which your search should begin. 11 1 2 1 1 4 3 2 3 2 3 4 2 3 5 1 3 6 3 4 7 3 5 7 2 6 9 1 7 8 2 8 9 2
1.4.2 Output
The output is expected to be a file namedpa 2 _op 4 .txt, containing the node that has the least distance to each of the three vertices. For example, 3
2 Turn-in
Turn-in all your code, including input files and output files your code generates. Create one master cpp file calledf inal.cppthat performs all four parts of the assignment and outputs the 5 output files with the exact names specified. Essentially, we should be able to run onlyf inal.cppand generate all output files needed.