В этом посте представлена реализация графа ссуд. Класс принадлежит этот репозиторий GitHub.
net.coderodde.loan.model.Node:
package net.coderodde.loan.model;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
/**
* This class implements a loan graph node.
*
* @author Rodion "coderodde" Efremov
* @version 1.61 (Sep 2, 2021)
* @since 1.6
*/
public class Node implements Iterable<Node> {
/**
* This is the name of a node. Also, this is treated as the ID of a
* node. (Two nodes <code>u</code>, <code>v</code> are considered as
* equal if and only if <code>u.name.equals(v.name)</code>.
*/
private final String name;
/**
* This is the map from lender to loan amount.
*/
private final Map<Node, Long> in = new HashMap<>();
/**
* This is the map from borrower to resources lent.
*/
private final Map<Node, Long> out = new HashMap<>();
/**
* The graph owning this node, if any.
*/
protected Graph ownerGraph;
/**
* If equity is below 0, this node owes, and, vice versa, if positive,
* is eligible to receive cash.
*/
private long equity;
/**
* Constructs a new node.
*
* @param name the name of the new node.
*/
public Node(String name) {
this.name = name;
}
/**
* Copy-constructs a node.
*
* @param copy the node to share the identity with.
*/
public Node(Node copy) {
this(copy.name);
}
/**
* Gets the name of this node.
*
* @return the name of this node.
*/
public String getName() {
return name;
}
/**
* Returns the number of borrowers.
*
* @return the number of borrowers.
*/
public int getNumberOfBorrowers() {
return this.out.size();
}
/**
* Returns the number of lenders.
*
* @return the number of lenders.
*/
public int getNumberOfLenders() {
return this.in.size();
}
/**
* Returns the weight of the directed arc {@code (this, borrower)}.
*
* @param borrower the head node of the arc.
* @return the arc weight.
*/
public long getWeightTo(Node borrower) {
checkBorrowerNotNull(borrower);
checkBorrowerBelongsToThisGraph(borrower);
checkBorrowerExists(borrower);
return this.out.get(borrower);
}
/**
* Sets the weight of the directed arc {@code (this, borrower)}.
*
* @param borrower the head node of the arc.
* @param weight the arc weight.
*/
public void setWeightTo(Node borrower, long weight) {
checkBorrowerNotNull(borrower);
checkBorrowerBelongsToThisGraph(borrower);
checkBorrowerExists(borrower);
long oldWeight = this.out.get(borrower);
this.out.put(borrower, weight);
borrower.in.put(this, weight);
// 50 = 100 - 50
long weightDelta = weight - oldWeight;
ownerGraph.flow += weightDelta;
equity += weightDelta;
borrower.equity -= weightDelta;
}
/**
* Connects this node to a borrower.
*
* @param borrower the borrower.
*/
public void connectToBorrower(Node borrower) {
checkBorrowerNotNull(borrower);
checkBorrowerBelongsToThisGraph(borrower);
if (out.containsKey(borrower)) {
return;
}
if (borrower.ownerGraph != this.ownerGraph) {
borrower.ownerGraph = this.ownerGraph;
borrower.clear();
}
out.put(borrower, 0L);
borrower.in.put(this, 0L);
ownerGraph.edgeAmount++;
}
public boolean isConnectedTo(Node borrower) {
return out.containsKey(borrower);
}
/**
* Remove the borrower of this node.
*
* @param borrower the borrower to remove.
*/
public void removeBorrower(final Node borrower) {
checkBorrowerNotNull(borrower);
if (borrower.ownerGraph != this.ownerGraph) {
return;
}
if (out.containsKey(borrower)) {
long w = out.get(borrower);
out.remove(borrower);
borrower.in.remove(this);
this.equity -= w;
borrower.equity += w;
ownerGraph.edgeAmount--;
ownerGraph.flow -= w;
}
}
/**
* Clear this node from all loans coming in and out.
*/
public void clear() {
Iterator<Node> iterator = iterator();
while (iterator.hasNext()) {
iterator.next();
iterator.remove();
}
iterator = parentIterable().iterator();
while (iterator.hasNext()) {
iterator.next();
iterator.remove();
}
}
public boolean isOrphan() {
return ownerGraph == null;
}
private void checkBorrowerBelongsToThisGraph(final Node borrower) {
if (borrower.ownerGraph != this.ownerGraph) {
throw new IllegalStateException("The input borrower node " +
borrower + " does not belong to this graph.");
}
}
/**
* Returns the string representation of this node.
* @return
*/
@Override
public String toString() {
return "[Node " + name + "; equity: " + getEquity() + "]";
}
/**
* Returns the hash code of this node. Depends only on the name of
* the node.
*
* @return the hash code of this node.
*/
@Override
public int hashCode() {
return name.hashCode();
}
/**
* Returns <code>true</code> if and only if the two nodes have the
* same name (identity).
*
* @param o the object to test against.
* @return <code>true</code> if and only if <code>o</code> is a node
* and has the same name.
*/
@Override
public boolean equals(Object o) {
return ((Node) o).name.equals(this.name);
}
/**
* Returns the iterator over this node's borrowers.
*
* @return the iterator over this node's borrowers.
*/
@Override
public Iterator<Node> iterator() {
return new ChildIterator();
}
/**
* Returns the iterable over this nodes lenders.
*
* @return the iterable over this nodes lenders.
*/
public Iterable<Node> parentIterable() {
return new ParentIterable();
}
/**
* Return the equity of this node.
*
* @return the equity of this node.
*/
public long getEquity() {
return this.equity;
}
/**
* Checks that borrower is not null and not this.
*
* @param borrower the borrower to check.
*/
private void checkBorrowerNotNull(final Node borrower) {
if (borrower == null) {
throw new NullPointerException("Borrower is null.");
}
}
/**
* This class implements the iterator over this node's borrowers.
*/
private class ChildIterator implements Iterator<Node> {
/**
* The actual iterator.
*/
private Iterator<Node> iterator = Node.this.out.keySet().iterator();
/**
* Holds the node last returned by <code>next</code>.
*/
private Node lastReturned;
/**
* Returns <code>true</code> if and only if there is more
* nodes to iterate.
*
* @return <code>true</code> if and only if there is more nodes
* to iterate.
*/
@Override
public boolean hasNext() {
return iterator.hasNext();
}
/**
* Returns the next node.
*
* @return the next node.
*/
@Override
public Node next() {
return (lastReturned = iterator.next());
}
/**
* Removes the node from this node's borrowers.
*/
@Override
public void remove() {
if (lastReturned == null) {
throw new NoSuchElementException(
"There is no current element to remove.");
}
final long weight = Node.this.getWeightTo(lastReturned);
iterator.remove();
lastReturned.in.remove(Node.this);
lastReturned = null;
if (ownerGraph != null) {
ownerGraph.edgeAmount--;
ownerGraph.flow -= weight;
}
}
}
/**
* Returns the iterable over this node's lenders.
*/
private class ParentIterable implements Iterable<Node> {
/**
* Returns the iterator over this node's lenders.
*
* @return the iterator over this node's lenders.
*/
@Override
public Iterator<Node> iterator() {
return new ParentIterator();
}
}
/**
* This class implements the iterator over this node's lenders.
*/
private class ParentIterator implements Iterator<Node> {
/**
* The actual iterator.
*/
private Iterator<Node> iterator = Node.this.in.keySet().iterator();
/**
* The node last returned.
*/
private Node lastReturned;
/**
* Return <code>true</code> if this iterator has more nodes
* to iterate.
*
* @return <code>true</code> if this iterator has more nodes to
* iterate.
*/
@Override
public boolean hasNext() {
return iterator.hasNext();
}
/**
* Returns the next node or throws
* <code>NoSuchElementException</code> if there is no more
* nodes.
*
* @return the next element.
*/
@Override
public Node next() {
return (lastReturned = iterator.next());
}
/**
* Removes this lender from this node's lender list.
*/
@Override
public void remove() {
if (lastReturned == null) {
throw new NoSuchElementException(
"There is no current element to remove.");
}
final long weight = lastReturned.getWeightTo(Node.this);
iterator.remove();
lastReturned.out.remove(Node.this);
lastReturned = null;
if (ownerGraph != null) {
ownerGraph.edgeAmount--;
ownerGraph.flow -= weight;
}
}
}
private void checkBorrowerExists(Node borrower) {
if (!out.containsKey(borrower)) {
throw new IllegalArgumentException(
"No arc (" + this + ", " + borrower + ").");
}
}
private void checkWeightDelta(final Node borrower, final long weightDelta) {
if (out.get(borrower) + weightDelta < 0L) {
throw new IllegalArgumentException(
"The weight delta (" + weightDelta +
") exceeds the arc weight (" +
out.get(borrower) + ").");
}
}
}
net.coderodde.loan.model.Graph:
package net.coderodde.loan.model;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
/**
* This class models a loan graph.
*
* @author coderodde
* @version 1.6
*/
public class Graph implements Iterable<Node> {
/**
* This map maps name of the nodes to respective node objects.
*/
private final Map<String, Node> nodeMap = new HashMap<>();
/**
* This list contains all the nodes currently stored in this graph.
*/
private final List<Node> nodeList = new ArrayList<>();
/**
* This variable caches the amount of edges in this graph.
*/
protected int edgeAmount;
/**
* This variable caches the total flow of this graph
* (sum of edge weights).
*/
protected long flow;
/**
* Constructs an empty graph.
*/
public Graph() {}
/**
* Constructs a graph with the same amount of nodes as in
* <code>copy</code> with the same node names. Edges are copied as well,
* and their respective arc weights are set correspondingly.
*
* @param copy the graph to copy.
*/
public Graph(Graph copy) {
Map<Node, Node> map = new HashMap<>(nodeList.size());
for (Node node : copy) {
Node newNode = new Node(node);
map.put(node, newNode);
add(newNode);
}
for (Node node : copy) {
Node tail = map.get(node);
for (Node borrower : node) {
Node head = map.get(borrower);
tail.connectToBorrower(head);
tail.setWeightTo(head, node.getWeightTo(borrower));
}
}
this.edgeAmount = copy.edgeAmount;
}
public Graph copyWithoutArcs() {
Graph result = new Graph();
for (Node node : this) {
result.add(new Node(node));
}
return result;
}
@Override
public String toString() {
return "[" + nodeList.size() + " nodes, " + edgeAmount + " edges, " +
flow + " flow]";
}
public String toDetailedString() {
StringBuilder stringBuilder = new StringBuilder();
for (Node node : this) {
Graph.this.toDetailedString(node, stringBuilder);
}
return stringBuilder.toString();
}
private static void toDetailedString(
Node node,
StringBuilder stringBuilder) {
stringBuilder.append(node).append("n");
for (Node child : node) {
stringBuilder.append(" Node ")
.append(child.getName())
.append(", w = ")
.append(node.getWeightTo(child))
.append("n");
}
}
/**
* Adds a node to this graph if not already in this graph.
*
* @param node the node to add.
*/
public void add(Node node) {
Objects.requireNonNull(node, "The input node is null.");
if (node.ownerGraph != this && node.ownerGraph != null) {
throw new IllegalArgumentException(
"The input node belongs to some another graph.");
}
if (nodeMap.containsKey(node.getName())) {
// Already in this graph.
return;
}
node.clear();
node.ownerGraph = this;
nodeMap.put(node.getName(), node);
nodeList.add(node);
}
/**
* Checks whether a node is included in this graph.
*
* @param node the node to query.
* @return <code>true</code> if this graph contains the query node;
* <code>false</code> otherwise.
*/
public boolean contains(Node node) {
Objects.requireNonNull(node, "The input node is null.");
if (node.ownerGraph != this) {
return false;
}
return nodeMap.containsKey(node.getName());
}
/**
* Returns a node with index <code>index</code>.
*
* @param index the node index.
* @return the node at index <code>index</code>.
*/
public Node get(int index) {
return nodeList.get(index);
}
/**
* Returns a node with name <code>name</code>.
*
* @param name the name of the query node.
* @return the node with name <code>name</code>; <code>null</code>
* otherwise.
*/
public Node get(String name) {
return nodeMap.get(name);
}
/**
* Removes a node from this graph if present.
*
* @param node the node to remove.
*/
public void remove(Node node) {
if (node.ownerGraph != this) {
throw new IllegalArgumentException(
"The input node does not belong to this graph.");
}
if (nodeMap.containsKey(node.getName())) {
nodeMap.remove(node.getName());
nodeList.remove(node);
node.clear();
node.ownerGraph = null;
}
}
/**
* Returns the amount of nodes in this graph.
*
* @return the amount of nodes in this graph.
*/
public int size() {
return nodeList.size();
}
/**
* Returns the amount of edges in this graph.
*
* @return the amount of edges in this graph.
*/
public int getEdgeAmount() {
return edgeAmount;
}
/**
* Returns the total flow (sum of all edge weights) of this graph.
*
* @return the total flow of this graph.
*/
public long getTotalFlow() {
return flow;
}
/**
* Returns an iterator over this graph's nodes.
*
* @return an iterator over this graph's nodes.
*/
@Override
public Iterator<Node> iterator() {
return new NodeIterator();
}
public boolean isEquivalentTo(Graph g) {
if (this.size() != g.size()) {
return false;
}
for (Node node : this) {
Node tmp = g.get(node.getName());
if (tmp == null) {
return false;
}
if (node.getEquity() != tmp.getEquity()) {
return false;
}
}
return true;
}
/**
* This class implements the iterators over this graph's nodes.
*/
private class NodeIterator implements Iterator<Node> {
/**
* The actual iterator.
*/
private Iterator<Node> iterator = nodeList.iterator();
/**
* The last returned node.
*/
private Node lastReturned;
/**
* Returns <code>true</code> if and only if there is more
* nodes to iterate.
*
* @return <code>true</code> if and only if there is more nodes to
* iterate.
*/
@Override
public boolean hasNext() {
return iterator.hasNext();
}
/**
* Returns the next node or throws
* <code>NoSuchElementException</code> if there is no more
* nodes to iterate.
*
* @return the next node.
*/
@Override
public Node next() {
return (lastReturned = iterator.next());
}
/**
* Removes the current node from this graph.
*/
@Override
public void remove() {
if (lastReturned == null) {
throw new NoSuchElementException(
"There is no current node to remove.");
}
iterator.remove();
nodeMap.remove(lastReturned.getName());
lastReturned.clear();
lastReturned = null;
}
}
private void checkNodeBelongsToThisGraph(Node node) {
if (node.ownerGraph != this) {
throw new IllegalArgumentException(
"The input node " + node +
" does not belong to this graph.");
}
}
}
(Этот класс проживает в GitHub.)
Похожие сообщения:
- Упрощение ссудного графа в Java: рекурсивная DFS для поиска ориентированных циклов
- Упрощение ссудного графа в Java: алгоритм минимизации дуги
Запрос на критику
Как всегда, я с нетерпением жду ваших комментариев.