Search dictionary for matching values
Tuples can be used as dictionary keys, so creating a second dictionary for reverse lookups can be as simple as:

reverse_lookup = {(lineID, vertex): idx 
                  for idx, (lineId, _, vertex) 
                  in instance.indexList.items()}