graph DS

Work in Progress

Succeeds: graphs

Summary

space

Operation	Method	Performance
`vertices()`	number of rows	- , traverse - , counter
`egdes()`	count through every cell	-
`neighbours(u)`	traverse through the row `u`	-
`find(u,v)`	direct indexing of cell `(u,v)`	-

the adjacency matrix of an undirected graph is symmetric

Adjacency list - compact array or hash table

space

Operation	Method	Performance
`vertices()`	size of array	- , traverse - , counter
`egdes()`	sum of sizes of the subarray	- , traverse - , counter
`neighbours(u)`	check the subarray of `u`	- - , for neighbours
`find(u,v)`	search the subarray of `u`	- - , for neighbours

neighbours(u) and find(u,v) are output-sensitive, if there are only neighbours of u, then is a tighter bound

Edge list - compact array

space

Operation	Method	Performance
`vertices()`	traverse the edges	-
`egdes()`	size of list	- , count - , keep track
`neighbours(u)`	check all edges	-
`find(u,v)`	linear search	-

Concept

Graph operations

vertices()
- count the number of vertices in the graph
egdes()
- count the number of edges in the graph
neighbours(u)
- return all the neighbours of vertex u
find(u,v)
- check if there exist an edge between u and v

Types of graphs

U/U -> undirected/unweighted
U/W -> undirected/weighted
D/U -> directed/unweighted
D/W -> directed/weighted

Simple graphs

do not include self-loops

Sparse

when the number of edges is closer to than to

Directed acyclic graph(DAG)

directed
no cycles

Planar graph

can be drawn on a 2D plane without edges crossing

Trees

acyclic graph
one unique path between any pair of vertices
sparse

undirected trees may have trivial cycles between 2 vertices, they are ignored
directed trees are DAGs

Complete graph

has an edge between every pair

Bipartite graph

vertices can be partitioned into two disjoint sets
no edge between members of the same set
no odd length cycles

Application

Leetcode: Maximal Network Rank

edge list -> adjacency list

java

// roads is an edge list
Map<Integer, List<Integer>> al = new HashMap<>();

for (int i = 0; i < n; i++) // initialise empty  adjacency list
	al.put(i, new ArrayList<>());

for (int[] road : roads) { // fill adjacency list from edge list
	al.computeIfPresent(road[0], (k,v) -> {v.add(road[1]); return v;});
	al.computeIfPresent(road[1], (k,v) -> {v.add(road[0]); return v;});
}

int max = 0;
for (int i = 0; i < n - 1; i++) // O(n^2) for checking every pair
	for (int j = i + 1; j < n; j++)
		max = Math.max(max, al.get(i).size() + al.get(j).size() - (al.get(i).contains(j) ? 1 : 0)); // -1 if they have a mutual edge

return max;

count ranks and connections
less concerned with finding the connection, but counting the connections

java

// roads is an edge list
int[] ranks = new int[n];
for(int[] road : roads) {
	++ranks[road[0]];
	++ranks[road[1]];
}

// identify first and second highest ranks
int first = 0;
int second = 0;
for(int rank : ranks) {
	if (rank > first) {
		second = first;
		first = rank;
	} else if (rank == first) {
		continue;
	} else if (rank > second) {
		second = rank;
	}
}

// count occurances
int firstCount = 0;
int secondCount = 0;
for(int rank : ranks) {
	if (rank == first) {
		++firstCount;
	} else if (rank == second) {
		++secondCount;
	}
}

// if only one first
if (firstCount == 1) {
	int count = 0;
	for(int[] road : roads) {
		if (ranks[road[0]] == first && ranks[road[1]] == second) {
			++count;
		} else if (ranks[road[1]] == first && ranks[road[0]] == second) {
			++count;
		}
	}
	// see if there is a second that is not connected to the first
	return first + second - (secondCount > count ? 0 : 1);
} else { // multiple firsts
	int count = 0;
	for(int[] road : roads) {
		if (ranks[road[0]] == first && ranks[road[1]] == first) {
			++count;
		}
	}
	// see if there are 2 firsts that are not connected
	return first + first - (firstCount * (firstCount - 1) / 2 > count ? 0 : 1);
	// nC2 = n*(n-1) / 2, max number of pairs among n nodes
}