Şimdi Ara

Para ile Java Ödevi Yapacaklar

Sıcak Fırsatlarda Tıklananlar

Editörün Seçtiği Fırsatlar

Daha Fazla

Bu Konudaki Kullanıcılar: Daha Az

2 Misafir - 2 Masaüstü

5 sn

1
Cevap

0
Favori

882
Tıklama

Daha Fazla
İstatistik

Konu İstatistikleri Yükleniyor

Konuya Özel

0 oy

Öne Çıkar

Cevapla

Sayfa: 1

Giriş

Mesaj

Arkadaşlar çok acil çarşamba geceye kadar yetişmesi gereken bir ödevim var, ücrette anlaşırız. proje detayları aşağıda...

CMPE3005 Programming Project

Graph Analysis

Many things in the real world (such as friendship relations among people, distance relations among cities or precedence relations among tasks) can be represented by graphs. Once these relations are represented as graphs then one often needs to answer certain questions about these graphs.

In this project your task to read a graph data, represented in with a suitable data structure in memory, and answer certain questions about it.

More specifically, you will be given a text file which contains an undirected graph information.

Below is a sample file:

1000

3 7

5 24

12 45

...

The number n (1000 in the above example) in the first indicates the maximum vertex id, i.e., vertex ids must be between 0 and n-1. The rest of the lines specifies the edges between these vertices. For example the second line specifies an edge between vertex 3 and vertex 7.

You should be able to read this file and build a suitable data structure (adjacency-list or adjacency-matrix) to store it. A sample file will be provided to you. Note that during the demos we will test your code with different text files (representing different graphs), so your code should work with any text file confirming the above specifications.

Then your program will print the following menu:

1> Sparsity of the graph.

2> Degree of a vertex.

3> Max, min, and avg. degrees.

4> Shortest path between two vertices.

5> Shortest path passing through a particular vertex.

6> Average shortest path length.

Your program should carry out these tasks for the loaded graph. Specifically:

1) If option 1 is selected then your program should print the sparsity value of the graph. Sparsity value of a graph is defined as the proportion of the number of edges to the total number of all possible edges (try to find the formula for total number of all possible edges your self).

2) If option 2 is selected then your program should get a vertex id as input and print its degree. The degree of a vertex is given by the number of edges connected to it.

3) If option 3 is selected then your program should print the maximum, minimum, and average degree values of all vertices.

4) If option 4 is selected then your program should get two vertex ids as input and print the shortest path length between these two vertices as well as the path itself.

5) If option 5 is selected your program should take three vertex ids as input and print the shortest path between the first two vertices which passes through the third vertex. Again, you should print both the shortest path length and the path itself.

6) If option 6 is selected then your program should print the average of the shortest paths between all possible pairs of vertices.