Как сделать список смежности из ОГРОМНОГО txt файла? - PullRequest
Новая
       31

Как сделать список смежности из ОГРОМНОГО txt файла?

0 голосов
/ 06 мая 2020

У меня есть ОГРОМНЫЙ файл, содержащий ребра ориентированного графа, и мне нужно составить список смежности для вычисления его сильно связанных компонентов с помощью алгоритма Косараджу . Проблема в том, что я не могу эффективно прочитать этот огромный файл или составить список смежности. Если входной файл небольшой (перечислено ~ 2-10000 ребер), мое решение работает отлично, но попытка обработать типичных огромных входных файлов (320000 вершин и более миллиона ребер) терпит неудачу из-за нехватки памяти и / или чрезвычайно низкая производительность.

Я пытался читать огромные файлы по частям вместо стандартного подхода readAsText(), но проблема с производительностью все еще остается. Я также подумал о каком-то «слепом способе» поиска SCC графа, который мог бы быть основан на списке ребер и работать «по частям» вместо того, чтобы задействовать весь ОГРОМНЫЙ список вершин и ребер, но я не стал не удалось.

Был парень, который задавал похожий вопрос почти по той же проблеме. Однако предоставленное там решение оказалось бесполезным для меня, потому что мне нужно обработать файл, а не просто создать массив вершин. 

//reading a local txt file and getting the graph
function readTextFile()
{
    console.clear();
    var fileToLoad = document.getElementById("fileToLoad").files[0];
    var fileReader = new FileReader();
    fileReader.readAsArrayBuffer(fileToLoad);
    fileReader.onload = function() {
        let buffer = new Uint8Array(fileReader.result);//got the buffer
        const MAX_CHUNK_SIZE = 1000;//is it big or small enough?
        var chunk = "";
        var curByteCounter = 0;
        var edges = [];
        while(curByteCounter<buffer.length)
        {
            if(MAX_CHUNK_SIZE<buffer.length)
                chunk = new TextDecoder('utf-8').decode(buffer.slice(curByteCounter,curByteCounter+MAX_CHUNK_SIZE));
            else
                //if the file is small enough we read it in one piece
                chunk = new TextDecoder('utf-8').decode(buffer);
            var newEdges = chunk.split("\n");
            if(chunk[chunk.length-1]!="\n")//we accidentally got the part of another edge 
                newEdges.pop();//drop the last element which is a part of another edge 
            //add new edges to the array
            edges = edges.concat(newEdges);
            //modify the counter if it's not the end of a file 
            curByteCounter+=chunk.lastIndexOf("\n")+1;
        }

        //pop the end of file (since it always ends at '\n' we have an element of '' in the end of edges[] 
        edges.pop();
        var adjacencyInput = makeAdjacencyList(edges);
        //debug - show an adjacency line of the first vertex
        console.log(adjacencyInput[0]);
    }
};

//make an adjacency list from the sorted list of edges
function makeAdjacencyList(edges){
    var adjacencyList = []; j = -1;
    for(var i = 0; i<edges.length; i++)
    {
        var edge = edges[i].split(" ").map(Number);
        if(adjacencyList.length == 0||adjacencyList[j][0] != edge[0]){
            //adjacencyList is empty or it's an edge of the same vertex
            adjacencyList.push([edge[0],edge[1]]);
            j++;
        }
        else
            //simply add a new edge to the current line
            adjacencyList[j].push(edge[1]);
    }
            
return adjacencyList;
}
<html>
<head>
	<title></title>
</head>
<body>
	<input type="file" id="fileToLoad">
	<button onclick="readTextFile()">Proceed!</button>
	<script src="js/SCC.js"></script>
</body>
</html>
...