CS Project Help (3.5 Degrees of Separation/6 Degrees of Separation)

I am working on something for CS and am having a lot of trouble figuring it all out.
The program I need to do has a concept of "Six Degrees of Separation" or "Six Degrees of Kevin Bacon." The idea is that any actor in any movie can be linked to Kevin Bacon through a series of actors that appeared in a movie together.

For example, Ian McKellen, who played Gandalf in the "Lord of the Rings" trilogy, was in "The DaVinci Code" with Tom Hanks, who was in "Apollo 13" with Kevin Bacon. This is a two movie link 'chain' connecting Ian McKellen and Kevin Bacon. Supposedly all actors can be linked back to Kevin Bacon in no more than six links.
The solution program will read a file whose content is a list of movies and a list of sets of actors that appeared in those movies. You need to find a chain of no more than three links that connect two given names (not only Kevin Bacon). We use three rather than six to keep input files of a reasonable size. Also, the current Facebook research shows that maybe the legend should be amended down to three; see the research link above.

This program will connect the actors/actresses in less than three links.

I have this for my to do and requirements set for myself:
My main program, ThreeDegrees.java, is a Java implementation that:

Prompts the user for the name of an input file.

Reads the file contents into a graph data structure.

Prints the graph data structure.

Prompts the user for two names to try connecting.

Performs the search and either will print the shortest chain linking the two names in a chain of maximum length three, or prints a message that reports no chain was found. (See the examples for the text your program should print.)

If either the first or second name is the empty string (the user hit enter giving no name), then the program should end.

If either name is not found in the graph, then the program should print a message to that effect, and request two new names for the next search.

Here is an example file of movie-actor relationships. (The program will read the file and process search queries):
*The title will always be one word and all names will be two words.
Apollo13 Kevin Bacon Tom Hanks Gary Sinise
HollowMan Elisabeth Shue Kevin Bacon Josh Brolin
AFewGoodMen Tom Cruise Demi Moore Jack Nicholson Kevin Bacon
OneCrazySummer John Cusack Demi Moore
DaVinciCode Tom Hanks Ian McKellen Audrey Tautou

Any and all help would be appreciated. Thanks in advance

Hi Jason, That's all good but what exactly are you having trouble with? Tell us what is your general plan of attack for this and show us what you've done so far that has you stumped. You have to do the heavy lifting on your homework, we're just here to advise and direct you around problems.

Junilu Lacar, thank you for the reply. I guess my biggest issue is finding the relation in the actors. I will explain more below.

I have made the following to add provided data to a Graph

I remember being suggested to turn the graph data into a string so I did the following for that (I could use some verification on if this is a decent way to do so)


So I guess it is best to say that I am having the most trouble with figuring out exactly how to compare everything and find the shortest way to connect actors.

It has been many years since I minored in Computer Science in school but I don't recall using a map to represent a graph. A graph is made up of nodes that are connected to each other. There are different kinds of graphs and you're going to have to choose the appropriate kind for this problem. There are also various algorithms to traverse a graph, some of which have to do with finding the shortest path between two nodes on the graph. Does this ring any bells for you? Surely, your instructor must have taught you about graph theory, didn't he/she?

Looking at your code again, I see how you're using the map. I suppose that is a convenient way to keep track of nodes. When I was studying graph theory in school many, many years ago, we used Pascal for our programs and had to write ALL of our abstract data types/structures ourselves. No predefined libraries to use back in those days.

When you say "how to compare everything" that doesn't really say much. Be more specific. Give examples of what you're trying to do. What graph traversal algorithm are you thinking of using? What algorithms have you learned so far?

Jason Ram wrote:Any and all help would be appreciated.

Well, my first thought is that you may be diving into the problem too quickly.

From your description, I get two things:
1. That you have two classes of data object: An Actor, and a Film, with each Film containing a list of Actors. So my first order of business would be to create Sets (perhaps HashSets) of each, which should be relatively easy to do directly from your input.

2. The "degrees of separation" are strictly Actor-to-Actor. How they are connected (ie, which films connect them) may not even be relevant to the problem, but I suspect that the number of connections is.

Now here I have to speculate because I never did graph theory or "shortest path" stuff, but in rdb terms the Actor-to-Actor relationship is a many:many one, so I would create an associative entity (Pairing?), each of which contains a reference to two different Actors and a list of the Films they both appear in (because the length of that list will give me a "link count"). And now that you have Sets of Actors and Films, it should be relatively simple to populate a list (or Set) of Pairings.

Now how you get from there to 'Nodes' (or indeed calculate whatever "distances" you have to) I'm not quite sure; but that's how I'd start out.

And hopefully I'm not totally out to lunch on this.

HIH

Winston

As far as searching goes, it was recommended to use breadth first search.

Winston, I'll give what you said a try.
I may end up going slightly out of the guidelines, but that is okay.

Jason Ram wrote:As far as searching goes, it was recommended to use breadth first search.
Winston, I'll give what you said a try.
I may end up going slightly out of the guidelines, but that is okay.

I hope I'm not steering you wrong, but Java is all about creating useful objects, and the data you showed me practically screams at Actor and Film classes at the very least.

One thing about a Pairing (if you decide to go with it): Two Pairings should be "equal" (ie, equals() should return true) if they involve the same Actors in any combination. That will stop you from creating duplicate pairings if you put them in a Set.

Unfortunately, that makes calculating the hashcode for a Pairing object a bit tricky, so here's my suggestion:
1. Make your Actor objects Comparable.
2. Put the Actors in each Pairing in ascending sequence - regardless of how they're supplied.

I suspect that once you have a Set of Pairings, you could also add them to the relevant Actors, which would kind of turn each Actor into a "node" (which I suspect is what you want).

HIH

Winston

Yes Winston, that sounds like what I need.

I haven't really learned about pairings yet but from your description they seem like they will work.
I'll give it a go after one or two more tries on something with nodes that I'm trying to do.

Thanks for the help so far

Winston Gutkowski wrote:I suspect that once you have a Set of Pairings, you could also add them to the relevant Actors, which would kind of turn each Actor into a "node" (which I suspect is what you want).

Sorry to keep adding stuff, but it occurs to me that I may have missed out "node", which is probably relevant.

I suspect that Node should be an interface that Actor implements, since it's "actor paths" we want to analyse; but exactly what methods a Node should have I'm not sure.
Someone with knowledge of node theory may be able to help you out there, and I doubt whether not having one will stop you from writing a solution; but I suspect you'll be able to write a much more generic one if you include it.

Hope it helps - and good luck.

Winston

Jason Ram wrote:I haven't really learned about pairings yet

Unsurprising, since it's just my "take" on the sort of information you're likely to need.

There may be easier ways to do it, but none leap out at me - but that could be simply because I don't know much about node theory.

So: Caveat ranchor.

Winston

PS: I totally forgot. Welcome to JavaRanch.

One thing that might help you is to first figure out some degrees of separation manually.

For example, you could try to manually find how many degrees of separation there are between

1. Ian McKellan and Josh Brolin
2. Audrey Tautou and Demi Moore
3. John Cusack and Gary Senise
4. Tom Hanks and Demi Moore
5. Jack Nicholson and Audrey Tautou

All of these pairings have degrees of separation that are greater than 1. Figure out how your chosen traversal algorithm works by tracing through it with these examples. Once you understand that, it becomes pretty easy to translate your understanding into code. Some pairings don't even have to go through Kevin Bacon. Like Ian McKellan and Gary Senise, who have 2 degrees of separation through Tom Hanks; a link through Kevin Bacon is redundant.

Junilu Lacar wrote:Some pairings don't even have to go through Kevin Bacon.

Perhaps I didn't make myself clear. A Pairing is simply a link between adjacent Actors - ie, ones who are known to have acted together.

"Separation" analysis is a whole different ballgame. I'm just trying to put together the "node map".

Sorry if I wasn't clear.

Winston

Jason Ram wrote:Any and all help would be appreciated.

One other thing occurred to me: your example data doesn't appear to have any "multiple" links - ie, pairs of Actors who have worked on more than 1 film together.

It might be good to add a few.

Winston

Winston Gutkowski wrote:
One thing about a Pairing (if you decide to go with it): Two Pairings should be "equal" (ie, equals() should return true) if they involve the same Actors in any combination. That will stop you from creating duplicate pairings if you put them in a Set.

I'm not sure why you would want a Pairing class.
From the input data you can create an adjacency map, say Map<Actor, Set<Actor>>.
(note: beware that in the input file an actor's name consists of first and last name, separated by a space!)
Then, looking for the shortest path connecting two actors is indeed a matter of BFS, requiring a queue and
a set of "actors already seen".

I have done some work, and using nodes is the way to go after talking to an assistant professor.
I have a Node class and a Graph Class. Both classes are below.

NODE


GRAPH


So I confirmed that these are both on the right track. I need to write another class that will actually do the work for finding the link.
I have an idea of what needs to be done and I will post it in the next reply

Well, of course it can be done in this way too!

The final class I need to write is going to be called ThreeDegrees.
It will do the following:
Find the chain of no more than three links connecting actors/actresses in various movies and asks for an input movie file and the two actors being connected.
Run the ThreeDegrees program which searches for a three or less chain link between two actors using the movies they have been in.

Now, where I am struggling is when it comes to finding out the best way to do that.

I figure I need to start with a setup of something like this

Interesting problem. I tried working this out and ended up with both an Actor class and a Movie class, both extending a Node class. In the end I wanted a list of Nodes so that I saw both Actors and the connecting Movies. Actors had a Map of Movies, and Movies had a Map of Actors. A recursive, breadth first search worked well with these classes.


P.S. If you have a bigger txt file could you post it?

Carey Brown, I do not have a bigger input file at this time. These are something I have to make and I haven't gotten around to making a bigger one. I will start working on one and get it posted in an hour or two.

How did you go about implementing the class to find the connections?

Without giving too much away, this was the class with the method implementations missing. The "MovieActor" class is what started out as Node.

here is a slightly larger test file


Apollo13 Kevin Bacon Tom Hanks Gary Sinise
HollowMan Elisabeth Shue Kevin Bacon Josh Brolin
AFewGoodMen Tom Cruise Demi Moore Jack Nicholson Kevin Bacon
OneCrazySummer John Cusack Demi Moore
DaVinciCode Tom Hanks Ian McKellen Audrey Tautou
ForestGump Tom Hanks Gary Sinise Robin Wright
TheMartian Matt Damon Jessica Chastain Jeff Daniels Michael Pena
Inception Leonardo Dicaprio Tom Hardy Ellen Page
TheRevenant Leonardo Dicaprio Tom Hardy Will Poulter
StarWarsTheForceAwakens Harrison Ford Adam Driver Daisy Ridley
JurassicWorld Chris Pratt Bryce Howard Jeff Goldblum

So I am still kind of confused. I was wondering if anyone else had any tips for me or if I could get some pseudo code for this.

Thanks for the help so far everyone

Sorry that is isn't really helpful but I can't stand looking at the input data format and not say anything.

It's kind of goofy how the title is smushed together into one word like that. Comma separated values (CSV) would have been a more standard and flexible format to use. I don't know what your instructor is thinking in giving you data in this oddball format.

CSV is easy to process with just the standard String methods. In particular, the split() method will give you an array of strings that you can process directly with much less code than what you're forced to write with this non-standard and inflexible format. The format you have to use makes it impossible to include one-name actors like Cher, Sting, and Madonna or actors who have three-part names like Tommy Lee Jones, Jamie Lee Curtis, and Max Von Sydow.

As for pseudocode, don't you have that for BFS? If you don't have it in your class notes, it's pretty easy to Google for it.

Piet Souris wrote:From the input data you can create an adjacency map, say Map<Actor, Set<Actor>>.

Yes you can; but that wouldn't give you any idea of how many times two actors are connected, which I suspect might be useful for a "shortest path" search (but I'm just guessing).
You'd also have to guard against entering "forward" and "reverse" relationships for the same two actors - or enforce it if you want a directed map.

Carey Brown wrote:I tried working this out and ended up with both an Actor class and a Movie class, both extending a Node class.

I quite like that idea, but doesn't that make each "degree" a double hop? If so, I suspect it increases the number of links quite a bit.

It also occurred to me that rather than making Node a base class, you could make it a container - ie, a Node<Actor> or a Node<Movie> - but I'm still struggling to come up with a list of methods for a generic Node.

Jason Ram wrote:So I am still kind of confused. I was wondering if anyone else had any tips for me or if I could get some pseudo code for this.

Well, like I say, I'm no expert on this, but I'm a bit puzzled how you get the film information out of your Node, since it only seems to hold the actor's name; but maybe I'm missing something.

This is along the lines I was thinking, because it's the separation between actors that we want; but my Pairing class was there to hold the information about which films (and how many of them) connect two actors together.

I suspect we're all basically doing the same thing; just with slightly different approaches.

I'm afraid it's beddie-byes time for me, but I'll revisit tomorrow. Good luck.

Winston

I agree with how the input file is annoying, it was given to us so nothing I can do.

I have been working on it for a while. Ended up restarting once. I just need to figure out how to get the print for a connection working.
This can be seen by my comment at the end of the code
an example of what it will print:
Enter first actor name (two case-sensitive words): Josh Brolin
Enter second actor name (two case-sensitive words): Ian McKellen
Josh Brolin was in HollowMan
with Kevin Bacon who was in Apollo13
with Tom Hanks who was in DaVinciCode
with Ian McKellen.

I just want to thank everyone again for the help.
I managed to use some concepts I learned while researching pairing to help give me ideas on how to do this program.

The way I have implemented it so far may not be the best way to implement it, but so far it all seems to be working just how I need it to work.

It's pretty dismaying to see students writing programs like what you've shown. There is way too much code in main(), which should have only a few lines of code. Graph traversal is a relatively advanced topic so I'm assuming this is not a CS-101 introductory class that your taking. If I remember correctly, Abstract Data Types was only covered in the second course I took after passing the "Introduction to Programming" course. I would have thought that by now you'd know that Java is an object-oriented language and as such, your programs should be working mostly with objects, not just static methods.

You should try to break the problem up into smaller chunks, with one method for each small, focused task. For example, reading the file in and populating nodes would be one smaller task. Even that might be too big. You might have one method read the file in and return a List of Strings, with each element in the List representing a line in the input file. Then you could pass that List to another method that iterates through the list and calls another method to create nodes from the data that is in one string. You could keep going smaller and smaller until each method is only 5 to 10 lines of code long. This helps you manage the complexity of your program.

Were you not taught this strategy by your teachers? This is basic functional decomposition and is an essential skill that all programmers should master. I believe you should master this from the very start, as a novice programmer because this is when you are most confused and likely to be overwhelmed by the size and scope of a problem. Experienced programmers will do that right away when they have problems of any appreciable size, such as this one.

Jason Ram wrote:

Take this section of code, for example. There are a number of poor coding practices you are doing here. Duplication of code, having multiple breaks inside a large block of code, having multiple continues inside a large section of code, comments that could be eliminated by writing more expressive code, while (true) - these are all poor coding form.

I have a friend who teaches young children, grade school age, how to swim. He's a stickler for proper form because he used to swim competitively. He knows that poor form can make swimming even more difficult than it already is for young learners so he makes it a point to help them work on have efficient stokes and keeping their bodies as parallel to the direction of swimming as possible to reduce drag. The same thing should go for novice programmers. You should be taught how to avoid doing things that will produce drag in your program and make it difficult for you to manage the complexity.

Here are a couple of things you can start doing:
1. Use good names that represent what things do or what their purpose is for being. "one" and "two" are very poor names. Think of better names so that when you read the code, it's telling you a story of what's happening in the program.
2. Break your code up into smaller chunks/methods. Each method should do one task. If a method reads lines from a file and then creates nodes for your graph, it's doing too many things. Break it up into two methods, one for reading lines from the input file, another for creating nodes for the graph.

Does that make sense? Once you start doing this while keeping in mind that your program should tell a story when you read it out loud, then you'll start getting a handle on the complexity and you might start seeing the forest for the trees.

BTW, my friend who teaches swimming has had some of his kids go on to swim competitively and win in many levels of competition. One of the kids he used to train when we were back in our hometown in the Philippines actually competed to be a Junior Olympian here in the US. She got a full ride in college as a swimmer. He lives in Cincinnati, OH now and I believe he coaches at a swim club and takes his kids to all kinds of club competitions up to regional and national levels. He's less than 5 ft tall but he swims like a dolphin and can beat people who have several inches on him in height. It's because he learned to compensate for his lack of height with a very efficient stroke. The fact that his family own a resort with an Olympic sized swimming pool didn't hurt either. That guy would swim 2km just to warm up. Ok, that's an exaggeration but he swam a lot.

The tips you just gave for breaking code up is more than I have been given in 2 semesters (one of python and now the 2nd with java). Thank you.

The comments like that are required specifically for this assignment only.

I have managed to implement everything in a way that works. I will work on trying to make it have better form next.

Jason Ram wrote:The tips you just gave for breaking code up is more than I have been given in 2 semesters (one of python and now the 2nd with java). Thank you.

You're welcome. The fact that you have 2 semesters of programming under your belt now is disappointing though. It's not about you though, I don't blame you. I feel like you're getting short-changed by the schools and instructors. They are are just adding to the problems we're seeing in the professional world of development. If I were to make another analogy, it's like they were sending you through boot camp and you came out to the front lines not knowing which was the business end of a rifle or how to use the safety on your weapon. I wouldn't want a soldier like that walking behind me in a life and death situation. It's not fair to you nor is it fair to the folks whose teams you're joining.

The comments like that are required specifically for this assignment only.

I have managed to implement everything in a way that works. I will work on trying to make it have better form next.

Yeah, I'd really love to see the day when kids get taught some of the basic good forms of programming instead of just letting them flail about not knowing if they doing well or not. Just getting your programs to run doesn't cut it in the real world of development. You need maintainability, readability, testability, and a whole slew of other -ities. You should start learning that right off the bat, from CS-101 and all the way through to graduation.

At least you're now aware that there are such things as poor form and good form in your code. Thanks for wanting to do better next time.

Jason Ram wrote:I just want to thank everyone again for the help.

No probs. And thank you for a fun problem, and a willingness to take things on board. Have a cow.

Winston