How to create nested list from hierarchy

Question

I have some UserInvites, where an invite has from and to User properties.

E.g.,

UserInvite1.from = User1
UserInvite1.to = User2

UserInvite1b.from = User1
UserInvite1b.to = User4

UserInvite2.from = User2
UserInvite2.to = User3

UserInvite3.from = User2
UserInvite3.to = User5

Thus, User1 invited User2 and User4; User2 invited User3 and User5.

Given a list of those invites, e.g., [UserInvite1, UserInvite2, ... ], or another means of iterating over them(?), how can I generate a "hierarchical" (nested) list representing those invited?

E.g., starting with the "root" User1, I'd like a nested list as such:

>>> make_nest_list_from_invites([invites])
[User1, [User2, [User3, User5], User4]]

If you're familiar with Django, I'm trying to get from my "invites" to something hierarchical that I can feed to the Django template tag unordered_list

Clearly this is something like tree traversal, but I'm stumped at the moment. I tried some recursion-ey stuff, but kept ending up with an extra level of nesting in places that was throwing things off.

UPDATE: Example of something I tried

def tree_from_here(user):
    children = get_children(user)
    if children:
        return [user, [tree_from_here(c) for c in children]]
    else:
        return user

Which gives:

>>> tree_from_here(User1)
[<User: 1>, [[<User: 2>, [<User: 3>, <User: 5>]], <User: 4>]]

Which is almost correct for my current set of users, with the exception that the nesting goes too deep in the second element.

I am trying for:

[<User: 1>, [<User: 2>, [<User: 3>, <User: 5>], <User: 4>]]

I feel like it's staring me in the face, but I am not sure how to return the right thing at the moment.

You've got a good idea of it - do a traversal of each user invited by the current user, then recursion over each user invited by those users, with a stopping condition of: when the to user is the same root user you started with or None. — Taylor D. Edmiston
– Taylor D. Edmiston, Commented Jun 10, 2018 at 0:18
I was thinking the root of the tree could either be relative (e.g., a user ID of interest) or absolute (e.g., the first user). I'm not sure the latter would work though: What if the first user invited no one and the second user joined without a referral? Perhaps a root node doesn't make sense here and this is more of a graph than a tree. — Taylor D. Edmiston
– Taylor D. Edmiston, Commented Jun 10, 2018 at 2:56
@TaylorEdmiston There is a concept of root, and no user without an invite from another. Thanks for trying to explain. What you described earlier appears to be how I say it out loud -- but putting the code together for the "then recursion over each invited..." is where I'm stumbling. I'll post an update and example of progress shortly. — anonymous coward
– anonymous coward, Commented Jun 10, 2018 at 3:00

wiesion · Accepted Answer · 2018-06-10 13:24:15Z

1

I had a hard time understanding your idea about this represantation of a nested structure, but after a lot of thinking and writing code i am confident that i understand, so i guess this is what you are after - description within the code and online demo here: https://repl.it/repls/EarlyWeeklyThings - was a nice challenge, thx :)

from pprint import pprint

# dummy user class
class User(object):
  def __init__(self, user_id):
    self.user_id = user_id
  def __repr__(self):
    return "User{}".format(self.user_id)

# dummy invite class 
class UserInvite(object):
  def __init__(self, from_user, to_user):
    self.from_user = from_user
    self.to_user = to_user
  def __repr__(self):
    return "From {} to {}".format(self.from_user, self.to_user)

# create 10 dummy users to create invites
users = [User(user_id) for user_id in range(1,11)]

# use natural numbers to reflect invites
# adjust in list comprehension
invite_map = (
  (1, 3), (1, 5), 
  (2, 4), (2, 6),
  (3, 7), (3, 8),
  (4, 9),
  (9, 10)
)

# create invitations based on the invite_map, fix natural numbers
example_invites = [
  UserInvite(users[inviter-1], users[invitee-1]) for inviter, invitee in invite_map
]

pprint(example_invites)
# =>
# [From User1 to User3,
#  From User1 to User5,
#  From User2 to User4,
#  From User2 to User6,
#  From User3 to User7,
#  From User3 to User8,
#  From User4 to User9,
#  From User9 to User10]

def get_nested_invites(invites, invited_by=None):
  result = []
  if not invited_by:
    # Assume that initial inviters were not invited by anyone
    # Use set comprehensions to avoid duplicates and for performance
    invitees = {invite.to_user for invite in invites}
    inviters = {invite.from_user for invite in invites if invite.from_user not in invitees}
  else:
    # Get the next potential inviters given their inviter
    # Use set comprehension to avoid duplicates and for performance
    inviters = {invite.to_user for invite in invites if invite.from_user == invited_by}
  for inviter in inviters:
    # Add the invited user/potential inviter 
    result.append(inviter)
    # Let's get nesty
    invitees = get_nested_invites(invites, inviter)
    if invitees:
      result.append(invitees)
  return result

pprint(get_nested_invites(example_invites))
# =>
# [User1,
#  [User3, [User7, User8], User5],
#  User2,
#  [User6, User4, [User9, [User10]]]]

pprint(get_nested_invites(example_invites, users[1]))
# =>
# [User6, User4, [User9, [User10]]]

edited Jun 10, 2018 at 13:24

answered Jun 10, 2018 at 12:55

wiesion

2,48515 silver badges22 bronze badges

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

2 Comments

anonymous coward Over a year ago

Thanks so much! Your approach does exactly what I desired! As you can see from my most recent "what I tried" bit: I was attempting to start at a User, and use a utility (get_children) to go down from there. Starting at the invites, as you did (and I mentioned in the original question) works fine! Thanks again!

wiesion Over a year ago

yw! If i may add, if you're going to use this productively with a lot of invites, you should probably subtract the invites covered by inviters before passing them to the nested call to avoid overhead lookups

Collectives™ on Stack Overflow

How to create nested list from hierarchy

UPDATE: Example of something I tried

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

UPDATE: Example of something I tried

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related