Hcfyk

I am trying to figure out the fastest way to perform search and sort on a pandas dataframe. Below are before and after dataframes of what I am trying to accomplish.

Before:

flightTo  flightFrom  toNum  fromNum  toCode  fromCode

   ABC       DEF       123     456     8000    8000

   DEF       XYZ       456     893     9999    9999

   AAA       BBB       473     917     5555    5555

   BBB       CCC       917     341     5555    5555

After search/sort:

flightTo  flightFrom  toNum  fromNum  toCode  fromCode

   ABC       XYZ       123     893     8000    9999

   AAA       CCC       473     341     5555    5555

In this example I am essentially trying to filter out 'flights' that exist in between end destinations. This should be done by using some sort of drop duplicates method but what leaves me confused is how to handle all of the columns. Would a binary search be the best way to accomplish this? Hints appreciated, trying hard to figure this out.

possible edge case:

What if the data is switched up and our end connections are in the same column?

flight1  flight2      1Num    2Num     1Code   2Code

   ABC       DEF       123     456     8000    8000

   XYZ       DEF       893     456     9999    9999

After search/sort:

flight1  flight2      1Num    2Num     1Code   2Code

   ABC       XYZ       123     893     8000    9999

This case logically shouldn't happen. After all how can you go DEF-ABC and DEF-XYZ? You can't, but the 'endpoints' would still be ABC-XYZ

This is network problem , so we using networkx , notice , here you can have more than two stops , which means you can have some case like NY-DC-WA-NC

import networkx as nx

G=nx.from_pandas_edgelist(df, 'flightTo', 'flightFrom')



# create the nx object from pandas dataframe



l=list(nx.connected_components(G))



# then we get the list of components which as tied to each other , 

# in a net work graph , they are linked 

L=[dict.fromkeys(y,x) for x, y in enumerate(l)]



# then from the above we can create our map dict , 

# since every components connected to each other , 

# then we just need to pick of of them as key , then map with others



d={k: v for d in L for k, v in d.items()}



# create the dict for groupby , since we need _from as first item and _to as last item 

grouppd=dict(zip(df.columns.tolist(),['first','last']*3))

df.groupby(df.flightTo.map(d)).agg(grouppd) # then using agg with dict yield your output 



Out[22]: 

         flightTo flightFrom  toNum  fromNum  toCode  fromCode

flightTo                                                      

0             ABC        XYZ    123      893    8000      9999

1             AAA        CCC    473      341    5555      5555

Installation networkx

• 
  Pip: pip install networkx
  


• 
  Anaconda: conda install -c anaconda networkx
  

Here's a NumPy solution, which might be convenient in the case performance is relevant:

def remove_middle_dest(df):

    x = df.to_numpy()

    # obtain a flat numpy array from both columns

    b = x[:,0:2].ravel()

    _, ix, inv = np.unique(b, return_index=True, return_inverse=True)

    # Index of duplicate values in b

    ixs_drop = np.setdiff1d(np.arange(len(b)), ix) 

    # Indices to be used to replace the content in the columns

    replace_at = (inv[:,None] == inv[ixs_drop]).argmax(0) 

    # Col index of where duplicate value is, 0 or 1

    col = (ixs_drop % 2) ^ 1

    # 2d array to index and replace values in the df

    # index to obtain values with which to replace

    keep_cols = np.broadcast_to([3,5],(len(col),2))

    ixs = np.concatenate([col[:,None], keep_cols], 1)

    # translate indices to row indices

    rows_drop, rows_replace = (ixs_drop // 2), (replace_at // 2)

    c = np.empty((len(col), 5), dtype=x.dtype)

    c[:,::2] = x[rows_drop[:,None], ixs]

    c[:,1::2] = x[rows_replace[:,None], [2,4]]

    # update dataframe and drop rows

    df.iloc[rows_replace, 1:] = c

    return df.drop(rows_drop)

Which fo the proposed dataframe yields the expected output:

print(df)

    flightTo flightFrom  toNum  fromNum  toCode  fromCode

0      ABC        DEF    123      456    8000      8000

1      DEF        XYZ    456      893    9999      9999

2      AAA        BBB    473      917    5555      5555

3      BBB        CCC    917      341    5555      5555



remove_middle_dest(df)



    flightTo flightFrom  toNum  fromNum  toCode  fromCode

0      ABC        XYZ    123      893    8000      9999

2      AAA        CCC    473      341    5555      5555

This approach does not assume any particular order in terms of the rows where the duplicate is, and the same applies to the columns (to cover the edge case described in the question). If we use for instance the following dataframe:

    flightTo flightFrom  toNum  fromNum  toCode  fromCode

0      ABC        DEF    123      456    8000      8000

1      XYZ        DEF    893      456    9999      9999

2      AAA        BBB    473      917    5555      5555

3      BBB        CCC    917      341    5555      5555



remove_middle_dest(df)



     flightTo flightFrom  toNum  fromNum  toCode  fromCode

0      ABC        XYZ    123      456    8000      9999

2      AAA        CCC    473      341    5555      5555