I am adding this answer, although there are correct answers with upvotes before me, only because you tagged java and python. So I will add java implementation now, and if needed the python implementation will follow.
The algorithm
This is a tweak on the classic topological sort:
- foreach vertex:
- foreach neighbour:
- if didn't yet calculate
m, calculate.
- Take the maximum of yourself and neighbours. Mark yourself as visited, and if asked again for
m, return the calculated.
It is implemented at calculateMostValuableVertex.
Time computation complexity
foreach vertex (O(|V|))
2. foreach edge(O(|E|) totally, as it will eventually go over each edge once.):
- If not yet computed, compute
m.
Please note that foreach vertex, it will be calculated either in stage 1, or 3. not twice, wince it is checked before the calculation.
Therefore the time complexity of this algorithm is O(|V| + |E|)
Assumptions
This solution relies heavily on the fact that HashMap in Java does operations such as add/update in O(1). That is true in average, but if that is not enough, the same idea can be fully implemented only with arrays, which will improve the solution into O(|V|+|E|) in the worst case.
Implementation
Let's first define the basic classes:
Vertex:
import java.util.ArrayList;
class Vertex {
String label;
public int r; // Worthiness
public int m; // Highest worthiness.
Vertex(String label, int r, int m) {
this.label = label;
this.r = r;
this.m = m;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result * r * m
+ ((label == null) ? 0 : label.hashCode());
return result;
}
@Override
public boolean equals(final Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Vertex other = (Vertex) obj;
boolean labelEquals;
if (label == null) {
labelEquals = other.label == null;
} else {
labelEquals = label.equals(other.label);
}
return labelEquals && r == other.r && m == other.m;
}
@Override
public String toString() {
return "Vertex{" +
"label='" + label + '\'' +
", r=" + r +
", m=" + m +
'}';
}
}
It is important to define the methods equals and hashCode so later on their hash computations will work as expected.
Graph:
class Graph {
private final Map<Vertex, List<Vertex>> adjVertices = new HashMap<>();
private final Map<String, Vertex> nameToVertex = new HashMap<>();
private final List<Vertex> vertices = new ArrayList<>();
void addVertex(String label, int r, int m) {
Vertex vertex = new Vertex(label, r, m);
adjVertices.putIfAbsent(vertex, new ArrayList<>());
nameToVertex.putIfAbsent(label, vertex);
vertices.add(vertex);
}
void addEdge(String label1, String label2) {
adjVertices.get(nameToVertex.get(label1)).add(nameToVertex.get(label2));
}
public void calculateMostValuableVertex() {
Map<Vertex, Boolean> visitedVertices = new HashMap<>();
for (Vertex vertex : vertices) {
visitedVertices.put(vertex, false);
}
for (Vertex vertex : vertices) {
if (visitedVertices.get(vertex)) {
continue;
}
calculateMostValuableVertexInternal(vertex, visitedVertices);
}
}
public void calculateMostValuableVertexInternal(Vertex vertex, Map<Vertex, Boolean> visitedVertices) {
List<Vertex> neighbours = adjVertices.get(vertex);
visitedVertices.put(vertex, true);
int max = vertex.r;
for (Vertex neighbour: neighbours) {
if (visitedVertices.get(neighbour)) {
max = Math.max(max, neighbour.m);
} else {
calculateMostValuableVertexInternal(neighbour, visitedVertices);
max = Math.max(max, neighbour.m);
}
}
vertex.m = max;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Iterator<Map.Entry<Vertex, List<Vertex>>> iter = adjVertices.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<Vertex, List<Vertex>> entry = iter.next();
sb.append(entry.getKey());
sb.append('=').append('"');
sb.append(entry.getValue());
sb.append('"');
if (iter.hasNext()) {
sb.append(',').append('\n');
}
}
return "Graph{" +
"adjVertices=\n" + sb +
'}';
}
}
Finally, to run the above logic, you can do:
Graph g = new Graph();
g.addVertex("A", 1, 1);
g.addVertex("B", 3, 3);
g.addVertex("C", 2, 2);
g.addVertex("D", 4, 4);
g.addEdge("A", "B");
g.addEdge("C", "B");
g.addEdge("A", "D");
g.calculateMostValuableVertex();
System.out.println(g);
The output of the above is:
Graph{adjVertices=
Vertex{label='A', r=1, m=4}="[Vertex{label='B', r=3, m=3}, Vertex{label='D', r=4, m=4}]",
Vertex{label='D', r=4, m=4}="[]",
Vertex{label='B', r=3, m=3}="[]",
Vertex{label='C', r=2, m=3}="[Vertex{label='B', r=3, m=3}]"}
as expected. It supports graphs with cycles as well. For example the output of:
Graph g = new Graph();
g.addVertex("A", 1, 1);
g.addVertex("B", 3, 3);
g.addVertex("C", 2, 2);
g.addVertex("D", 4, 4);
g.addVertex("E", 5, 5);
g.addVertex("F", 6, 6);
g.addVertex("G", 7, 7);
g.addEdge("A", "B");
g.addEdge("C", "B");
g.addEdge("A", "D");
g.addEdge("A", "E");
g.addEdge("E", "F");
g.addEdge("F", "G");
g.addEdge("G", "A");
g.calculateMostValuableVertex();
System.out.println(g);
is:
Graph{adjVertices=
Vertex{label='A', r=1, m=7}="[Vertex{label='B', r=3, m=3}, Vertex{label='D', r=4, m=4}, Vertex{label='E', r=5, m=7}]",
Vertex{label='B', r=3, m=3}="[]",
Vertex{label='C', r=2, m=3}="[Vertex{label='B', r=3, m=3}]",
Vertex{label='D', r=4, m=4}="[]",
Vertex{label='E', r=5, m=7}="[Vertex{label='F', r=6, m=7}]",
Vertex{label='F', r=6, m=7}="[Vertex{label='G', r=7, m=7}]",
Vertex{label='G', r=7, m=7}="[Vertex{label='A', r=1, m=7}]"}
