'Get list of all possible Paths with a start node and many end nodes C#
I am working on finding/listing critical path and alternate paths of a road navigation data in a C# winforms app. This is the first time I work on a navigation / road project so any type of advise including my data structure will be appreciated. Here is the data structure (I have modified the original data to make it more simple):
public class Path
{
public Guid Id { get; set; }
public Guid TripId { get; set; }
public virtual Trip Trip { 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; }
}
public class Node
{
public Guid Id { get; set; }
public Guid TripId { get; set; }
public virtual Trip Trip { get; set; }
public int NodeNo { get; set; }
public NodeType NodeType { get; set; }
public double Elevation { get; set; }
[InverseProperty("StartNode")]
public virtual ICollection<MainCalculation> StartNodesInCalculation { get; set; }
[InverseProperty("EndNode")]
public virtual ICollection<MainCalculation> EndNodesInCalculation { get; set; }
[InverseProperty("PathStartNode")]
public virtual ICollection<Path> StartNodesInPath { get; set; }
[InverseProperty("PathEndNode")]
public virtual ICollection<Path> EndNodesInPath { get; set; }
}
public class MainCalculation
{
public Guid Id { get; set; }
public Guid TripId { get; set; }
public virtual Trip Trip { 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 SectionNo { get; set; }
public double Length { get; set; }
}
public class Trip
{
public Guid Id { get; set; }
public string TripTagNo { get; set; }
public double MinTripLength { get; set; }
public virtual ICollection<MainCalculation> MainCalculations { get; set; }
public virtual ICollection<Node> Nodes { get; set; }
public virtual ICollection<Path> Paths { get; set; }
}
Basically, the objective is to Get list of Nodes of each Path by matching end node of a section with start node of the next section.
- A node is representing an intersection, a start point or an end point. Start point and end point cannot be an intersection.
- Sections (MainCalculation) are created by the user.
- A section is a piece of road between a user selected start node and an end node. Each path consists of one or many sections.
- A path is not defined by user in the app. App must find it by using links between start and end nodes of sections.
- The user also creates the nodes and selects the end node and start node for each section.
- Each path has a PathEndNode and PathStartNode.
- PathStartNode must be a "Source" type.
- Each path is separated based on the end node, this means each path has only 1 end node.
- So within a path, start node of the last section is equal to the end node of the previous section. Last section is the section having the pathEndNode as its end node.
Here is the method I am working on to list the nodes:
private void ListPathNodes()
{
//for each path list
foreach (Path path in worker.PathService.GetList(c => c.TripId == selectedTrip.Id))
{
IEnumerable<MainCalculation> SectionsOfPathList = worker.MainCalculationService.GetList(c => c.TripId == selectedTrip.Id, c => c.Trip);
foreach (MainCalculation mainCalc in SectionsOfPathList)
{
if (mainCalc.StartNode.NodeType == NodeType.Source)
{
worker.PathNodeService.Add(new PathNode
{
Id = Guid.NewGuid(),
MainCalculationId = mainCalc.Id,
PathId = path.Id,
NodeId = (Guid)mainCalc.StartNodeId,
});
worker.PathNodeService.Add(new PathNode
{
Id = Guid.NewGuid(),
MainCalculationId = mainCalc.Id,
PathId = path.Id,
NodeId = (Guid)mainCalc.EndNodeId,
});
}
if ((Guid)mainCalc.EndNodeId == (Guid)path.PathEndNodeId)
{
worker.PathNodeService.Add(new PathNode
{
Id = Guid.NewGuid(),
MainCalculationId = mainCalc.Id,
PathId = path.Id,
NodeId = (Guid)mainCalc.StartNodeId,
});
worker.PathNodeService.Add(new PathNode
{
Id = Guid.NewGuid(),
MainCalculationId = mainCalc.Id,
PathId = path.Id,
NodeId = (Guid)mainCalc.EndNodeId
});
}
//Below this line does not work. I have included here the below code just to show that I am unable to convert the following to an algorithm to apply the code not for 3 nodes only but to the whole list of nodes.
if ((Guid)mainCalc.EndNodeId != (Guid)path.PathEndNodeId)
{
MainCalculation mcalcEnd = worker.MainCalculationService.Get(c => c.TripId == selectedTrip.Id && c.EndNodeId == (Guid)path.PathEndNodeId, c => c.EndNode, c => c.StartNode);
MainCalculation mcalcN = worker.MainCalculationService.Get(c => c.TripId == selectedTrip.Id && c.EndNodeId == mcalcEnd.StartNodeId, c => c.EndNode, c => c.StartNode);
MainCalculation mcalcN1 = worker.MainCalculationService.Get(c => c.TripId == selectedTrip.Id && c.EndNodeId == mcalcN.StartNodeId, c => c.EndNode, c => c.StartNode);
LinkedListNode<>
worker.PathNodeService.Add(new PathNode
{
Id = Guid.NewGuid(),
MainCalculationId = mcalcN.Id,
PathId = path.Id,
NodeId = (Guid)mcalcN.StartNodeId
});
worker.PathNodeService.Add(new PathNode
{
Id = Guid.NewGuid(),
MainCalculationId = mcalcN.Id,
PathId = path.Id,
NodeId = (Guid)mcalcN.EndNodeId
});
//
//
}
}
}
}
Please note that this method is incomplete and does not work. I am not able to create an algorithm to list the nodes for each path. End node of a section should be equal to start node of the following section in a path. Please advise.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|