从 Dijkstra 算法 C# 的点符号输入解析图形

Question

我正在尝试从文本文件中读取图形并对其进行解析，以便能够提取用于 Dijkstra 算法实现的顶点、边和权重。

文本文件包含以下结构：

graph {
    a -- b[label="5",weight="5"];
    a -- c[label="1",weight="1"];
    c -- b[label="3",weight="3"];
    c -- e[label="1",weight="1"];
    e -- b[label="1",weight="1"];
}

发现很难使用 .split，因为数据不是由相同的分隔符分隔的。

我需要从第一行中提取例如： a 需要设置为 from。 b 需要设置为并且 5 需要设置为 weight

请问我如何解决这个问题？

Answer 1

我们可以使用这个正则表达式轻松提取值：

(\w+) -- (\w+)\[label="(\w+)",weight="([0-9]*\.?[0-9]+)"\];

完整代码：

string rawData = File.ReadAllText("H:\data.txt");
string pattern = "(\w+) -- (\w+)\[label=\"(\w+)\",weight=\"([0-9]*\.?[0-9]+)\"\];";
var matches = Regex.Matches(rawData, pattern);

编辑： 以下是我们如何从每个匹配对象中获取不同的值

定义一个 Edge class 只是为了保存数据

class Edge {
    public string NodeALabel;
    public string NodeBLabel;
    public double Weight;
    public string EdgeLabel;
}

从每场比赛中获取组值。分组号由分组左侧有多少个左括号决定。

var edgeList = matches.Select(match => new Edge() {
    NodeALabel= match.Groups[1].Value,
    NodeBLabel= match.Groups[2].Value,
    Weight= double.Parse(match.Groups[4].Value),
    EdgeLabel= match.Groups[3].Value
}).ToList();

从 Dijkstra 算法 C# 的点符号输入解析图形

Parsing a graph from a dot notation input for Dijkstra's Algorithm C#

c#

split

graph

dijkstra

data-structures