Graph - Grafos

Como usar la documentación

Para leer la guía de uso de la documentación, por favor diríjase a la sección Guía de documentación.

Elementos

vertex.py

new_vertex(key, value)

Crea un nuevo vertice con la llave key, el valor value y sus adyacentes vacio.

El vertice es creado con los siguientes atributos:

Parameters:

  • key (any) – Llave del vertice

  • value (any) – Valor del vertice

Returns:

Vertice recien creado

Return type:

vertex

Example:
# App/logic.py
from DataStructures.Graph import vertex as V

# Crear un nuevo vertice
vertex = V.new_vertex(1, {"nombre": "A"})
print(vertex)
# Salida esperada:
# {
#   'key': 1,
#   'value': {
#     'nombre': 'A'
#   },
#   'adjacents': {
#     'prime': 109345121,
#     'capacity': 2,
#     'scale': 96269727,
#     'shift': 48310553,
#     'table': {
#       'elements': [
#         {
#           'key': None,
#           'value': None
#         },
#         {
#           'key': None,
#           'value': None
#         }
#       ],
#       'size': 2
#     },
#     'current_factor': 0,
#     'limit_factor': 0.5,
#     'size': 0
#   }
# }
#
get_key(vertex)

Retorna el key del vertice vertex.

Parameters:

vertex (vertex) – Vertice del cual se quiere obtener la llave

Returns:

Llave del vertice

Return type:

any

Example:
# App/logic.py
from DataStructures.Graph import vertex as V

# Crear un nuevo vertice
vertex = V.new_vertex(1, {"nombre": "A"})
print(V.get_key(vertex))
# Salida esperada: 1
get_value(vertex)

Retorna el value del vertice vertex

Parameters:

vertex (vertex) – Vertice del cual se quiere obtener el valor

Returns:

Valor del vertice

Return type:

any

Example:
# App/logic.py
from DataStructures.Graph import vertex as V

# Crear un nuevo vertice
vertex = V.new_vertex(1, {"nombre": "A"})
print(V.get_value(vertex))
# Salida esperada: {'nombre': 'A'}
set_value(vertex, new_value)

Cambia el value del vertice vertex por el valor new_value

Parameters:

  • vertex (vertex) – Vertice al cual se le quiere cambiar el valor

  • value (any) – Nuevo valor del vertice

Example:
# App/logic.py
from DataStructures.Graph import vertex as V

# Crear un nuevo vertice
vertex = V.new_vertex(1, {"nombre": "A"})
print(V.get_value(vertex))
# Salida esperada: {'nombre': 'A'}

# Cambiar el valor del vertice
V.set_value(vertex, {"nombre": "B"})
print(V.get_value(vertex))
# Salida esperada: {'nombre': 'B'}
get_adjacents(vertex)

Retorna el mapa con los arcos map_linear_probing del vertice vertex

Parameters:

vertex (vertex) – Vertice del cual se quiere obtener el mapa de arcos

Returns:

Mapa de arcos del vertice

Return type:

map_linear_probing

Example:
# App/logic.py
from DataStructures.Graph import vertex as V

# Crear un nuevo vertice
key_u = "KEY_U"
key_v = "KEY_V"
key_w = "KEY_W"
vertex_u = V.new_vertex(key_u, {"nombre": "Vertice U"})

V.add_adjacent(vertex_u, key_v, 10)
V.add_adjacent(vertex_u, key_w, 15)

print(V.get_adjacents(vertex_u))
# Salida esperada:
# {
#   'prime': 109345121,
#   'capacity': 5,
#   'scale': 60497948,
#   'shift': 74210530,
#   'table': {
#     'elements': [
#       {
#         'key': None,
#         'value': None
#       },
#       {
#         'key': 'KEY_V',
#         'value': {
#           'to': 'KEY_V',
#           'weight': 10
#         }
#       },
#       {
#         'key': None,
#         'value': None
#       },
#       {
#         'key': 'KEY_W',
#         'value': {
#           'to': 'KEY_W',
#           'weight': 15
#         }
#       },
#       {
#         'key': None,
#         'value': None
#       }
#     ],
#     'size': 5
#   },
#   'current_factor': 0.4,
#   'limit_factor': 0.5,
#   'size': 2
# }
get_edge(vertex, key_v)

Retorna el edge adyacente en el vertice vertex con la llave key_v Si no existe el arco, retorna None.

Parameters:

  • vertex (vertex) – Vértice del cual se quiere obtener un arco adyacente con el vértice con la llave key_v

  • key_v (any) – Llave del vértice destino del arco que se busca con origen el vertex['key']

Returns:

El arco entre los vertices con llaves vertex['key'] y key_v. Valor None si no existe.

Return type:

edge

Example:
# App/logic.py
from DataStructures.Graph import vertex as V

# Crear un nuevo vertice
key_u = "KEY_U"
vertex_u = V.new_vertex(key_u, {"nombre": "Vertice U"})

# llaves de vertices existentes
key_v = "KEY_V"
key_w = "KEY_W"
key_x = "KEY_X"

V.add_adjacent(vertex_u, key_v, 10)
V.add_adjacent(vertex_u, key_w, 15)

# Obtener el arco con vertice adyacente
print(V.get_edge(vertex_u, key_v))
# Salida esperada: {'to': 'KEY_V', 'weight': 10}

# Obtener arco con vertice no adyacente
print(V.get_edge(vertex_u, key_x))
# Salida esperada: None
add_adjacent(vertex, key_to_vertex, weight)

Agrega un arco en el vertice vertex hacia el vertice con llave key_to_vertex y peso weight

Parameters:

  • vertex (vertex) – Vertice origen del nuevo arco

  • key_to_vertex (any) – Llave del vertice destino del nuevo arco

  • weight (double) – Peso del arco

Returns:

Vertice con el arco agregado

Return type:

vertex

Example:
# App/logic.py
from DataStructures.Graph import vertex as V

# Crear un nuevo vertice
key_u = "KEYU"
key_v = "KEYV"
key_w = "KEYW"
vertex_u = V.new_vertex(key_u, {"nombre": "Vertice U"})

vertex_u = V.add_adjacent(vertex_u, key_v, 10)
print(vertex_u)
# Salida esperada:
# {
#   'key': 'KEYU',
#   'value': {
#     'nombre': 'Vertice U'
#   },
#   'adjacents': {
#     'prime': 109345121,
#     'capacity': 5,
#     'scale': 86271125,
#     'shift': 104195991,
#     'table': {
#       'elements': [
#         {
#           'key': None,
#           'value': None
#         },
#         {
#           'key': None,
#           'value': None
#         },
#         {
#           'key': None,
#           'value': None
#         },
#         {
#           'key': 'KEYV',
#           'value': {
#             'to': 'KEYV',
#             'weight': 10
#           }
#         },
#         {
#           'key': None,
#           'value': None
#         }
#       ],
#       'size': 5
#     },
#     'current_factor': 0.2,
#     'limit_factor': 0.5,
#     'size': 1
#   }
# }

# Agregar otro vertice adyacente
vertex_u = V.add_adjacent(vertex_u, key_w, 15)
print(vertex_u)
# Salida esperada:
# {
#   'key': 'KEYU',
#   'value': {
#     'nombre': 'Vertice U'
#   },
#   'adjacents': {
#     'prime': 109345121,
#     'capacity': 5,
#     'scale': 54639149,
#     'shift': 57004010,
#     'table': {
#       'elements': [
#         {
#           'key': None,
#           'value': None
#         },
#         {
#           'key': 'KEYV',
#           'value': {
#             'to': 'KEYV',
#             'weight': 10
#           }
#         },
#         {
#           'key': None,
#           'value': None
#         },
#         {
#           'key': None,
#           'value': None
#         },
#         {
#           'key': 'KEYW',
#           'value': {
#             'to': 'KEYW',
#             'weight': 15
#           }
#         }
#       ],
#       'size': 5
#     },
#     'current_factor': 0.4,
#     'limit_factor': 0.5,
#     'size': 2
#   }
# }
degree(vertex)

Retorna el grado del vertice vertex.

Parameters:

vertex (vertex) – Vertice de consulta

Returns:

Grado del vertice (equivale al numero de sus adyacentes)

Return type:

int

Example:
# App/logic.py
from DataStructures.Graph import vertex as V

# Crear un nuevo vertice
key_u = "KEYU"
key_v = "KEYV"
key_w = "KEYW"
vertex_u = V.new_vertex(key_u, {"nombre": "Vertice U"})

vertex_u = V.add_adjacent(vertex_u, key_v, 10)
print(V.degree(vertex_u))
# Salida esperada: 1

vertex_u = V.add_adjacent(vertex_u, key_w, 15)
print(V.degree(vertex_u))
# Salida esperada: 2

edge.py

new_edge(key_v, weight=0)

Crea un nuevo arco hacia el vertices con llave key_v con un peso weight

Se crea un arco con los siguientes atributos:

  • to: llave del vertice destino

  • weight: Peso del arco

Parameters:

  • key_v (any) – Llave del vertice destino del arco

  • weight (double) – Peso del arco

Returns:

Arco recien creado

Return type:

edge

Example:
from DataStructures.Graph import edge as E

# Crear un nuevo arco
edge = E.new_edge("A", 5)
print(edge)
# Ssalida esperada: {'to': 'A', 'weight': 5}
to(edge)

Retorna la llave de vertice destino del arco edge

Parameters:

edge (edge) – Arco del cual se quiere obtener el vertice destino

Returns:

Llave del vertice destino del arco

Return type:

any

Example:
from DataStructures.Graph import edge as E

# Crear un nuevo arco
edge = E.new_edge("A", 5)
print(E.to(edge))
# Salida esperada: A
weight(edge)

Retorna el peso del arco edge

Parameters:

edge (edge) – Arco del cual se quiere obtener el peso

Returns:

Peso del arco

Return type:

double

Example:
from DataStructures.Graph import edge as E

# Crear un nuevo arco
edge = E.new_edge("A", 5)
print(E.weight(edge))
# Salida esperada: 5
set_weight(edge, new_weight)

Actualiza el peso del arco edge por el valor new_weight

Parameters:

  • edge (edge) – Arco al cual se le quiere cambiar el peso

  • weight (double) – Nuevo peso del arco

Returns:

Arco con el nuevo peso

Return type:

edge

Example:
from DataStructures.Graph import edge as E

# Crear un nuevo arco
edge = E.new_edge("A", 5)
print(E.weight(edge))
# Ssalida esperada: 5

# Cambiar el peso del arco
E.set_weight(edge, 10)
print(E.weight(edge))
# Salida esperada: 10

Implementaciones

digraph.py

new_graph(order)

Crea un grafo dirigido vacio.

Se crea un grafo con los siguientes atributos:

Parameters:

order (int) – Numero de vertices inicial del grafo.

Returns:

Grafo vacio (sin vertices ni arcos)

Return type:

digraph

Importante

Para asegurar obtener los mismos resultados en los mapas de los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

Example:
# App/logic.py
from DataStructures.Graph import digraph as G

# Crea un grafo vacio
my_graph = G.new_graph(1)
print(my_graph)
# Salida esperada a continuacion:

Salida esperada:

{
    'vertices': {
        'prime': 109345121,
        'capacity': 3,
        'scale': 1,
        'shift': 0,
        'table': {
            'elements': [
                {
                    'key': None,
                    'value': None
                },
                {
                    'key': None,
                    'value': None
                },
                {
                    'key': None,
                    'value': None
                }
            ],
            'size': 3
        },
        'current_factor': 0,
        'limit_factor': 0.5,
        'size': 0
    },
    'num_edges': 0
}
insert_vertex(my_graph, key_u, info_u)

Agrega un nuevo vertice al grafo my_graph.

Se crea un nuevo vertice con la llave key_u, la informacion info_u y con los adyacentes vacio. Posteriomente, el vertice se agrega al mapa de vertices del grafo. Nota: Si el vertice existe, se reemplaza toda su informacion.

Parameters:

  • my_graph (digraph) – Grafo al que se le desea agregar el nuevo vertice

  • key_u (any) – Llave del nuevo vertice

  • info_u (any) – Informacion asociada al vertice

Returns:

El grafo con el nuevo vertice

Return type:

digraph

Importante

Para asegurar obtener los mismos resultados en los mapas de los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

Example:
1# App/logic.py
2from DataStructures.Graph import digraph as G
3
4# Crea un grafo vacio
5my_graph = G.new_graph(1)
6print(my_graph)
7# Salida esperada a continuacion:
Salida esperada creacion de un grafo vacio:
{
  'vertices': {
    'prime': 109345121,
    'capacity': 3,
    'scale': 1,
    'shift': 0,
    'table': {
      'elements': [
        {
          'key': None,
          'value': None
        },
        {
          'key': None,
          'value': None
        },
        {
          'key': None,
          'value': None
        }
      ],
      'size': 3
    },
    'current_factor': 0,
    'limit_factor': 0.5,
    'size': 0
  },
  'num_edges': 0
}

 8# Agrega un vertice al grafo
 9my_graph = G.insert_vertex(my_graph, "Armenia", {"nombre": "Armenia", "población": 300000})
10print(my_graph)
11# Salida esperada a continuacion:
Salida esperada al agregar un vertice:
{
  'vertices': {
    'prime': 109345121,
    'capacity': 3,
    'scale': 1,
    'shift': 0,
    'table': {
      'elements': [
        {
          'key': None,
          'value': None
        },
        {
          'key': 'Armenia',
          'value': {
            'key': 'Armenia',
            'value': {
              'nombre': 'Armenia',
              'población': 300000
            },
            'adjacents': {
              'prime': 109345121,
              'capacity': 2,
              'scale': 1,
              'shift': 0,
              'table': {
                'elements': [
                  {
                    'key': None,
                    'value': None
                  },
                  {
                    'key': None,
                    'value': None
                  }
                ],
                'size': 2
              },
              'current_factor': 0,
              'limit_factor': 0.5,
              'size': 0
            }
          }
        },
        {
          'key': None,
          'value': None
        }
      ],
      'size': 3
    },
    'current_factor': 0.3333333333333333,
    'limit_factor': 0.5,
    'size': 1
  },
  'num_edges': 0
}
Test Scenarios:

  • Inserta un vertice en un grafo vacio: Se crea un grafo vacio y se inserta un vertice.

    1# App/logic.py
2from DataStructures.Graph import digraph as G
3
4# Crea un grafo vacio
5my_graph = G.new_graph(1)
6print(my_graph)
7# Salida esperada a continuacion:
    Salida esperada creacion de un grafo vacio:
    {
  'vertices': {
    'prime': 109345121,
    'capacity': 3,
    'scale': 1,
    'shift': 0,
    'table': {
      'elements': [
        {
          'key': None,
          'value': None
        },
        {
          'key': None,
          'value': None
        },
        {
          'key': None,
          'value': None
        }
      ],
      'size': 3
    },
    'current_factor': 0,
    'limit_factor': 0.5,
    'size': 0
  },
  'num_edges': 0
}

     8# Agrega un vertice al grafo
 9my_graph = G.insert_vertex(my_graph, "Armenia", {"nombre": "Armenia", "población": 300000})
10print(my_graph)
11# Salida esperada a continuacion:
    Salida esperada al agregar un vertice:
    {
  'vertices': {
    'prime': 109345121,
    'capacity': 3,
    'scale': 1,
    'shift': 0,
    'table': {
      'elements': [
        {
          'key': None,
          'value': None
        },
        {
          'key': 'Armenia',
          'value': {
            'key': 'Armenia',
            'value': {
              'nombre': 'Armenia',
              'población': 300000
            },
            'adjacents': {
              'prime': 109345121,
              'capacity': 2,
              'scale': 1,
              'shift': 0,
              'table': {
                'elements': [
                  {
                    'key': None,
                    'value': None
                  },
                  {
                    'key': None,
                    'value': None
                  }
                ],
                'size': 2
              },
              'current_factor': 0,
              'limit_factor': 0.5,
              'size': 0
            }
          }
        },
        {
          'key': None,
          'value': None
        }
      ],
      'size': 3
    },
    'current_factor': 0.3333333333333333,
    'limit_factor': 0.5,
    'size': 1
  },
  'num_edges': 0
}

  • Inserta un vertice en un grafo con varios vertices: Se crea un grafo con varios vertices y se inserta otro vertice.

    1# App/logic.py
2from DataStructures.Graph import digraph as G
3
4# Crea un grafo vacio
5my_graph = G.new_graph(1)
6my_graph = G.insert_vertex(my_graph, "Armenia", {"nombre": "Armenia", "población": 300000})
7my_graph = G.insert_vertex(my_graph, "Bogotá", {"nombre": "Bogotá", "población": 8000000})
8print(my_graph)
9# Salida esperada a continuacion:
    Salida esperada creacion de un grafo vacio:
    {
  'vertices': {
    'prime': 109345121,
    'capacity': 7,
    'scale': 1,
    'shift': 0,
    'table': {
      'elements': [
        {
          'key': None,
          'value': None
        },
        {
          'key': None,
          'value': None
        },
        {
          'key': None,
          'value': None
        },
        {
          'key': 'Armenia',
          'value': {
            'key': 'Armenia',
            'value': {
              'nombre': 'Armenia',
              'población': 300000
            },
            'adjacents': {
              'prime': 109345121,
              'capacity': 2,
              'scale': 1,
              'shift': 0,
              'table': {
                'elements': [
                  {
                    'key': None,
                    'value': None
                  },
                  {
                    'key': None,
                    'value': None
                  }
                ],
                'size': 2
              },
              'current_factor': 0,
              'limit_factor': 0.5,
              'size': 0
            }
          }
        },
        {
          'key': None,
          'value': None
        },
        {
          'key': 'Bogotá',
          'value': {
            'key': 'Bogotá',
            'value': {
              'nombre': 'Bogotá',
              'población': 8000000
            },
            'adjacents': {
              'prime': 109345121,
              'capacity': 2,
              'scale': 1,
              'shift': 0,
              'table': {
                'elements': [
                  {
                    'key': None,
                    'value': None
                  },
                  {
                    'key': None,
                    'value': None
                  }
                ],
                'size': 2
              },
              'current_factor': 0,
              'limit_factor': 0.5,
              'size': 0
            }
          }
        },
        {
          'key': None,
          'value': None
        }
      ],
      'size': 7
    },
    'current_factor': 0.2857142857142857,
    'limit_factor': 0.5,
    'size': 2
  },
  'num_edges': 0
}

     8# Agrega un vertice al grafo
 9my_graph = G.insert_vertex(my_graph, "Cali", {"nombre": "Cali", "población": 2000000})
10print(my_graph)
11# Salida esperada a continuacion:
    Salida esperada al agregar un vertice:
    {
  'vertices': {
    'prime': 109345121,
    'capacity': 7,
    'scale': 1,
    'shift': 0,
    'table': {
      'elements': [
        {
          'key': None,
          'value': None
        },
        {
          'key': None,
          'value': None
        },
        {
          'key': 'Cali',
          'value': {
            'key': 'Cali',
            'value': {
              'nombre': 'Cali',
              'población': 2000000
            },
            'adjacents': {
              'prime': 109345121,
              'capacity': 2,
              'scale': 1,
              'shift': 0,
              'table': {
                'elements': [
                  {
                    'key': None,
                    'value': None
                  },
                  {
                    'key': None,
                    'value': None
                  }
                ],
                'size': 2
              },
              'current_factor': 0,
              'limit_factor': 0.5,
              'size': 0
            }
          }
        },
        {
          'key': None,
          'value': None
        },
        {
          'key': 'Armenia',
          'value': {
            'key': 'Armenia',
            'value': {
              'nombre': 'Armenia',
              'población': 300000
            },
            'adjacents': {
              'prime': 109345121,
              'capacity': 2,
              'scale': 1,
              'shift': 0,
              'table': {
                'elements': [
                  {
                    'key': None,
                    'value': None
                  },
                  {
                    'key': None,
                    'value': None
                  }
                ],
                'size': 2
              },
              'current_factor': 0,
              'limit_factor': 0.5,
              'size': 0
            }
          }
        },
        {
          'key': 'Bogotá',
          'value': {
            'key': 'Bogotá',
            'value': {
              'nombre': 'Bogotá',
              'población': 8000000
            },
            'adjacents': {
              'prime': 109345121,
              'capacity': 2,
              'scale': 1,
              'shift': 0,
              'table': {
                'elements': [
                  {
                    'key': None,
                    'value': None
                  },
                  {
                    'key': None,
                    'value': None
                  }
                ],
                'size': 2
              },
              'current_factor': 0,
              'limit_factor': 0.5,
              'size': 0
            }
          }
        },
        {
          'key': None,
          'value': None
        }
      ],
      'size': 7
    },
    'current_factor': 0.42857142857142855,
    'limit_factor': 0.5,
    'size': 3
  },
  'num_edges': 0
}
update_vertex_info(my_graph, key_u, new_info_u)

Actualiza la información del vertice con llave key_u con la nueva información new_info_u.

Se busca el vertice en el grafo y se actualiza su información. Si el vertice existe, se actualiza su información y se retorna el grafo actualizado. Si el vertice no existe, se retorna el grafo sin actualizar.

Parameters:

  • my_graph (digraph) – El grafo sobre el que se ejecuta la operacion

  • key_u (any) – Llave del vertice que se desea actualizar

  • new_info_u (any) – La nueva informacion asociada al vertice

Returns:

El grafo con la nueva informacion asociada al vertice (si existe)

Return type:

digraph

Importante

Para asegurar obtener los mismos resultados en los mapas de los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

Example:
1# App/logic.py
2from DataStructures.Graph import digraph as G
3
4# Crea un grafo vacio
5my_graph = G.new_graph(1)
6
7my_graph = G.insert_vertex(my_graph, "Madrid", {"nombre": "Madrid", "pais": "España"})
8print(my_graph)

{
  "vertices": {
    "prime": 109345121,
    "capacity": 3,
    "scale": 1,
    "shift": 0,
    "table": {
      "elements": [
        {
          "key": null,
          "value": null
        },
        {
          "key": "Madrid",
          "value": {
            "key": "Madrid",
            "value": {
              "nombre": "Madrid",
              "pais": "España"
            },
            "adjacents": {
              "prime": 109345121,
              "capacity": 2,
              "scale": 1,
              "shift": 0,
              "table": {
                "elements": [
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": null,
                    "value": null
                  }
                ],
                "size": 2
              },
              "current_factor": 0,
              "limit_factor": 0.5,
              "size": 0
            }
          }
        },
        {
          "key": null,
          "value": null
        }
      ],
      "size": 3
    },
    "current_factor": 0.3333333333333333,
    "limit_factor": 0.5,
    "size": 1
  },
  "num_edges": 0
}

 9my_graph = G.update_vertex_info(my_graph, "Madrid", {"nombre": "Madrid", "pais": "Colombia"})
10# Salida esperada:

{
  "vertices": {
    "prime": 109345121,
    "capacity": 3,
    "scale": 1,
    "shift": 0,
    "table": {
      "elements": [
        {
          "key": "Madrid",
          "value": {
            "key": "Madrid",
            "value": {
              "nombre": "Madrid",
              "pais": "Colombia"
            },
            "adjacents": {
              "prime": 109345121,
              "capacity": 2,
              "scale": 1,
              "shift": 0,
              "table": {
                "elements": [
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": null,
                    "value": null
                  }
                ],
                "size": 2
              },
              "current_factor": 0,
              "limit_factor": 0.5,
              "size": 0
            }
          }
        },
        {
          "key": null,
          "value": null
        },
        {
          "key": null,
          "value": null
        }
      ],
      "size": 3
    },
    "current_factor": 0.3333333333333333,
    "limit_factor": 0.5,
    "size": 1
  },
  "num_edges": 0
}
Test Scenario:

  • Vertice existente: Actualiza la información de un vértice existente en el grafo.

    1# App/logic.py
2from DataStructures.Graph import digraph as G
3
4# Crea un grafo vacio
5my_graph = G.new_graph(1)
6
7my_graph = G.insert_vertex(my_graph, "Madrid", {"nombre": "Madrid", "pais": "España"})
8print(my_graph)
9# Salida esperada:
    Salida esperada
    {
"vertices": {
    "prime": 109345121,
    "capacity": 3,
    "scale": 1,
    "shift": 0,
    "table": {
    "elements": [
        {
        "key": null,
        "value": null
        },
        {
        "key": "Madrid",
        "value": {
            "key": "Madrid",
            "value": {
            "nombre": "Madrid",
            "pais": "España"
            },
            "adjacents": {
            "prime": 109345121,
            "capacity": 2,
            "scale": 1,
            "shift": 0,
            "table": {
                "elements": [
                {
                    "key": null,
                    "value": null
                },
                {
                    "key": null,
                    "value": null
                }
                ],
                "size": 2
            },
            "current_factor": 0,
            "limit_factor": 0.5,
            "size": 0
            }
        }
        },
        {
        "key": null,
        "value": null
        }
    ],
    "size": 3
    },
    "current_factor": 0.3333333333333333,
    "limit_factor": 0.5,
    "size": 1
},
"num_edges": 0
}

     9my_graph = G.update_vertex_info(my_graph, "Madrid", {"nombre": "Madrid", "pais": "Colombia"})
10# Salida esperada:
    Salida esperada creacion de un grafo vacio:
    {
"vertices": {
    "prime": 109345121,
    "capacity": 3,
    "scale": 1,
    "shift": 0,
    "table": {
    "elements": [
        {
        "key": "Madrid",
        "value": {
            "key": "Madrid",
            "value": {
            "nombre": "Madrid",
            "pais": "Colombia"
            },
            "adjacents": {
            "prime": 109345121,
            "capacity": 2,
            "scale": 1,
            "shift": 0,
            "table": {
                "elements": [
                {
                    "key": null,
                    "value": null
                },
                {
                    "key": null,
                    "value": null
                }
                ],
                "size": 2
            },
            "current_factor": 0,
            "limit_factor": 0.5,
            "size": 0
            }
        }
        },
        {
        "key": null,
        "value": null
        },
        {
        "key": null,
        "value": null
        }
    ],
    "size": 3
    },
    "current_factor": 0.3333333333333333,
    "limit_factor": 0.5,
    "size": 1
},
"num_edges": 0
}

  • Vertice no existente en el grafo: Intenta actualizar la información de un vértice que no existe en el grafo y verifica que no se produce ningún cambio.

     1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacio
 5my_graph = G.new_graph(1)
 6
 7# Actualiza la información de un vértice que no existe
 8my_graph = G.update_vertex_info(my_graph, "Madrid", {"nombre": "Madrid", "pais": "Colombia"})
 9
10print(my_graph)
11# Salida esperada:

{
  "vertices": {
    "prime": 109345121,
    "capacity": 3,
    "scale": 1,
    "shift": 0,
    "table": {
      "elements": [
        {
          "key": null,
          "value": null
        },
        {
          "key": null,
          "value": null
        },
        {
          "key": null,
          "value": null
        }
      ],
      "size": 3
    },
    "current_factor": 0.0,
    "limit_factor": 0.5,
    "size": 0
  },
  "num_edges": 0
}
remove_vertex(my_graph, key_u)

Remueve el vertice con llave key_u del grafo my_graph.

Se busca el vertice en el grafo y se elimina del mapa de vertices. Al eliminar un vertice se deben eliminar todos los arcos que salen y llegan al vertice. Si el vertice existe, se elimina y se retorna el grafo actualizado. Si el vertice no existe, se retorna el grafo sin actualizar.

Parameters:

  • graph (digraph) – El grafo sobre el que se ejecuta la operacion

  • key_vertex (any) – Llave del vertice que se desea eliminar

Returns:

El grafo sin el vertice

Return type:

digraph

add_edge(my_graph, key_u, key_v, weight=1.0)

Agrega un arco dirigido al grafo my_graph del vertice con llave key_u al vertice con llave key_v con peso weight.

Se busca el vertice key_u en el grafo y se verifica si existe. Si no existe, se lanza una excepcion. Se busca el vertice key_v en el grafo y se verifica si existe. Si no existe, se lanza una excepcion. Si ambos vertices existen y el arco NO existe, se agrega el arco de key_u a key_v. Si el arco ya existe, se reemplaza el peso del arco (NO se aceptan arcos paralelos).

Parameters:

  • my_graph (digraph) – El grafo sobre el que se ejecuta la operacion

  • key_u (any) – Llave del vertice de inicio

  • key_v (any) – Llave del vertice destino

  • weight (double) – Peso del arco, por defecto 1

Returns:

El grafo con el nuevo arco

Return type:

digraph

Importante

Para lanzar error si no se encuentran los vertices, use el siguiente código como referencia:

raise Exception("El vertice u no existe")

Importante

Para asegurar obtener los mismos resultados en los mapas de los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacio
 5my_graph = G.new_graph(1)
 6
 7# Inserta vertices
 8my_graph = G.insert_vertex(my_graph, "Armenia", {"nombre": "Armenia", "poblacion": 300000})
 9my_graph = G.insert_vertex(my_graph, "Bogota", {"nombre": "Bogota", "poblacion": 8000000})
10
11# Inserta un arco
12my_graph = G.add_edge(my_graph, "Armenia", "Bogota", 100)
13
14print(my_graph)
15# Salida esperada:

{
  "vertices": {
    "prime": 109345121,
    "capacity": 7,
    "scale": 1,
    "shift": 0,
    "table": {
      "elements": [
        {
          "key": "Bogota",
          "value": {
            "key": "Bogota",
            "value": {
              "nombre": "Bogota",
              "poblacion": 8000000
            },
            "adjacents": {
              "prime": 109345121,
              "capacity": 2,
              "scale": 1,
              "shift": 0,
              "table": {
                "elements": [
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": null,
                    "value": null
                  }
                ],
                "size": 2
              },
              "current_factor": 0,
              "limit_factor": 0.5,
              "size": 0
            }
          }
        },
        {
          "key": null,
          "value": null
        },
        {
          "key": null,
          "value": null
        },
        {
          "key": null,
          "value": null
        },
        {
          "key": null,
          "value": null
        },
        {
          "key": "Armenia",
          "value": {
            "key": "Armenia",
            "value": {
              "nombre": "Armenia",
              "poblacion": 300000
            },
            "adjacents": {
              "prime": 109345121,
              "capacity": 5,
              "scale": 1,
              "shift": 0,
              "table": {
                "elements": [
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": "Bogota",
                    "value": {
                      "to": "Bogota",
                      "weight": 100
                    }
                  }
                ],
                "size": 5
              },
              "current_factor": 0.2,
              "limit_factor": 0.5,
              "size": 1
            }
          }
        },
        {
          "key": null,
          "value": null
        }
      ],
      "size": 7
    },
    "current_factor": 0.2857142857142857,
    "limit_factor": 0.5,
    "size": 2
  },
  "num_edges": 1
}
Test Scenario:

  • Grafo sin vertices: Lanza error si no se encuentran los vertices.

     1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacio
 5my_graph = G.new_graph(1)
 6
 7# Inserta vertices
 8my_graph = G.insert_vertex(my_graph, "Armenia", {
 9                "nombre": "Armenia", "poblacion": 300000})
10my_graph = G.insert_vertex(
11    my_graph, "Bogota", {"nombre": "Bogota", "poblacion": 8000000})
12
13# Inserta un arco
14my_graph = G.add_edge(my_graph, "A", "B", 100, )
15# Salida esperada en consola:
16#   raise Exception("El vertice u no existe")
17# Exception: El vertice u no existe

  • Grafo con vertices: Se crea un grafo con vertices y se le agregan arcos.

     1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacio
 5my_graph = G.new_graph(1)
 6
 7# Inserta vertices
 8my_graph = G.insert_vertex(my_graph, "Armenia", {"nombre": "Armenia", "poblacion": 300000})
 9my_graph = G.insert_vertex(my_graph, "Bogota", {"nombre": "Bogota", "poblacion": 8000000})
10my_graph = G.insert_vertex(my_graph, "Cali", {"nombre": "Cali", "poblacion": 2000000})
11
12# Inserta un arco
13my_graph = G.add_edge(my_graph, "Armenia", "Bogota", 100)
14my_graph = G.add_edge(my_graph, "Armenia", "Cali", 200)
15my_graph = G.add_edge(my_graph, "Bogota", "Cali", 300)
16
17print(my_graph)
18# Salida esperada:
    Respuesta inserción del arco
    {
  "vertices": {
    "prime": 109345121,
    "capacity": 7,
    "scale": 1,
    "shift": 0,
    "table": {
      "elements": [
        {
          "key": "Cali",
          "value": {
            "key": "Cali",
            "value": {
              "nombre": "Cali",
              "poblacion": 2000000
            },
            "adjacents": {
              "prime": 109345121,
              "capacity": 2,
              "scale": 1,
              "shift": 0,
              "table": {
                "elements": [
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": null,
                    "value": null
                  }
                ],
                "size": 2
              },
              "current_factor": 0,
              "limit_factor": 0.5,
              "size": 0
            }
          }
        },
        {
          "key": null,
          "value": null
        },
        {
          "key": "Armenia",
          "value": {
            "key": "Armenia",
            "value": {
              "nombre": "Armenia",
              "poblacion": 300000
            },
            "adjacents": {
              "prime": 109345121,
              "capacity": 5,
              "scale": 1,
              "shift": 0,
              "table": {
                "elements": [
                  {
                    "key": "Bogota",
                    "value": {
                      "to": "Bogota",
                      "weight": 100
                    }
                  },
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": "Cali",
                    "value": {
                      "to": "Cali",
                      "weight": 200
                    }
                  },
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": null,
                    "value": null
                  }
                ],
                "size": 5
              },
              "current_factor": 0.4,
              "limit_factor": 0.5,
              "size": 2
            }
          }
        },
        {
          "key": "Bogota",
          "value": {
            "key": "Bogota",
            "value": {
              "nombre": "Bogota",
              "poblacion": 8000000
            },
            "adjacents": {
              "prime": 109345121,
              "capacity": 5,
              "scale": 1,
              "shift": 0,
              "table": {
                "elements": [
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": "Cali",
                    "value": {
                      "to": "Cali",
                      "weight": 300
                    }
                  },
                  {
                    "key": null,
                    "value": null
                  },
                  {
                    "key": null,
                    "value": null
                  }
                ],
                "size": 5
              },
              "current_factor": 0.2,
              "limit_factor": 0.5,
              "size": 1
            }
          }
        },
        {
          "key": null,
          "value": null
        },
        {
          "key": null,
          "value": null
        },
        {
          "key": null,
          "value": null
        }
      ],
      "size": 7
    },
    "current_factor": 0.42857142857142855,
    "limit_factor": 0.5,
    "size": 3
  },
  "num_edges": 3
}
order(my_graph)

Retorna el orden del grafo, es decir, el numero de vertices del grafo my_graph.

Parameters:

my_graph (digraph) – El grafo sobre el que se ejecuta la operacion

Returns:

El numero de vertices del grafo

Return type:

int

Importante

Para asegurar obtener los mismos resultados en los mapas de los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

Example:
1# App/logic.py
2from DataStructures.Graph import digraph as G
3
4# Crea un grafo vacio
5my_graph = G.new_graph(1)
6
7print(G.order(my_graph))
8# Salida esperada: 0
Test Scenario:

  • Grafo vacio: Se crea un grafo vacio y se imprime su contenido

    1# App/logic.py
2from DataStructures.Graph import digraph as G
3
4# Crea un grafo vacio
5my_graph = G.new_graph(1)
6
7print(G.order(my_graph))
8# Salida esperada: 0

  • Grafo con vertices: Se crea un grafo con vertices y se imprime su contenido

     1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacio
 5my_graph = G.new_graph(1)
 6my_graph = G.insert_vertex(my_graph, "Armenia", {"nombre": "Armenia", "población": 300000})
 7my_graph = G.insert_vertex(my_graph, "Bogotá", {"nombre": "Bogotá", "población": 8000000})
 8
 9print(G.order(my_graph))
10# Salida esperada: 2
size(my_graph)

Retorna el tamaño del grafo, es decir, el numero de arcos del grafo my_graph.

Parameters:

my_graph (digraph) – El grafo sobre el que se ejecuta la operacion

Returns:

El numero de arcos del grafo

Return type:

int

Importante

Para asegurar obtener los mismos resultados en los mapas de los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

Example:
1# App/logic.py
2from DataStructures.Graph import digraph as G
3
4# Crea un grafo vacio
5my_graph = G.new_graph(1)
6
7print(G.size(my_graph))
8# Salida esperada: 0
Test Scenario:

  • Grafo vacio: Se crea un grafo vacio y se imprime su contenido

    1# App/logic.py
2from DataStructures.Graph import digraph as G
3
4# Crea un grafo vacio
5my_graph = G.new_graph(1)
6
7print(G.size(my_graph))
8# Salida esperada: 0

  • Grafo con varios vertices y arcos: Se crea un grafo con varios vertices y arcos.

     1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacio
 5my_graph = G.new_graph(1)
 6my_graph = G.insert_vertex(my_graph, "Armenia", {"nombre": "Armenia", "población": 300000})
 7my_graph = G.insert_vertex(my_graph, "Bogotá", {"nombre": "Bogotá", "población": 8000000})
 8my_graph = G.insert_vertex(my_graph, "Cali", {"nombre": "Cali", "población": 2000000})
 9
10my_graph = G.add_edge(my_graph, "Armenia", "Bogotá", 100 )
11my_graph = G.add_edge(my_graph, "Armenia", "Cali", 200)
12my_graph = G.add_edge(my_graph, "Bogotá", "Cali", 300)
13
14print(G.size(my_graph))
15# Salida esperada: 3
vertices(my_graph)

Retorna una lista con las llaves de todos los vertices del grafo my_graph.

Parameters:

my_graph (digraph) – El grafo sobre el que se ejecuta la operacion

Returns:

La lista con los vertices del grafo

Return type:

array_list

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacio
 5my_graph = G.new_graph(1)
 6
 7# Inserta vertices
 8my_graph = G.insert_vertex(my_graph, "Armenia", {"nombre": "Armenia", "poblacion": 300000})
 9my_graph = G.insert_vertex(my_graph, "Bogota", {"nombre": "Bogota", "poblacion": 8000000})
10my_graph = G.insert_vertex(my_graph, "Cali", {"nombre": "Cali", "poblacion": 2000000})
11
12print(G.vertices(my_graph))
13# Salida esperada:

{
  "elements": [
    "Cali",
    "Armenia",
    "Bogota"
  ],
  "size": 3
}
Test Scenarios:

  • Grafo sin vertices: Se crea un grafo vacio y se imprime su contenido

    1# App/logic.py
2from DataStructures.Graph import digraph as G
3
4# Crea un grafo vacio
5my_graph = G.new_graph(1)
6
7print(G.vertices(my_graph))
8# Salida esperada:

    {
  "elements": [],
  "size": 0
}

  • Grafo con vertices: Se crea un grafo con vertices y se imprime su contenido

     1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacio
 5my_graph = G.new_graph(1)
 6my_graph = G.insert_vertex(my_graph, "Armenia", {"nombre": "Armenia", "poblacion": 300000})
 7my_graph = G.insert_vertex(my_graph, "Bogota", {"nombre": "Bogota", "poblacion": 8000000})
 8my_graph = G.insert_vertex(my_graph, "Cali", {"nombre": "Cali", "poblacion": 2000000})
 9
10print(G.vertices(my_graph))
11# Salida esperada:

    {
  "elements": [
    "Cali",
    "Armenia",
    "Bogota"
  ],
  "size": 3
}
degree(my_graph, key_u)

Retorna el grado del vertice con llave key_u, es decir, el numero de arcos adyacentes al vertice.

Si el vertice no existe, se lanza una excepcion.

Parameters:

  • my_graph (digraph) – El grafo sobre el que se ejecuta la operacion

  • key_u (any) – Llave del vertice del que se desea conocer el grado

Returns:

El grado del vertice. Lanza una excepcion en caso de que el vertice no exista.

Return type:

int

Importante

Para lanzar error si no se encuentran los vertices, use el siguiente código como referencia:

raise Exception("El vertice no existe")
Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacio
 5my_graph = G.new_graph(1)
 6
 7# Inserta vertices
 8my_graph = G.insert_vertex(my_graph, "Armenia", {"nombre": "Armenia", "poblacion": 300000})
 9my_graph = G.insert_vertex(my_graph, "Bogota", {"nombre": "Bogota", "poblacion": 8000000})
10my_graph = G.insert_vertex(my_graph, "Cali", {"nombre": "Cali", "poblacion": 2000000})
11
12# Inserta un arco
13my_graph = G.add_edge(my_graph, "Armenia", "Bogota", 100)
14my_graph = G.add_edge(my_graph, "Armenia", "Cali", 200)
15
16print(G.degree(my_graph, "Armenia"))
17# Salida: 2
get_edge(my_graph, key_u, key_v)

Retorna el arco que conecta al vertice con llave key_u con el vertice con llave key_v.

Si el vertice key_u no existe, se lanza una excepcion. Si el arco no existe, se retorna None.

Parameters:

  • my_graph (digraph) – El grafo sobre el que se ejecuta la operacion

  • key_u (any) – Llave del vertice de inicio

  • key_v (any) – Llave del vertice destino

Returns:

El arco que une el vertice con llave key_u al vertice con llave key_v

Return type:

edge

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacio
 5my_graph = G.new_graph(1)
 6
 7# Inserta vertices
 8my_graph = G.insert_vertex(my_graph, "Armenia", {"nombre": "Armenia", "poblacion": 300000})
 9my_graph = G.insert_vertex(my_graph, "Bogota", {"nombre": "Bogota", "poblacion": 8000000})
10my_graph = G.insert_vertex(my_graph, "Cali", {"nombre": "Cali", "poblacion": 2000000})
11
12# Inserta un arco
13my_graph = G.add_edge(my_graph, "Armenia", "Bogota", 100)
14my_graph = G.add_edge(my_graph, "Armenia", "Cali", 200)
15
16print(G.degree(my_graph, "Armenia"))
17# Salida: 2
get_vertex_information(my_graph, key_u)

Retorna la informacion (value) asociada al vertice con llave key_u

Si el vertice no existe, se lanza una excepcion.

Parameters:

  • my_graph (digraph) – El grafo sobre el que se ejecuta la operacion

  • key_u (any) – Llave del vertice del que se quiere la informacion

Returns:

La informacion asociada al vertice.

Return type:

any

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacío
 5my_graph = G.new_graph(1)
 6
 7# Inserta vértices con información
 8my_graph = G.insert_vertex(my_graph, "Medellin", {"nombre": "Medellin", "poblacion": 2500000})
 9my_graph = G.insert_vertex(my_graph, "Cartagena", {"nombre": "Cartagena", "poblacion": 1000000})
10
11# Obtiene la información de un vértice existente
12info = G.get_vertex_information(my_graph, "Medellin")
13print(info)
14# Salida esperada: {'nombre': 'Medellin', 'poblacion': 2500000}
15
16# Intenta obtener la información de un vértice que no existe
17try:
18    info = G.get_vertex_information(my_graph, "Barranquilla")
19except Exception as e:
20    print(e)
21# Salida esperada: El vertice no existe
contains_vertex(my_graph, key_u)

Retorna si el vertice con llave``key_u`` esta presente en el grafo.

Parameters:

  • my_graph (digraph) – El grafo sobre el cual consultar la existencia del vertice

  • key_u (any) – Llave del vertice a buscar

Returns:

True si el vertice esta presente, False en caso contrario

Return type:

bool

Example:
 1# App/logic.py
 2
 3from DataStructures.Graph import digraph as G
 4
 5# Crea un grafo vacío
 6my_graph = G.new_graph(1)
 7
 8# Inserta algunos vértices
 9my_graph = G.insert_vertex(my_graph, "Santa Marta", {"nombre": "Santa Marta", "poblacion": 500000})
10my_graph = G.insert_vertex(my_graph, "Manizales", {"nombre": "Manizales", "poblacion": 400000})
11
12# Verifica si existen ciertos vértices
13print(G.contains_vertex(my_graph, "Santa Marta"))   # Salida esperada: True
14print(G.contains_vertex(my_graph, "Cucuta"))        # Salida esperada: False
adjacents(my_graph, key_u)

Retorna una lista con las llaves de los vertices adyacentes al vertice vertex con llave key_u.

Si el vertice no existe, se lanza una excepcion. Si el vertice existe, se retorna una lista con las llaves de los vertices adyacentes. Si el vertice no tiene vertices adyacentes, se retorna una lista vacia.

Parameters:

  • my_grph (digraph) – El grafo sobre el que se ejecuta la operacion

  • key_u (any) – Llave del vertice del que se quiere la lista

Returns:

La lista de las llaves de sus vertices adyacentes (si tiene).

Return type:

array_list

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacío
 5my_graph = G.new_graph(1)
 6
 7# Inserta vértices
 8my_graph = G.insert_vertex(my_graph, "Tunja", {"nombre": "Tunja", "poblacion": 200000})
 9my_graph = G.insert_vertex(my_graph, "Villavicencio", {"nombre": "Villavicencio", "poblacion": 300000})
10my_graph = G.insert_vertex(my_graph, "Neiva", {"nombre": "Neiva", "poblacion": 350000})
11
12# Inserta arcos
13my_graph = G.add_edge(my_graph, "Tunja", "Villavicencio", 150)
14my_graph = G.add_edge(my_graph, "Tunja", "Neiva", 180)
15
16# Consulta de adyacencias
17adj = G.adjacents(my_graph, "Tunja")
18print(adj)
19# Salida esperada: ['Villavicencio', 'Neiva']
20
21# Consulta de adyacencias para un vértice sin conexiones
22adj = G.adjacents(my_graph, "Neiva")
23print(adj)
24# Salida esperada: []
25
26# Consulta de adyacencias para un vértice inexistente
27try:
28    adj = G.adjacents(my_graph, "Popayan")
29except Exception as e:
30    print(e)
31# Salida esperada: El vertice no existe
edges_vertex(my_graph, key_u)

Retorna una lista con todos los arcos asociados a los vértices adyacentes del vertice con llave key_u.

Si el vertice no existe, se lanza una excepcion. Si el vertice existe, se retorna una lista con los arcos asociados a los vertices adyacentes. Si el vertice no tiene arcos adyacentes, se retorna una lista vacia.

Parameters:

  • my_graph (digraph) – El grafo sobre el que se ejecuta la operacion

  • key_u (any) – Llave del vértice del que se quiere la lista

Returns:

La lista de arcos adyacentes. Retorna una lista vacia en caso de que el vertice no exista.

Return type:

array_list

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacío
 5my_graph = G.new_graph(1)
 6
 7# Inserta vértices
 8my_graph = G.insert_vertex(my_graph, "Pasto", {"nombre": "Pasto", "poblacion": 400000})
 9my_graph = G.insert_vertex(my_graph, "Ibague", {"nombre": "Ibague", "poblacion": 500000})
10my_graph = G.insert_vertex(my_graph, "Monteria", {"nombre": "Monteria", "poblacion": 300000})
11
12# Inserta arcos
13my_graph = G.add_edge(my_graph, "Pasto", "Ibague", 120)
14my_graph = G.add_edge(my_graph, "Pasto", "Monteria", 250)
15
16# Consulta de arcos salientes del vértice 'Pasto'
17edges = G.edges_vertex(my_graph, "Pasto")
18for edge in edges:
19    print(edge)
20# Salida esperada (dependiendo de la representación interna, algo como):
21# ('Pasto', 'Ibague', 120)
22# ('Pasto', 'Monteria', 250)
23
24# Consulta de arcos salientes para un vértice sin conexiones
25edges = G.edges_vertex(my_graph, "Ibague")
26print(edges)
27# Salida esperada: []
28
29# Consulta de arcos salientes para un vértice inexistente
30try:
31    edges = G.edges_vertex(my_graph, "Leticia")
32except Exception as e:
33    print(e)
34# Salida esperada: El vertice no existe
get_vertex(my_graph, key_u)

Retorna la informacion completa del vertice con llave key_u.

Si el vertice no existe, se retorna None.

Parameters:

  • my_graph (digraph) – El grafo sobre el que se ejecuta la operacion

  • key_u (any) – Llave del vertice del que se quiere la informacion completa

Returns:

El vertice buscado. Retorna None en caso de que el vertice no exista.

Return type:

vertex

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3
 4# Crea un grafo vacío
 5my_graph = G.new_graph(1)
 6
 7# Inserta algunos vértices
 8my_graph = G.insert_vertex(my_graph, "Sincelejo", {"nombre": "Sincelejo", "poblacion": 280000})
 9my_graph = G.insert_vertex(my_graph, "Quibdo", {"nombre": "Quibdo", "poblacion": 130000})
10
11# Obtener el vértice existente
12vertex = G.get_vertex(my_graph, "Sincelejo")
13print(vertex)
14# Salida esperada (dependiendo de implementación): el objeto vértice o su representación
15# Por ejemplo: ('Sincelejo', {'nombre': 'Sincelejo', 'poblacion': 280000})
16
17# Intentar obtener un vértice inexistente
18try:
19    vertex = G.get_vertex(my_graph, "Mocoa")
20except Exception as e:
21    print(e)
22# Salida esperada: El vertice no existe

Algoritmos en grafos

dfs.py

dfs(my_graph, source)

Inicia un recorrido Depth First Search (DFS) sobre el grafo my_graph a partir de un vertice inicial con llave source. Esta es la función máscara para iniciar el recorrido recursivo usando la funcion auxiliar dfs_vertex(…). Cada vertice alcanzable se agrega a un mapa con su llave y como valor un diccionarion con la informacion {“marked”, “edge_from”}.

Parameters:

  • my_graph (digraph) – El grafo a recorrer

  • source (any) – Llave del vertice de inicio del recorrido.

Returns:

Una estructura para determinar los vertices conectados a source

Return type:

map

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3from App.Algorithms import dfs as DFS
 4
 5# Crear un grafo vacío
 6my_graph = G.new_graph(1)
 7
 8# Insertar vértices
 9my_graph = G.insert_vertex(my_graph, "Bogota", {})
10my_graph = G.insert_vertex(my_graph, "Medellin", {})
11my_graph = G.insert_vertex(my_graph, "Cali", {})
12my_graph = G.insert_vertex(my_graph, "Barranquilla", {})
13
14# Agregar arcos (dirigidos)
15my_graph = G.add_edge(my_graph, "Bogota", "Medellin", 1)
16my_graph = G.add_edge(my_graph, "Medellin", "Cali", 1)
17my_graph = G.add_edge(my_graph, "Cali", "Barranquilla", 1)
18
19# Ejecutar DFS desde "Bogota"
20dfs_result = DFS.dfs(my_graph, "Bogota")
21
22# Mostrar los resultados del recorrido
23print(dfs_result)
24
25# Salida esperada:

{'prime': 109345121,
'capacity': 11,
'scale': 32943225,
'shift': 9869347,
'table': {'elements': [{'key': 'Barranquilla',
                        'value': {'marked': True,
                        'edge_from': 'Cali'}},
                        {'key': None,
                        'value': None},
                        {'key': None,
                        'value': None},
                        {'key': None,
                        'value': None},
                        {'key': None,
                        'value': None},
                        {'key': None,
                        'value': None},
                        {'key': None,
                        'value': None},
                        {'key': 'Bogota',
                        'value': {'marked': True,
                                'edge_from': None}},
                        {'key': 'Cali',
                        'value': {'marked': True,
                                'edge_from': 'Medellin'}},
                        {'key': None,
                        'value': None},
                        {'key': 'Medellin',
                        'value': {'marked': True,
                                'edge_from': 'Bogota'}}],
'size': 11},
'current_factor': 0.36363636363636365,
'limit_factor': 0.5,
'size': 4}
dfs_vertex(my_graph, vertex, visited_map)

Funcion recursiva que permite obtener un recorrido DFS desde un vertice inicial. La funcion aplica a los vertices adyacentes del vertice inicial. Esta función es usada por la funcion depth_first_search. Cada vertice alcanzable se agrega a un mapa con su llave y como valor un diccionarion con la informacion {“marked”, “edge_from”}.

Parameters:

  • my_graph (digraph) – El grafo a recorrer

  • vertex (any) – Llave del vertice de inicio del recorrido.

  • visited_map (map) – Mapa que almacena las llaves de los vertices visitados.

Returns:

El mapa actualizado con los nuevos vertices visitados

Return type:

map

has_path_to(key_v, visited_map)

Indica si existe un camino entre el vertice source y el vertice vertex a partir del mapa de recorrido.

Precondición

Se debe haber ejecutado previamente la funcion dfs.

Parameters:

  • key_v (any) – Llave del vertice destino

  • visited_map (map) – Mapa resultante del recorrido DFS

Returns:

True si existe un camino entre source y key_v, False en caso contrario

Return type:

bool

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3from DataStructures.Graph import dfs as DFS
 4
 5# Crear un grafo vacío
 6my_graph = G.new_graph(1)
 7
 8# Agregar vértices
 9my_graph = G.insert_vertex(my_graph, "A", {"nombre": "A"})
10my_graph = G.insert_vertex(my_graph, "B", {"nombre": "B"})
11my_graph = G.insert_vertex(my_graph, "C", {"nombre": "C"})
12my_graph = G.insert_vertex(my_graph, "D", {"nombre": "D"})
13
14# Agregar aristas
15my_graph = G.add_edge(my_graph, "A", "B", 1)
16my_graph = G.add_edge(my_graph, "B", "C", 1)
17my_graph = G.add_edge(my_graph, "C", "D", 1)
18
19# Realizar DFS desde el vértice A
20visited_map = DFS.dfs(my_graph, "A")
21
22# Verificar si existe camino de A a D
23has_path = DFS.has_path_to("D", visited_map)
24print(f"¿Existe camino de A a D? {has_path}")  # True
25
26# Verificar si existe camino de D a A
27has_path = DFS.has_path_to("A", visited_map)
28print(f"¿Existe camino de D a A? {has_path}")  # True (porque A es el origen)
29
30# Verificar si existe camino a un vértice que no existe
31has_path = DFS.has_path_to("E", visited_map)
32print(f"¿Existe camino de A a E? {has_path}")  # False
path_to(key_v, visited_map)

Retorna el camino entre los vertices con llaves source y key_v a partir del mapa de recorrido. Retorna None si No hay camino.

Precondición

Se debe haber ejecutado previamente la funcion dfs.

Parameters:

  • key_v (any) – Llave del vertice de destino

  • visited_map (map) – Mapa resultante del recorrido DFS

Returns:

Una pila con el camino entre el vertices source y el vertice vertex

Return type:

stack

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3from DataStructures.Graph import dfs as DFS
 4from DataStructures.Stack import stack as st
 5
 6# Crear un grafo vacío
 7my_graph = G.new_graph(1)
 8
 9# Agregar vértices
10my_graph = G.insert_vertex(my_graph, "A", {"nombre": "A"})
11my_graph = G.insert_vertex(my_graph, "B", {"nombre": "B"})
12my_graph = G.insert_vertex(my_graph, "C", {"nombre": "C"})
13my_graph = G.insert_vertex(my_graph, "D", {"nombre": "D"})
14
15# Agregar aristas
16my_graph = G.add_edge(my_graph, "A", "B", 1)
17my_graph = G.add_edge(my_graph, "B", "C", 1)
18my_graph = G.add_edge(my_graph, "C", "D", 1)
19
20# Realizar DFS desde el vértice A
21visited_map = DFS.dfs(my_graph, "A")
22
23# Obtener el camino de A a D
24path = DFS.path_to("D", visited_map)
25if path is not None:
26    print("Camino de A a D:")
27    while not st.is_empty(path):
28        vertex = st.pop(path)
29        print(vertex, end=" -> ")
30    print("Fin")
31else:
32    print("No existe camino de A a D")
33
34#salida esperada: Camino de A a D: A -> B -> C -> D -> Fin
35
36# Obtener el camino de A a un vértice que no existe
37path = DFS.path_to("E", visited_map)
38if path is not None:
39    print("Camino de A a E:")
40    while not st.is_empty(path):
41        vertex = st.pop(path)
42        print(vertex, end=" -> ")
43    print("Fin")
44else:
45    print("No existe camino de A a E")
46
47#alida esperada: No existe camino de A a E

bfs.py

bfs(my_graph, source)

Inicia un recorrido Breath First Seacrh (BFS) sobre el grafo a partir de un vertice inicial. Crea un mapa de visitados y posteriormente llama a la funcion auxiliar bfs_vertex.

Parameters:

  • my_graph (digraph) – El grafo a recorrer

  • source (any) – Llave del vertice de inicio del recorrido.

Returns:

Mapa con la información de los vertices conectados a source (padre y distancia)

Return type:

map

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3from DataStructures.Graph import bfs as BFS
 4
 5# Crear un grafo vacío
 6my_graph = G.new_graph(1)
 7
 8# Agregar vértices
 9my_graph = G.insert_vertex(my_graph, "A", {"nombre": "A"})
10my_graph = G.insert_vertex(my_graph, "B", {"nombre": "B"})
11my_graph = G.insert_vertex(my_graph, "C", {"nombre": "C"})
12my_graph = G.insert_vertex(my_graph, "D", {"nombre": "D"})
13my_graph = G.insert_vertex(my_graph, "E", {"nombre": "E"})
14
15# Agregar aristas
16my_graph = G.add_edge(my_graph, "A", "B", 1)
17my_graph = G.add_edge(my_graph, "A", "C", 1)
18my_graph = G.add_edge(my_graph, "B", "D", 1)
19my_graph = G.add_edge(my_graph, "C", "E", 1)
20my_graph = G.add_edge(my_graph, "D", "E", 1)
21
22# Realizar BFS desde el vértice A
23visited_map = BFS.bfs(my_graph, "A")
24
25# Verificar los vértices visitados
26print("Vértices visitados desde A:")
27vertices = G.vertices(my_graph)
28for i in range(lt.size(vertices)):
29    vertex = lt.get_element(vertices, i)
30    if map.contains(visited_map, vertex):
31        info = map.get(visited_map, vertex)
32        print(f"Vértice {vertex}:")
33        print(f"  - Distancia: {info['dist_to']}")
34        print(f"  - Viene de: {info['edge_from']}")
bfs_vertex(my_graph, source, visited_map)

Función auxiliar para calcular un recorrido BFS usada por la función bfs.

Parameters:

  • my_graph (digraph) – El grafo a recorrer

  • source (any) – Vertice de inicio del recorrido.

  • visited_map (map) – Mapa para almacenar el recorrido

Returns:

El mapa actualizado con los vertices alcanzables

Return type:

map

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3from DataStructures.Graph import bfs as BFS
 4from DataStructures.Map import map_linear_probing as map
 5
 6# Crear un grafo vacío
 7my_graph = G.new_graph(1)
 8
 9# Insertar vértices
10my_graph = G.insert_vertex(my_graph, "Bogota", {})
11my_graph = G.insert_vertex(my_graph, "Medellin", {})
12my_graph = G.insert_vertex(my_graph, "Cali", {})
13my_graph = G.insert_vertex(my_graph, "Barranquilla", {})
14
15# Agregar arcos (dirigidos)
16my_graph = G.add_edge(my_graph, "Bogota", "Medellin", 1)
17my_graph = G.add_edge(my_graph, "Medellin", "Cali", 1)
18my_graph = G.add_edge(my_graph, "Cali", "Barranquilla", 1)
19
20# Crear el mapa de visitados
21visited_map = map.new_map(
22    num_elements=G.order(my_graph),
23    load_factor=0.5
24)
25
26# Inicializar el vértice origen
27map.put(visited_map, "Bogota", {
28    "edge_from": None,
29    "dist_to": 0
30})
31
32# Ejecutar BFS desde "Bogota"
33visited_map = BFS.bfs_vertex(my_graph, "Bogota", visited_map)
34
35# Mostrar los resultados del recorrido
36print("Vértices visitados desde Bogotá:")
37vertices = G.vertices(my_graph)
38for i in range(lt.size(vertices)):
39    vertex = lt.get_element(vertices, i)
40    if map.contains(visited_map, vertex):
41        info = map.get(visited_map, vertex)
42        print(f"{vertex}: distancia {info['dist_to']} desde {info['edge_from']}")
has_path_to(key_v, visited_map)

Indica si existe un camino entre el vertice source y el vertice vertex a partir del mapa de recorrido.

Precondición

Se debe haber ejecutado previamente la funcion bfs.

Parameters:

  • key_v (any) – Llave del vertice destino

  • visited_map (map) – Mapa resultante del recorrido BFS

Returns:

True si existe un camino entre source y vertex, False en caso contrario

Return type:

bool

path_to(key_v, visited_map)

Retorna el camino entre el vertices source y el vertice vertex a partir del mapa de recorrido.

Precondición

Se debe haber ejecutado previamente la funcion bfs.

Parameters:

  • key_v (any) – Llave del vertice destino

  • visited_map (map) – Mapa resultante del recorrido BFS

Returns:

Una pila con el camino entre source y vertex. Si no existe camino retorna None.

Return type:

stack

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3from DataStructures.Graph import bfs as BFS
 4from DataStructures.Stack import stack as st
 5
 6# Crear un grafo vacío
 7my_graph = G.new_graph(1)
 8
 9# Agregar vértices
10my_graph = G.insert_vertex(my_graph, "A", {"nombre": "A"})
11my_graph = G.insert_vertex(my_graph, "B", {"nombre": "B"})
12my_graph = G.insert_vertex(my_graph, "C", {"nombre": "C"})
13my_graph = G.insert_vertex(my_graph, "D", {"nombre": "D"})
14my_graph = G.insert_vertex(my_graph, "E", {"nombre": "E"})
15
16# Agregar aristas
17my_graph = G.add_edge(my_graph, "A", "B", 1)
18my_graph = G.add_edge(my_graph, "A", "C", 1)
19my_graph = G.add_edge(my_graph, "B", "D", 1)
20my_graph = G.add_edge(my_graph, "C", "E", 1)
21my_graph = G.add_edge(my_graph, "D", "E", 1)
22
23# Realizar BFS desde el vértice A
24visited_map = BFS.bfs(my_graph, "A")
25
26# Obtener el camino de A a E
27path = BFS.path_to("E", visited_map)
28if path is not None:
29    print("Camino de A a E:")
30    while not st.is_empty(path):
31        vertex = st.pop(path)
32        print(vertex, end=" -> ")
33    print("Fin")
34else:
35    print("No existe camino de A a E")
36
37# Obtener el camino de A a un vértice que no existe
38path = BFS.path_to("F", visited_map)
39if path is not None:
40    print("Camino de A a F:")
41    while not st.is_empty(path):
42        vertex = st.pop(path)
43        print(vertex, end=" -> ")
44    print("Fin")
45else:
46    print("No existe camino de A a F")

dfo.py

dfo(my_graph)

Inicia un recorrido Depth First Order (DFO) sobre el grafo. Crea una estructura de busqueda dfo_search y posteriormente llama a la funcion dfs_vertex.

Parameters:

my_graph (adj_list_graph) – El grafo a recorrer

Returns:

Una estructura de busqueda para determinar el orden de los vertices

Return type:

dfo_search

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3from DataStructures.Graph import dfo as DFO
 4
 5# Crear un grafo vacío
 6my_graph = G.new_graph(1)
 7
 8# Insertar vértices
 9my_graph = G.insert_vertex(my_graph, "Bogotá", {})
10my_graph = G.insert_vertex(my_graph, "Medellín", {})
11my_graph = G.insert_vertex(my_graph, "Cali", {})
12my_graph = G.insert_vertex(my_graph, "Barranquilla", {})
13my_graph = G.insert_vertex(my_graph, "Cartagena", {})
14
15# Agregar arcos dirigidos
16my_graph = G.add_edge(my_graph, "Bogotá", "Medellín", 1)
17my_graph = G.add_edge(my_graph, "Medellín", "Cali", 1)
18my_graph = G.add_edge(my_graph, "Cali", "Barranquilla", 1)
19my_graph = G.add_edge(my_graph, "Barranquilla", "Cartagena", 1)
20
21# Ejecutar DFO sobre el grafo
22dfo_result = DFO.dfo(my_graph)
23
24# Mostrar resultados
25print("Preorden:", dfo_result["pre"]["elements"])
26print("Postorden:", dfo_result["post"]["elements"])
27print("Reverse postorden (pila):", dfo_result["reversepost"])
28
29# Salida esperada:
30# Preorden: ['Cartagena', 'Cali', 'Barranquilla', 'Bogotá', 'Medellín']
31# Postorden: ['Cartagena', 'Barranquilla', 'Cali', 'Medellín', 'Bogotá']
32# Reverse postorden (pila): {'first': {'info': 'Cartagena', 'next': {'info': 'Barranquilla', 'next': {'info': 'Cali', 'next': {'info': 'Medellín', 'next': {'info': 'Bogotá', 'next': None}}}}}, 'last': {'info': 'Bogotá', 'next': None}, 'size': 5}
dfs_vertex(my_graph, key_v, aux_structure)

Función auxiliar para calcular un recorrido DFO usada por la función depth_first_order.

Parameters:

  • my_graph (adj_list_graph) – El grafo a recorrer

  • search (dfo_search) – Estructura para almacenar el recorrido

  • vertex (any) – Vertice de inicio del recorrido.

Returns:

Una estructura para determinar los vertices conectados a source

Return type:

dfo_search

Example:
 1# App/logic.py
 2from DataStructures.Graph import digraph as G
 3from DataStructures.Graph import dfo_structure as dfo_structure
 4from DataStructures.Graph import dfo as DFO
 5
 6def pruebas():
 7    # Crear un grafo vacío
 8    my_graph = G.new_graph(1)
 9
10    # Insertar vértices
11    my_graph = G.insert_vertex(my_graph, "Tunja", {})
12    my_graph = G.insert_vertex(my_graph, "Medellín", {})
13    my_graph = G.insert_vertex(my_graph, "Neiva", {})
14    my_graph = G.insert_vertex(my_graph, "Villavicencio", {})
15    my_graph = G.insert_vertex(my_graph, "Cali", {})
16
17    # Agregar arcos dirigidos
18    my_graph = G.add_edge(my_graph, "Tunja", "Medellín", 1)
19    my_graph = G.add_edge(my_graph, "Medellín", "Neiva", 1)
20    my_graph = G.add_edge(my_graph, "Neiva", "Villavicencio", 1)
21    my_graph = G.add_edge(my_graph, "Villavicencio", "Cali", 1)
22
23    # Crear la estructura auxiliar de búsqueda
24    aux_structure = dfo_structure.new_dfo_structure(G.order(my_graph))
25
26    # Ejecutar DFS desde "Tunja"
27    result = DFO.dfs_vertex(my_graph, "Tunja", aux_structure)
28
29    # Mostrar resultados
30    print("Preorden:", result["pre"]["elements"])
31    print("Postorden:", result["post"]["elements"])
32    print("Reverse postorden (pila):", result["reversepost"])
33
34# Salida esperada:
35# Preorden: ['Tunja', 'Medellín', 'Neiva', 'Villavicencio', 'Cali']
36# Postorden: ['Cali', 'Villavicencio', 'Neiva', 'Medellín', 'Tunja']
37# Reverse postorden (pila): {'first': {'info': 'Cali', 'next': {'info': 'Villavicencio', 'next': {'info': 'Neiva', 'next': {'info': 'Medellín', 'next': {'info': 'Tunja', 'next': None}}}}}, 'last': {'info': 'Tunja', 'next': None}, 'size': 5}

prim.py

prim_mst(my_graph, source)

Implementa el algoritmo de Prim para encontrar el arbol de expansion minima (MST) de un grafo no dirigido. El algoritmo inicia en el vertice con llave source y va agregando arcos de menor peso que conecten vertices que no esten en el MST. El algoritmo termina cuando todos los vertices alcanzables estan en el MST. El algoritmo es similar al algoritmo de Dijkstra, pero en lugar de agregar vertices al arbol de expansion minima, se agregan arcos de costo minimo.

Parameters:

  • my_graph (digraph) – El grafo a examinar

  • source (any) – La llave del vertice inicial

Returns:

Estructura resultante con la información para llegar a cada vertice alcanzable desde el vertice source aplicando Prim

Return type:

prim_structure

Example:
 1from DataStructures.Graph import digraph as G
 2from DataStructures.Graph import prim as PRIM
 3
 4def pruebas():
 5    # Crear un grafo no dirigido
 6    my_graph = G.new_graph(3)
 7    my_graph = G.insert_vertex(my_graph, "Bogotá", {})
 8    my_graph = G.insert_vertex(my_graph, "Medellín", {})
 9    my_graph = G.insert_vertex(my_graph, "Cali", {})
10
11    my_graph = G.add_edge(my_graph, "Bogotá", "Medellín", 3)
12    my_graph = G.add_edge(my_graph, "Medellín", "Bogotá", 3)
13    my_graph = G.add_edge(my_graph, "Bogotá", "Cali", 1)
14    my_graph = G.add_edge(my_graph, "Cali", "Bogotá", 1)
15
16    # Ejecutar algoritmo de Prim desde "Bogotá"
17    resultado = PRIM.prim_mst(my_graph, "Bogotá")
18    print("Estructura devuelta por prim_mst:")
19    print(resultado)
20
21# Salida esperada (estructura prim_structure):
22# {
23#     'source': 'Bogotá',
24#     'visited': {
25#         'prime': 109345121,
26#         'capacity': 7,
27#         'scale': ...,
28#         'shift': ...,
29#         'table': {
30#             'elements': [
31#                 {'key': 'Bogotá', 'value': {'edge_from':None, 'dist_to':0.0, 'marked':True},
32#                 {'key': 'Cali', 'value': {'edge_from':'Bogotá', 'dist_to':1, 'marked':True},
33#                 {'key': 'Medellín', 'value': {'edge_from':'Bogotá', 'dist_to':3, 'marked':True},
34#                 ...
35#             ],
36#             'size': 7
37#         },
38#         'size': 3
39#     },
40#     'pq': {
41#         'elements': {'elements': [None], 'size': 1},
42#         'size': 0,
43#         'cmp_function': <function cmp_function_lower_value at ...>
44#     }
45# }
edges_mst(my_graph, aux_structure)

Retorna los arcos del arbol de expansion minima (MST) en una lista

Precondición

Se debe haber ejecutado previamente la funcion prim_mst.

Parameters:

  • my_graph (digraph) – El grafo a examinar

  • aux_structure (prim_structure) – La estructura de busqueda resultante

Returns:

La lista con los arcos del MST

Return type:

array_list

Example:
 1from DataStructures.Graph import digraph as G
 2from DataStructures.Graph import prim as PRIM
 3from DataStructures.List import array_list as lt
 4
 5def pruebas():
 6    my_graph = G.new_graph(3)
 7    my_graph = G.insert_vertex(my_graph, "Bogotá", {})
 8    my_graph = G.insert_vertex(my_graph, "Medellín", {})
 9    my_graph = G.insert_vertex(my_graph, "Cali", {})
10
11    my_graph = G.add_edge(my_graph, "Bogotá", "Medellín", 3)
12    my_graph = G.add_edge(my_graph, "Medellín", "Bogotá", 3)
13    my_graph = G.add_edge(my_graph, "Bogotá", "Cali", 1)
14    my_graph = G.add_edge(my_graph, "Cali", "Bogotá", 1)
15
16    resultado = PRIM.prim_mst(my_graph, "Bogotá")
17    edges = PRIM.edges_mst(my_graph, resultado)
18
19    print("Arcos del MST:")
20    for i in range(lt.size(edges)):
21        arco = lt.get_element(edges, i)
22        print(arco)
23
24# Salida esperada:
25# Arcos del MST:
26# {'edge_from':'Bogotá', 'to':'Medellín', 'dist_to':3}
27# {'edge_from':'Bogotá', 'to':'Cali', 'dist_to':1}
weight_mst(my_graph, aux_structure)

Retorna el peso total del arbol de expansion minima (MST).

Precondición

Se debe haber ejecutado previamente la funcion prim_mst.

Parameters:

  • my_graph (digraph) – El grafo a examinar

  • aux_structure (prim_structure) – La estructura de busqueda resultante

Returns:

El peso total del arbol de expansion minima (MST)

Return type:

float

Importante

Para asegurar obtener los mismos resultados en los mapas de los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

Example:
# App/logic.py
from DataStructures.Graph import digraph as G
from DataStructures.Graph import prim as prim

# Crear un grafo No dirigido
my_graph = G.new_graph(6)

# Agregar vértices con su información
G.insert_vertex(my_graph, "Bogotá", {"nombre": "Bogotá", "poblacion": 7400000})
G.insert_vertex(my_graph, "Medellín", {"nombre": "Medellín", "poblacion": 2600000})
G.insert_vertex(my_graph, "Cali", {"nombre": "Cali", "poblacion": 2300000})
G.insert_vertex(my_graph, "Barranquilla", {"nombre": "Barranquilla", "poblacion": 1300000})
G.insert_vertex(my_graph, "Cartagena", {"nombre": "Cartagena", "poblacion": 1000000})
G.insert_vertex(my_graph, "Londres", {"nombre": "Londres", "poblacion": 8866000})

# Agregar aristas con distancias
G.add_edge(my_graph, "Bogotá", "Medellín", 415)
G.add_edge(my_graph, "Medellín", "Bogotá", 415)
G.add_edge(my_graph, "Bogotá", "Cali", 468)
G.add_edge(my_graph, "Cali", "Bogotá", 468)
G.add_edge(my_graph, "Medellín", "Cali", 412)
G.add_edge(my_graph, "Cali", "Medellín", 412)
G.add_edge(my_graph, "Medellín", "Barranquilla", 738)
G.add_edge(my_graph, "Barranquilla", "Medellín", 738)
G.add_edge(my_graph, "Cali", "Barranquilla", 1020)
G.add_edge(my_graph, "Barranquilla", "Cali", 1020)
G.add_edge(my_graph, "Barranquilla", "Cartagena", 120)
G.add_edge(my_graph, "Cartagena", "Barranquilla", 120)

# Ejecutar algoritmo de Prim desde Bogotá
structure = prim.prim_mst(my_graph, "Bogotá")
weight = prim.weight_mst(my_graph, structure)
print ("Peso del MST: " + str(weight))

Salida esperada:

Peso del MST: 1685

dijsktra.py

dijkstra(my_graph, source)

Implementa el algoritmo de Dijkstra para encontrar los caminos mas baratos desde el vertice source hasta todos sus vertices alcanzables (a los que se pueda llegar).

Parameters:

  • my_graph (digraph) – El grafo de busqueda

  • source (any) – La llave del vertice de inicio

Returns:

Estructura resultante con la información para llegar a cada vertice alcanzable desde el vertice source aplicando Dijkstra

Return type:

dijsktra_structure

Importante

Para asegurar obtener los mismos resultados en los mapas de los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

Example:
# App/logic.py
from DataStructures.Graph import digraph as G
from DataStructures.Graph import dijsktra as dijk

# Crear un grafo
my_graph = G.new_graph(1)

# Agregar vértices con su información
G.insert_vertex(my_graph, "Bogotá", {"nombre": "Bogotá", "poblacion": 7400000})
G.insert_vertex(my_graph, "Medellín", {"nombre": "Medellín", "poblacion": 2600000})
G.insert_vertex(my_graph, "Cali", {"nombre": "Cali", "poblacion": 2300000})
G.insert_vertex(my_graph, "Barranquilla", {"nombre": "Barranquilla", "poblacion": 1300000})
G.insert_vertex(my_graph, "Cartagena", {"nombre": "Cartagena", "poblacion": 1000000})
G.insert_vertex(my_graph, "Londres", {"nombre": "Londres", "poblacion": 8866000})

# Agregar aristas con distancias
G.add_edge(my_graph, "Bogotá", "Medellín", 415)
G.add_edge(my_graph, "Bogotá", "Cali", 468)
G.add_edge(my_graph, "Medellín", "Cali", 412)
G.add_edge(my_graph, "Medellín", "Barranquilla", 738)
G.add_edge(my_graph, "Cali", "Barranquilla", 1020)
G.add_edge(my_graph, "Barranquilla", "Cartagena", 120)

# Ejecutar algoritmo de Dijkstra desde Bogotá
structure = dijk.dijkstra(my_graph, "Bogotá")
print(structure)

Salida esperada:

{
    "source": "Bogotá",
    "visited": {
        "prime": 109345121,
        "capacity": 13,
        "scale": 1,       #(ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
        "shift": 0,       #(ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
        "table": {
            "elements": [
                {
                    "key": "Barranquilla",
                    "value": {"marked": True, "edge_from": "Medellín", "dist_to": 1153}
                },
                {
                    "key": "Cali",
                    "value": {"marked": True, "edge_from": "Bogotá", "dist_to": 468}
                },
                {"key": None, "value": None},
                {
                    "key": "Londres",
                    "value": {"marked": False, "edge_from": None, "dist_to": inf}
                },
                {"key": None, "value": None},
                {"key": None, "value": None},
                {"key": None, "value": None},
                {"key": None, "value": None},
                {"key": None, "value": None},
                {
                    "key": "Cartagena",
                    "value": {"marked": True, "edge_from": "Barranquilla", "dist_to": 1273}
                },
                {"key": None, "value": None},
                {
                    "key": "Medellín",
                    "value": {"marked": True, "edge_from": "Bogotá", "dist_to": 415}
                },
                {
                    "key": "Bogotá",
                    "value": {"marked": True, "edge_from": None, "dist_to": 0}
                }
            ],
            "size": 13
        },
        "current_factor": 0.46153846153846156,
        "limit_factor": 0.5,
        "size": 6,
        "type": "PROBING",
    },
    "pq": {
        "elements": {
            "elements": [None],
            "size": 1
        },
        "size": 0,
        "cmp_function": <function default_compare_lower_value>
    }
}
dist_to(key_v, aux_structure)

Retorna el costo del camino para llegar del vertice source al vertice key_v.

Parameters:

  • key_v (any) – La llave del vertice destino

  • aux_structure (dijsktra_structure) – La estructura de busqueda resultante de Dijkstra

Returns:

El costo total para llegar de source a vertex. Infinito si no existe camino

Return type:

float

Importante

Para asegurar obtener los mismos resultados en los mapas de los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

Example:
# App/logic.py
from DataStructures.Graph import digraph as G
from DataStructures.Graph import dijsktra as dijk

# Crear un grafo
my_graph = G.new_graph(1)

# Agregar vértices con su información
G.insert_vertex(my_graph, "Bogotá", {"nombre": "Bogotá", "poblacion": 7400000})
G.insert_vertex(my_graph, "Medellín", {"nombre": "Medellín", "poblacion": 2600000})
G.insert_vertex(my_graph, "Cali", {"nombre": "Cali", "poblacion": 2300000})
G.insert_vertex(my_graph, "Barranquilla", {"nombre": "Barranquilla", "poblacion": 1300000})
G.insert_vertex(my_graph, "Cartagena", {"nombre": "Cartagena", "poblacion": 1000000})
G.insert_vertex(my_graph, "Londres", {"nombre": "Londres", "poblacion": 8866000})

# Agregar aristas con distancias
G.add_edge(my_graph, "Bogotá", "Medellín", 415)
G.add_edge(my_graph, "Bogotá", "Cali", 468)
G.add_edge(my_graph, "Medellín", "Cali", 412)
G.add_edge(my_graph, "Medellín", "Barranquilla", 738)
G.add_edge(my_graph, "Cali", "Barranquilla", 1020)
G.add_edge(my_graph, "Barranquilla", "Cartagena", 120)

# Ejecutar algoritmo de Dijkstra desde Bogotá
structure = dijk.dijkstra(my_graph, "Bogotá")
print("Distancia de Bogotá a Cali: " + str(dijk.dist_to("Cali", structure)))
print("Distancia de Bogotá a Cartagena: " + str(dijk.dist_to("Cartagena", structure)))
print("Distancia de Bogotá a Londres: " + str(dijk.dist_to("Londres", structure)))

Salida esperada:

Distancia de Bogotá a Cali: 468
Distancia de Bogotá a Cartagena: 1273
Distancia de Bogotá a Londres: inf
has_path_to(key_v, aux_structure)

Indica si hay camino entre source y key_v.

Parameters:

  • key_v (any) – La llave del vertice de destino

  • aux_structure (dijsktra_structure) – La estructura de busqueda resultante de Dijkstra

Returns:

True si existe camino, False de lo contrario

Return type:

bool

Importante

Para asegurar obtener los mismos resultados en los mapas de los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

Example:
# App/logic.py
from DataStructures.Graph import digraph as G
from DataStructures.Graph import dijsktra as dijk

# Crear un grafo
my_graph = G.new_graph(1)

# Agregar vértices con su información
G.insert_vertex(my_graph, "Bogotá", {"nombre": "Bogotá", "poblacion": 7400000})
G.insert_vertex(my_graph, "Medellín", {"nombre": "Medellín", "poblacion": 2600000})
G.insert_vertex(my_graph, "Cali", {"nombre": "Cali", "poblacion": 2300000})
G.insert_vertex(my_graph, "Barranquilla", {"nombre": "Barranquilla", "poblacion": 1300000})
G.insert_vertex(my_graph, "Cartagena", {"nombre": "Cartagena", "poblacion": 1000000})
G.insert_vertex(my_graph, "Londres", {"nombre": "Londres", "poblacion": 8866000})

# Agregar aristas con distancias
G.add_edge(my_graph, "Bogotá", "Medellín", 415)
G.add_edge(my_graph, "Bogotá", "Cali", 468)
G.add_edge(my_graph, "Medellín", "Cali", 412)
G.add_edge(my_graph, "Medellín", "Barranquilla", 738)
G.add_edge(my_graph, "Cali", "Barranquilla", 1020)
G.add_edge(my_graph, "Barranquilla", "Cartagena", 120)

# Ejecutar algoritmo de Dijkstra desde Bogotá
structure = dijk.dijkstra(my_graph, "Bogotá")
print("¿Existe camino entre Bogotá y Medellín?: " + str(dijk.has_path_to("Medellín", structure)))
print("¿Existe camino entre Bogotá y Barranquilla?: " + str(dijk.has_path_to("Barranquilla", structure)))
print("¿Existe camino entre Bogotá y Londres?: " + str(dijk.has_path_to("Londres", structure)))

Salida esperada:

¿Existe camino entre Bogotá y Medellín?: True
¿Existe camino entre Bogotá y Barranquilla?: True
¿Existe camino entre Bogotá y Londres?: False
path_to(key_v, aux_structure)

Retorna el camino entre source y key_v en una pila.

Parameters:

  • key_v (any) – La llave del vertice de destino

  • aux_structure (dijsktra_structure) – La estructura de busqueda resultante de Dijkstra

Returns:

Una pila con los vertices del camino entre source y vertex. None si no hay camino.

Return type:

stack

Importante

Para asegurar obtener los mismos resultados en los mapas de los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

Example:
# App/logic.py
from DataStructures.Graph import digraph as G
from DataStructures.Graph import dijsktra as dijk

# Crear un grafo
my_graph = G.new_graph(1)

# Agregar vértices con su información
G.insert_vertex(my_graph, "Bogotá", {"nombre": "Bogotá", "poblacion": 7400000})
G.insert_vertex(my_graph, "Medellín", {"nombre": "Medellín", "poblacion": 2600000})
G.insert_vertex(my_graph, "Cali", {"nombre": "Cali", "poblacion": 2300000})
G.insert_vertex(my_graph, "Barranquilla", {"nombre": "Barranquilla", "poblacion": 1300000})
G.insert_vertex(my_graph, "Cartagena", {"nombre": "Cartagena", "poblacion": 1000000})
G.insert_vertex(my_graph, "Londres", {"nombre": "Londres", "poblacion": 8866000})

# Agregar aristas con distancias
G.add_edge(my_graph, "Bogotá", "Medellín", 415)
G.add_edge(my_graph, "Bogotá", "Cali", 468)
G.add_edge(my_graph, "Medellín", "Cali", 412)
G.add_edge(my_graph, "Medellín", "Barranquilla", 738)
G.add_edge(my_graph, "Cali", "Barranquilla", 1020)
G.add_edge(my_graph, "Barranquilla", "Cartagena", 120)

# Ejecutar algoritmo de Dijkstra desde Bogotá
structure = dijk.dijkstra(my_graph, "Bogotá")
print("Camino de Bogotá a Cali:")
print(str(dijk.path_to("Cali", structure)))
print("Camino de Bogotá a Cartagena:")
print(str(dijk.path_to("Cartagena", structure)))

Salida esperada:

Camino de Bogotá a Cali:
{
    "first": {
        "info": "Cali",
        "next": {
            "info": "Bogotá",
            "next": None
        }
    },
    "last": {
        "info": "Bogotá",
        "next": None
    },
    "size": 2
}
Camino de Bogotá a Cartagena:
{
    "first": {
        "info": "Cartagena",
        "next": {
            "info": "Barranquilla",
            "next": {
                "info": "Medellín",
                "next": {
                    "info": "Bogotá",
                    "next": None
                }
            }
        }
    },
    "last": {
        "info": "Bogotá",
        "next": None
    },
    "size": 4
}

Estructuras de recorrido

dfo_structure.py

new_dfo_structure(g_order)

Crea una estructura de busqueda usada en el algoritmo depth_first_order.

Se crea una estructura de busqueda con los siguientes atributos:

  • marked: Mapa con los vertices visitados. Se inicializa en None

  • pre: Cola con los vertices visitados en preorden. Se inicializa como una cola vacia.

  • post: Cola con los vertices visitados en postorden. Se inicializa como una cola vacia.

  • reversepost: Pila con los vertices visitados en postorden inverso. Se inicializa como una pila vacia.

Returns:

Estructura de busqueda

Return type:

dfo_search

Example:
 1# App/logic.py
 2from DataStructures.Graph import dfo_structure as dfo_structure
 3
 4def pruebas():
 5    estructura = dfo_structure.new_dfo_structure(2)
 6    print(estructura)
 7
 8# Salida esperada:
 9# {
10#     'marked': {
11#         'prime': 109345121,
12#         'capacity': 5,
13#         'scale': 14959102,
14#         'shift': 108263934,
15#         'table': {
16#             'elements': [
17#                 {'key': None, 'value': None},
18#                 {'key': None, 'value': None},
19#                 {'key': None, 'value': None},
20#                 {'key': None, 'value': None},
21#                 {'key': None, 'value': None}
22#             ],
23#             'size': 5
24#         },
25#         'current_factor': 0,
26#         'limit_factor': 0.5,
27#         'size': 0
28#     },
29#     'pre': {'elements': [], 'size': 0},
30#     'post': {'elements': [], 'size': 0},
31#     'reversepost': {'first': None, 'last': None, 'size': 0}
32# }

prim_structure.py

new_prim_structure(source, g_order)

Crea una estructura de busqueda usada en el algoritmo prim.

Se crea una estructura de busqueda con los siguientes atributos:

  • source: Llave del vertice de origen. Se inicializa con el parametro source

  • visited: Mapa con los vertices visitados. Inicialmente vacia.

  • pq: Cola de prioridad orientada a menor (Min-PQ) con los vertices por visitar. Inicialmente vacia.

Parameters:

  • source (any) – Llave del vertice inicial del recorrido

  • g_order (int) – Numero de vertices del grafo a recorrer

Returns:

Estructura resultante con la información para llegar a cada vertice alcanzable desde el vertice source aplicando Prim

Return type:

prim_structure

Importante

Para asegurar obtener los mismos resultados en los mapas de los ejemplos, se debe modificar la función new_map como se indica en la sección Como hacer pruebas con tablas.

Example:
# App/logic.py
from DataStructures.Graph import digraph as G
from DataStructures.Graph import prim_structure as ps

# Crea una estructura de Prim vacia
structure = ps.new_prim_structure("Bogotá", 1)
print(structure)
# Salida esperada a continuacion:

Salida esperada:

{
    "source": "Bogotá",
    "visited": {
        "prime": 109345121,
        "capacity": 3,
        "scale": 1,       #(ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
        "shift": 0,       #(ESTE VALOR QUEDA FIJO POR MODIFICACIÓN DE PRUEBAS)
        "table": {
            "elements": [
                {"key": None, "value": None},
                {"key": None, "value": None},
                {"key": None, "value": None}
            ],
            "size": 3
        },
        "current_factor": 0,
        "limit_factor": 0.5,
        "size": 0,
        "type": "PROBING"
    },
    "pq": {
        "elements": {
            "elements": [None],
            "size": 1
        },
        "size": 0,
        "cmp_function": function default_compare_lower_value
    }
}

dijsktra_structure.py

new_dijsktra_structure(source, g_order)

Crea una estructura de busqueda usada en el algoritmo dijsktra.

Se crea una estructura de busqueda con los siguientes atributos:

  • source: Llave del vertice de origen. Se inicializa con el parametro source.

  • visited: Mapa con los vertices visitados. Inicialmente vacia.

  • pq: Cola de prioridad orientada a menor (Min-PQ) con los vertices por visitar. Inicialmente vacia.

La prioridad corresponde al peso/costo del camino desde el vertice source hasta cada vertice alcanzable.

Parameters:

  • source (any) – Llave del vertice inicial del recorrido

  • g_order (int) – Numero de vertices del grafo a recorrer

Returns:

Estructura resultante con la información para llegar a cada vertice alcanzable desde el vertice source aplicando Dijkstra

Return type:

dijsktra_structure