es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Representando el grafo de enlaces web inversos en Scheme.

15 Jul, 2023 Programación

Hola, estoy intentando hacer unos ejercicios en Scheme y puedo hacerlos usando Python (usando hashmaps). Tengo un gráfico de enlaces web hecho de enlaces de sitios web, de manera que para cada sitio web considerado, sé qué sitios web contienen enlaces a él.

Estoy tratando de hacer una función para representar el gráfico de enlaces web invertido. Estoy intentando usar listas para la representación.

Si la entrada es [[a, b, c], [b, c, e], [c, b, a]], esto significa que el sitio a está enlazado desde los sitios b y c, el sitio b está enlazado desde c y e, y el sitio c está enlazado desde los sitios b y a.

Por lo tanto, mi función debería devolver la lista: [[a, c], [b, a, c], [c, a, b], [e, b]]. En este caso, el primer elemento de cada sublista es el sitio de origen y la cola representa todos los sitios de destino a los que está enlazado.

¡Gracias por tu ayuda!

Este es el código de Python que parece funcionar, solo como referencia:

def reverse_linkgraph(G):
    hash_map = {}
    for u, *v in G:        
        for to in v:
            if to not in hash_map:
                hash_map[to] = set()
            hash_map[to].add(u)

    rev_g = []
    print(hash_map)
    for k,v in hash_map.items():       
        rev_g.append([k, *v])
    return rev_g
Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para crear el grafo inverso de enlaces web en Scheme utilizando listas como representación, podemos seguir un enfoque similar al código de Python. Utilizaremos una tabla hash para almacenar los enlaces desde cada sitio de destino a sus sitios de origen. Luego, iteraremos sobre la tabla hash y crearemos el grafo inverso representado como una lista de listas.

    Aquí está el código en Scheme:

    (define (reverse-linkgraph G)
  (define hash-map (make-hash))

  ; Poblar la tabla hash con los sitios de destino como claves y los sitios de origen como valores
  (for-each (lambda (lst)
              (let ((dest (car lst))
                    (srcs (cdr lst)))
                (for-each (lambda (src)
                            (let ((lst (hash-map-get hash-map src)))
                              (if (null? lst)           ; Si la clave no existe en la tabla hash
                                  (hash-map-put! hash-map src (list dest)) ; Crear un nuevo par clave-valor
                                  (set! lst (cons dest lst))))))  ; De lo contrario, añadir el sitio de destino a la lista existente
                         srcs)))
            G)

  ; Crear el grafo inverso como una lista de listas
  (let ((rev-g '()))
    (hash-for-each hash-map (lambda (k v)
                              (set! rev-g (cons (cons k v) rev-g))))
    rev-g))

    Vamos a probar la función:

    (reverse-linkgraph '((a b c) (b c e) (c b a)))
; => ((a c) (b a c) (c a b) (e b))

    La salida es el grafo inverso esperado representado como una lista de listas. El primer elemento de cada sublista es el sitio de origen, y el resto de los elementos representan los sitios de destino a los que enlaza.

Comments are closed.