Pregled končnih kod

[MancaStrgar]

Pozdravljeni, midva sva sedaj napisala vse najine kode in naju zanima, če se vam zdijo v redu ali bi kaj popravili oz. izboljšali. Hvala za predloge. Kode: https://cocalc.com/share/f2f7d7cf-3047-495e-86cc-25e9c4844e6a/vse%20skupaj.sagews?viewer=share

[jaanos]

Koda izgleda v redu - edino pri kromatičnem številu je zadnja zanka nepotrebna, saj želeno (sosedni vozlišči nista iste barve) dosežeta že pri drugi zanki.

Svetoval bi sicer, da kodo razdelita v funkcije, ki jih potem kličeta na izbranem grafu. Pri tem je funkcije mogoče tudi gnezditi, npr.

def maksimalne_neodvisne_mnozice(G):
    mnozice = []
    pregledane = set()

    def backtrack(A, B):
        if len(B) == 0:
            mnozice.append(A)
        for v in B:
            C = A + Set([v])
            if C in pregledane:
                continue
            pregledane.add(C)
            backtrack(C, B - G[v] - [v])

    backtrack(Set(), Set(G))
    return mnozice

G.relabel() raje kličita izven funkcij (npr. takoj, ko ustvarita graf). Sicer pa se temu lahko izogneta, če izpustita ustvarjanje matrike A in omejitve podasta kar neposredno na podlagi maksimalnih neodvisnih množic:

def deljeno_kromaticno_stevilo(G, mnozice=None):
    if mnozice is None:
        mnozice = maksimalne_neodvisne_mnozice(G)
    m = len(mnozice)
    n = G.order()
    p = MixedIntegerLinearProgram(maximization = False)
    y = p.new_variable(real=True, nonnegative=True)
    p.set_objective(sum([y[i] for i in range(m)]))
    for v in G:
        p.add_constraint(sum(y[i] for i in range(m) if v in mnozice[i]) >= 1)

    return p.solve()

def deljeno_klicno_stevilo(G, mnozice=None):
    if mnozice is None:
        mnozice = maksimalne_neodvisne_mnozice(G)
    m = len(mnozice)
    n = G.order()
    p = MixedIntegerLinearProgram(maximization = True)
    y = p.new_variable(real=True, nonnegative=True)
    p.set_objective(sum([y[v] for v in G]))
    for i in range(m):
        p.add_constraint(sum(y[v] for v in mnozice[i]) <= 1)

    return p.solve()

Tako lahko neposredno kličeta deljeno_kromaticno_stevilo in deljeno_klicno_stevilo na poljubnem grafu - da se pa izogneta dvakratnemu iskanju maksimalnih neodvisnih množic, lahko to storita vnaprej:

mnozice = maksimalne_neodvisne_mnozice(G)
deljeno_kromaticno_stevilo(G, mnozice)
deljeno_klicno_stevilo(G, mnozice)

[MancaStrgar]

Imam še eno vprašanje. Kaj točno nam naredi ta del kode pri iskanju maksimalnih neodvisnih množic

if C in pregledane:
            continue
        pregledane.add(C)

[jaanos]

Množica pregledane hrani tiste neodvisne množice, ki so bile že pregledane (torej tiste, na katerih se je že klical backtrack). Do iste množice lahko namreč prideta na več načinov (več vrstnih redov dodajanja vozlišč) - tako poskrbita, da se že pregledane množice in vse njihove razširitve ne pregledajo več kot enkrat. Če je bila torej množica C že pregledana, se zanka nadaljuje z novim vozliščem, sicer se pa označi kot pregledana.

[MancaStrgar]

Pozdravljeni, mi lahko samo prosim poveste, ali sem pravilno pokomentirala ti dve funkciji:

def deljeno_kromaticno_stevilo(G, mnozice=None):
    if mnozice is None: # če nimamo definiranega seznama z maksimalnimi neodvisnimi množicami, ga sedaj s pomočjo funkcije
        mnozice = maksimalne_neodvisne_mnozice(G)   # maksimalne<-neodvisne_mnozice(G) definiramo
    m = len(mnozice) #m predstavlja število maksimalnih neodvisnih množic grafa G
    n = G.order()  #n prestravlja število vozlišč grafa G
    p = MixedIntegerLinearProgram(maximization = False) #linearni program, kjer iščemo minimum
    y = p.new_variable(real=True, nonnegative=True) #def. realno in nenegativno spremenljivko y
    p.set_objective(sum([y[i] for i in range(m)])) #iščemo min vsote y[i]
    for v in G:
        p.add_constraint(sum(y[i] for i in range(m) if v in mnozice[i]) >= 1) #vsako vozlišče se mora vsaj enkrat pojaviti v mnozici

    return p.solve()

def deljeno_klicno_stevilo(G, mnozice=None):
    if mnozice is None:  # če nimamo definiranega seznama z maksimalnimi neodvisnimi množicami, ga sedaj s pomočjo funkcije
        mnozice = maksimalne_neodvisne_mnozice(G) # maksimalne<-neodvisne_mnozice(G) definiramo
    m = len(mnozice)  #m predstavlja število maksimalnih neodvisnih množic grafa G
    n = G.order()     #n prestravlja število vozlišč grafa G
    p = MixedIntegerLinearProgram(maximization = True) #linearni program, kjer iščemo maksimum
    y = p.new_variable(real=True, nonnegative=True)        #def. realno in nenegativno spremenljivko y
    p.set_objective(sum([y[v] for v in G]))               #iščemo max vsote y[v]
    for i in range(m):
        p.add_constraint(sum(y[v] for v in mnozice[i]) <= 1) # v vsaki maksimalni neod. mn. se vsako vozlišče lahko pojavi največ enkrat

    return p.solve()

[jaanos]

Izgleda v redu.