I am trying to calculate the edge loads of a (power grid) network but am stuck and can't figure out the right implementation.
Given the following data structure:
export type Network = {
readonly nodes: readonly Node[];
readonly edges: readonly Edge[];
}
export type Node = {
readonly id: string;
readonly displayName: string;
readonly type: NodeType;
readonly isGreenProduction: boolean;
readonly hasFixedProduction: boolean;
readonly maxProduction: number;
production: number;
readonly requiresGreenConsumption: boolean;
readonly hasFixedConsumption: boolean;
readonly maxConsumption: number;
consumption: number;
}
export type NodeType = "participant" | "connection";
export type Edge = {
readonly nodes: [Node, Node];
readonly capacity: number;
readonly maxCapacity: number;
}
and a few test cases (that should be the correct values for the edges):
const defaultNode: Node = {
id: "testNode",
displayName: "testNode",
type: "participant",
production: 0,
maxProduction: 0,
isGreenProduction: false,
hasFixedProduction: false,
consumption: 0,
maxConsumption: 0,
requiresGreenConsumption: false,
hasFixedConsumption: false,
};
const defaultEdge: Edge = {
nodes: [defaultNode, defaultNode],
capacity: 0,
maxCapacity: 0,
};
describe("Edge calculation", () => {
/**
* Producer(100) --- Consumer(100)
*/
it("simple", () => {
const producer: Node = { ...defaultNode, production: 100 };
const consumer: Node = { ...defaultNode, consumption: 100 };
const edge: Edge = { ...defaultEdge, nodes: [producer, consumer] };
const network: Network = { nodes: [producer, consumer], edges: [edge] };
calculateEdges(network);
expect(edge.capacity).toBe(100);
});
/**
* Producer(150) --- Consumer(100)
* |
* Consumer(50)
*/
it("simple split consumer", () => {
const producer: Node = { ...defaultNode, production: 150 };
const consumer: Node = { ...defaultNode, consumption: 100 };
const consumer2: Node = { ...defaultNode, consumption: 50 };
const edge1: Edge = { ...defaultEdge, nodes: [producer, consumer] };
const edge2: Edge = { ...defaultEdge, nodes: [producer, consumer2] };
const network: Network = { nodes: [producer, consumer, consumer2], edges: [edge1, edge2] };
calculateEdges(network);
expect(edge1.capacity).toBe(100);
expect(edge2.capacity).toBe(50);
});
/**
* Producer(150) --- Consumer(200)
* /
* Producer(50)
*/
it("simple split producer", () => {
const producer: Node = { ...defaultNode, production: 150 };
const producer2: Node = { ...defaultNode, production: 50 };
const consumer: Node = { ...defaultNode, consumption: 200 };
const edge1: Edge = { ...defaultEdge, nodes: [producer, consumer] };
const edge2: Edge = { ...defaultEdge, nodes: [producer2, consumer] };
const network: Network = { nodes: [producer, producer2, consumer], edges: [edge1, edge2] };
calculateEdges(network);
expect(edge1.capacity).toBe(150);
expect(edge2.capacity).toBe(50);
});
/**
* Producer(100) --- Connection --- Consumer(100)
*/
it("simple connection", () => {
const producer: Node = { ...defaultNode, production: 100 };
const consumer: Node = { ...defaultNode, consumption: 100 };
const connection: Node = { ...defaultNode, type: "connection" };
const edge1: Edge = { ...defaultEdge, nodes: [producer, connection] };
const edge2: Edge = { ...defaultEdge, nodes: [connection, consumer] };
const network: Network = { nodes: [producer, consumer, connection], edges: [edge1, edge2] };
calculateEdges(network);
expect(edge1.capacity).toBe(100);
expect(edge2.capacity).toBe(100);
});
/**
* Producer(100) --- Connection --- Connection --- Consumer(100)
*/
it("simple double connection", () => {
const producer: Node = { ...defaultNode, production: 100 };
const consumer: Node = { ...defaultNode, consumption: 100 };
const connection: Node = { ...defaultNode, type: "connection" };
const connection2: Node = { ...defaultNode, type: "connection" };
const edge1: Edge = { ...defaultEdge, nodes: [producer, connection] };
const edge2: Edge = { ...defaultEdge, nodes: [connection, connection2] };
const edge3: Edge = { ...defaultEdge, nodes: [connection2, consumer] };
const network: Network = {
nodes: [producer, consumer, connection, connection2],
edges: [edge1, edge2, edge3],
};
calculateEdges(network);
expect(edge1.capacity).toBe(100);
expect(edge2.capacity).toBe(100);
expect(edge2.capacity).toBe(100);
});
/**
* / Consumer(50)
* Producer(100) --- Connection
* \ Consumer(50)
*/
it("simple connection with split", () => {
const producer: Node = { ...defaultNode, production: 100 };
const consumer: Node = { ...defaultNode, consumption: 50 };
const consumer2: Node = { ...defaultNode, consumption: 50 };
const connection: Node = { ...defaultNode, type: "connection" };
const edge1: Edge = { ...defaultEdge, nodes: [producer, connection] };
const edge2: Edge = { ...defaultEdge, nodes: [connection, consumer] };
const edge3: Edge = { ...defaultEdge, nodes: [connection, consumer2] };
const network: Network = {
nodes: [producer, consumer, consumer2, connection],
edges: [edge1, edge2, edge3],
};
calculateEdges(network);
expect(edge1.capacity).toBe(100);
expect(edge2.capacity).toBe(50);
expect(edge3.capacity).toBe(50);
});
/**
*
* Producer(100) --- Connection --- Consumer(150)
* |
* Producer(50)
*/
it("double producer", () => {
const producer: Node = { ...defaultNode, production: 100 };
const producer2: Node = { ...defaultNode, production: 50 };
const consumer: Node = { ...defaultNode, consumption: 150 };
const connection: Node = { ...defaultNode, type: "connection" };
const edge1: Edge = { ...defaultEdge, nodes: [producer, connection] };
const edge2: Edge = { ...defaultEdge, nodes: [producer2, connection] };
const edge3: Edge = { ...defaultEdge, nodes: [connection, consumer] };
const network: Network = {
nodes: [producer, producer2, consumer, connection],
edges: [edge1, edge2, edge3],
};
calculateEdges(network);
expect(edge1.capacity).toBe(100);
expect(edge2.capacity).toBe(50);
expect(edge3.capacity).toBe(150);
});
/**
*
* Producer(100green) --- Connection --- Consumer(100green)
* |
* Producer(50)
*/
it("double producer green prefered", () => {
const producer: Node = { ...defaultNode, production: 100, isGreenProduction: true };
const producer2: Node = { ...defaultNode, production: 50 };
const consumer: Node = { ...defaultNode, consumption: 100, requiresGreenConsumption: true };
const connection: Node = { ...defaultNode, type: "connection" };
const edge1: Edge = { ...defaultEdge, nodes: [producer, connection] };
const edge2: Edge = { ...defaultEdge, nodes: [producer2, connection] };
const edge3: Edge = { ...defaultEdge, nodes: [connection, consumer] };
const network: Network = {
nodes: [producer, producer2, consumer, connection],
edges: [edge1, edge2, edge3],
};
calculateEdges(network);
expect(edge1.capacity).toBe(100);
expect(edge2.capacity).toBe(0);
expect(edge3.capacity).toBe(100);
});
/**
*
* Producer(100green) --- Connection --- Consumer(150green)
* |
* Producer(50)
*/
it("double producer green prefered grey fillup", () => {
const producer: Node = { ...defaultNode, production: 100, isGreenProduction: true };
const producer2: Node = { ...defaultNode, production: 50 };
const consumer: Node = { ...defaultNode, consumption: 150, requiresGreenConsumption: true };
const connection: Node = { ...defaultNode, type: "connection" };
const edge1: Edge = { ...defaultEdge, nodes: [producer, connection] };
const edge2: Edge = { ...defaultEdge, nodes: [producer2, connection] };
const edge3: Edge = { ...defaultEdge, nodes: [connection, consumer] };
const network: Network = {
nodes: [producer, producer2, consumer, connection],
edges: [edge1, edge2, edge3],
};
calculateEdges(network);
expect(edge1.capacity).toBe(100);
expect(edge2.capacity).toBe(50);
expect(edge3.capacity).toBe(150);
});
/**
*
* Consumer(50)
* |
* Producer(100green) --- Connection --- Connection --- Consumer(150green)
* | |
* Connection ---
* |
* Producer(100)
*/
it("simple circle", () => {
const producer: Node = { ...defaultNode, production: 100, isGreenProduction: true };
const producer2: Node = { ...defaultNode, production: 100 };
const consumer: Node = { ...defaultNode, consumption: 150, requiresGreenConsumption: true };
const consumer2: Node = { ...defaultNode, consumption: 50 };
const connection: Node = { ...defaultNode, type: "connection" };
const connection2: Node = { ...defaultNode, type: "connection" };
const connection3: Node = { ...defaultNode, type: "connection" };
const edge1: Edge = { ...defaultEdge, nodes: [producer, connection] };
const edge2: Edge = { ...defaultEdge, nodes: [producer2, connection2] };
const edge3: Edge = { ...defaultEdge, nodes: [connection, connection2] };
const edge4: Edge = { ...defaultEdge, nodes: [connection, consumer2] };
const edge5: Edge = { ...defaultEdge, nodes: [connection, connection3] };
const edge6: Edge = { ...defaultEdge, nodes: [connection2, connection3] };
const edge7: Edge = { ...defaultEdge, nodes: [connection3, consumer] };
const network: Network = {
nodes: [producer, producer2, consumer, consumer2, connection, connection2, connection3],
edges: [edge1, edge2, edge3, edge4, edge5, edge6, edge7],
};
calculateEdges(network);
expect(edge1.capacity).toBe(100);
expect(edge2.capacity).toBe(50);
expect(edge3.capacity).toBe(50);
expect(edge4.capacity).toBe(50);
expect(edge5.capacity).toBe(100);
expect(edge6.capacity).toBe(50);
expect(edge7.capacity).toBe(150);
});
});
type CalcNode = {
giving: number;
requesting: number;
realNode: Node;
};
export function calculateEdges(network: Network): void {
const calcNodes: CalcNode[] = network.nodes.map((node) => {
const calcNode: CalcNode = { giving: 0, requesting: 0, realNode: node };
if (node.type === "connection") {
network.edges
.filter((edge) => edge.nodes[0] === node || edge.nodes[1] === node)
.forEach((edge) => {
// TODO add
if (edge.nodes[0] === node) {
calcNode.giving = Math.max(calcNode.giving, edge.nodes[1].production);
calcNode.requesting = Math.max(
calcNode.requesting,
edge.nodes[1].consumption,
);
} else if (edge.nodes[1] === node) {
calcNode.giving = Math.max(calcNode.giving, edge.nodes[0].production);
calcNode.requesting = Math.max(
calcNode.requesting,
edge.nodes[0].consumption,
);
}
});
} else {
calcNode.giving = node.production;
calcNode.requesting = node.consumption;
}
return calcNode;
});
calcNodes.forEach((node) => console.log(node));
network.edges.forEach((edge) => {
const node1 = calcNodes.find((calcNode) => calcNode.realNode === edge.nodes[0])!;
const node2 = calcNodes.find((calcNode) => calcNode.realNode === edge.nodes[1])!;
if (node1.requesting == 0) {
edge.capacity = Math.max(node1.giving, node2.giving, node2.requesting);
}
});
}
Any help is appreciated, since all my implementations only solve the first few test cases. The problem is networks with connection-nodes, since these have production=0 and consumption=0. Thank you in advance!
This is the "maximum flow through a graph" problem.
Find a path from a source to a sink, using the Dijkstra
algorithm
Find minimum capacity ( F ) of any link on the path,
or the demand of the sink if less than minimum capacity
Reduce capacity of all links on path by F
Reduce demand of sink by F
Remove any link that now has zero capacity
Repeat above steps until no more paths can be found.
You can find a C++ implementation of this at https://github.com/JamesBremner/PathFinder/wiki/Flows which might be helpful. I know nothing about typescript.