Define an augmented graph from the input graph and perform the appropriate computation on the augmented graph.