Algorithm for Graph/Data Structure on Java

I have been working on the following problem where, I have a CSV file with two columns, we can say the filed names are "Friends". Both the columns contain letters from A to Z. e.g.

A B
B C
A E
D F
E F

Each row has two different letters(no duplication in the row). A is a friend of B, C is a friend of D etc...If person A talks to person B and Person B talks to person C, then B and C will become aquitances. Aquintaces are who share a common friend. I need to fin out who has more aquintances?

I have been trying with two different methods one using differnt data structures like hashmap, arraylist, stack etc, and another using graph theory (JGraphT library). But, i am stuck with the logic if I use data strcutres and I am stuck with traversal in the graph if I use graph theory.

I have following questions:-

  1. What is a better approach to go with data structures or graph? Or any other better approach/logic/algorithm than this?
  2. Does anyone know how to traverse a graph in JgraphT Library. I am not able to do this, they have very limited documentation about the library.

Please, any help would really be appreciated.

Answers


Generally HashMaps are among the most rapid and easy to use. I would recommend you use them rather any custom libraries, except if you are sure that some library will do easily something you need and something that will take longtime for you to code.

In your case, just you can just use each person as a key and the list of his friends as the object pointed to by. Parsing your .csv file and filling the HashMap accordingly will solve your issue, as a previous comment pointed out.


You can have a hash table first that maps every letter to the set of its friends, e.g. A maps to { B }, B maps to { C }, and if Z has two friends Y and W then Z maps to { Y, W }. This is a hash map from letters to sets-of-letters.

To calculate the acquaintances, iterate through the hash map. When you are at entry A -> { B, C, F } then iterate in an inner loop through the set B, C, F. Collect their friends (three sets) into a single set (just insert the elements into a temp set) and remove A from that set if A was found. The size of that set is then the number of acquaintances for A. Rinse and repeat.


Need Your Help

the relation of the bezier Curve and ellipse?

html5 canvas relationship bezier

I want to draw a oval in html5 canvas,and i found a good method for it in stackoverflow.but I have another quesition.

How to get upload speed in JAVA

java android tomcat servlets

I am studying android app and I would like to build example code to check upload speed.