Read text file and create multidimensional array from it

Question

I want to read a txt file and create a multidimensional int array in the following form:

var graph = new[,]
    {
        // 0   1   2   3   4   5   6   7   8   9  10  11...n
        { 0,  0,  0,  0,  0,  0, 10,  0, 12,  0,  0,  0 }, // 0
        { 0,  0,  0,  0, 20,  0,  0, 26,  0,  5,  0,  6 }, // 1
        { 0,  0,  0,  0,  0,  0,  0, 15, 14,  0,  0,  9 }, // 2
        { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  7,  0 }, // 3
        { 0, 20,  0,  0,  0,  5, 17,  0,  0,  0,  0, 11 }, // 4
        { 0,  0,  0,  0,  5,  0,  6,  0,  3,  0,  0, 33 }, // 5
        {10,  0,  0,  0, 17,  6,  0,  0,  0,  0,  0,  0 }, // 6
        { 0, 26, 15,  0,  0,  0,  0,  0,  0,  3,  0, 20 }, // 7
        {12,  0, 14,  0,  0,  3,  0,  0,  0,  0,  0,  0 }, // 8
        { 0,  5,  0,  0,  0,  0,  0,  3,  0,  0,  0,  0 }, // 9
        { 0,  0,  0,  7,  0,  0,  0,  0,  0,  0,  0,  0 }, // 10
        { 0,  6,  9,  0, 11, 33,  0, 20,  0,  0,  0,  0 }, // 11..n
  };

this should represent nodes in a graph and there distances between each other. my txt file looks like this (picture and graph values doesn't match):

the first value is the start node, the second value is the end node and the third value should be the distance. so the index of the rows in the table are the existing start nodes and the values in the fields should be 0, if there is no direct connection between the nodes or it should have the distance from the txt file if a direct connection exists. the index of the columns should be all end nodes.

i started like this:

 using (var reader = new StreamReader(@"USA-road-d.CAL.gr"))
    {
        while (!reader.EndOfStream)
        {
            var lineCount = File.ReadLines(@"USA-road-d.CAL.gr").Count();
            var pre_graph = new int[lineCount];

            //initialize array with 0s
            Array.Clear(pre_graph, 0, pre_graph.Length);

            string new_line;

            while ((new_line = reader.ReadLine()) != null)
            {
                var values = new_line.Split(null);
                pre_graph[int.Parse(values[2])] = int.Parse(values[3]);
            }
        }
    }

var pre_graph = new int[lineCount]; is wrong because of multiple edges. i only want the count of distinct start nodes as array length.

i am not sure how to get this. can anybody help?

in the end i want to use this graph for an implementation of the dijkstra algorithm:

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

public static class DijkstraWithoutQueue
{
    public static List<int> DijkstraAlgorithm(int[,] graph, int sourceNode, int destinationNode)
    {
        var n = graph.GetLength(0);

        var distance = new int[n];
        for (int i = 0; i < n; i++)
        {
            distance[i] = int.MaxValue;
        }

        distance[sourceNode] = 0;

        var used = new bool[n];
        var previous = new int?[n];

        while (true)
        {
            var minDistance = int.MaxValue;
            var minNode = 0;
            for (int i = 0; i < n; i++)
            {
                if (!used[i] && minDistance > distance[i])
                {
                    minDistance = distance[i];
                    minNode = i;
                }
            }

            if (minDistance == int.MaxValue)
            {
                break;
            }

            used[minNode] = true;

            for (int i = 0; i < n; i++)
            {
                if (graph[minNode, i] > 0)
                {
                    var shortestToMinNode = distance[minNode];
                    var distanceToNextNode = graph[minNode, i];

                    var totalDistance = shortestToMinNode + distanceToNextNode;

                    if (totalDistance < distance[i])
                    {
                        distance[i] = totalDistance;
                        previous[i] = minNode;
                    }
                }
            }
        }

        if (distance[destinationNode] == int.MaxValue)
        {
            return null;
        }

        var path = new LinkedList<int>();
        int? currentNode = destinationNode;
        while (currentNode != null)
        {
            path.AddFirst(currentNode.Value);
            currentNode = previous[currentNode.Value];
        }

        return path.ToList();
    }

    public static void Main()
    {


        var graph = new[,]
        {
            // 0   1   2   3   4   5   6   7   8   9  10  11
            { 0,  0,  0,  0,  0,  0, 10,  0, 12,  0,  0,  0 }, // 0
            { 0,  0,  0,  0, 20,  0,  0, 26,  0,  5,  0,  6 }, // 1
            { 0,  0,  0,  0,  0,  0,  0, 15, 14,  0,  0,  9 }, // 2
            { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  7,  0 }, // 3
            { 0, 20,  0,  0,  0,  5, 17,  0,  0,  0,  0, 11 }, // 4
            { 0,  0,  0,  0,  5,  0,  6,  0,  3,  0,  0, 33 }, // 5
            {10,  0,  0,  0, 17,  6,  0,  0,  0,  0,  0,  0 }, // 6
            { 0, 26, 15,  0,  0,  0,  0,  0,  0,  3,  0, 20 }, // 7
            {12,  0, 14,  0,  0,  3,  0,  0,  0,  0,  0,  0 }, // 8
            { 0,  5,  0,  0,  0,  0,  0,  3,  0,  0,  0,  0 }, // 9
            { 0,  0,  0,  7,  0,  0,  0,  0,  0,  0,  0,  0 }, // 10
            { 0,  6,  9,  0, 11, 33,  0, 20,  0,  0,  0,  0 }, // 11
        };

        PrintPath(graph, 0, 2);
        PrintPath(graph, 0, 10);
        PrintPath(graph, 0, 11);
        PrintPath(graph, 0, 1);
    }

    public static void PrintPath(int[,] graph, int sourceNode, int destinationNode)
    {
        Console.Write(
            "Shortest path [{0} -> {1}]: ",
            sourceNode,
            destinationNode);

        var path = DijkstraWithoutQueue.DijkstraAlgorithm(graph, sourceNode, destinationNode);

        if (path == null)
        {
            Console.WriteLine("no path");
        }
        else
        {
            int pathLength = 0;
            for (int i = 0; i < path.Count - 1; i++)
            {
                pathLength += graph[path[i], path[i + 1]];
            }

            var formattedPath = string.Join("->", path);
            Console.WriteLine("{0} (length {1})", formattedPath, pathLength);
        }
    }
    }

Answer 1

I prepared a solution for you at GitHub,

It is not a good idea to go online with array for 1890815x1890815 matrix. It is about 28 601 450 Megabytes needed to represent such an array (1890815x1890815x4x2), or you heed a solution with 28 Petabytes of memory.

I suppose you will never be able to create solid matrix for USA road map, because, you will probably nedd about 1T of DDR memory (with optimizations) or 28 petabytes including zeroes, i prepared Visual Studio Solution for you (VS2019 Preview is required to open project):

• https://github.com/hack2root/read-matrix

It is a good news, also, you can create and use connectivity matrix (C# 8.0) to load data from file and create tree structure of nodes and edges in about just 5 secs, if forget about 28 Petabytes requirement.

5.6 secs to load all USA roads from archieve in memory, and verify structure

    static class Program
    {
        static async Task Main(string[] args)
        {
            using (var archive = ZipFile.OpenRead(args[0]))
            {
                var entry = archive.Entries.Where(_ => _.FullName.Equals("USA-road-d.CAL.gr", StringComparison.OrdinalIgnoreCase)).FirstOrDefault();
                if (entry != null)
                {
                    var stopwatch = new Stopwatch();
                    stopwatch.Start();
                    var data = new List<string>(Decompress(entry.Open()));
                    var graph = new Graph(data);
                    stopwatch.Watch();
                    Console.ReadLine();
                }
            }
        }

        public static IEnumerable<string> Decompress(Stream stream)
        {
            using (var reader = new StreamReader(stream, Encoding.ASCII))
            {
                string line;
                while ((line = reader.ReadLine()) != null)
                {
                    yield return line;
                }
            }
        }

        public class Edge
        {
            public Edge(Graph graph, Node v1, Node v2, int distance, bool isDirectional = false)
            {
                Graph = graph;
                V1 = v1;
                V2 = v2;
                Distance = distance;
                v1.AddEdge(this);
                if (!IsDirectional)
                    v2.AddEdge(this);
            }
            internal Graph Graph { get; }
            public Node V1 { get; }
            public Node V2 { get; }
            public int Distance { get; }
            public bool IsDirectional { get; }
        }

        public class Node
        {
            static int counter = 0;
            readonly List<Edge> _edges = new List<Edge>();
            public Node(Graph graph, int index)
            {
                Graph = graph;
                Index = index;
                Number = counter++;
            }
            internal Graph Graph { get; }
            public int Index { get; }
            public int Number { get; }
            public IEnumerable<Edge> Edges => _edges;
            public void AddEdge(Edge edge) => _edges.Add(edge);
        }

        public class Graph
        {
            Dictionary<int, Node> _nodes { get; } = new Dictionary<int, Node>();
            readonly Parameters _parameters;
            readonly List<Edge> _edges;
            readonly List<string> _comments;
            public IParameters Parameters => _parameters;
            public IEnumerable<Edge> Edges => _edges;
            public IEnumerable<string> Comments => _comments;
            public Node GetNode(int index) => _nodes.ContainsKey(index) ? _nodes[index] : (_nodes[index] = new Node(this, index));
            public Graph(IEnumerable<string> lines, bool isDirectional = false)
            {
                IEnumerable<string> parameters = new List<string>(lines.Where(_ => _[0] == 'p'));
                IEnumerable<string> edges = new List<string>(lines.Where(_ => _[0] == 'a'));
                IEnumerable<string> comments = new List<string>(lines.Where(_ => _[0] == 'c'));
                _parameters = 
                    parameters
                    .Select(_ => _.Split(' '))
                    .Select(_ => _[1] == "sp" ? new Parameters(int.Parse(_[2]), int.Parse(_[3])) : null).FirstOrDefault();
                _edges =
                    edges
                    .Select(_ => _.Split(' '))
                    .Select(_ => new Edge(this, GetNode(int.Parse(_[1])), GetNode(int.Parse(_[2])), int.Parse(_[3]), isDirectional))
                    .ToList();
                _comments =
                    comments
                    .Select(_ => _.Substring(1)).ToList();
                if (_parameters.Nodes != _nodes.Keys.Count)
                {
                    throw new Exception("invalid nodes count");
                }
                if (_parameters.Edges != _edges.Count)
                {
                    throw new Exception("invalid edges count");
                }
            }
        }

        public interface IParameters
        {
            int Nodes { get; }
            int Edges { get; }
        }
        public class Parameters: IParameters
        {
            public int Nodes { get; }
            public int Edges { get; }
            public Parameters(int nodes, int edges)
            {
                Nodes = nodes;
                Edges = edges;
            }
        }

    }

    public static class StopwatchExtensions
    {
        public static void Watch(this Stopwatch stopwatch, string message = "",
        [CallerMemberName] string memberName = "",
        [CallerFilePath] string sourceFilePath = "",
        [CallerLineNumber] int sourceLineNumber = 0) =>
        Console.WriteLine(
            $"{stopwatch.Elapsed} " +
            $"{message} " +
            $"{memberName} " +
            $"{sourceFilePath}:{sourceLineNumber}");
    }