在“邀请者”和“被邀请者”列中，如何找到之前有1、2、3个邀请的邀请者？

Question

注意：我可以使用MySQL或python

编辑：为了让我的问题如user:strawberry所建议的那样成为MRE，我创建了我的表，如下所示（创建的，删除的表其实并不需要，所以我只使用了所有相同的日期）：

CREATE table invites (
  ID                INT AUTO_INCREMENT,
  invitee_id        INT,
  inviter_id        INT,
  inviter_user_code VARCHAR(20),
  created_at        datetime,
  updated_at        datetime,
  PRIMARY KEY (ID)
); 
INSERT INTO invites (invitee_id, inviter_id, inviter_user_code, created_at,updated_at)
VALUES 
  (17365, 17374, 'BDMX5Z', '2019-02-01', '2019-02-01'),
  (17401, 17349, 'BDMX58', '2019-02-01', '2019-02-01'),
  (17403, 17349, 'BDMX58', '2019-02-01', '2019-02-01'),
  (17452, 17349, 'BDMX8C', '2019-02-01', '2019-02-01'),
  (17457, 17449, 'BDMX8J', '2019-02-01', '2019-02-01');

为了让我自己明白我的数据帧是什么样子的：

    id invitee_id   inviter_id  inviter_user_code   created_at           updated_at
    1   17375       17374             BDMX5Z    2019-02-01 10:28:44 2019-02-01 10:28:44
    2   17401       17349             BDMX58    2019-02-01 11:59:47 2019-02-01 11:59:47
    3   17403       17349             BDMX58    2019-02-01 12:03:22 2019-02-01 12:03:22
    4   17452       17449             BDMX8C    2019-02-01 13:39:31 2019-02-01 13:39:31
    5   17457       17455             BDMX8J    2019-02-01 14:00:25 2019-02-01 14:00:25
    6   17502       17501             BDMX9Y    2019-02-01 15:50:44 2019-02-01 15:50:44
    7   17541       17540             BDMXB7    2019-02-01 17:15:06 2019-02-01 17:15:06
    8   17542       17546             BDMXBD    2019-02-01 17:34:48 2019-02-01 17:34:48
    9   17696       17630             BDMXDZ    2019-02-02 11:46:14 2019-02-02 11:46:14
    10  17706       13191             BDMT3A    2019-02-02 12:23:47 2019-02-02 12:23:47

invitee_id是被邀请的用户。
inviter_id是邀请新用户的用户。

因此，如果您是第一个没有事先邀请的邀请，inviter_id将不会包含在invitee_id。

为此我做了

select 
  *
from user_invitations
where
  inviter_id in
    (select invitee_id
     from user_invitations)

在此之后，我将有inviter_id作为事先邀请的邀请者。你知道吗

我的问题是如何获得事先邀请的邀请者（也有事先邀请的人）等等…
我在mysql中尝试了多种方法，包括直接创建df和使用df。你知道吗

对生成的表执行上述查询，如下所示：

With one_prior as (
    select 
      *
    from user_invitations
    where
      inviter_id in
        (select invitee_id
          from user_invitations)
) 
select *
from one_prior
where 
  inviter_id in
   (select invitee_id 
    from one_prior);

我已经手动检查了一个用户，但如果有办法检查所有用户，这似乎是正确的？你知道吗

我创建了两个查询：

select *
from user_invitations
where inviter_id = 17349;


select *
from user_invitations
where invitee_id = 23764;

来回检查。 例如，如果inviter\u id=17349是第一个邀请而没有事先邀请，则它不会出现在第二个查询中。然后从inviter\u id=17349的第一次查询的结果中，我得到invitee\u id=17401、17403等。。然后我将把它们作为邀请者id放入第一个查询中。重复上述步骤。你知道吗

此外，是否有一种方法可以创建一个分布式点图，其中每个点代表用户，并且有一条线连接具有“邀请者/被邀请者”关系的用户？你知道吗

编辑： 比如说我正在做的第五个链接，代码似乎冗长乏味，我希望能找到更有效的方法。你知道吗

query = """
With five_prior as
(
    With four_prior as
    (
        With three_prior as 
        (
            With two_prior as 
            (
                With one_prior as 
                (
                    select 
                      *
                    from user_invitations
                    where inviter_id in
                          (select invitee_id
                          from user_invitations)
                ) 
            select *
            from one_prior
            where inviter_id in
                  (select invitee_id 
                   from one_prior)
            ) 
        select *
        from two_prior
        where inviter_id in
              (select invitee_id 
               from two_prior)
        )
    select *
    from three_prior
    where inviter_id in
          (select invitee_id
           from three_prior)
    )
select *
from four_prior
where inviter_id in
      (select invitee_id
       from four_prior)
)

select *
from five_prior
where inviter_id in
      (select invitee_id
       from five_prior)
group by inviter_id
"""
df = pd.read_sql(query, con=conn)

five_link = list(df.inviter_id)
print(len(five_link))

Answer 1

下面是一种在python中使用动态编程解决方案的简单方法：

previous_invites = { r["invitee"]: 0 for r in rows }

changed = True

while changed:
  changed = False
  for r in rows:
    update_prev_invites = max(previous_invites[r["invitee"]], previous_invites.get(r["inviter"], 0) + 1)
    if update_prev_invites > previous_invites[r["invitee"]]:
      changed = True
      previous_invites[r["invitee"]] = update_prev_invites

for r in rows:
  print "User " + str(r["id"]) + " had a chain of " + str(previous_invites[r["invitee"]]) + " inviter(s) behind them"

这假设rows是包含数据库中数据的字典数组。它通过将inviteesprevious_invites值设置为其inviter+1的previous_invites来构建previous_invites字典（将被邀请者映射到其“链”中的邀请者数量）。此循环将一直运行，直到字典收敛到正确答案为止。你知道吗

由于n用户和m是最长邀请者链的长度，此解决方案在O（n）空间和O（n*m）时间内运行。你知道吗