algorithmgraphgraph-theorymax-flowford-fulkerson

Maximize flow through a multigraph, where edges can be added subject to restrictions

I'm doing a course in algorithms and I'm stuck on this problem.

Given a set of vertices on a grid. Every vertex has a coordinate (x,y). An source and a sink has been given. From every vertex there can only be drawn 4 types of edges.

O1: The edge can be drawn from v1 to v2 if v1.x=v2.x or v1.y==v1.y.

O2: The edge can be drawn from v1 to v2 if the euclidean distance between v1 and v2 is the largest possible.

O3: The edge can be drawn from v1 to v2 if there's at least 2 vertices on the line segment between v1 and v2.

O4: The edge can be drawn from v1 to the sink.

Every vertex has a maximum number for each edge type that can be drawn from it.

Input example for one vertex:

0,1,4,0,2,0 - Is the vertex at coordinate 0,1 where the maximum number of type O1 edges that can be drawn is 4, type O2 is 0, type O3 is 2 and type O4 is 0.

The problem is to find the maximum flow of the graph.

My approach is that if I'm able to generate a weighted directed graph, I can apply Ford-Fulkerson and get the result. I'm able to generate the graph with all possible edges, but I have no idea how to figure out which edges should be drawn to ensure maximum flow (the restriction on the number of edge types from a given vertex is what trips me up).

I assume that every edge have weight 1, in the resulting multigraph, thus making the maximum flow problem well defined.

Example:

0 1 4 0 2 0
2 2 1 2 3 4
4 1 3 1 1 0
4 3 1 0 0 1
6 4 0 0 1 1
9 1 1 0 0 2
9 4 2 0 0 1
9 3 0 0 0 0

Possible edges:

Possible edges in example

Drawn solution:

One possible optimal solution

I know the answer to this instance of the problem is 5.

Solution

  • Nevermind my previous answer, think I got it:

    Start with the complete graph

    Re-write each node into five nodes, one input and then one output of each type

    Add nodes from the input node to each output node depending on how many edges of that type the original node was allowed to have

    Calculate max flow on the translated graph

    So if in your original graph you had a node n with n.O1_out outgoing neighbors, n.01_limit limit, n.O2_out, n.O2_limit, etc, you'll translate that into:

    Sorry, this is a pain to describe clearly, but does that make sense?