我试图计算(电网)网络的边缘负载,但被卡住了,无法找出正确的实现。
给定以下数据结构:
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;
}
和一些测试用例(应该是边缘的正确值):
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);
}
});
}
任何帮助都是值得赞赏的,因为我的所有实现都只解决了前几个测试用例。问题是具有连接节点的网络,因为这些网络的生产=0,消费=0。感谢您的评分
2条答案
按热度按时间qpgpyjmq1#
这就是“通过图的最大流”问题。
你可以在https://github.com/JamesBremner/PathFinder/wiki/Flows找到一个C++实现,这可能会有所帮助。我对打字一窍不通。
e0bqpujr2#
对于任何人遇到这个。我找到了一个很好的图书馆,做实际的重型lifiting(福特富尔克森算法),并决定使用它。以下是我的工作(到目前为止)实现: