Algorithm for Matching a Graph

Question

If we have an amount of nodes which are connected with edges (like a crossing with streets), and each node has a value of 0 to 3. The edges have the value 0.

Now I would like to write an algorithm, that allocates the value of the nodes to the value edges, so after the algorithm terminates all nodes have the value 0 and all edges <= 1.

For example, given this graph:

I'd like to produce this:

.

My Solution:

I have defined the datatypes Crossing and Street:

public class Crossing{
    int value;
}

public class Street{
    int value;
    Crossing A, B;
}

The algorithm iterates through the crossings and allocates the values to the streets (Notice that a crossing can allocate its value only to the streets which are adjacent).

void allocate(Crossing[] crossings, Street[] streets){
    foreach(crossings as c){ //iterate through every Crossing
        foreach(streets as s){ //Find the streets, which are adjacent to c
            if((s.A == c || s.B == c) && s.value < 1 && c.value != 0) 
                // The value of the crossing is >0 and the value of the 
                // street is 0.
                c.value -= 1;
                s.value += 1;
        }
    }
}

Will my algorithm work? If yes: is it efficient, or is there a better solution?

Answer 1

I am afraid your algorithm will not always work.

For example, if we have nodes A-B-C with A and B having value 1 (and C having value 0), then your algorithm will fail if the value from B is given to the A-B crossing instead of the B-C crossing (because then the A value has nowhere to go).

I would recommend reading up on the maximum flow algorithm e.g. with this topcoder tutorial

To solve this problem with the maximum flow algorithm you wish to define a new directed graph. This new graph has a node for each of your crossings, and a node for each of your streets (plus a source and sink node).

You need edges:

1. From source to each crossing with capacity equal to the value on the crossing
2. From each crossing to its connected streets with capacity 1
3. From each street to the sink node with capacity 1

If you construct the maximum flow from source to sink, then the flow in the edges from the crossings to the streets tells you how to assign the values.