Implementation of graph in Java from Database

Question

What I have is 2 tables :

    Users (id, name, lastname) 
    Friends (id1, id2)

Given these 2 tables, I need to be able to find the distance between 2 users d(id1,id2)

I defined a User class, that holds each of the user attribute in the table.

I need to build a graph. My data structure for the graph is

     Map<User, Set<User>>

mapping a user to a set of his friends. How am I building the graph ? I queried the db for the ids of all the users in the db. I got an

   int[] userids

Then for each int in this array:

(1) I build a User object, fetching in the db the attributes of that user

(2) I query the Friends table in the db to have the ids of the friends of that user :

    int [] friends

(3) for each int in this friends array, I build a User object fetching in the db the attributes of that user and add it to

    Set<User> friends = new Set<User>();

Question 1 : Any ideas how to do this better ? It takes forever, given that I have 500 users, and 20000 entries in the Friends table ...

The big problem here is that when 2 users are the "same" in the database, they are referenced in differents objects in my graph !!

Which is messing up my distance algorithm. I start with a User u, get his Friends {f1,f2} , and when I wanna get the friends of friends using graph.get(f1) and graph.get(f2) I get null (for the reason stated in my problems, ie 1 db user in many different User objects)

I need to find a way to build my graph such that 1 given user say (1, John, Doe) is referenced in one and only User object in the heap ...

Question 2 : How ??

Thank you so much

Help with Java Graph Implementation

How about storing all the userids in a set? that'll take care of the duplicates — Chetter Hummin
– Chetter Hummin, Commented Apr 20, 2012 at 16:19

Keith Randall · Accepted Answer · 2012-04-20 17:04:29Z

0

Reading one user at a time is going to be slow, that's lots of round-trips to the database. It will be especially slow if there is no index on the Friends table.

You are better off just grabbing all the data from the database and building the graph in Java yourself.

select UserId, ... from Users;

as you are doing now, to build a User for each user. You'll want to create a Map from userId to User for use in step 2 (so you don't get multiple User objects for the same userId).

select id1, id2 from Friends;

Then look up the two ids in the Map above, then add each User to the other User's outbound edge set.

answered Apr 20, 2012 at 17:04

Keith Randall

23.3k3 gold badges38 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Myna Over a year ago

OK then my graph would become Map<Integer, Set<Integer>> (ids and ids of friends) and a Map<Integer, User> (id to user object) ?

Keith Randall Over a year ago

The former could be Map<User,Set<User>> as well. As a third option, I generally like to store the friend edges in User itself, i.e. User has an instance variable Set<User> which contains the friends of that user. Personal preference, though, you could do it either way.

Myna Over a year ago

I have been working on this more, and what I have is the following : Map<Integer, User> : lookup table by id Map<Integer, Set<Node>>, which maps a user_id to the nodes of his friends, and a which is a look-up table. I

Collectives™ on Stack Overflow

Implementation of graph in Java from Database

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related