CODEWITHSUNDEEP
javagraphadjacency-list
Kolka Tankari
Kolka Tankari

Reputation: 49

Converting Edgelist to Adjacency List

I have an object that shows me the connection between the indexes and that has variables index1,index2. Based on the connection of the indexes I would like to create a tree, that would always start from 0.

In this example the 0 is connected with 2 and 5 so they would be added to the tree first, then continuing from the lowest, I would need to find what numbers are connected to 2, which in this case are 6 and 7, etc..

{index1=0, index2=2}
{index1=3, index2=4}
{index1=1, index2=4}
{index1=0, index2=5}
{index1=2, index2=6}
{index1=1, index2=5}
{index1=2, index2=7}


               0
          2       5
       6    7       1
                      4

It seems like what I need is to convert it to Adjacency list.

As a final result I need to preorder traverse through the tree or all of the nodes and get a result, which in this case would be:

0 - 2 - 6 - 7 - 5 - 1 - 4

What should I use to get the desired result?

Or how can I create a Adjacency List, where I could add to the root, meaning that if I were to give values (0, 2) and then (0,5) it would add those values not under eachother but separately and then (2, 6) would go under the node 2.

Upvotes: 2

Views: 3430

Answers (2)

Majid Arasteh
Majid Arasteh

Reputation: 36

import os

vertexNum =#Vertexes
edgeNum = #Edges
edgeList = [[0,[-3]]]

source = "destination of edgelist file"

f = open(source, "r")
l = f.readlines()
l2 = [line.rstrip('\n') for line in l]

for i in range(1,vertexNum+1):
    edgeList.append([i,[]])

for line in l2:
    graph_Local = [line.split(" ")[0],line.split(" ")[1]]
    edgeList[int(graph_Local[0])][1].append(int(graph_Local[1]))
    edgeList[int(graph_Local[1])][1].append(int(graph_Local[0]))


with open('destination to save adjacency list','w') as eFile:
    for item in edgeList:
        eFile.write("%s\n" % item[1])

eFile.close()

Upvotes: 1

vijay
vijay

Reputation: 187

Not so optimized but i think it will work.

static class Connection{
  int index1;
  int index2;
  Connection(int index1,int index2){
       this.index1=index1;
       this.index2=index2;
  }
}

private static List<Connection> connections;
private static List<List<Integer>> adjList;
private static int max;

static void makeAdjList(){
     for(int i=0;i<max;i++){
        for(int j=0;j<connections.size();j++){
            Connection c=connection.get(j);
            if(c.index1==0||c.index2==0){
               adjList.get(i).add(c.index1==0?c.index2:index1);
            }
        }
     }
}

Upvotes: 0

Related Questions