2:35 AM
1
A: How to Compare Hierarchy in 2 Pandas DataFrames? (New Sample Data Updated)

mozwayI would use networkx to form a directed graph from df1, and then a simple check of presence of the edges or nodes: import networkx as nx # create a graph from df1 pairs = (['Ultimate Parent', 'Parent'], ['Parent', 'Child']) G1 = nx.compose(*(nx.from_pandas_edgelist(df1, source=x[0], target=x[1],...

 
L H
awesome outcome. Exactly what I need for df2. But do you have any idea how to transform the Graph (df1) into df1's column showing their hierarchy (just like my original post)? Thanks!
 
@LH sure, see update. Note that adding the hierarchy to all rows might be uselessely duplicating information. Also be aware that the hierarchy here suppose that the subgraphs are not branched. If they are pretty me know and I'll update, but this would require more computations.
 
L H
you're right. Some info will be duplicated but I can't figure a better way to do it so far. If I simply assign a group ID to each family, it can't show their relationship, although I guess I can group by ultimate parent->parent and get an idea. I've got another error from your codes above saying "networkXUnfeasible: Graph contains a cycle or graph changed during iteration". Will this error come from data cleaning issue? Eg. I have some rows having same value in all 3 columns if they're ultimate parent. I can remove them if needed but I'm not sure whether that's what this error means.
also, I just realized your method only check the parent and child pair. Therefore, for C, A, B --> this should be wrong hierarchy, but will be considered correct in your function
 
Can you update your example to reflect these two cases (cycle and different hierarchy)?
 
L H
sure. Let me do it right now!
 
2:35 AM
OK, I'll check this in a few hours (AFK)
 
L H
Thanks! Btw I think the current issue is coming from you only checking the (parent, child) pair in

df2['Right/Wrong'] = ['Right' if e in G1.edges else 'Wrong'
for e in zip(df2['Parent'], df2['Child'])]

and here

m = df2['Right/Wrong'].eq('Wrong')
df2.loc[m, 'Reason'] = [
'wrong hierarchy' if set(e).issubset(G1) else 'wrong entities'
for e in zip(df2.loc[m, 'Parent'], df2.loc[m, 'Child'])
]
I was trying to fix it by adding another (ult_parent, parent) pair in both lines but nothing's changed..
Thanks for the help..
 
3:34 AM
@LH got is, I thought only Parent->Child should be checked
I updated the answer, however since there is no direct link between UP -> P, I checked if there is a path between UP -> P and if there is an edge between P -> C. You can adapt this to your exact needs
I also handled the "networkXUnfeasible" error by adding a check for cyclic subgraphs, this will output "cyclic hierarchy" if such a case happens (see example).
 
L H
Thanks so much! lemme take a look and try it now
 
I just did some minor edits to the code (changing parameter order and fixing a G1 instead of G)
 
L H
quick question - does "cyclic hierarchy" mean there are 2 same entities in 1 row, eg. ult parent = parent or parent = child or all 3 are the same?
 
3:50 AM
it means that there is a cycle, it could involve more than 3 nodes (or just 2 X->Y/Y->X), which makes it ambiguous to define a hierarchy (unless removing edges to break the cycle)
since your hierarchies are defined across all rows, this could involve more than 1 row
 
L H
I see. Understand. So in short, those edges marked as cyclic hierarchy will not be included into a hierarchy for comparison right?
 
Check the example in my answer that demonstrates a cycle involving two rows
I'm not sure what is your end goal, so it's tricky to answer that ;)
you could say a cycle doesn't allow you to define a classical hierarchy
(like for workers in a company, you'd rarely have an employee looping back as superior of the CEO)
Anyway, defining a hierarchy can be tricky for other reasons, there could be branches for instance, like if you replaced C->D->E by C->F->E in your example
now C branches to both D and F, which wouldn't allow a "linear" hierarchy
with my current code this would define A,B,C,F,D,E since F/D have the same rank
 
L H
got you. I'm doing some cross-checking and like you said it's really a bit tricky
the end goal is to cross check 2 dataframes, 1 with internal data which its hierarchy is analyzed internally, and the other df is bought from the external, which should be more accurate. And that's why I will use the more complete df as a benchmark to do the comparison
 
If you have branhces, modify the code to:
cc = {frozenset(c): ','.join(map('/'.join, nx.topological_generations(H)))
if nx.is_directed_acyclic_graph(H:=G1.subgraph(c))
else 'cyclic hierarchy'
for c in nx.weakly_connected_components(G1)}

df1['Hierarchy'] = df1['Child'].map({n: x for c,x in cc.items() for n in c})
this will give you a hierarchy like: A,B,C,F/D,E
or, if you really want a different path for each row, this is possible bu much more computationally intensive (you have to compute the path per row, not per subgraph)
 
L H
I think the df1 is good to go. The only issue right now for df2 is whenever the entity(node) is included in a cyclic hierarchy, they will be defined as wrong hierarchy. However, some are actually wrong entities by definition. I'm still trying to figure out if it's logic wise issue or it
 
4:03 AM
anyway, I'd suggest to open a new question if you have follow-up issues to more complex cases, keep in mind the goal of SO it to have Q/A to unit programming problems, not really to build a full project ;)
 
L H
it's from my original data*
Yes!!!
ofc!
Thank you so much for your help!! Really appreciate!
 
good luck with your project