I working on a simple water pipeline path modeling and listing each path. In my model, water flows in a single direction always; from root to leaves. No loops. I would like to create a table of nodes for each path on the tree. My proposed data structure is as follows:
//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; }
}
- Nodes are created in runtime by the user. User assigns Node Type for each node if the node is root or leaf.
- Segments are created in runtime by the user and user assigns End and Start Nodes for each segment.
- Paths should be created automatically when min required data is entered by the user. Min requirement for a path: the root node and an leaf node is assigned in the list of segments and the user correctly assigned start and end nodes for each segment (correctly means: for traceability, end node of the first segment should be equal to the start node of the next segment, this should go until reaching the leaf or vice versa).
- What is the required algorithm or code to achieve this?
Edit 10-May-2022
I use the following code to add "PathNode"s. No issues adding the start and end nodes for a path since filtering these 2 nodes are easy.
I am stuck on writing a loop to add the other remaining nodes. The only relation between segments is lastSegment.StartNodeId==segmentBeforeTheLastSegment.EndNodeId. This is ok, but what about the other following segments? how to define a general statement to get all related segments of the path and accordingly their nodes? What condition or loop to use?
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?
}
}
}
}
CodePudding user response：
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?
This can be done using the Dijkstra algorithm ( look it up )
As a practical method:
Place the nodes and the links into the graph class of your favorite graph theory library, then use the library's Dijkstra method to find the path from the source to the leaf. The method will return a list of all the nodes on the path, from which you can get all other segments of the path
I am not proficient in C#, but here is how I would do it in C using the graph theory library PathFinder for Dijkstra ( 