Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Hashmap representation of graph

I have a text file with graph edges, for example

1 2

1 3

2 5

etc. , and want to represent my graph in some way. I tried to use a hashmap, is it the best way to represent edges? And second question, how can I access first and second entries in my hashmap? My code here

    DataInputStream dStream = new DataInputStream(new FileInputStream("C:/Programming/Java/test.txt"));
    BufferedReader bReader = new BufferedReader(new InputStreamReader(dStream));

    HashMap<Integer, Integer> graphEdges = new HashMap<Integer, Integer>();
    String line;
    while( (line = bReader.readLine()) != null) {
        String[] firstSecond = line.split(" ");
        int firstDigit = Integer.parseInt(firstSecond[0]);
        int secondDigit = Integer.parseInt(firstSecond[1]);

        graphEdges.put(firstDigit, secondDigit);
    }

    System.out.println(graphEdges);

    bReader.close();
}
like image 328
user2081119 Avatar asked Feb 24 '13 08:02

user2081119


People also ask

How do you make a HashMap graph in Java?

The Graph class is implemented using HashMap in Java. As we know HashMap contains a key and a value, we represent nodes as keys and their adjacency list in values in the graph. Illustration: An undirected and unweighted graph with 5 vertices.

What is the representation of graph?

A graph can be represented using 3 data structures- adjacency matrix, adjacency list and adjacency set. An adjacency matrix can be thought of as a table with rows and columns. The row labels and column labels represent the nodes of a graph.

How is graph represented in memory?

A graph is a data structure that consist a sets of vertices (called nodes) and edges. There are two ways to store Graphs into the computer's memory: Sequential representation (or, Adjacency matrix representation) Linked list representation (or, Adjacency list representation)

How do you represent a graph with weights?

Weighted graphs can be represented in two ways: Directed graphs where the edges have arrows that show path direction. Undirected graphs where edges are bi-directional and have no arrows.


1 Answers

Among many possible representations of a graph, the 2 basic are the following:

  • Adjacency lists

enter image description here

In Java:

Map<Integer, List<Integer>> graph = new HashMap<>();
...
while( (line = bReader.readLine()) != null) {
    String[] tokens = line.split(" ");
    int firstNode = Integer.parseInt(tokens[0]);
    int secondNode = Integer.parseInt(tokens[1]);

    if(!graph.containsKey(firstNode)) graph.put(firstNode, new LinkedList());
    graphEdges.get(firstNode).add(secondNode);
}
  • Adjacency Matrix

enter image description here

In Java:

int[][] graph = new int[numberOfNodes][numberOfNodes];
while( (line = bReader.readLine()) != null) {
    String[] tokens = line.split(" ");
    int firstNode = Integer.parseInt(tokens[0]);
    int secondNode = Integer.parseInt(tokens[1]);

    graph[firstNode-1][secondNode-1] = 1;
    graph[secondNode-1][firstNode-1] = 1;
}

Below is a comparison of operations and storage efficiency of these 2 representations:

                   |     Adjacency List    |   Adjacency Matrix   |
Storage            |      O(nodes+edges)   |     O(nodes^2)       |
Add node           |          O(1)         |     O(nodes^2)*      |
Add edge           |          O(1)         |        O(1)          |
Remove node        |        O(edges)       |     O(nodes^2)*      |
Remove edge        |        O(edges)       |        O(1)          |
isAdjacent(x1,x2)  |        O(nodes)       |        O(1)          |
*Requires copying of the whole array

You can also make a slight modification in the adjacency lists and use HashSets, instead of LinkedList for storing the adjacent nodes. In that case, everything is the same, except the isAdjacent(x1,x2) operation that now has O(1) complexity (amortized).

like image 109
Dimos Avatar answered Sep 21 '22 23:09

Dimos