Acyclic undirected graph allocation problem-CodePudding

We have an allocation problem: each node is a fuel source, and every edge contains a number of evenly spaced out lamps (think of them as being 1m apart from eachother). Each fuel source can power lamps that are on the immediate edges around it (it cannot fuel lamps through other nodes) a fuel source also has a radius in which it fuels lamps around it - depending on the radius (in meters) we can calculate the amount of fuel a give fuel source provides - example: a fuel source with a radius of 2 can fuel all the lamps within its radius and, in total, uses up 2 liters of fuel (fuel usage is a function of the radius).

note that two nodes have only one path between each other (meaning that that the number of edges is equal to the number of nodes - 1).

The goal is to calculate the optimal radii of the fuel sources so that we minimize the fuel usage while fueling all the lamps.

Here is an example graph The solution to this graph looks like this The red ellipsoids are supposed to visualize the radii of the fuel sources, bellow is a table of the relevant values:

Node, fuel source	Radius, fuel consumption
0	1
1	2
2	0
3	2
4	0
5	0

After we add up all the fuel amounts we get the result: 5.

The input for the above task looks like this:

6     // 6 nodes (numVertices)
0 1 3 // node 0 with an edge containing 3 nodes going to node 3 (src dest lights)
1 2 1 // ...
2 3 2
1 4 2
1 5 2

So far I've tried loading up my edges like this (note that this solution is quite cursed, especially with my use of pointers):

struct light {
    int count;
};

struct node {
    int d;
    light* l;
};

std::vector<node*>* tree;
int numVertices;

// do this for all values in the input
void AddEdge(int src, int dest, int lights) {
        light* l = new light{ lights };
        tree[src].push_back(new node{ dest, l });
        tree[dest].push_back(new node{ src, l });
}

And then I solved the graph by using a greedy algorithm to 'remove' as many lamps per step as possible:

void Solve() {
    int fuel = 0;

    while (true) {
        int maxNode = 0;
        int maxNodeLights = 0;

        for (int A = 0; A < numVertices; A  )
        {
            int lightsOnNode = 0;

            for (node* B : tree[A])
            {
                lightsOnNode  = B->l->count;
            }

            if (lightsOnNode > maxNodeLights) {
                maxNodeLights = lightsOnNode;
                maxNode = A;
            }
        }

        if (maxNodeLights > 0) {
            bool addedRange = false;

            for (node* B : tree[maxNode])
            {
                if (B->l->count > 0) {
                    B->l->count--;
                    addedRange = true;
                }
            }

            if (addedRange) {
                fuel  ;
            }
        }
        else {
            break;
        }
    }
        
    std::cout << fuel << '\n';
}

If we were to parse the input string from the example case it would look like this:

numVertices = 6;

AddEdge(0, 1, 3);
AddEdge(1, 2, 1);
AddEdge(2, 3, 2);
AddEdge(1, 4, 2);
AddEdge(1, 5, 2);

Solve();

This works for simple graphs like the one above, but fails by a small margin once a more complex graph is introduced, since the greedy algorithm doesn't look ahead if there is a better option a couple steps in the future.

CodePudding user response：

This needs two passes.

Pass1 The lamps that are on edges leading to leaf nodes ( nodes with exactly one edge ) MUST be fueled from the source at the other end of the edge. So this pass sets the radius of these sources to the number of lamps on the edge.

Pass2 Increase the radius of sources that are most efficient.

Define the fuel source radius efficiency rate as the number of extra lamps that can be fueled by a radius increase of one unit.

e.g. fuel source 1 can fuel 4 extra lamps if the radius increases from 0 to 1.

Pass 2 algorithm:

loop over sources, calculating their current efficiency rate
Check for zero efficiency rate on all sources. This means all lamps have been fueled, so STOP
Increase the radius of the source with the greatest efficiency
repeat

c code for this is at https://gist.github.com/JamesBremner/39f4016ca738d99b56864302107cd75f ( No pointers! )

OP's example

Input

Output

radius 1 2 2 0 0 0
total fuel 5

@MarkB example

Input

Output

radius 0 1 0 1 0 1 0
total fuel 3

OP's second example ( from comments )

Input

1 0 1 2 1 1 3 0 1 4 0 1 5 0 1 6 4 1 7 6 1 8 4 1 9 2 1 10 5 1

Output

 1 0 2 3 4 5 6 7 8 9 10
 0 1 1 0 1 1 1 0 0 0 0
total fuel 5

@MarkB second example

Input

Output

radius 1 1 0 1 0 0 0 1 0 1 0 1 0
total fuel 6