# Problem statement

We are given a directed graph $G = (V, A)$, where $V$ is the set of actors and $A \subseteq V^2$ is the set of directed arcs. Existence of an arc $(u, v) \in A$ is interpreted as that actor $u$ can lend some or all of its potential to $v$. Speaking of which, we are given a potential function $\mathfrak{P} \colon V \to [0, \infty) = \mathbb{R}_{\geq 0}$, which maps each actor to the potential it has at its disposal. Also, we are given an interest rate function $\mathfrak{I} \colon A \to \mathbb{R}_{\geq 0}$ that maps each arc $(u, v)$ to the interest rate $u$ can offer $v$ if $v$ decides to lend from $u$.

In a problem instance, we are given a lending actor $a$, maximum affordable interest rate $i$, and the required potential to collect $P$. The task is to find such a lending arrangement that the interest rate expenses are minimized. Also, note that if the lending actor cannot collect enough of potential from its immediate parents, the parents may need to lend from their parents and so on. Note also, however, that, for example, if the chain is two arcs long, one with both with interest rate $10\% = 0.1$, the effective interest rate becomes $21\% = 0.21$. (See this post for details.)

The above uses a very simplistic interest rate model: given an initial principal $\mathfrak{A}$, an interest rate $r$ and the time elapsed from the moment the principal was issued $t$, the accumulated sum is $\mathfrak{A}(1 + r)^t$.

# Code

Actor.java

package net.coderodde.finance.loan;

import java.util.Objects;

/**
* This class implements an actor in a loan graph. Each actor can interact with
* other actors. These relationships are implemented via actor graph directed
* arcs. Each actor can have identity that might be name, ID, or any other
* token.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 1, 2018)
* @param <I> the identity type.
*/
public final class Actor<I> {

/**
* The identity of this actor.
*/
private final I identity;

/**
* The actor graph this actor belongs to.
*/
private ActorGraph<I> ownerGraph;

public Actor(I identity) {
this.identity = Objects.requireNonNull(identity,
"The input identity is null.");
}

public ActorGraph<I> getActorGraph() {
return ownerGraph;
}

public I getIdentity() {
return identity;
}

@Override
public String toString() {
return "[Actor, " + identity.toString() + "]";
}

@Override
public int hashCode() {
return Objects.hashCode(identity);
}

@Override
public boolean equals(Object other) {
if (other == null) {
return false;
}

if (other == this) {
return true;
}

if (!getClass().equals(other.getClass())) {
return false;
}

Actor o = (Actor) other;
return getIdentity().equals(o.getIdentity());
}

void setOwnerActorGraph(ActorGraph<I> ownerGraph) {
this.ownerGraph = ownerGraph;
}
}


ActorGraph.java

package net.coderodde.finance.loan;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import static net.coderodde.finance.loan.Utils.checkPotential;

/**
* This class implements a directed actor graph.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 1, 2018)
* @param <I> the actor identity type.
*/
public final class ActorGraph<I> {

/**
* This map maps each actor node in the graph to the maximum number of
* resource units the node can lend. By definition, this value cannot be
* less than zero.
*/
private final Map<Actor<I>, Double> potentialMap = new HashMap<>();

/**
* Maps each arc in the actor graph to interest rate the tail actor can
* offer to the head actor.
*/
private final Map<Actor<I>, Map<Actor<I>, Double>>
interestRateMap = new HashMap<>();

/**
* Maps each actor <code>A</code> to the list of all other actors which have
* incoming arcs to <code>A</code>.
*/
private final Map<Actor<I>, Set<Actor<I>>> incomingActors =
new HashMap<>();

/**
* Caches the current number of arcs in this actor graph.
*/
private int numberOfArcs;

/**
* Returns the number of actors present in this actor graph.
*
* @return the number of actors.
*/
public int getNumberOfActors() {
return potentialMap.size();
}

/**
* Returns the number of arcs in this actor graph.
*
* @return the number of arcs.
*/
public int getNumberOfArcs() {
return numberOfArcs;
}

/**
* Adds a new actor to the graph with a specified potential. If the input
* actor is already in this graph, the potential and maximum interest rate
* are updated.
*
* @param actor               a new actor.
* @param potential           the potential of the actor.
*/
public void addActor(Actor<I> actor, double potential) {
Objects.requireNonNull(actor, "The input actor is null.");
potentialMap.put(actor, checkPotential(potential));

if (!actorBelongsToThisGraph(actor)) {
if (actorBelongsToOtherGraph(actor)) {
// If the input actor belongs to another graph, we need to
// disconnect it from there:
actor.getActorGraph().removeActor(actor);
}

actor.setOwnerActorGraph(this);
interestRateMap.put(actor, new HashMap<>());
incomingActors.put(actor, new HashSet<>());
}
}

/**
* Removes the actor and completely disconnects it from this graph.
*
* @param actor the actor to remove.
*/
public void removeActor(Actor<I> actor) {
Objects.requireNonNull(actor, "The input actor is null.");
potentialMap.remove(actor);
numberOfArcs -= incomingActors.get(actor).size();
numberOfArcs -= interestRateMap.get(actor).size();

for (Actor<I> incomingActor : incomingActors.get(actor)) {
interestRateMap.get(incomingActor).remove(actor);
}

for (Actor<I> outgoingActor : interestRateMap.get(actor).keySet()) {
incomingActors.get(outgoingActor).remove(actor);
}

interestRateMap.remove(actor);
incomingActors.remove(actor);
actor.setOwnerActorGraph(null);
}

/**
* Adds a new actor arc to this actor graph with a specified interest rate.
*
* @param sourceActor  the loan source actor.
* @param targetActor  the loan target actor.
* @param interestRate the interest rate {@code sourceActor} can offer to
*                     {@code targetActor}.
*/
Actor<I> targetActor,
double interestRate) {
checkArc(sourceActor, targetActor);
checkNotSelfLoop(sourceActor, targetActor);

if (!interestRateMap.get(sourceActor).containsKey(targetActor)) {
// Once here, the input arc does not exist in this graph so
// increment the number of arcs counter.
numberOfArcs++;
}

interestRateMap.get(sourceActor)
.put(targetActor,
Utils.checkInterestRate(interestRate));
}

/**
* Checks whether the given arc is in this graph.
*
* @param sourceActor
* @param targetActor
* @return {@code true} only if there is a an arc from {@code sourceActor}
*         to {@code targetActor}.
*/
public boolean hasArc(Actor<I> sourceActor, Actor<I> targetActor) {
checkArc(sourceActor, targetActor);
return interestRateMap.get(sourceActor).containsKey(targetActor);
}

/**
* Makes sure the arc <code>(sourceActor, targetActor)</code> does not
* appear in this graph.
*
* @param sourceActor the tail actor.
* @param targetActor the head actor.
*/
public void removeArc(Actor<I> sourceActor, Actor<I> targetActor) {
checkArc(sourceActor, targetActor);

if (interestRateMap.get(sourceActor).containsKey(targetActor)) {
numberOfArcs--;
interestRateMap.get(sourceActor).remove(targetActor);
incomingActors.get(targetActor).remove(sourceActor);
}
}

/**
* Clears this graph.
*/
public void clear() {
potentialMap.clear();
interestRateMap.clear();
incomingActors.clear();
}

/**
* Returns a set view of incoming actors.
*
* @param actor the target actor.
* @return a set view of incoming actors.
*/
public Set<Actor<I>> getIncomingArcs(Actor<I> actor) {
Objects.requireNonNull(actor, "The input actor is null.");
checkActorIsInGraph(
actor,
"The input actor (" + actor + ") is not in this graph.");
return Collections.unmodifiableSet(incomingActors.get(actor));
}

/**
* Returns a set view of outgoing actors.
*
* @param actor the target actor.
* @return a set view of outgoing actors.
*/
public Set<Actor<I>> getOutgoingArcs(Actor<I> actor) {
Objects.requireNonNull(
actor,
"The input actor (" + actor + ") is not in this graph.");
checkActorIsInGraph(
actor,
"The input actor (" + actor + ") is not in this graph.");
return Collections.unmodifiableSet(interestRateMap.get(actor).keySet());
}

/**
* Returns the interest rate {@code sourceActor} can offer to
* {@code targetActor}.
*
* @param sourceActor the lender actor.
* @param targetActor the actor receiving the actor.
* @return the interest rate offered to {@code sourceActor} to
*         {@code targetActor}.
*/
public double getInterestRate(Actor<I> sourceActor, Actor<I> targetActor) {
Objects.requireNonNull(sourceActor, "The input source actor is null.");
Objects.requireNonNull(targetActor, "The input target actor is null.");
checkActorIsInGraph(sourceActor,
"The source actor is not in this graph.");
checkActorIsInGraph(targetActor,
"The target actor is not in this graph.");
checkArcExists(sourceActor, targetActor);
return interestRateMap.get(sourceActor).get(targetActor);
}

/**
* Returns the potential of an input actor.
*
* @param actor the target actor.
* @return the potential of an input actor.
*/
public double getActorPotential(Actor<I> actor) {
Objects.requireNonNull(actor, "The input actor is null.");
checkActorIsInGraph(actor, "The input actor is not in this graph.");
return potentialMap.get(actor);
}

/**
* Checks that the given actors are not {@code null}, and that both the
* input actors are in this graph.
*
* @param sourceActor the source actor.
* @param targetActor the target actor.
*/
private void checkArc(Actor<I> sourceActor, Actor<I> targetActor) {
Objects.requireNonNull(sourceActor, "The source actor is null.");
Objects.requireNonNull(targetActor, "The target actor is null.");
checkActorIsInGraph(
sourceActor,
"The input source actor (" + sourceActor
+ ") is not in this graph.");
checkActorIsInGraph(
targetActor,
"The input target actor (" + targetActor
+ ") is not in this graph.");
}

// Returns true only if the input actor belongs to this graph:
private boolean actorBelongsToThisGraph(Actor<I> actor) {
return actor.getActorGraph() == this;
}

// Returns true only if the input graph does not belong to this graph and
// its owner graph is not set to null:
private boolean actorBelongsToOtherGraph(Actor<I> actor) {
return !actorBelongsToThisGraph(actor) && actor.getActorGraph() != null;
}

// This validation method is called only after we make sure the two input
// actors are in the graph, so this one simply checks that there is an arc
// from the source actor to the target actor.
private void checkArcExists(Actor<I> sourceActor, Actor<I> targetActor) {
if (!interestRateMap.get(sourceActor).containsKey(targetActor)) {
throw new IllegalStateException(
"The input arc (" + sourceActor + ", " + targetActor +
") is not in this graph.");
}
}

// Makes sure the input actor is in this graph.
private void checkActorIsInGraph(Actor<I> actor, String errorMessage) {
if (actor.getActorGraph() != this) {
throw new IllegalStateException(errorMessage);
}
}

// Makes sure that the two input actors are not same.
private void checkNotSelfLoop(Actor<I> actor1, Actor<I> actor2) {
if (actor1.equals(actor2)) {
throw new IllegalArgumentException(
"Self-loops are not allowed. Trying to create a " +
"self-loop for " + actor1 + ".");
}
}
}


MostCostEffectiveLoan.java

package net.coderodde.finance.loan;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
* This class implements a most cost-effective loan.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 2, 2018)
* @param <I> the actor identity type.
*/
public final class MostCostEffectiveLoan<I> {

/**
* The actor requesting actor.
*/
private final Actor<I> lenderActor;

/**
* The actual potential the target actor can lend. The value of this field
* may be smaller than {@code requestedPotential} in case the requested
* potential is too large and/or the graph is not sufficiently large.
*/
private final double potential;

/**
* The requested potential. The value of this field may be larger than the
* value of {@code potential} in case the requested potential is too large
* and/or the graph is not sufficiently large.
*/
private final double requestedPotential;

/**
* The maximum interest rate the actor can afford.
*/
private final double maximumInterestRate;

/**
* Maps each relevant actor to the potential he/she issued to the lender
* actor directly or indirectly.
*/
private Map<Actor<I>, Double> potentialMap = new HashMap<>();

/**
* Maps each relevant actor to another actor to whom he issued some
* potential.
*/
private Map<Actor<I>, Actor<I>> directionMap = new HashMap<>();

public MostCostEffectiveLoan(Actor<I> lenderActor,
double potential,
double requestedPotential,
double maximumInterestRate,
Map<Actor<I>, Double> potentialMap,
Map<Actor<I>, Actor<I>> directionMap) {
this.lenderActor =
Objects.requireNonNull(lenderActor,
"The input lender actor is null.");
this.potential = Utils.checkPotential(potential);
this.requestedPotential =
Utils.checkRequestedPotential(requestedPotential);
this.maximumInterestRate =
Utils.checkMaximumInterestRate(maximumInterestRate);
this.potentialMap = new HashMap<>(potentialMap);
this.directionMap = new HashMap<>(directionMap);
}

public Actor<I> getLenderActor() {
return lenderActor;
}

return potential;
}

public double getRequestedPotential() {
return requestedPotential;
}

public double getMaximumInterestRate() {
return maximumInterestRate;
}

public Map<Actor<I>, Double> getPotentialMapView() {
return Collections.unmodifiableMap(potentialMap);
}

public Map<Actor<I>, Actor<I>> getDirectionMap() {
return Collections.unmodifiableMap(directionMap);
}

// Used for unit testing.
@Override
public boolean equals(Object o) {
if (o == null) {
return false;
}

if (o == this) {
return true;
}

if (!getClass().equals(o.getClass())) {
return false;
}

MostCostEffectiveLoan<I> other = (MostCostEffectiveLoan<I>) o;

return getLenderActor().equals(other.getLenderActor())
&& getRequestedPotential() == other.getRequestedPotential()
&& getMaximumInterestRate() == other.getMaximumInterestRate()
&& potentialMap.equals(other.potentialMap)
&& directionMap.equals(other.directionMap);
}

@Override
public String toString() {
StringBuilder stringBuilder =
new StringBuilder("[Loan, actor = ")
.append(lenderActor)
.append(",\npotential = ")
.append(potential)
.append(",\nrequested potential = ")
.append(requestedPotential)
.append(",\nmaximum interest rate = ")
.append(maximumInterestRate)
.append(",\npotentials:");

for (Map.Entry<Actor<I>, Double> entry : potentialMap.entrySet()) {
stringBuilder.append("\n")
.append(entry.getKey())
.append(" -> ")
.append(entry.getValue());
}

for (Map.Entry<Actor<I>, Actor<I>> entry : directionMap.entrySet()) {
stringBuilder.append("\n")
.append(entry.getKey())
.append(" -> ")
.append(entry.getValue());
}

return stringBuilder.append("]").toString();
}
}


MostCostEffectiveLoanFinder.java

package net.coderodde.finance.loan;

/**
* This interface defines the API for all most cost effective loan finder
* algorithms.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 1, 2018)
* @param <I> the actor identity type.
*/
public interface MostCostEffectiveLoanFinder<I> {

/**
* Computes a most cost effective loans for the input actor in the input
* actor graph such that the actor receives {@code requiredPrincipal} with
* minimal interest rates or as much as possible while obeying the interest
* rate constraints.
*
* @param actor               the debt actor.
* @param requiredPrincipal   the required principal.
* @param maximumInterestRate the maximum allowed effective interest rate.
* @return the object describing the loan arrangements.
*/
public MostCostEffectiveLoan<I>  findLenders(Actor<I> actor,
double requiredPrincipal,
double maximumInterestRate);
}


Utils.java

package net.coderodde.finance.loan;

/**
* This class provides some common utility methods.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 2, 2018)
*/
public final class Utils {

private Utils() {}

/**
* Checks that the input potential is a finite, non-NaN, non-negative value.
*
* @param potential the potential to check.
* @return the input value.
*/
public static double checkPotential(double potential) {
return checkDoubleIsPositiveOrZero(
potential,
"The input potential is NaN.",
"The input potential is negative: " + potential + ".",
"The input potential is positive infinite.");
}

/**
* Checks that the input requested potential is a finite, non-NaN,
* non-negative value.
*
* @param requestedPotential the requested potential to check.
* @return the input value.
*/
public static double checkRequestedPotential(double requestedPotential) {
return checkDoubleIsPositiveOrZero(
requestedPotential,
"The input requested potential is NaN.",
"The input requested potential is negative: " +
requestedPotential + ".",
"The input requested potential is positive infinite.");
}

/**
* Checks that the input maximum interest rate is a finite, non-NaN,
* non-negative value.
*
* @param maximumInterestRate the maximum interest rate to check.
* @return the input value.
*/
public static double checkMaximumInterestRate(double maximumInterestRate) {
return checkDoubleIsPositiveOrZero(
maximumInterestRate,
"The input maximum interest rate is NaN.",
"The input maximum interest rate is negative: " +
maximumInterestRate + ".",
"The input maximum interest rate is positive infinite.");
}

/**
* Checks that the input interest rate is a finite, non-NaN,
* non-negative value.
*
* @param interestRate the interest rate to check.
* @return the input value.
*/
public static double checkInterestRate(double interestRate) {
return checkDoubleIsPositiveOrZero(
interestRate,
"The input interest rate is NaN.",
"The input interest rate is negative: " +
interestRate + ".",
"The input interest rate is positive infinite.");
}

private static double checkDoubleIsPositiveOrZero(
double targetValue,
String errorMessageOnNaN,
String errorMessageOnNegative,
String errorMessageOnInfinite) {
if (Double.isNaN(targetValue)) {
throw new IllegalArgumentException(errorMessageOnNaN);
}

if (targetValue < 0.0) {
throw new IllegalArgumentException(errorMessageOnNegative);
}

if (Double.isInfinite(targetValue)) {
throw new IllegalArgumentException(errorMessageOnInfinite);
}

return targetValue;
}
}


BinaryHeapMostCostEffectiveLoanFinder.java

package net.coderodde.finance.loan.support;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import net.coderodde.finance.loan.Actor;
import net.coderodde.finance.loan.ActorGraph;
import net.coderodde.finance.loan.MostCostEffectiveLoan;
import net.coderodde.finance.loan.Utils;
import net.coderodde.finance.loan.MostCostEffectiveLoanFinder;

/**
* This class implements the default most cost effective loan finder using a
* binary heap.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 1, 2018)
* @param <I> the actor identity type.
*/
public final class BinaryHeapMostCostEffectiveLoanFinder<I>
implements MostCostEffectiveLoanFinder<I> {

/**
* {@inheritDoc }
*/
@Override
public MostCostEffectiveLoan<I> findLenders(Actor<I> actor,
double requestedPotential,
double maximumInterestRate) {
// Sanity checks:
checkActorBelongsToGraph(actor);
Utils.checkRequestedPotential(requestedPotential);
ActorGraph<I> actorGraph = actor.getActorGraph();

// Algorithm state:
Queue<HeapNode<I>> open = new PriorityQueue<>();
Set<Actor<I>> closed = new HashSet<>();
Map<Actor<I>, Double> solutionPotentialFunction = new HashMap<>();
Map<Actor<I>, Actor<I>> directionFunction = new HashMap<>();
double currentPrincipal = 0.0;

// Loop initialization:
for (Actor<I> initialIncomingActor
: actorGraph.getIncomingArcs(actor)) {
if (actorGraph.getInterestRate(initialIncomingActor, actor)
<= maximumInterestRate) {
new HeapNode(
initialIncomingActor,
actor,
actorGraph.getInterestRate(initialIncomingActor, actor)
)
);
}
}

while (!open.isEmpty() && currentPrincipal < requestedPotential) {
HeapNode<I> currentHeapNode = open.remove();
Actor<I> currentActor = currentHeapNode.getActor();
Actor<I> previousActor = currentHeapNode.getPreviousActor();
double effectiveInterestRate =
currentHeapNode.getEffectiveInterestRate();
double potentialIncrease =
Math.min(actorGraph.getActorPotential(currentActor),
requestedPotential - currentPrincipal);

currentPrincipal += potentialIncrease;
solutionPotentialFunction.put(currentActor, potentialIncrease);
directionFunction.put(currentActor, previousActor);

for (Actor<I> lendingActor :
actorGraph.getIncomingArcs(currentActor)) {
if (!closed.contains(lendingActor)) {
double nextInterestRate =
combineInterestRates(
effectiveInterestRate,
actorGraph.getInterestRate(lendingActor,
currentActor));

if (nextInterestRate <= maximumInterestRate) {
currentActor,
nextInterestRate));
}
}
}
}

return new MostCostEffectiveLoan<>(
actor,
currentPrincipal,
requestedPotential,
maximumInterestRate,
solutionPotentialFunction,
directionFunction);
}

private double combineInterestRates(double interestRate1,
double interestRate2) {
return interestRate1 + interestRate2 + interestRate1 * interestRate2;
}

private static final class HeapNode<I> implements Comparable<HeapNode<I>> {

private final Actor<I> actor;
private final Actor<I> previousActor;
private final double effectiveInterestRate;

HeapNode(Actor<I> actor,
Actor<I> previousActor,
double effectiveInterestRate) {
this.actor = actor;
this.previousActor = previousActor;
this.effectiveInterestRate = effectiveInterestRate;
}

Actor<I> getActor() {
return actor;
}

Actor<I> getPreviousActor() {
return previousActor;
}

double getEffectiveInterestRate() {
return effectiveInterestRate;
}

@Override
public int compareTo(HeapNode<I> o) {
return Double.compare(effectiveInterestRate,
o.effectiveInterestRate);
}
}

private void checkActorBelongsToGraph(Actor<I> actor) {
if (actor.getActorGraph() == null) {
throw new IllegalStateException(
"The input actor does not belong to an actor graph.");
}
}
}