从节点列表创建树来表示管网

Question

我正在研究一个简单的输水管道路径建模并列出每条路径。在我的模型中，水总是单向流动；从根到叶。没有循环。我想为树上的每条路径创建一个 table 节点。我提出的数据结构如下：

 //Segment class is representing each piece of pipe between the start node and end node 
public class Segment
{
    public Guid Id { get; set; }
    public Guid? StartNodeId { get; set; }
    public virtual Node StartNode { get; set; }
    public Guid? EndNodeId { get; set; }
    public virtual Node EndNode { get; set; }
    public int SegmentNo { get; set; }
    public double PressureLoss { get; set; }
}
public class Node
{
    public Guid Id { get; set; }
    public int NodeNo { get; set; }
    public NodeType NodeType { get; set; }
    [InverseProperty("StartNode")]
    public virtual ICollection<Segment> StartNodesInSegments { get; set; }
    [InverseProperty("EndNode")]
    public virtual ICollection<Segment> EndNodesInSegments { get; set; }
    [InverseProperty("PathStartNode")]
    public virtual ICollection<Path> StartNodesInPath { get; set; }
    [InverseProperty("PathEndNode")]
    public virtual ICollection<Path> EndNodesInPath { get; set; }
}
public enum NodeType
{
    Source, //source node is the **root** node
    Discharge //discharge nodes are the **leaf** nodes
}
//Path class is to list paths with corresponding start node and end node.
public class Path
{
    public Guid Id { get; set; }
    public int PathNo { get; set; }
    public Guid? PathStartNodeId { get; set; }
    public virtual Node PathStartNode { get; set; }
    public Guid? PathEndNodeId { get; set; }
    public virtual Node PathEndNode { get; set; }
    public double PathLength { get; set; }
    public virtual ICollection<PathNode> PathNodes { get; set; }
}

//PathNode class is to list nodes of the related path and the corresponding segment no.
public class PathNode
{
    public Guid Id { get; set; }
    public Guid PathId { get; set; }
    public virtual Path Path { get; set; }
    public Guid SegmentId { get; set; }
    public virtual Segment Segment { get; set; }
    public Guid NodeId { get; set; }
    public virtual Node Node { get; set; }
}

节点由用户在运行时创建。如果节点是根节点或叶节点，则用户为每个节点分配节点类型。
段由用户在运行时创建，用户为每个段分配结束节点和开始节点。
当用户输入所需的最少数据时，应自动创建路径。路径的最低要求：在段列表中分配了根节点和叶节点，并且用户为每个段正确分配了开始和结束节点（正确的意思是：为了可追溯性，第一段的结束节点应等于下一段的起始节点，这应该一直持续到到达叶子，反之亦然）。
实现此目标所需的算法或代码是什么？

编辑 2022 年 5 月 10 日

我使用以下代码添加“PathNode”。为路径添加开始和结束节点没有问题，因为过滤这 2 个节点很容易。我坚持写一个循环来添加其他剩余的节点。段之间的唯一关系是 lastSegment.StartNodeId==segmentBeforeTheLastSegment.EndNodeId。这没问题，但接下来的其他部分呢？如何定义一个通用语句来获取路径的所有相关段及其节点？使用什么条件或循环？

private void ListPathNodes()
{
    foreach (Path path in worker.PathService.GetList(null)//no filter, get all paths)
    {
        //get all segments
        IEnumerable<Segment> SegmentsOfPathList 
             = worker.SegmentService.GetList(null);
        foreach (Segment segment in SegmentsOfPathList)
        {
            if (segment.StartNode.NodeType == NodeType.Source)
            {
                // if "segment" has the source node 
                // then add its start node 
                // into the PathNode list of the path. 
                worker.PathNodeService.Add(new PathNode
                {
                    Id = Guid.NewGuid(),
                    SegmentId = segment.Id,
                    PathId = path.Id,
                    NodeId = (Guid)segment.StartNodeId,
                });
                //do this also for its end node.
                worker.PathNodeService.Add(new PathNode
                {
                    Id = Guid.NewGuid(),
                    SegmentId = segment.Id,
                    PathId = path.Id,
                    NodeId = (Guid)segment.EndNodeId,
                });
            }
            if ((Guid)segment.EndNodeId == 
                 (Guid)path.PathEndNodeId)
            {
                //if "segment" has the leaf node of the path
                // then add its end node 
                // to the PathNode list of the path.
                worker.PathNodeService.Add(new PathNode
                {
                    Id = Guid.NewGuid(),
                    SegmentId = segment.Id,
                    PathId = path.Id,
                    NodeId = (Guid)segment.EndNodeId
                });
                //do this also for its start node.
                worker.PathNodeService.Add(new PathNode
                {
                    Id = Guid.NewGuid(),
                    SegmentId = segment.Id,
                    PathId = path.Id,
                    NodeId = (Guid)segment.StartNodeId,
                });

            }
            //Below this line does not work for all segments at once. 
            //I have included here the below code just to show
            // that I am unable to convert the following
            // to an algorithm to get "PathNode"s 
            // not only for 3 segments 
            // but for the whole list of segments. 
            if ((Guid)mainCalc.EndNodeId != (Guid)path.PathEndNodeId)
            {
                //get the last segment of the path to use its start node to find the parent segment of the last segment. 
                Segment segmentEnd = worker.SegmentService.Get(c.EndNodeId == (Guid)path.PathEndNodeId, c => c.EndNode, c => c.StartNode);
                //segmentN is one before the last. 
                Segment segmentN = worker.SegmentService.Get(c.EndNodeId == segmentEnd.StartNodeId, c => c.EndNode, c => c.StartNode);
                //segmentN1 is 2 before the last. 
                Segment segmentN1 = worker.SegmentService.Get(c.EndNodeId == segmentN.StartNodeId, c => c.EndNode, c => c.StartNode);

                //add start node of the above filtered segmentN into PathNode list of the path.
                worker.PathNodeService.Add(new PathNode
                {
                    Id = Guid.NewGuid(),
                    MainCalculationId = mcalcN.Id,
                    PathId = path.Id,
                    NodeId = (Guid)segmentN.StartNodeId
                });
                //do this also for its end node.
                worker.PathNodeService.Add(new PathNode
                {
                    Id = Guid.NewGuid(),
                    MainCalculationId = mcalcN.Id,
                    PathId = path.Id,
                    NodeId = (Guid)segmentN.EndNodeId
                });
                //the above can be applied for segmentN1 and then segmentN2 etc,
                // number of segments is a variable for different paths 
                // so how to get all other segments of the path?
            }
        }
    }
}

Answer 1

the above can be applied for segmentN1 and then segmentN2 etc, number of segments is a variable for different paths so how to get all other segments of the path?

这可以使用 Dijkstra 算法完成（查找）

作为实用方法：

将节点和链接放入您最喜欢的图论库的图 class 中，然后使用该库的 Dijkstra 方法找到从源到叶子的路径。该方法将 return 路径上所有节点的列表，您可以从中获取所有其他节点路径段

我不精通 C#，但这是我在 C++ 中如何使用 Dijkstra 的图论库 PathFinder (https://github.com/JamesBremner/PathFinder)

void Test()
{
    // Construct a pipe tree with two limbs
    thePlumbing.add(
        cNode::eType::source, "source1",
        cNode::eType::none, "n1");
    thePlumbing.add(
        cNode::eType::none, "n1",
        cNode::eType::none, "n2");
    thePlumbing.add(
        cNode::eType::none, "n2",
        cNode::eType::none, "n3");
    thePlumbing.add(
        cNode::eType::none, "n3",
        cNode::eType::discharge, "sink1");
    thePlumbing.add(
        cNode::eType::none, "n2",
        cNode::eType::none, "n4");
    thePlumbing.add(
        cNode::eType::none, "n4",
        cNode::eType::discharge, "sink2");

    // initialize graph with pipe tree
    PF.directed();
    for (auto &p : thePlumbing)
        PF.addLink(
            p.start()->name(),
            p.end()->name());

    // loop over every possible source, sink pair
    for (auto &sd : thePlumbing.SourceDischargePairs())
    {
        // find path from source to sink
        PF.start(PF.find(sd.first));
        PF.end(PF.find(sd.second));
        PF.path();

        // check if path exists
        if ( ! PF.getPath().size())
            continue;

        // print segments in path
        PrintPathPipes();
    }
}

这段代码的输出是

Pipe from source1 to n1
Pipe from n1 to n2
Pipe from n2 to n3
Pipe from n3 to sink1

Pipe from source1 to n1
Pipe from n1 to n2
Pipe from n2 to n4
Pipe from n4 to sink2

可在 https://github.com/JamesBremner/TimOPipes

找到完整应用程序的代码

我添加了一个功能来报告无法连接的源和汇。您还需要其他功能吗？

提供一个真实问题的例子怎么样？请使用此输入文件格式

从节点列表创建树来表示管网

Creating a tree from list of nodes to represent a pipe network

algorithm

tree

nodes

graph-theory