CODEWITHSUNDEEP
javadatabase
namarath
namarath

Reputation: 141

Shortest path problem with DB and java

I have a movie database (postgreSQL). One of tables contains actors and movie titles. The assignment which I have to solve in java is as follows: two actors (A and B) are connected together when they in the same movie. Further two actors, A and B, are also connected when there is a third actor C, who plays with both of them in different movies (A and B don't play together!) and so on... I hope you get the idea :) Now I have to find the shortest connection (= path) between two actors.

Now to the implementation: fetching the data from the DB (prepared statements) and saving the names (as strings) in a linked list is working. As well as simple connection between actors like A -> B (= both play in the same movie). I'm hitting the wall trying to include more complicated connections (like A -> B -> C).

I am storing the actor names in a HashMap like this:

Map<String, List<String>> actorHashMap = new HashMap<String, List<String>>();

So when I load the first actor (Johnny Depp) I have his name as key, and other actors playing with him in a list referenced by the key. Checking, whether another actor played with him is easy: 

List<String> connectedActors = actorHashMap.get(sourceActor);
if(connectedActors.contains(actor)) {
         found = true; }

But... what do I do if the actor I'm looking for is not in the HashMap (ie. when I have to go one level deeper to find him)? I assume I would have to pick the first actors' name form the connectedActors list, insert it as new key into the HashMap, and fetch all actors he played with him to insert them to. Then search in this list.
But that's exactly the part which i can't figure out. I already tried to store the names in graph nods and using bfs to search for them, but same problem here, just don't know how to go "one level down" without creating an infinite loop... Does anyone have an idea how i can solve this? I am just starting with java as well as programing in general so it's probably simple, but I just can't see it :/

Upvotes: 1

Views: 520

Answers (1)

toto2
toto2

Reputation: 5326

First I would use a Set to store the actors someone played with:

Map<String, Set<String>> actorHashMap = ...

instead of a List to avoid duplicate names.

In order to find how many degrees of separation between 2 actors I would start with one actor and generate all actors that are separated by 1, 2, 3... degrees. I would fix a maximum search depth, however that might not be necessary if the number of actors is not too large.

String actor = "Johnny Depp";
String targetActor = "John Travolta";
Map<String, Integer> connectedActorsAndDepth = new HashMap<String, Integer>();
Integer depth = 1;
Set<String> actorsAddedAtCurrentDepth = actorHashMap.get(actor);
for (String otherActor : actorsAddedAtPrecedingDepth) {
    if (otherActor.equals(targetActor)) return depth;
    connectedActorsAndDepth.put(otherActor, depth);
}
Set<String> actorsAddedAtPrecedingDepth = actorAddedAtCurrentDepth;
Integer maxDepth = 10;
while (++depth < maxDepth) {
    actorsAddedAtCurrentDepth = new HashSet<String>():
    for (String otherActor : actorsAddedAtPrecedingDepth) {
       if (otherActor.equals(targetActor)) return depth;
       if (!connectedActorsAndDepth.contains(otherActor)) {
           actorsAddedAtCurrentDepth.add(otherActor);
           connectedActorsAndDepth.put(otherActor, depth);
       }
    }
    actorsAddedAtPrecedingDepth = actorsAddedAtCurrentDepth;
}

I do not claim it is the most efficient algorithm. There might also be bugs in the code above.

Upvotes: 0

Related Questions