A "graph" consists of "nodes", also known as "vertices". Nodes may or may not be connected with one another. 
In our definition below the node "A0" is connected with the node "A3", but "A0" is not connected with "A1".

The connecting line between two nodes is called an edge. If the edges between the nodes are undirected, 
the graph is called an undirected graph. A weighted graph is a graph in which a number (the weight) is assigned to each edge.
A graph is acyclic if it has no loop.

A graph can be represented as a dictionary:


`graph = {'A0': [('A3', 1), ('A5', 4)], 
 'A1': [('A2', 2)], 
 'A2': [('A1', 1), ('A2', 2), ('A3', 1), ('A4', 1)],
 'A3': [('A0', 1), ('A2', 1)], 
 'A4': [('A2', 1), ('A4', 1)], 
 'A5': [('A3', 3)]
}`

Here the nodes are A0...A5; following each nodes is the edges list of linked nodes with their weight.
A0 is linked to A3 with a weight of 1 and to A5 with weight 4. A dictionary is not ordered but the list
of linked nodes is sorted. So: 

`'A0': [('A3', 1), ('A5', 4)]`is correct but `'A0': [('A5', 4), ('A3', 1)]`is not.

The edges E of a graph G induce a binary relation that is called the adjacency relation of G.
One can associate an adjacency matrix:

`M = 
[[0, 0, 0, 1, 0, 4], 
 [0, 0, 2, 0, 0, 0], 
 [0, 1, 2, 1, 1, 0], 
 [1, 0, 1, 0, 0, 0], 
 [0, 0, 1, 0, 1, 0], 
 [0, 0, 0, 3, 0, 0]]`

Let us imagine that lines are numbered from A0 to A5 and the same for columns.
The first line correspond to A0 and we can see that A0 is connected to A3 with weight 1, A0 is also connected to A5 with weight 4.

Another way is to use an adjacency list: An adjacency list representation for a graph 
associates each vertex in the graph with the collection of its neighboring edges:

`L = [['A0', [('A3', 1), ('A5', 4)]], 
     ['A1', [('A2', 2)]], 
     ['A2', [('A1', 1), ('A2', 2), ('A3', 1), ('A4', 1)]], 
     ['A3', [('A0', 1), ('A2', 1)]], 
     ['A4', [('A2', 1), ('A4', 1)]], 
     ['A5', [('A3', 3)]]] `

L is sorted in order A0 to A5 and each sublist is sorted as in a graph dictionary.

In the kata nodes will be numbered from A0 to A(n-1) for a graph with n nodes. 
The task is to go from each represention to each other one
and at last to find *all* paths from a node to another node.

Below is a skeleton for our class `Graph`.

class Graph():
 
    def __init__(self, vertices_num):
        # number of nodes (an integer)
        self.v = vertices_num
        # (maybe not useful here) : list of nodes from "A0", "A1" ... to "A index (vertices_num - 1)"
        self.nodes = None

    # from adjacency matrix to dictionary
    def adjmat_2_graph(self, adjm):
        
    # from dictionary to adjacency matrix
    def graph_2_mat(self, graph):
    
    # from dictionary to adjacency list    
    def graph_2_list(self, graph):
        
    # from adjacency list to dictionary
    def list_2_graph(self, lst):
        
    # from adjacency matrix to adjacency list    
    def mat_2_list(self, mat):
     
    # from adjacency list to adjacency matrix
    def list_2_mat(self, lst):
        
    # find all paths from node start_vertex to node end_vertex
    def find_all_paths(self, graph, start_vertex, end_vertex):

# Examples: 
- see: graph, M, L above.
- finding all paths:

`dct = {'A3': [('A0', 1), ('A2', 1)], 'A0': [('A3', 1), ('A2', 1)], 'A4': [('A2', 1)], 'A1': [('A2', 1)], 'A2': [('A1', 1), ('A2', 1), ('A3', 1), ('A4', 1)]}`

`g = Graph(5)`

`g.find_all_paths(dct, "A0", "A4") return l = ['A0-A2-A4', 'A0-A3-A2-A4']`

Note that ['A0-A2-A4', 'A0-A3-A2-A4'] is sorted (hint: sorted(sorted(l, key=str), key=len))

Translators and critics are welcome.

Source: codewars | Difficulty: MEDIUM
Tags: Matrices

Fundamentals

Graph algorithms

Data structures

Starter code: def __init__(self, vertices_num):
	

Solutions:
from collections import deque

class Graph:

	def __init__(self, vertices_num):
		self.v = vertices_num

	def adjmat_2_graph(self, adjm):
		d = {f'A{i}': [] for i in range(self.v)}
		for (i, j) in enumerate(adjm):
			for (k, l) in enumerate(j):
				if l:
					d[f'A{i}'].append((f'A{k}', l))
		return d

	def graph_2_mat(self, graph):
		mat = [[0 for _ in range(self.v)] for _ in range(self.v)]
		for (i, j) in graph.items():
			for (k, l) in j:
				mat[int(i[1])][int(k[1])] = l
		return mat

	def graph_2_list(self, graph):
		return [[i, j] for (i, j) in sorted(graph.items())]

	def list_2_graph(self, lst):
		return {i: x for (i, x) in lst}

	def mat_2_list(self, mat):
		return self.graph_2_list(self.adjmat_2_graph(mat))

	def list_2_mat(self, lst):
		return self.graph_2_mat(self.list_2_graph(lst))

	def find_all_paths(self, graph, start, end):
		graph = {i: [k[0] for k in j] for (i, j) in graph.items()}
		(Q, paths) = (deque([[start, []]]), [])
		while Q:
			(node, path) = Q.popleft()
			path.append(node)
			if node == end:
				paths.append('-'.join(path))
			for n in graph[node]:
				if n not in path:
					Q.append([n, path[:]])
		return sorted(paths, key=len)


class Graph:

	def __init__(self, vertices_num):
		self.v = vertices_num
		self.nodes = [f'A{i}' for i in range(self.v)]
		self.ids = {x: i for (i, x) in enumerate(self.nodes)}

	def adjmat_2_graph(self, adjm):
		return {self.nodes[i]: [(self.nodes[j], x) for (j, x) in enumerate(row) if x] for (i, row) in enumerate(adjm)}

	def graph_2_mat(self, graph):
		result = [[0] * self.v for _ in range(self.v)]
		for (i, L) in graph.items():
			for (j, x) in L:
				result[self.ids[i]][self.ids[j]] = x
		return result

	def graph_2_list(self, graph):
		return list(map(list, sorted(graph.items())))

	def list_2_graph(self, lst):
		return dict(lst)

	def mat_2_list(self, mat):
		return self.graph_2_list(self.adjmat_2_graph(mat))

	def list_2_mat(self, lst):
		return self.graph_2_mat(self.list_2_graph(lst))

	@staticmethod
	def gen(graph, start, end, seen):
		if start == end:
			yield [end]
		else:
			for (k, v) in graph[start]:
				if k not in seen:
					for L in Graph.gen(graph, k, end, seen | {k}):
						yield ([start] + L)

	def find_all_paths(self, graph, start_vertex, end_vertex):
		return sorted(map('-'.join, Graph.gen(graph, start_vertex, end_vertex, {start_vertex})), key=lambda x: (len(x), x))


class Graph:

	def __init__(self, vertices_num):
		self.v = vertices_num

	def sort_adj_list(self, lst):
		res = []
		for l in lst:
			res.append([l[0], sorted(l[1])])
		return sorted(res)

	def adjmat_2_graph(self, adjm):
		if len(adjm) != self.v:
			return 'Dimension error'
		nodes = ['A' + str(i) for i in range(0, self.v)]
		graph = {}
		for (n, v) in enumerate(nodes):
			voisin = []
			for (i, dist) in enumerate(adjm[n]):
				if dist != 0:
					voisin.append((nodes[i], dist))
			graph[v] = voisin
		self.graph = graph
		return graph

	def graph_2_mat(self, graph):
		nodes = sorted(graph.keys())
		adjm = []
		for node in nodes:
			L = [0] * len(nodes)
			parcours = graph[node]
			for (voisin, dist) in parcours:
				L[nodes.index(voisin)] = dist
			adjm.append(L)
		return adjm

	def graph_2_list(self, graph):
		r = [[k, graph[k]] for k in sorted(graph.keys())]
		return self.sort_adj_list(r)

	def list_2_graph(self, lst):
		if len(lst) != self.v:
			return 'Dimension error'
		dct = {}
		for l in lst:
			dct[l[0]] = l[1]
		return dct

	def mat_2_list(self, mat):
		if len(mat) != self.v:
			return 'Dimension error'
		return self.graph_2_list(self.adjmat_2_graph(mat))

	def list_2_mat(self, lst):
		if len(lst) != self.v:
			return 'Dimension error'
		return self.graph_2_mat(self.list_2_graph(lst))

	def find_all_paths_aux(self, start, end, path=[]):
		graph = self.graph
		path = path + [start]
		if start == end:
			return [path]
		if start not in graph:
			return []
		paths = []
		for vertex in list([x[0] for x in graph[start]]):
			if vertex not in path:
				extended_paths = self.find_all_paths_aux(vertex, end, path)
				for p in extended_paths:
					paths.append(p)
		return paths

	def find_all_paths(self, graph, start, end):
		self.graph = graph
		paths = self.find_all_paths_aux(start, end)
		paths = list(['-'.join(x) for x in paths])
		return sorted(sorted(paths, key=str), key=len)


class Graph:

	def __init__(self, vertices_num):
		self.v = vertices_num
		self.nodes = None

	def adjmat_2_graph(self, matrix):
		dictionary = {}
		step = 0
		for row in matrix:
			dictionary[f'A{step}'] = []
			column = 0
			for value in row:
				if value:
					dictionary[f'A{step}'].append((f'A{column}', value))
				column += 1
			step += 1
		return dictionary

	def graph_2_mat(self, dictionary):
		matrix = []
		step = 0
		while step < len(dictionary):
			row = [0] * len(dictionary)
			for edge in dictionary[f'A{step}']:
				row[int(edge[0][1])] = edge[1]
			matrix.append(row)
			step += 1
		return matrix

	def graph_2_list(self, dictionary):
		list = []
		step = 0
		while step < len(dictionary):
			vertex = [f'A{step}', dictionary[f'A{step}']]
			list.append(vertex)
			step += 1
		return list

	def list_2_graph(self, list):
		dictionary = {}
		for vertex in list:
			dictionary[vertex[0]] = vertex[1]
		return dictionary

	def mat_2_list(self, matrix):
		list = []
		step = 0
		for row in matrix:
			vertex = [f'A{step}', []]
			column = 0
			for value in row:
				if value:
					vertex[1].append((f'A{column}', value))
				column += 1
			list.append(vertex)
			step += 1
		return list

	def list_2_mat(self, list):
		matrix = []
		step = 0
		while step < len(list):
			for vertex in list:
				if vertex[0] == f'A{step}':
					row = [0] * len(list)
					for edge in vertex[1]:
						row[int(edge[0][1])] = edge[1]
					matrix.append(row)
					step += 1
		return matrix

	def find_all_paths(self, dictionary, start, end):

		def dfs(dictionary, start, end, path=[]):
			path = path + [start]
			if start == end:
				return [path]
			if start not in dictionary:
				return []
			paths = []
			for edge in dictionary[start]:
				if edge[0] not in path:
					newpaths = dfs(dictionary, edge[0], end, path)
					for newpath in newpaths:
						paths.append(newpath)
			return paths
		paths = dfs(dictionary, start, end)
		return sorted(sorted(['-'.join(path) for path in paths], key=str), key=len)


class Graph:

	def __init__(self, vertices_num):
		self.v = vertices_num
		self.nodes = None

	def adjmat_2_graph(self, adjm):
		d = {}
		for (indice, ligne) in enumerate(adjm):
			print((indice, ligne))
			cle = 'A' + str(indice)
			laliste = []
			for (indiceVoisin, nombre) in enumerate(ligne):
				if nombre:
					t = ('A' + str(indiceVoisin), nombre)
					laliste.append(t)
			d[cle] = laliste
		return d

	def graph_2_mat(self, graph):
		m = [[0 for k in range(self.v)] for i in range(self.v)]
		for noeud in graph:
			indice = int(noeud[1:])
			for voisin in graph[noeud]:
				indiceVoisin = int(voisin[0][1:])
				distance = voisin[1]
				m[indice][indiceVoisin] = distance
		return m

	def graph_2_list(self, graph):
		m = []
		for noeud in graph:
			laliste = [noeud, graph[noeud]]
			m.append(laliste)
		m.sort()
		return m

	def list_2_graph(self, lst):
		d = {}
		for elt in lst:
			cle = elt[0]
			laliste = elt[1]
			d[cle] = laliste
		return d

	def mat_2_list(self, mat):
		d = self.adjmat_2_graph(mat)
		adj = self.graph_2_list(d)
		return adj

	def list_2_mat(self, lst):
		d = self.list_2_graph(lst)
		a = self.graph_2_mat(d)
		return a

	def find_all_paths(self, graph, start_vertex, end_vertex):
		if start_vertex == end_vertex:
			return [end_vertex]
		start_vertex = int(start_vertex[1:])
		end_vertex = int(end_vertex[1:])
		lesChemins = []
		m = self.graph_2_mat(graph)
		noeuds = list(range(self.v))
		pile = [[start_vertex]]
		while pile:
			chemin = pile.pop()
			dernier = chemin[-1]
			lesVoisins = [k for k in noeuds if m[dernier][k] > 0 and k not in chemin]
			for voisin in lesVoisins:
				if voisin == end_vertex:
					bonChemin = chemin.copy()
					bonChemin.append(voisin)
					bonChemin = ['A' + str(k) for k in bonChemin]
					lesChemins.append('-'.join(bonChemin))
				else:
					leChemin = chemin.copy()
					leChemin.append(voisin)
					pile.append(leChemin)
		lesChemins.sort()
		lesChemins.sort(key=len)
		return lesChemins


class Graph:

	def __init__(self, vertices_num):
		self.v = vertices_num
		self.nodes = None

	def adjmat_2_graph(self, adjm):
		gra = {}
		for (vern, i) in enumerate(adjm):
			tem = []
			for (ind, v) in enumerate(i):
				if v != 0:
					tem.append(('A{}'.format(ind), v))
					gra['A{}'.format(vern)] = tem
		return gra

	def graph_2_mat(self, graph):
		mat = [[0 for _ in range(len(graph))] for _ in range(len(graph))]
		for (k, v) in graph.items():
			for i in v:
				mat[int(k[1])][int(i[0][1])] = i[1]
		return mat

	def graph_2_list(self, graph):
		return sorted([[k, v] for (k, v) in graph.items()], key=lambda x: x[0])

	def list_2_graph(self, lst):
		return {i[0]: i[1] for i in lst}

	def mat_2_list(self, mat):
		lst = []
		for (ind, v) in enumerate(mat):
			tem = []
			for (ind1, i) in enumerate(v):
				if i != 0:
					tem.append(('A{}'.format(ind1), i))
			lst.append(['A{}'.format(ind), tem])
		return sorted(lst, key=lambda x: x[0])

	def list_2_mat(self, lst):
		mat = [[0 for _ in range(len(lst))] for _ in range(len(lst))]
		for i in lst:
			for j in i[1]:
				mat[int(i[0][1])][int(j[0][1])] = j[1]
		return mat

	def find_all_paths(self, graph, start_vertex, end_vertex):
		all_paths = []
		sta = [[start_vertex]]
		while sta:
			a = sta.pop()
			if a[-1] == end_vertex:
				all_paths.append(a)
				continue
			for i in graph[a[-1]]:
				if i[0] not in a:
					sta.append(a + [i[0]])
		return ['-'.join([i for i in p]) for p in sorted(sorted(all_paths), key=len)]


class Graph:

	def __init__(self, vertices_num):
		self.v = vertices_num
		self.nodes = None

	def adjmat_2_graph(self, adjm):
		g = {f'A{x}': [] for x in range(self.v)}
		for i in range(self.v):
			for j in range(self.v):
				if adjm[i][j] != 0:
					g[f'A{i}'].append((f'A{j}', adjm[i][j]))
		return g

	def graph_2_mat(self, graph):
		m = [[0 for j in range(self.v)] for i in range(self.v)]
		for x in range(self.v):
			for g in graph[f'A{x}']:
				m[x][int(g[0][1:])] = g[1]
		return m

	def graph_2_list(self, graph):
		return sorted([[key, val] for (key, val) in list(graph.items())])

	def list_2_graph(self, lst):
		return {el[0]: el[1] for el in lst}

	def mat_2_list(self, mat):
		return self.graph_2_list(self.adjmat_2_graph(mat))

	def list_2_mat(self, lst):
		return self.graph_2_mat(self.list_2_graph(lst))

	def find_all_paths(self, graph, start_vertex, end_vertex):
		paths = [[start_vertex]]
		new_paths = []
		res = []
		if start_vertex == end_vertex:
			return [start_vertex]
		while paths:
			for p in paths:
				for t in graph[p[-1]]:
					if t[0] == end_vertex:
						res.append('-'.join(p + [t[0]]))
						continue
					if t[0] in p:
						continue
					else:
						new_paths.append(p + [t[0]])
			paths.clear()
			(paths, new_paths) = (new_paths, paths)
		return res


class Graph:

	def __init__(self, vertices_num):
		pass

	@staticmethod
	def adjmat_2_graph(adjm):
		nodes_dct = {}
		for (row, weights) in enumerate(adjm):
			edges = [('A' + str(col), w) for (col, w) in enumerate(weights) if w > 0]
			nodes_dct['A' + str(row)] = edges
		return nodes_dct

	@staticmethod
	def graph_2_mat(graph):
		g_size = len(list(graph.keys()))
		matrix = [[0 for _ in range(g_size)] for _ in range(g_size)]
		for (vname, edges) in list(graph.items()):
			v = int(vname[1:])
			for e in edges:
				u = int(e[0][1:])
				matrix[u][v] = e[1]
		return matrix

	@staticmethod
	def graph_2_list(graph):
		return [[k, v] for (k, v) in sorted(graph.items())]

	@staticmethod
	def list_2_graph(lst):
		return dict(((vertex[0], vertex[1]) for vertex in lst))

	@staticmethod
	def mat_2_list(mat):
		return Graph.graph_2_list(Graph.adjmat_2_graph(mat))

	@staticmethod
	def list_2_mat(lst):
		return Graph.graph_2_mat(Graph.list_2_graph(lst))

	@staticmethod
	def find_all_paths(graph, start_vertex, end_vertex):
		if start_vertex == end_vertex:
			return [start_vertex]
		paths = []

		def find(path):
			for e in graph[path[-1]]:
				v = e[0]
				if v not in path:
					new_path = path[:] + [v]
					if v == end_vertex:
						paths.append(new_path)
					else:
						find(new_path)
		find([start_vertex])
		l = list(['-'.join(p) for p in paths])
		return sorted(sorted(l, key=str), key=len)


class Graph:

	def __init__(self, vertices_num):
		self.v = vertices_num

	def adjmat_2_graph(self, adjm):
		if len(adjm) != self.v:
			return 'Dimension error'
		nodes = ['A' + str(i) for i in range(0, self.v)]
		graph = {}
		for (n, v) in enumerate(nodes):
			voisin = []
			for (i, dist) in enumerate(adjm[n]):
				if dist != 0:
					voisin.append((nodes[i], dist))
			graph[v] = voisin
		self.graph = graph
		return graph

	def graph_2_mat(self, graph):
		result = [[0] * self.v for _ in range(self.v)]
		for (k, links) in graph.items():
			for (n, d) in links:
				result[int(k[1:])][int(n[1:])] = d
		return result

	def graph_2_list(self, graph):
		return list(map(list, sorted(graph.items())))

	def list_2_graph(self, lst):
		return {k: a for (k, a) in lst}

	def mat_2_list(self, mat):
		return self.graph_2_list(self.adjmat_2_graph(mat))

	def list_2_mat(self, lst):
		return self.graph_2_mat(self.list_2_graph(lst))

	def find_all_paths(self, graph, start_vertex, end_vertex):
		pths = []
		st = [[start_vertex]]
		while st:
			top = st.pop()
			if top[-1] == end_vertex:
				pths.append('-'.join(top))
				continue
			for (n, _) in graph[top[-1]]:
				if n not in top:
					st.append(top + [n])
		return sorted(sorted(pths), key=len)


class Graph:

	def __init__(self, vertices_num):
		self.v = vertices_num
		self.nodes = [f'A{n}' for n in range(vertices_num)]

	def adjmat_2_graph(self, adjm):
		return {self.nodes[src_index]: [(self.nodes[dst_index], weight) for (dst_index, weight) in enumerate(weights) if weight > 0] for (src_index, weights) in enumerate(adjm) if any((weight > 0 for weight in weights))}

	def graph_2_mat(self, graph):
		result = [[0 for _ in range(self.v)] for _ in range(self.v)]
		for (src, edges) in graph.items():
			src_index = self.nodes.index(src)
			for (dst, weight) in edges:
				dst_index = self.nodes.index(dst)
				result[src_index][dst_index] = weight
		return result

	def graph_2_list(self, graph):
		return sorted([[src, edges] for (src, edges) in graph.items()], key=lambda x: x[0])

	def list_2_graph(self, lst):
		return {src: edges for (src, edges) in lst}

	def mat_2_list(self, mat):
		return self.graph_2_list(self.adjmat_2_graph(mat))

	def list_2_mat(self, lst):
		return self.graph_2_mat(self.list_2_graph(lst))

	def find_all_paths(self, graph, start_vertex, end_vertex, seen=None):
		if start_vertex == end_vertex and seen is None:
			return [start_vertex]
		if seen is None:
			seen = set()
		seen = seen | {start_vertex}
		next_options = [dst for (dst, weight) in graph.get(start_vertex, []) if dst not in seen]
		paths = [start_vertex + '-' + path for option in next_options for path in self.find_all_paths(graph, option, end_vertex, seen)]
		if end_vertex in next_options:
			paths.append(start_vertex + '-' + end_vertex)
		return sorted(sorted(paths, key=str), key=len)