CODEWITHSUNDEEP
c#data-structuresgraphsplitdijkstra
Avril Fenech
Avril Fenech

Reputation: 13

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

I am trying to read a graph from a text file and parse it to be able to extract the vertices, edges and weight to use for a Dijkstra's Algorithm implementation.

The text file contains the following structure:

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"];
}

Finding it difficult to use the .split since the data is not seperated by the same delimeter.

I need to extract for example from the first line: a needs to be set as from. b needs to be set as to and 5 needs to set as weight

Any ideas on how I can approach this please?

Upvotes: 1

Views: 503

Answers (1)

Anonta
Anonta

Reputation: 2540

We can extract the values easily using this regular expression:

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

Full Code: 

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

Edit: Here's how we can get the different values from each match object

Define an Edge class just for holding data 

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

Get the group values from each match. The group number is determined by how many opening parenthesis there are on the left side of the group.

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();

Upvotes: 2

Related Questions