We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + Link For Past Papers, Solved MCQs, Short Notes & More

Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion

# CS502 GDB

Dear Students,

Graded discussion (GDB) will be launched on 22nd January, 2018 and it will remain open for two days. You can post your comments on the below mentioned topic till 23rd January, 2018.

Scenario

Consider a very large undirected graph of Email Networks. The nodes (or vertices) represent email addresses, and an edge represents the fact that there was at least one email in at least one direction between the two addresses.

Which technique will you use for representation of the above mentioned Graph in a computer program for its manipulation?

A concise, coherent and to the point comment is preferred over lengthy comment having irrelevant details. Your comment must not be more than 4-5 lines. Comments, posted on regular Lesson's MDB or sent through email will NOT be considered in any case. For any queries please email at CS502@vu.edu.pk

Best of Luck!

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?

Views: 5707

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

### Replies to This Discussion

CS502 GDB SOLUTION
Solution 1:
I would use 2 flat tables.

Solution 2:
It depends on the number of people emailing each other and on the operations done on the graph.

If there is a high chance that 2 people have emailed each other then you should go with adjacency matrix.

On the other hand if the number of edges (2 people who emailed each other at least one) is small compared to the number of email addresses you should go with adjacency list.

Another thing to look at is what types of operations are you doing on the graph.

Plz check and tell

which is correct tec

Attachments:

how?

koi argument to dyn

storage for matrix is n^2 while for list is n+e which is less than matrix

It depends on the number of people emailing each other and on the operations done on the graph.

If there is a high chance that 2 people have emailed each other then you should go with adjacency matrix.

On the other hand if the number of edges (2 people who emailed each other at least one) is small compared to the number of email addresses you should go with adjacency list.

Another thing to look at is what types of operations are you doing on the graph.

So, if the majority of the operations consist of querying if two nodes have an edge between them, then adjacency matrix would be the best choice.

On the other hand if the majority of the operations are traversing the graph or querying the list of nodes connected to a given node, then adjacency list would be better.

If you are doing a mix of both types of queries, you could represent the graph as an array of hash tables. So, it would be an adjacency list representation using hash tables instead of lists.

I would use 2 flat tables.

Address1 will be the ID number that is numerically lower of the pair.

OR

Hints:
Properties of the given dataset:

1. Could have a large number of nodes.
2. Generally very large and sparce.
3. Requires relatively efficient search algorithm given a node.
4. In general, contains cycles.
Since cycles are present, we can safely eliminate trees. Lists are not useful since the number of branches is not constant. Consider matrix (each column/row is a node, intersection determines edges) but matrices are not space efficient.
Hash tables should provide an efficient storage, as well as rapid searches.

41 minutes ago
52 minutes ago
52 minutes ago
1 hour ago
3 hours ago
4 hours ago
4 hours ago
4 hours ago
4 hours ago
4 hours ago
4 hours ago
4 hours ago

1

2

3