Studoši

Blic:

Zadatak:

Kod za nadopuniti:

def AugmentedHierholzer(G: Dict[str, List[str]], start: str) -> Tuple[List[str], List[List[str]]]:
    stog = deque()
    stog.append(start)
    
    ####################
    ## YOUR CODE HERE ##
    ####################
    
    while stog:
        u = stog[-1]
        adj = G[u]
        if len(adj) > 0:
            v = G[u][0]
            stog.append(v)
            G[u].remove(v)
            G[v].remove(u)
        else:
            ####################
            ## YOUR CODE HERE ##
            ####################
            stog.pop()
    return ...

Kod za testni primjer:

import copy
G = {'a': ['b', 'c', 'd', 'e'],
     'b': ['a', 'd', 'e'],
     'c': ['a', 'e'],
     'd': ['a', 'b', 'e'],
     'e': ['a', 'b', 'c', 'd']}
G1 = copy.deepcopy(G)
path, circles = AugmentedHierholzer(G1, 'b')
path.reverse()
assert path == ['b', 'a', 'c', 'e', 'a', 'd', 'b', 'e', 'd']
assert circles == [['d', 'e', 'b', 'd'], ['e', 'b', 'd', 'a', 'e'], ['a', 'e', 'c', 'a'], ['b', 'd', 'a', 'e', 'c', 'a', 'b']]

G1 = copy.deepcopy(G)
path, circles = AugmentedHierholzer(G1, 'd')
path.reverse()
assert path == ['d', 'a', 'b', 'd', 'e', 'a', 'c', 'e', 'b']
assert circles == [['e', 'c', 'a', 'e'], ['b', 'e', 'c', 'a', 'e', 'd', 'b'], ['a', 'e', 'd', 'b', 'a'], ['d', 'b', 'a', 'd']]

tempest zna li netko kako dobiju krugove u ovom redoslijedu? Mislim da nije bitno ali ako su testovi ovakvi onda valjda ocekuju da bude isti redoslijed ko njima

Nova pitanja
Zadatak je isti

from typing import Dict, Hashable, List,Set
import collections
import random


class DirectedGraph(object):
    def __init__(self, adjacency_list:Dict[Hashable,Set]=None):
        if adjacency_list is None:
            adjacency_list = []
        self.vertex_dict = adjacency_list

    def getVertices(self)->List:
        """return all vertex labels

        Returns:
            List: list of all vertex-labels in the graph
        """
        return list(self.vertex_dict.keys())

    def getNeighbors(self, vertex:Hashable)->Set:
        """returns a list of vertex neighbors

        Args:
            vertex (Hashable): Vertex label

        Raises:
            ValueError: if there is no vertex with a given label
            in the graph

        Returns:
            Set: set of neighbors
        """
        if vertex not in self.vertex_dict.keys():
            raise ValueError(f'Vertex {vertex} does not exist in this graph')
        return self.vertex_dict[vertex]


def detect_cycle(graph: DirectedGraph)->bool:
    """Detects if there exists a cycle in directed graph that might be consisting
    of disconnected components

    Args:
        graph (DirectedGraph): input graph

    Returns:
        bool: True if there is cycle in a graph, else False
    """
    visited = []
    stack = collections.deque()
    for source in graph.getVertices():
        #TODO: dovrsite ovdje orkestraciju preko komponenti 
    return False


def detect_cycle_recursive(graph:DirectedGraph, current_vertex:Hashable, visited: List, stack:collections.deque)->bool:
    """recursively searches for any cycle in connected components

    Args:
        graph (DirectedGraph): input graph
        current_vertex (Hashable): search goes from this vertex
        visited (List): mark visited vertices
        stack (collections.deque): current DFS track

    Returns:
        bool: True if found cycle, False
    """
    visited.append(current_vertex)
    stack.append(current_vertex)
    for v in graph.getNeighbors(current_vertex):
        #TODO: dovrsite ovdje kod za komponentu
    return False


############# test #############

def construct_deterministic1():
    graph_adjacency = {}
    graph_adjacency['a'] = {'b'}
    graph_adjacency['b'] = {'c'}
    graph_adjacency['c'] = {'d', 'e', 'f'}
    graph_adjacency['d'] = set()
    graph_adjacency['e'] = {'b'}
    graph_adjacency['f'] = {'b'}
    return DirectedGraph(graph_adjacency)


def construct_deterministic2():
    graph_adjacency = {}
    graph_adjacency['a'] = {'b'}
    graph_adjacency['b'] = {'c'}
    graph_adjacency['c'] = set()
    graph_adjacency['d'] = set()
    graph_adjacency['e'] = {'b'}
    graph_adjacency['f'] = {'b'}
    return DirectedGraph(graph_adjacency)
    
def test_detect_cycle(constructor):
    is_cyclical = detect_cycle(constructor())
    print(is_cyclical)


# ako Vam kod ne radi na ova dva primjera ispod, dobivate automatski 0 bodova

test_detect_cycle(construct_deterministic1) # prints True

test_detect_cycle(construct_deterministic2) # prints False

Labos u 13:
Ponovljeno sve i nema novih pitanja. Zadatak je bio detekcija od kolege Olive Oil

FERella

Ja sam dobio detekciju ciklusa preko DFS-a, kao u postu gore: Olive Oil
Na blicu nisam dobio nijedno novo pitanje.

zaboravila sam kopirati kod koji dali, ovo je što imam…
sjecam se da su implemtirane funkcije: NewAdjMatrix, edges, FindCycle, FindCycle_r

mrkva jel ta funkcija FindCycle pogresno opisana? Valjda prima graf ili tezinsku matricu grafa a ne minimalno razapinjujuce stablo?

azex bih kada bih skuzila zasto odjednom ne da formatirati kod - skuzila sam minutu nakon sto je proslo vrijeme za editanje

mrkva
DIJKSTRA MST
hint: ako cete imati u MST zadatku time exceeded error na jednom od zadataka i ako ste u NewAdjMatrix copy stavili u True, probajte promijeniti u False, tj. ostaviti default vrijednost

dobiveni kod

import collections
import copy
def _NewAdjMatrix(G, copy=False):
    am = {}
    for u in G:
        am[u] = {}
        for v in G[u]:
            if copy:
                am[u][v] = G[u][v]
            else:
                am[u][v] = 0
    return am
def _FindCyclesMatrix(G):
    visited = []
    cycs = []
    S = collections.deque()
    for u0 in G:
        if u0 not in visited:
            P = _NewAdjMatrix(G)
            _FindCyclesMatrix_r(G, P, u0, visited, S, cycs)
    return cycs
def _FindCyclesMatrix_r(G, P, u, visited, S, cycs):
    visited.append(u)
    S.append(u)
    n = []
    for v in G[u]:
        if G[u][v] != 0: n.append(v)
    for v in n:
        if v not in S:
            P[u][v] = P[v][u] = 1
            _FindCyclesMatrix_r(G, P, v, visited, S, cycs)
        else:
            if P[u][v] != 1:  # prevents turning back to the previous vertex in undirected graphs
                c = []
                for vx in reversed(S):
                    c.append(vx)
                    if vx is v:
                        break
                if c not in cycs:
                    cycs.append(c)
    S.pop()
def _adj(G, u):
    a = []
    for v in G[u]:
        if G[u][v] != 0:
            a.append(v)
    return a
def _edges(G):
    e = {}
    for u in G:
        for v in _adj(G, u):
            if not (v, u) in e.keys():
                e[(u, v)] = G[u][v]
    return e
def FindCycle(G: dict) -> dict:
    c = _FindCyclesMatrix(G)
    E2 = {}
    E = _edges(G)
    if len(c) > 0:
        c = c[0]
        cp = [(c[-1], c[0])]
        for i in range(len(c) - 1):
            cp.append((c[i], c[i + 1]))
        for cpi in cp:
            E2 = {**E2, **dict(filter(lambda x: x[0][0] in cpi and x[0][1] in cpi, E.items()))}
    return E2
#za testiranje#
    G = {'a': {'a': 0, 'b': 2, 'c': 3, 'd': 0},
         'b': {'a': 2, 'b': 0, 'c': 5, 'd': 0},
         'c': {'a': 3, 'b': 5, 'c': 0, 'd': 0},
         'd': {'a': 0, 'b': 0, 'c': 0, 'd': 0}}

u 13 ova dva nova pitanja sa slozenostima + Dijkstra MST

idontwannabemyself bi li mogao ti kopirati dani kod za taj zadatak?

Rene
idu po stogu i kupe krugove od trenutnog vrha na stogu, ako postoji, pa do ponovne pojave tog slova (krug/ciklus, ne)
ono sto rade u slucaju kad postoji jedan unutar drugog, zapravo prvo zapisu onaj unutar pa tek onaj vani, iako ce vrlo vjerojatno vecini implementacijski doci i spremiti se prvo vanjski pa unutarnji jer tako i idu slova po stogu (tako je i meni)

kak sam ja to “popravila” da mi ispadne kao njima je da sam nakon dobivenih svih krugova isla jos jednom po njima i provjerila postoji li neki krug koji je u cijelosti sadrzan u nekom drugom (hint: jedan su pored drugog jer tako i idu po stogu), i ako jest, onda im zamijenila pozicije u listi i dobio se ispis koji su oni htjeli

koode7 Hierholzer* i prezentacija 10, slajd 36

Rene ja sam reverseala path (odnosno kopiju koju sam koristila za krugove) i onda svaki krug i na kraju listu svih krugva i dobijem taj redoslijed njihov

EDIT: malo lose objasnjenje, al krugove sam trazila iz patha na kraju funkcije, sto vj nije optimalno

idontwannabemyself je li dovoljno provjeriti samo za susjedne, jel moguce da se unutar jednog kruga pojavi drugi krug, te unutar tog kruga jos jedan
ne kuzim zast su ovo zakomplicirali s ispisom

Evo braćo teorije.

Mozete li pokrenut lab?

foobar ne, kaže time has passed

foobar tako je i meni bilo prosli tjedan, samo je nakon par min proradilo.

Je li itko uspio dosad uci ili jos uvijek nista

Extended_mix
i meni istu poeuku daje