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.

Difficulty: interview

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)}

    # from adjacency matrix to dictionary
    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)}
        
    # from dictionary to adjacency matrix
    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
    
    # from dictionary to adjacency list    
    def graph_2_list(self, graph):
        return list(map(list, sorted(graph.items())))
        
    # from adjacency list to dictionary
    def list_2_graph(self, lst):
        return dict(lst)
        
    # from adjacency matrix to adjacency list    
    def mat_2_list(self, mat):
        return self.graph_2_list(self.adjmat_2_graph(mat))
    
    # from adjacency list to adjacency matrix
    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
        
    # find all path from node start_vertex to node end_vertex
    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):
        # number of nodes (integer)
        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"
        # list of nodes from "A0", "A1" ... to "A index (vertices_num - 1)"
        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):
        # 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, 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
        
    # from dictionary to adjacency matrix
    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
    
    # from dictionary to adjacency list    
    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
        
    # from adjacency list to dictionary
    def list_2_graph(self, list):
        dictionary = {}
        for vertex in list:
            dictionary[vertex[0]] = vertex[1]
        return dictionary
        
    # from adjacency matrix to adjacency list    
    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
    
    # from adjacency list to adjacency matrix
    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
        
    # find all path from node start_vertex to node end_vertex
    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):
        # 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):
        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
    
    # from dictionary to adjacency matrix
    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
    
    # from dictionary to adjacency list    
    def graph_2_list(self, graph):
        m = []
        for noeud in graph:
            laliste = [noeud, graph[noeud]]
            m.append(laliste)
        m.sort()
        return m
    
    # from adjacency list to dictionary
    def list_2_graph(self, lst):
        d = {}
        for elt in lst:
            cle = elt[0]
            laliste = elt[1]
            d[cle] = laliste
        return d
            
            
    # from adjacency matrix to adjacency list    
    def mat_2_list(self, mat):
        d = self.adjmat_2_graph(mat)
        adj = self.graph_2_list(d)
        return adj
    
    # from adjacency list to adjacency matrix
    def list_2_mat(self, lst):
        d = self.list_2_graph(lst)
        a = self.graph_2_mat(d)
        return a
        
    
    
    # find all path from node start_vertex to node end_vertex
    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):
        # 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): 
        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    
        
    # from dictionary to adjacency matrix
    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
    # from dictionary to adjacency list    
    def graph_2_list(self, graph): 
        return sorted([[k, v] for k, v in graph.items()], key = lambda x: x[0])
        
    # from adjacency list to dictionary
    def list_2_graph(self, lst): 
        return {i[0]:i[1] for i in lst}
        
    # from adjacency matrix to adjacency list    
    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])
    
    # from adjacency list to adjacency matrix
    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
        
    # find all path from node start_vertex to node end_vertex
    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):
        # 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):
        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
    
    # from dictionary to adjacency matrix
    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

    # from dictionary to adjacency list    
    def graph_2_list(self, graph):
        return sorted([[key, val]for key, val in list(graph.items())])

    # from adjacency list to dictionary
    def list_2_graph(self, lst):
        return {el[0]: el[1] for el in lst}

    # from adjacency matrix to adjacency list    
    def mat_2_list(self, mat):
        return self.graph_2_list(self.adjmat_2_graph(mat))    
    
    # from adjacency list to adjacency matrix
    def list_2_mat(self, lst):
        return self.graph_2_mat(self.list_2_graph(lst))    

    # find all path from node start_vertex to node end_vertex
    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

    # from adjacency matrix to dictionary
    @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())]

    # from adjacency list to dictionary
    @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

    # from adjacency matrix to dictionary
    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

    # from dictionary to adjacency matrix
    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

    # from dictionary to adjacency list
    def graph_2_list(self, graph):
        return list(map(list, sorted(graph.items())))

    # from adjacency list to dictionary
    def list_2_graph(self, lst):
        return {k: a for k, a in lst}

    # from adjacency matrix to adjacency list
    def mat_2_list(self, mat):
        return self.graph_2_list(self.adjmat_2_graph(mat))

    # from adjacency list to adjacency matrix
    def list_2_mat(self, lst):
        return self.graph_2_mat(self.list_2_graph(lst))

    # find all path from node start_vertex to node end_vertex
    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)]

    # adjacency matrix to dictionary
    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)
        }
        
    # dictionary to adjacency matrix
    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
    
    # dictionary to adjacency list    
    def graph_2_list(self, graph):
        return sorted([
            [src, edges]
            for src, edges in graph.items()
        ], key=lambda x: x[0])
        
    # adjacency list to dictionary
    def list_2_graph(self, lst):
        return {
            src: edges
            for src, edges in lst
        }
        
    # adjacency matrix to adjacency list    
    def mat_2_list(self, mat):
        return self.graph_2_list(self.adjmat_2_graph(mat))
    
    # adjacency list to adjacency matrix
    def list_2_mat(self, lst):
        return self.graph_2_mat(self.list_2_graph(lst))
        
    # all paths from node start_vertex to node end_vertex
    def find_all_paths(self, graph, start_vertex, end_vertex, seen=None):
        if start_vertex == end_vertex and seen is None: # Non-recursive case only
            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)