Augmenting paths

Your task is to construct a directed graph with the nodes $1,2,\dots,100$ so that the algorithm in the course material forms exactly $x$ augmenting paths when it computes the maximum flow from the node $1$ to the node $100$.

You are free to choose the number of edges. Every edge has an integer weight. The graph may not have two edges with both the same start node and the same target node. The start node and the target node of an edge cannot be the same node.

In a file augmenting.py, implement the function create_edges that constructs the desired graph. The function should return the graph as a list of edges.

For example, the list [(1, 2, 5), (1, 3, 1)] means that the graph has two edges. The first edge goes from the node $1$ to the node $2$ and has the weight $5$. The second edge goes from the node $1$ to the node $3$ and has the weight $1$.

You can construct any graph that satisfies the conditions. The function will be tested with the parameter values $1 \le x \le 100$.

# slightly modified version of the class in the course material
class MaximumFlow:
    # ...

    def construct(self, source, sink):
        self.flow = self.graph.copy()
        total = 0
        self.path_count = 0
        while True:
            self.seen = set()
            add = self.add_flow(source, sink, float("inf"))
            if add == 0:
                break
            total += add
            self.path_count += 1
        return total

def create_edges(x):
    # TODO

if __name__ == "__main__":
    edges = create_edges(42)

    maximum_flow = MaximumFlow(range(1, 100 + 1))

    for edge in edges:
        maximum_flow.add_edge(edge[0], edge[1], edge[2])

    maximum_flow.construct(1, 100)
    print(maximum_flow.path_count) # 42