How to represent a Bipartite graph?

Question

2.00/5 (1 vote)

See more:

So, I'm trying to implement a program that calculates the degree of separation between 2 actors, for example if they both starred in the same movie then the degree of separation between them is 1. The problem is not how to calculate the degree of separation as I was able to demonstrate it, my problem is now I'm required to show all different shortest paths between these 2 actors, so if they starred in movie 0, movie 1, movie 7 together then the path should be movie 0 or movie 1 or movie 7. The problem is when I implemented my class I implemented it as an adjacency list (i.e ActorA : its neighbors ActorB, ActorC, ActorD) so when I implemented it I didn't include the movies. So, I did some research and I stumbled upon the concept of Bipartite Graphs but my question is how to represent it as an adjacency list? like from I gathered is that I'm supposed to make vertices for the actors and vertices for the movies so does that mean it's represented as this?

ActorA : Movie0, Movie1, Movie7
Movie0 : ActorA, ActorB , ActorC
ActorB : Movie0, Movie1, Movie2
.... etc

Posted 20-Dec-15 15:19pm

Member 12160712

Add a Solution

Comments

Sergey Alexandrovich Kryukov 20-Dec-15 21:35pm

You should choose the representation of the graph, whatever it is, the way suitable for the set of operations of some calculations you need to do on the graph. As you did not explain your goals or the set of operations you need to implement, any particular advice on such presentation would not make too much sense. Adjacency list is just one of the ways to represent graphs. I don't understand what could be a problem. The definition of adjacency list clearly explain how a graph can be represented. Which part of it is unclear?

Yes, you mention that your goal is to point out some paths between actors, but you have to define it strictly. Do you mean that the path between actors should go through the movies where both have starred in? In all cases, it's not quite clear what would it mean, "all shortest"? I can guess, but you have to define it...

—SA

Member 12160712 20-Dec-15 22:03pm

I'm sorry if I was a bit vague... No, what I meant is that I applied the Breadth first search algorithm to calculate the shortest path between each 2 actors, but now my problem is another 2 functions first a function called Relation Strength: If Actor A and actor B are directly linked with a degree of separation equal 1. The relation strength between them is three movies since they are directly appeared together in the three movies.
If Actor C and actor E are linked with a degree of separation equal 2 through either actor A, actor B or actor D. The relation strength should equal the max of the three options. The second function is to show this path, so in the situation for ActorA and Actor B, the path should be either movie0, movie1, movie7. So, now I would like to represent the graph while including the movies but I don't know how, so that's why I thought of the bipartite graph.

Sergey Alexandrovich Kryukov 20-Dec-15 22:29pm

No problem, but I still did not get the rules for a valid link between two actors. From what you say, I can see this is not what I thought at first. If a such movie M exists that actor A and actor B are starring in it, it would be the degree of separation of 1, right? But how to define the situation of 2? Say, the only path from A to B lies through the actor D. What properties of D defines the arc between A and D and D and B? If you say it's the same (A and D were starring in movie1 and D and B starring in some movie2), that would be one of the possible definitions. Do I understand it right?

Now, it's not a big deal to find out the shortest path in a brute-force way, and it might be not the only path. You can find all paths and the degrees will be the lengths of them; and you would need to find the shortest ones; as soon as you find one way shorter than previous ones, you can forget all longer ways. So, I would apply "algorithm first" thinking: imagine how the algorithm works and design most suitable data structure for this algorithm.

But did I understand the problem correctly?

—SA

Member 12160712 20-Dec-15 22:37pm

Yeah, you did understand it! I will try to think again of how to represent my graph, Thank you!

BillWoodruff 21-Dec-15 3:12am

Is it really necessary to implement an object-graph database with nodes, vertices, etc., here ? I have implemented something similar to this, but I used standard .NET Generic data-structures. If you want to see an example of that code, just ask.

Member 12160712 21-Dec-15 9:16am

Yes, thank you that would be great to see an example for it. And to answer your question if it's necessary I am not sure to be honest like at first I only made my graph as a standard adjacency list by using standard .Net Generic data-structures too with only nodes of actors and if 2 actors appeared in the same movie then there would be en edge between them, but now the problem is what if they appeared in more than one movie how to represent that in order to apply BFS on them that will show that there are 3 shortest paths movie1, movie 2, movie 7?

BillWoodruff 21-Dec-15 10:51am

I'm not really sure my code could help you, but I will take a look and see what might be involved in getting adjacency levels via Linq. Is there a sample public database of movie titles, and lists of actors/actresses you are aware of.

I'm in the process of studying Neo4j, and trying to get up to speed on graph databases.

You may be interested to see this article posted recently here:

http://www.codeproject.com/Articles/1038391/In-Memory-Graph-Database-API-for-NET

However the author has not yet decided if he is going to post source-code: necessary 'dll's are included in the download he provides.

Member 12160712 21-Dec-15 11:13am

Sorry, I think I might have expressed myself wrongly... I am not actually reading the database via Linq, the database is stored in a text file. Its simplest format is:
movie 0/Z/A movie 1/A/B/C movie 2/D/E/A/B .....etc My problem is I don't know how to represent it in a way where I include the movies in the scenario. So far I was able to represent the actors and their neighbors or example A its neighbors are Z B C. Now I want to represent it that A and B are neighbors not only because there is an edge between them but because there are 3 different edges between them (i.e movie 1, movie 2, movie 7). page 22 in this link http://www.cs.princeton.edu/courses/archive/spring07/cos126/lectures/18.pdf kind of visualize how to draw it on paper but I don't know how to translate this in the form of a data structure, like from what I gathered it made the movies and the performers as nodes, which I can't fully understand.

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)