hypergraph_min_cut.py

import copy
import math
import matplotlib.pyplot as plt

import networkx as nx
import numpy
import hypernetx as hx  # for hypergraph
import hypernetx.algorithms.hypergraph_modularity as hmod
import numpy as np
import os
import scipy.cluster.hierarchy
import cv2


from oriented_matroid import *
from meta_function import *
from combtools import *
from progress.bar import *
import tracemalloc
from module_om import *
from width_and_params import *
import gc
from smc import *
# from creates_examples import *
from creates_examples import draw_geom, draw_geom_with_partition

"""
Let mathcal{M} be a collection of oriented matroids of rank r on a ground set E and chi be its set of constant bases 
then we can see this collection as an hypergraph H such that the vertices are elements of E and hyperedges are 
the constant bases.
In such an hypergraph, for each bipartition of E we can calculates the number of edges that have at least an element in
each part (those edges are called split-bases in our context). The function that associates such a bipartition to its 
number of splited-edges is submodular.
The problem of minimizing this function is addressed in this file, as well as some related problems.

"""

class ChiroHypergraph:
    """
    Structure made to creates an hypergraph from a ConstantChirotope X
    the ground set is the same, each bases of X is an hyperedge of H
    each edge has a positive weight, it is initialised at 1
    edges are tuples
    """

    def __init__(self, chi: ConstantChirotope = None):
        self.ground_set = ()
        self.edges = {}

        if chi:
            self.from_constant_chirotope(chi)

    def from_constant_chirotope(self, chi):
        self.ground_set = chi.get_ground_set()
        for tup in chi:
            self.edges[tup] = 1

    def equivalent_digraph(self):
        """
        we compute the equivalent digraph of an hypergraph as in the article of LAW73
        :return:
        """
        G = nx.DiGraph()
        for e in self.edges:
            for v in e:
                G.add_edge(v, str(e) + "-", capacity=float("inf"))
                G.add_edge(str(e) + "+", v, capacity=float("inf"))
            G.add_edge(str(e) + "-", str(e) + "+", capacity=self.edges[e])
        return G

    def equivalent_digraph_sym(self):
        """
        we compute the equivalent digraph of an hypergraph as in the article of LAW73
        :return:
        """
        G = nx.DiGraph()
        for e in self.edges:
            for v in e:
                G.add_edge(str(e) + "-", v, capacity=float("inf"))
                G.add_edge(v, str(e) + "+", capacity=float("inf"))
            G.add_edge(str(e) + "+", str(e) + "-", capacity=self.edges[e])
        return G

    def contraction(self, U: set): #TODO A OPTI
        assert set(U) <= set(self.ground_set)

        #we need to take an element from u to represent U
        u = None
        for e in U:
            u = e
            break

        new_ground_set = tuple(e for e in self.ground_set if e not in U) + (u,)
        new_edges = {}

        for edge in self.edges:
            set_edge = set(edge)
            inter = set_edge.intersection(U)
            if inter == set():
                new_edges[edge] = self.edges[edge]
            elif inter != U and inter!=set_edge:
                new_e = tuple(e for e in edge if e not in U) + (u,)
                if new_e in new_edges:
                    new_edges[new_e] += self.edges[edge]
                else:
                    new_edges[new_e] = self.edges[edge]

        new_hypergraph = ChiroHypergraph()
        new_hypergraph.edges = new_edges
        new_hypergraph.ground_set = new_ground_set

        return new_hypergraph, u

    def merge(self, s,t):
        assert {s,t} <= set(self.ground_set)
        u = max(self.ground_set)+1

        new_ground_set = tuple(e for e in self.ground_set if e not in {s,t})+(u,)
        new_edges = {}

        for edge in self.edges:
            set_edge = set(edge)
            inter = set_edge.intersection({s,t})
            if not set_edge == {s, t}:
                if inter == set():
                    new_edges[edge] = self.edges[edge]
                else:
                    new_edge = tuple(sorted(set(edge).union({u})-{s,t}))
                    if new_edge in new_edges:
                        new_edges[new_edge] += self.edges[edge]
                    else:
                        new_edges[new_edge] = self.edges[edge]


        new_hypergraph = ChiroHypergraph()
        new_hypergraph.edges = new_edges
        new_hypergraph.ground_set = new_ground_set

        return new_hypergraph, u

    def splited_edges(self,A: set):
        A=set(A)
        set_ground_set = set(self.ground_set)
        assert A <= set(self.ground_set)
        Acomp = set_ground_set-A
        count = 0
        for edge in self.edges:
            set_edge = set(edge)
            if len(set_edge.intersection(A))!=0 and len(set_edge.intersection(Acomp))!=0:
                count+=1
        return count

    def ponderate_splited_edges(self,A: set):
        A=set(A)
        set_ground_set = set(self.ground_set)
        assert A <= set(self.ground_set)
        Acomp = set_ground_set-A
        count = 0
        for edge in self.edges:
            set_edge = set(edge)
            if len(set_edge.intersection(A))!=0 and len(set_edge.intersection(Acomp))!=0:
                count+=len(A.intersection(set_edge))
        return count

    def splited_edges_weighted(self,A: set):
        A=set(A)
        set_ground_set = set(self.ground_set)
        assert A <= set(self.ground_set)
        Acomp = set_ground_set-A
        count = 0
        for edge in self.edges:
            set_edge = set(edge)
            if len(set_edge.intersection(A))!=0 and len(set_edge.intersection(Acomp))!=0:
                count+=self.edges[edge]
        return count



def wag_hypergraph_mincut(G: ChiroHypergraph,a):#TODO: BUGGED !
    """
    Wagner 96 algorithm to compute a minimal cut of an hypergraph.
    :param G:
    :return:
    """
    assert None, "wag_hypergraph_mincut is bugged !"
    def most_tighly_connected_vertex(H:ChiroHypergraph, A: set):
        V = set(H.ground_set)

        assert A <= V, f"A: {A}, V {V}"
        Vcomp = V-A

        def score_tighly(y):
            assert y in Vcomp
            count = 0
            for edge in H.edges:
                if y in edge:
                    if set(edge) <= Vcomp.union({y}):
                        count+=H.edges[edge]
            return count

        most_tighly_con = None
        score_max = 0
        for e in Vcomp:
            score_e = score_tighly(e)
            print(score_e)
            if score_e >= score_max:
                score_max = score_e
                most_tighly_con = e
        assert most_tighly_con, f"Vcomp {Vcomp},score_max {score_max}, V: {V}"

        return most_tighly_con

    def minimum_cut_phase(a):
        V = set(G.ground_set)
        assert a in G.ground_set
        A = [a]
        while set(A) != V:
            A.append(most_tighly_connected_vertex(G,set(A)))
        s,t = A[-2],A[-1]
        return s,t,set(A[:-1])

    V = set(G.ground_set)
    assert a in V
    minimum_cut = None
    minimum_cut_score = float("inf")
    cut_merged = {}
    merged = {}
    while len(V) > 1:
        s,t,C = minimum_cut_phase(a)
        score_C = G.splited_edges_weighted(C)


        if score_C < minimum_cut_score:
            minimum_cut = C
            minimum_cut_score = score_C
            cut_merged = merged
        G,u = G.merge(s,t)
        merged[u] = {s,t}
        V = set(G.ground_set)
    return minimum_cut,minimum_cut_score,cut_merged










class ChiroHypergraphWeighted(ChiroHypergraph):

    def __init__(self,coll: ChirotopesCollection):
        assert type(coll) == ChirotopesCollection
        #TODO



############################blocks to the function minmax_hypergraph_k_parts############################################
def sym_digraph(digraph):
    """
    symmetrize a digraph

    :param digraph:
    :return:
    """
    symdigraph = nx.DiGraph()
    for u, v, d in digraph.edges(data=True):
        symdigraph.add_edge(v, u, capacity=d["capacity"])
    return symdigraph


def add_source_and_sink(digraph, S: set, T: set):
    assert S.intersection(T) == set()
    new_digraph = digraph.copy()
    for e in S:
        new_digraph.add_edge("s", e, capacity=float("inf"))
    for e in T:
        new_digraph.add_edge(e, "t", capacity=float("inf"))
    return new_digraph


def add_source_and_sink_sym(digraph, S: set, T: set):
    assert S.intersection(T) == set()
    for e in S:
        digraph.add_edge(e,"s", capacity=float("inf"))
    for e in T:
        digraph.add_edge("t",e, capacity=float("inf"))

def change_source_and_sink(digraph: nx.DiGraph,S,T):
    assert S.intersection(T) == set()
    digraph.remove_node("s")
    digraph.remove_node("t")
    for e in S:
        digraph.add_edge("s", e, capacity=float("inf"))
    for e in T:
        digraph.add_edge(e, "t", capacity=float("inf"))

def change_source_and_sink_sym(digraph: nx.DiGraph,S,T):
    assert S.intersection(T) == set()
    if "s" in digraph.nodes:
        digraph.remove_node("s")
    if "t" in digraph.nodes:
        digraph.remove_node("t")
    for e in S:
        digraph.add_edge(e,"s", capacity=float("inf"))
    for e in T:
        digraph.add_edge( "t",e, capacity=float("inf"))

def generate_candidates(eq_digraph_sym: nx.DiGraph,k: int,V: set, Q: set):
    """
    function from article Min–Max Partitioning of Hypergraphs and Symmetric
Submodular Functions Karthekeyan Chandrasekaran1 · Chandra Chekuri1
    adapted for hypergraph mincut
    eq_digraph is the equivalent digraph of some hypergraph

    :return:
    """

    R = set({})
    VmQ = V-Q
    lenQ = len(Q)
    lenT = k-1-lenQ

    #For every disjoint S,T subset V with |S| \leq k-1, Q \subseteq T and |T|=k-1:
    for i in range(1,k):
        for S in combinations(VmQ,i):
            S = set(S)
            VmQmS = VmQ - S
            for T in combinations(VmQmS,lenT):
                T = set(T).union(Q)

                #Compute the source maximal minimum (S,T)-terminal cut:
                change_source_and_sink_sym(eq_digraph_sym,S,T)
                # now we can calculate the maximal source minimum (S,T) terminal cut via maxflow/mincut in the updated graph
                val, partition = nx.minimum_cut(eq_digraph_sym, "t", "s",flow_func=nx.flow.shortest_augmenting_path) # the sink became a source and the source a sink

                U = tuple(sorted([v for v in partition[1] if type(v)==int])) # we keep only vertices of the part of the cut that contain the source and
                # that corresponds to vertices in the hypergraph. They are the only vertices such that their type is int.
                # print("S:",S,"T:",T,"V:", V,"Q:",Q)
                # print("U:",U)
                R.update({U})

    print("len(R):",len(R))


    return R
########################################################################################################################

def minmax_hypergraph_k_parts(hyper: ChiroHypergraph,k: int):
    """

    pour papillon13ots et k=3:
    Partition minmax: ((10,), (7,), (0, 1, 2, 3, 4, 5, 6, 8, 9, 11, 12)) Value: 101

    pour crane 16 pts et k=4 en exhaustif:
    MinMax
[[0], [1], [2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15], [6]]
697
MinSum
[[0], [1], [2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15], [8]]
1547
pour k=3
[[0], [1], [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]]
499
MinSum
[[0], [1], [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]]
1053
est-ce qu'il faut virer 0 et 1 et essayer ?


    :param hyper:
    :param k:
    :return:
    """
    V = set(hyper.ground_set)

    # Initialize C1 <- generate_candidates(f,k,Q=set())
    C_1 = {(U,) for U in generate_candidates(hyper.equivalent_digraph_sym(),k,V,set())} # we see partition has tuple
    C_pred = C_1 #for all i C_pred will be C_i-1
    for i in range(2,k):
        print("i=",i)
        C_i = set()
        for partition in C_pred:
            Q = set()
            contracted_hyper = copy.deepcopy(hyper)
            new_V = V
            for part in partition: # Si len(part)=1 alors f/part = f et on à déjà calculer les candidats...
                set_part = set(part)
                contracted_hyper, u = contracted_hyper.contraction(set_part)
                Q.update({u})
                new_V = new_V - set_part
                new_V.update({u})
            R_i = generate_candidates(contracted_hyper.equivalent_digraph_sym(),k,new_V,Q)
            for U in R_i:
                C_i.update({partition+(U,)})
            C_pred = C_i
    # we creates the k-partition.
    C_k = set()
    for partition in C_pred:
        set_partition = set()
        for part in partition:
            set_part = set(part)
            set_partition.update(set_part)
        C_k.update({partition+(tuple(V-set_partition),)})

    print(C_k)
    print(len(C_pred))
    print(len(C_k))
    dict_value = {}
    min_partition = None
    min_value = float("inf")
    for partition in C_k:
        max_value_partition = 0
        for part in partition:
            if part in dict_value:
                value = dict_value[part]
            else:
                value = hyper.splited_edges(part)
                dict_value[part] = value
            if value > max_value_partition:
                max_value_partition = value
        print("Partition", partition, "Value:", max_value_partition)
        if max_value_partition < min_value:
            min_value = max_value_partition
            min_partition = partition
    dict_value[part]
    print("Partition minmax:",min_partition,"Value:",min_value)

def exhaustive_k_parts(hyper: ChiroHypergraph,k: int):
    # minmax_hypergraph_k_parts(hyper,k)

    dict_value = {A: hyper.splited_edges_weighted(A) for A in powerset(hyper.ground_set)}
    print(dict_value)
    min_max_value = float("inf")
    min_max_partition = None
    min_sum_value = float("inf")
    min_sum_partition = None
    max_min_value = 0
    max_min_partition = None
    max_sum_value = 0
    max_sum_partition = None
    for partition in algorithm_u(hyper.ground_set, k):
        max_partition = 0
        sum_partition = 0
        min_partition = float("inf")
        for part in partition:
            part = tuple(part)
            value_part = dict_value[part]
            if value_part > max_partition:
                max_partition = value_part
            sum_partition += value_part
            if value_part < min_partition:
                min_partition = value_part
        if max_partition < min_max_value:
            min_max_partition = partition
            min_max_value = max_partition
        if sum_partition < min_sum_value:
            min_sum_value = sum_partition
            min_sum_partition = partition
        if min_partition > max_min_value:
            max_min_partition = partition
            max_min_value = min_partition
        if sum_partition > max_sum_value:
            max_sum_partition = partition
            max_sum_value = sum_partition
    print("MinMax")
    print(min_max_partition)
    print(min_max_value)
    print("MinSum")
    print(min_sum_partition)
    print(min_sum_value)
    print("MaxMin")
    print(max_min_partition)
    print(max_min_value)
    print("MaxSum")
    print(max_sum_partition)
    print(max_sum_value)

def gh_mincut_value_and_sets(G):
    """
    use example in https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.gomory_hu_tree.html
    to find a minimal cut using gomory hu tree, its value and the edges set.
    :return:
    """
    T = nx.gomory_hu_tree(G)

    def minimum_edge_weight_in_shortest_path(T, u, v):
        path = nx.shortest_path(T, u, v, weight="weight")

        return min((T[u][v]["weight"], (u, v)) for (u, v) in zip(path, path[1:]))


    edge = min((edge for edge in T.edges),key=lambda x: T[x[0]][x[1]]["weight"])
    cut_value = T[edge[0]][edge[1]]["weight"]
    print(cut_value)
    T.remove_edge(*edge)
    U, V = list(nx.connected_components(T))
    cutset = set()
    for x, nbrs in ((n, G[n]) for n in U):
        cutset.update((x, y) for y in nbrs if y in V)

    return cutset,(U,V),cut_value


def kcut_efficient(G: nx.Graph):
    """
        Use algorithm Efficient of the article Finding k-cuts within twice the optimal
        to find a desired k-cut for all 1<k<n

        :param G:
        :return:
        """
    # first we need to compute a gomory hu tree:
    T = nx.gomory_hu_tree(G)
    Tcopy = T.copy()

    def gh_cut_set(edge,GH):
        cut_value = GH[edge[0]][edge[1]]["weight"]
        GH.remove_edge(*edge)
        U, V = list(nx.connected_components(GH))
        cutset = set()
        for x, nbrs in ((n, G[n]) for n in U):
            cutset.update((x, y) for y in nbrs if y in V)
        return cutset

    sorted_edges = sorted([edge for edge in T.edges],key=lambda x: T[x[0]][x[1]]["weight"])

    for edge in sorted_edges:
        curr_cutset = gh_cut_set(edge,Tcopy)
        Tcopy = T.copy()
        G.remove_edges_from(curr_cutset)
        print([set(c) for c in nx.connected_components(G)],nx.number_connected_components(G))


def gomory_hu_constant_bases():
    geom = read("files/ldk/10CUBESv2.ldk").sub({i for i in range(0, 16)})
    chiro_geom = chiro(geom)
    const_chiro = const(chiro_geom)
    G = nx.Graph()
    for i in range(0, len(geom.get_ground_set())):
        for j in range(i + 1, len(geom.get_ground_set())):
            G.add_edge(geom.get_ground_set()[i], geom.get_ground_set()[j], capacity=0)
    for B in const_chiro:
        for i in range(0, geom.get_rank()):
            for j in range(i + 1, geom.get_rank()):
                G[B[i]][B[j]]["capacity"] += 1

    print(G.edges)
    plt.subplot(121)
    pos = nx.spring_layout(G)
    nx.draw(G, pos)
    labels = nx.get_edge_attributes(G, 'capacity')
    nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
    plt.show()
    GHu = nx.gomory_hu_tree(G)
    print(GHu)
    pos = nx.spring_layout(GHu)
    nx.draw(GHu, pos, with_labels=True)
    labels = nx.get_edge_attributes(GHu, 'weight')
    nx.draw_networkx_edge_labels(GHu, pos, edge_labels=labels)
    plt.show()

def gomory_hu_constant_circuits():
    # geom = read("files/ldk/humsinge.txt") - "human"
    geom = read("files/ldk/humsinge.txt")
    chiro_geom = chiro(geom)
    const_chiro = const(chiro_geom)
    const_circuit = circ(const_chiro)
    G = nx.Graph()
    for i in range(0, len(geom.get_ground_set())):
        for j in range(i + 1, len(geom.get_ground_set())):
            G.add_edge(geom.get_ground_set()[i], geom.get_ground_set()[j], capacity=0)
    for c in const_circuit:
        pos = sorted(c.pos)
        len_pos = len(pos)
        for i in range(0, len_pos):
            for j in range(i + 1, len_pos):
                G[pos[i]][pos[j]]["capacity"] += 1
    # for i in range(0,len(geom.get_ground_set()),2):
    #     G[i][i+1]["capacity"]=100000
    print(G.edges)
    plt.subplot(121)
    pos = nx.spring_layout(G)
    nx.draw(G, pos)
    labels = nx.get_edge_attributes(G, 'capacity')
    nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
    plt.show()
    GHu = nx.gomory_hu_tree(G)
    print(GHu)
    pos = nx.spring_layout(GHu)
    nx.draw(GHu, pos, with_labels=True)
    labels = nx.get_edge_attributes(GHu, 'weight')
    nx.draw_networkx_edge_labels(GHu, pos, edge_labels=labels)
    plt.show()

def gomoryhu_hypergraphstcut():
    geom = read("files/ldk/10CUBESv2.ldk").sub(range(0, 32))
    chiro_geom = chiro(geom)
    constant = const(chiro_geom)
    H = ChiroHypergraph(constant)
    groundset = chiro_geom.get_ground_set()
    n = chiro_geom.get_n()

    G = H.equivalent_digraph()
    G.add_node("s")
    G.add_node("t")
    # for u in range(0,n):
    #     for v in range(u+1,n):
    #
    #         G.add_edge(groundset[u],groundset[v],capacity=randint(0,10))

    # # Draw the graph
    # plt.plot(1)
    # pos = nx.spring_layout(G)
    # nx.draw(G, pos,with_labels=True)
    # labels = nx.get_edge_attributes(G, 'capacity')
    # nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
    # plt.show()

    # complete graph of all cut
    Gcut = nx.Graph()
    for u in range(0, n):
        for v in range(u + 1, n):
            change_source_and_sink(G, {u}, {v})
            minuvcut = nx.minimum_cut(G, groundset[u], groundset[v])[0]
            print(minuvcut)
            Gcut.add_edge(groundset[u], groundset[v], capacity=minuvcut)
    plt.plot(1)
    pos = nx.spring_layout(Gcut)
    nx.draw(Gcut, pos, with_labels=True)
    labels = nx.get_edge_attributes(Gcut, 'capacity')
    nx.draw_networkx_edge_labels(Gcut, pos, edge_labels=labels)
    plt.show()

    # minimal spanning tree:
    Tcut = nx.minimum_spanning_tree(Gcut, "capacity")
    print([(edge, Tcut[edge[0]][edge[1]]) for edge in Tcut.edges])
    plt.plot(1)
    pos = nx.spring_layout(Gcut)
    nx.draw(Tcut, pos, with_labels=True)
    labels = nx.get_edge_attributes(Tcut, 'capacity')
    nx.draw_networkx_edge_labels(Tcut, pos, edge_labels=labels)
    plt.show()
    # GomoryHu tree:
    GH = nx.gomory_hu_tree(Gcut)
    print([(edge, GH[edge[0]][edge[1]]) for edge in GH.edges])
    plt.plot(1)
    pos = nx.spring_layout(GH)
    nx.draw(GH, pos, with_labels=True)
    labels = nx.get_edge_attributes(GH, 'weight')
    nx.draw_networkx_edge_labels(GH, pos, edge_labels=labels)
    plt.show()

########################################################################################################################
# create an hypergraph such that the edges are constant submodels and find minimal/maximal kcuts.
########################################################################################################################
def minmax_on_smc(smc: ConstantSubmodels, ground_set):
    H = ChiroHypergraph()
    H.ground_set = ground_set
    for i in smc:
        if i > 5:
            for sm in smc[i]:
                H.edges[sm] = 1
    # minmax_hypergraph_k_parts(H,2)
    exhaustive_k_parts(H, 2)



def segmentation_ressemblance_via_OM():

    # On veut regarder si l'on peut faire du mincut avec comme valeur entre les sommets le nombre de bases qui diffèrent
    # dans M/e-f et M/f-e. Le GH donne toujours une étoile donc ce n'est pas très intéressant...
    # geom = draw_geom()
    geom = read("files/ldk/humsinge.txt")
    chiro_geom = chiro(geom)
    chiro_geom = chiro_geom.chirotope("ENF001")
    ground_set = geom.get_ground_set()



    def width(e,f):
        w = 0
        _ground = tuple(elem for elem in ground_set if elem not in {e,f})
        for tup in combinations(_ground,3):
            tup1 = tup +(e,)
            tup2 = tup + (f,)
            if sign_perm(tup1)*chiro_geom[tuple(sorted(tup1))] ==  sign_perm(tup2)*chiro_geom[tuple(sorted(tup2))]:
                w +=1
        return w

    n  = len(ground_set)
    G = nx.Graph()
    for i in range(0,n):
        for j in range(i+1,n):
            G.add_edge(ground_set[i],ground_set[j],capacity=width(ground_set[i],ground_set[j]))
    print(G.nodes)
    plt.plot(1)
    pos = nx.spring_layout(G)
    nx.draw(G, pos, with_labels=True)
    labels = nx.get_edge_attributes(G, 'capacity')
    nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
    plt.show()

    GH = nx.gomory_hu_tree(G)
    plt.plot(1)
    pos = nx.spring_layout(GH)
    nx.draw(GH, pos, with_labels=True)
    labels = nx.get_edge_attributes(GH, 'weight')
    nx.draw_networkx_edge_labels(GH, pos, edge_labels=labels)
    plt.show()


def splited_bases_over_CSM():
    """
    We count the number of splited bases of the CSM of a model

    :return:
    """
    geom = read("files/ldk/humsinge.txt")
    chiro_geom = chiro(geom)
    constant_chiro = const(chiro_geom)
    non_constant = constant_chiro.non_const()
    submodels = APriori(constant_chiro)[1]
    submodels = [model for key in submodels for model in submodels[key]]
    print("submodels", len(submodels))
    # submodels = {model: function_interaction_rate(constant_chiro, set(model)) for model in submodels}
    submodels = {model: function_interaction_rate(non_constant, set(model)) for model in submodels}
    print(min(submodels, key=lambda x: submodels[x]))
    sorted_list = {model: submodels[model] for model in sorted(submodels, key=lambda x: submodels[x])}
    print(sorted_list)