How to model social graph in Java

Very simple scenario

N users, each user can have 0 .. N - 1 friends (who are also users)

How can I model this in Java for AppEngine data store

Scenario to consi开发者_开发问答der

• user x and user y become friends (so both need update their own status, in a transaction

We've modeled user relations as a simple UserRelation entity:

class UserRelation {
  User _from;
  User _to;
  RelationState _state;
}

Where RelationState is an enum, describing states (normally, there is more than friendship)

enum RelationState {
  BLOCKED, NONE, PENDING_FRIEND, FRIEND;
}

Actually, we also use this enum for authorizaton, e.g. on user profiles.

enum RelationState implements IRole {
  BLOCKED, NONE(BLOCKED), PENDING_FRIEND(NONE), FRIEND(PENDING_FRIEND);

  private final List<IRole> _impliedRoles;
  private final List<String> _roleStrings;

  private RelationState(final IRole... impliedRoles) {
    HashSet<IRole> set = new HashSet<IRole>();
    for (final IRole impliedRole : impliedRoles) {
      set.add(impliedRole);
      set.addAll(impliedRole.getImpliedRoles());
    }
    _impliedRoles = Collections.unmodifiableList(new ArrayList<IRole>(set));

    ArrayList<String> list = new ArrayList<String>(getImpliedRoles().size() + 1);
    list.add(getName());
    for (final IRole implied : getImpliedRoles()) {
      list.add(implied.getName());
    }
    _roleStrings = Collections.unmodifiableList(list);
  }

  public List<IRole> getImpliedRoles() {
    return _impliedRoles;
  }

  public String getName() {
    return name();
  }

  public boolean hasRole(final IRole role) {
    return this == role || _impliedRoles.contains(role);
  }

  public List<String> getRoleStrings() {
    return _roleStrings;
  }
}

public interface IRole {
  public List<? extends IRole> getImpliedRoles();
  public String getName();
  public boolean hasRole(final IRole role);
  public List<String> getRoleStrings();
}

It's easiest to have two objects for each (symmetric) relationship (e.g. friendship as used on facebook) and only a single object for non-symmetric relationships (e.g. followers as used on twitter or blocked users). While this might look like overhead in the first place, using two objects certainly simplifies querying.

I think the AppEngine part itself should then be pretty straight forward.

Consider using a Friendship table with just two foreign keys, user1 and user2. An entry in this table models an social connection between two users. You could even add more columns to describe the type of this social relation.

(or consider sfussenegger's answer ;) same idea but better presentation)