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:
Drawn solution:
I know the answer to this instance of the problem is 5.
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:
n_input
such that all nodes that previously had edges to n
now have edges to n_input
n_O1_output
such that n_O1_output
has edges to all nodes previously in n.O1_out
(repeat for O2
, etc)n.O1_limit
edges (or one edge with n.O1_limit
weight) going from n_input
to n_O1_output
(repeat for O2
, etc)Sorry, this is a pain to describe clearly, but does that make sense?