typescript 网络边缘负载计算

xfyts7mz  于 2023-06-07  发布在  TypeScript
关注(0)|答案(2)|浏览(150)

我试图计算（电网）网络的边缘负载，但被卡住了，无法找出正确的实现。
给定以下数据结构：

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。感谢您的评分

typescript

2条答案

按热度按时间
qpgpyjmq

qpgpyjmq1#

这就是“通过图的最大流”问题。

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.

你可以在https://github.com/JamesBremner/PathFinder/wiki/Flows找到一个C++实现，这可能会有所帮助。我对打字一窍不通。

赞(0）分享  回复(0）举报  2023-06-07
e0bqpujr

e0bqpujr2#

对于任何人遇到这个。我找到了一个很好的图书馆，做实际的重型lifiting（福特富尔克森算法），并决定使用它。以下是我的工作（到目前为止）实现：

import type { Network } from "$lib/files/api";
import JsGraphs from "js-graph-algorithms";

export function calculateEdges(network: Network): Network {
    // add synthetic single source and sink to graph
    const source = network.nodes.length;
    const sink = network.nodes.length + 1;

    const graph: JsGraphs.FlowNetwork = new JsGraphs.FlowNetwork(network.nodes.length + 2); // 2 synthetic nodes

    // transform network into JsGraph
    const syntheticProductionEdges: Record<string, JsGraphs.FlowEdge> = {};
    const syntheticConsumptionEdges: Record<string, JsGraphs.FlowEdge> = {};
    network.nodes.forEach((node, i) => {
        graph.node(i).label = node.id;

        // connect synthetic source to all producers
        if (node.targetProduction > 0) {
            const productionEdge: JsGraphs.FlowEdge = new JsGraphs.FlowEdge(
                source,
                i,
                node.targetProduction,
            );
            productionEdge.label = `SourceEdge-${node.id}`;

            graph.addEdge(productionEdge);
            syntheticProductionEdges[node.id] = productionEdge;
        }

        // connect all consumers to synthetic sink
        if (node.targetConsumption > 0) {
            const consumptionEdge: JsGraphs.FlowEdge = new JsGraphs.FlowEdge(
                i,
                sink,
                node.targetConsumption,
            );
            consumptionEdge.label = `SinkEdge-${node.id}`;

            graph.addEdge(consumptionEdge);
            syntheticConsumptionEdges[node.id] = consumptionEdge;
        }
    });

    const flowEdges: [JsGraphs.FlowEdge, JsGraphs.FlowEdge][] = [];
    network.edges.forEach((edge) => {
        const node1Index = network.nodes.indexOf(edge.nodes[0]);
        const node2Index = network.nodes.indexOf(edge.nodes[1]);

        // edges between nodes have a bi-directional flow of maxCapacity
        const flowEdge: JsGraphs.FlowEdge = new JsGraphs.FlowEdge(
            node1Index,
            node2Index,
            edge.maxCapacity,
        );
        flowEdge.label = `${edge.nodes[0].id}-${edge.nodes[1].id}`;

        const reverseFlowEdge: JsGraphs.FlowEdge = new JsGraphs.FlowEdge(
            node2Index,
            node1Index,
            edge.maxCapacity,
        );
        flowEdge.label = `${edge.nodes[1].id}-${edge.nodes[0].id}`;

        graph.addEdge(flowEdge);
        graph.addEdge(reverseFlowEdge);

        flowEdges.push([flowEdge, reverseFlowEdge]);
    });

    // create new FordFulkerson and grab flow values from FlowEdge-ref
    new JsGraphs.FordFulkerson(graph, source, sink);

    return {
        nodes: network.nodes.map((node, i) => ({
            ...node,
            consumption: syntheticConsumptionEdges[node.id]
                ? syntheticConsumptionEdges[node.id].residualCapacityTo(i)
                : 0,
            production: syntheticProductionEdges[node.id]
                ? syntheticProductionEdges[node.id].residualCapacityTo(source)
                : 0,
        })),
        edges: network.edges.map((edge, i) => ({
            ...edge,
            capacity: Math.abs(
                flowEdges[i][0].residualCapacityTo(network.nodes.indexOf(edge.nodes[0])) -
                    flowEdges[i][1].residualCapacityTo(network.nodes.indexOf(edge.nodes[1])),
            ),
        })),
    };
}
赞(0）分享  回复(0）举报  2023-06-07
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com