Вы сказали, что есть два предположения:
- Узлы R1 и R2 могут быть четко распознаны как корневые узлы из-за типа узла на них. (Концентрические круги с красным внешним кругом).
- Доступен также список всех ребер, напрямую соединенных с узлом, например, узел N8 будет иметь сегменты
N8-L7, N8-R2, N8-N9, N8-N7.
Я собираюсь предположить, что есть также сегменты L7-N8, R2-N8, N9-N8, N7-N8. Если нет, вы можете построить их достаточно легко из существующих сегментов, которые вы упомянули.
Вы также сказали, отвечая на мои вопросы, что у корней нет родителей, и у каждого узла есть только один родитель. Это делает это намного проще.
Сначала создайте словарь с именами узлов в качестве ключей, а значением является список узлов, к которым он подключается. Это будет Dictionary<string, List<string>>. В приведенном выше примере вы получите:
key value
N8 L7, R2, N9, N7
L7 N8
R2 N8
N9 N8
N7 N8
В приведенном выше списке только N8 заполнен полностью. Ваш словарь будет содержать все соединения для всех узлов.
Чтобы построить это:
var segmentDict = new Dictionary<string, List<string>>();
foreach (var segment in SegmentList)
{
List<string> nodeConnections;
if (!segmentDict.TryGetValue(segment.From, out nodeConnections))
{
// This node is not in dictionary. Create it.
nodeConnections = new List<string>();
segmentDict.Add(segment.From, nodeConnections);
}
nodeConnections.Add(segment.To);
}
Теперь мы создадим новый Dictionary<string, List<string>>, который изначально пуст. Это будет последнее дерево, в котором есть только дочерние элементы для каждого узла.
Поскольку вы знаете, что у корневых узлов нет родителей, и что у узла не более одного родителя, вы можете начать с корней и начать устанавливать соединения. Сканируйте словарь и для каждого корневого узла добавьте его в очередь и создайте запись в finalTree с пустым дочерним списком:
var finalTree = new Dictionary<string, List<string>>();
var nodeQueue = new Queue<string>();
foreach (var nodeName in segmentDict.Keys)
{
if (nodeName.StartsWith("R")) // if it's a root node
{
finalTree.Add(nodeName, new List<string>()); // add tree node
nodeQueue.Enqueue(nodeName); // and add node to queue
}
}
Теперь приступим к обработке очереди. Для каждого имени узла, которое вы извлекаете из очереди:
- Создайте запись в
finalTree для этого узла.
- Получить список соединений для этого узла из
segmentDict.
- Для каждого из соединений узла, если в
finalTree нет записи для этого узла, добавьте узел в очередь и добавьте его в список соединений для этого узла в finalTree.
Повторяйте это, пока очередь не станет пустой.
Код выглядит примерно так:
while (nodeQueue.Count > 0)
{
var fromNode = nodeQueue.Dequeue();
var nodeChildren = finalTree[fromNode];
foreach (var toNode in segmentDict[fromNode])
{
if (finalTree.ContainsKey(toNode))
{
// This node has already been seen as a child node.
// So this connection is from child to parent. Ignore it.
break;
}
nodeChildren.Add(toNode); // update children for this node
finalTree.Add(toNode, new List<string>()); // create tree entry for child node
nodeQueue.Enqueue(toNode); // add child to queue
}
}
Что я сделал здесь, так это проследил за деревом от корней до листьев, поэтому, когда я впервые сталкиваюсь с узлом, я знаю, что это ссылка «родитель-потомок», а не ссылка «потомок-родитель». Таким образом, все дочерние родительские ссылки удаляются.
Затем вы можете получить свое дерево, пройдя через finalTree и выполнив первый глубинный обход для каждого корневого узла:
foreach (var kvp in finalTree)
{
if (kvp.Key.StartsWith("R"))
{
PrintTree(kvp.Key, kvp.Value);
}
}
void PrintTree(string nodeName, List<string> children)
{
Console.WriteLine("node {1} has children {2}.", nodeName, string.Join(",", children);
foreach (var child in children)
{
PrintTree(child, finalTree[child]);
}
}
Вы, конечно, захотите наладить вывод, но это показывает, как обходить деревья от корней.