Chapter 3
Lecture Representations and Conversions
Computers are not humans!
0
5
3
1
2
4
Can see with eyes🡪
Understand the network
Don’t have eyes!
Only understand numbers
Reads information from files
How would you represent network to
make computers understand it?
Computers are not humans!
0
5
3
1
2
4
Do some conversion
Into some sort of numbers or something
Later
Write to a file
The file will have many lines
depending on the conversion
Then the computer can read it!
Edge List
0
5
3
1
2
4
0 | 1 |
0 | 2 |
0 | 4 |
1 | 2 |
1 | 3 |
2 | 5 |
3 | 4 |
3 | 5 |
Edge List
0
5
3
1
2
4
0 | 1 |
0 | 2 |
0 | 4 |
1 | 2 |
1 | 3 |
2 | 5 |
3 | 4 |
3 | 5 |
Rules????
Every Edge Appears once in a separate Row
For every edge, we keep the two nodes it connects
Use numbers to label the nodes, starting from 0
Every edge, lowest label first, for example 0,1 or 0,2
Assumptions
No self edge : 0 to 0 itself, like a loop
Nope!
Only one edge between nodes
5
3
Nope!
In this case, we assume edges have no direction or weight
5
3
5 miles
Nope
Adjacency Matrix
0
5
3
1
2
4
| 0 | 1 | 2 | 3 | 4 | 5 |
0 | 0 | 1 | 1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 | 1 | 0 | 0 |
2 | 1 | 1 | 0 | 0 | 0 | 1 |
3 | 0 | 1 | 0 | 0 | 1 | 1 |
4 | 1 | 0 | 0 | 1 | 0 | 0 |
5 | 0 | 0 | 1 | 1 | 0 | 0. |
Adjacency Matrix
0
5
3
1
2
4
| 0 | 1 | 2 | 3 | 4 | 5 |
0 | 0 | 1 | 1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 | 1 | 0 | 0 |
2 | 1 | 1 | 0 | 0 | 0 | 1 |
3 | 0 | 1 | 0 | 0 | 1 | 1 |
4 | 1 | 0 | 0 | 1 | 0 | 0 |
5 | 0 | 0 | 1 | 1 | 0 | 0 |
N*N matrix 🡪
N = number of nodes
Rules
5
5
Row i represents the neighbors of row i
0 🡪 no edge (circles)
1 🡪 there is an edge (triangles)
No self edges
So, Matrix[i][j] Says if there is an edge from I to j
Matrix[4][3] ? Row 4 Column 3 is 1. so yes there is an edge!
Adjacency List
0
5
3
1
2
4
Network.txt
Line 0 🡪 1 2 4
Line 1 🡪 0 2 3
Line 2🡪 0 1 5
Line 3 🡪 1 4 5
Line 4🡪 0 3
Line 5🡪 2 3
1 2 4
0 2 3
0 1 5
1 4 5
0 3
2 3
Line 0 is neighbors of node 0
Line 1 is neighbors of node 1
And so on
Rules?
Total N lines, N = 5 nodes
Separated by spaces
Directed Graphs
0
5
3
1
2
4
Edges have Direction
Every edge is different, even if they are between the same nodes!
Alice
Kate
Is Parent of
Is Child of
Let’s try to represent them then! Edge list, adjacency matrix and adjacency list
Directed Graph
0
5
3
1
2
4
0 | 2 |
0 | 4 |
1 | 0 |
1 | 2 |
2 | 0 |
2 | 5 |
3 | 1 |
3 | 4 |
5 | 2 |
5 | 3 |
Edge list like before
Directed Graph
0
5
3
1
2
4
Adjacency list like before
| 0 | 1 | 2 | 3 | 4 | 5 |
0 | 0 | 0 | 1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 | 0 | 0 | 0 |
2 | 1 | 0 | 0 | 0 | 0 | 1 |
3 | 0 | 1 | 0 | 0 | 1 | 0 |
4 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 0 | 0 | 1 | 1 | 0 | 0. |
From 0, we have directed edges to 2 and 4
From 1, we have directed edges to 0 and 2
And so on
Matrix[1][0] = 1 but matrix[0][1] = 0. why?
Directed Graph
0
5
3
1
2
4
2 4
0 2
0 5
1 4
2 3
Adjacency List
Line 0 -> edges going out from node 0
Line 1 -> edges going out from node 1
No edges from 4. Empty line
Weighted network
5
3
1
2
4
0
2
3
4
1
6
1
5
| 0 | 1 | 2 | 3 | 4 | 5 |
0 | 0 | 4 | 3 | 0 | 2 | 0 |
1 | 4 | 0 | 1 | 6 | 0 | 0 |
2 | 3 | 1 | 0 | 0 | 0 | 5 |
3 | 0 | 6 | 0 | 0 | 5 | 1 |
4 | 2 | 0 | 0 | 5 | 0 | 0 |
5 | 0 | 0 | 5 | 1 | 0 | 0 |
Anything > 0 🡪 edge presence and weight
5
What’s better?
0
5
3
1
2
4
| 0 | 1 | 2 | 3 | 4 | 5 |
0 | 0 | 1 | 1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 | 1 | 0 | 0 |
2 | 1 | 1 | 0 | 0 | 0 | 1 |
3 | 0 | 1 | 0 | 0 | 1 | 1 |
4 | 1 | 0 | 0 | 1 | 0 | 0 |
5 | 0 | 0 | 1 | 1 | 0 | 0 |
1 2 4
0 2 3
0 1 5
1 4 5
0 3
2 3
Adjacency matrix
Adjacency list
Which one takes less space?
I want to know if 0 and 2 are neighbors.
Which one gives me faster result?
Trade off