Generating Graphs for Evaluating maximum flow algorithm (eg Edmonds-Karp & Dinic)

Question

I'm currently working on a project focusing on the Edmonds-Karp and Dinic's algorithms (classic implementations). One of the tasks is to verify their complexity through simulations. Specifically, I need to automatically generate graphs on which maximum flow algorithms can operate and demonstrate that Dinic's algorithm is generally better.

To generate the graph, I envisioned a method where I create a certain graph G with capacity, create a source node S, randomly create arcs from S to G with random capacities, do the same for the sink node T, and create arcs with random capacities from G to T. However, I'm unsure what condition to add to guarantee the existence of flow and a path from S to T through G. If I add overly strict conditions, my generation may not be truly random, defeating the purpose of running multiple simulations on random graphs to verify complexity.

Another idea for evaluation is to consider the worst-case complexity. In this scenario, I would need to create one or more graphs that represent these worst cases. While I understand theoretically what constitutes a worst-case scenario, I'm unsure how to practically achieve it.

Any insights or suggestions on:

• How to ensure the generated graphs allow for the existence of flow and a path from S to T without imposing overly strict conditions?
• How to practically create graphs that represent worst-case scenarios for evaluating complexity?
• Would you know of a source where I could find real flow networks to demonstrate applications on real networks?

Thanks