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 clave key y el valor value.

El vertice es creado con los siguientes atributos:

  • key: Llave del vertice.

  • value: Valor del vertice.

  • adjacents: Lista de arcos adyacentes al vertice. Implementada como un mapa map_linear_probing.

Parameters:

  • key (any) – Clave 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 clave

Returns:

Clave 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 la lista de arcos<graph-edge>`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 = 1
key_v = 2
key_w = 3
vertex_u = V.new_vertex(key_u, {"nombre": "Vertice U"})

V.add_adjacent(key_u, key_v, 10)
V.add_adjacent(key_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': 'KEYV',
#         'value': {
#           'to': 'KEYV',
#           'weight': 10
#         }
#       },
#       {
#         'key': None,
#         'value': None
#       },
#       {
#         'key': 'KEYW',
#         'value': {
#           'to': 'KEYW',
#           'weight': 10
#         }
#       },
#       {
#         'key': None,
#         'value': None
#       }
#     ],
#     'size': 5
#   },
#   'current_factor': 0.4,
#   'limit_factor': 0.5,
#   'size': 2
# }
get_edge(vertex, key_v)

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

Parameters:

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

Returns:

Mapa con la lista de arcos adyacentes vertice

Return type:

map_linear_probing

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"})

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

# Obtener el vertice adyacente
print(V.get_edge(vertex_u, vertex_v))
# Salida esperada: {'to': 'KEYV', 'weight': 10}

# Obtener el vertice no adyacente
print(V.get_edge(vertex_u, "KEYX"))
# Salida esperada: None
add_adjacent(vertex, key_vertex, weight)

Agrega un arco al vertice vertex con el vertice key_vertex y el peso weight

Parameters:

  • vertex (vertex) – Vertice al cual se le quiere agregar el arco

  • key_vertex (any) – Clave del vertice al cual se le quiere agregar el 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 del cual se quiere obtener el grado

Returns:

Grado del vertice

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 recien creado

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 y la informacion info_u. Posteriomente, el vertice se agrega a la lista de vertices del grafo.

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 no existe, se retorna None. Si el vertice existe, se actualiza la información y se retorna el grafo actualizado.

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

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: None
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 de la lista de vertices. Si el vertice no existe, se retorna None. Si el vertice existe, se elimina y se retorna el grafo actualizado. Es importante tener en cuenta que al eliminar un vertice, se deben eliminar todos los arcos asociados a ese vertice.

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 al grafo my_graph entre los vertices con llaves key_u y 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, se agrega el arco entre ellos. 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) – Vertice de inicio

  • key_v (any) – 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: 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) – El 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 asociado a los vertices con llave key_u a key_v.

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

Importante

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

raise Exception("El vertice u no existe")
Parameters:

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

  • key_u (any) – Vertice de inicio

  • key_v (any) – Vertice destino

Returns:

El arco que une los verices key_u a 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 asociada al vertice con llave key_u

Si el vertice no existe, se lanza una excepcion.

Importante

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

raise Exception("El vertice no existe")
Parameters:

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

  • key_u (any) – 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) – 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 no tiene vertices adyacentes, se retorna una lista vacia.

Importante

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

raise Exception("El vertice no existe")
Parameters:

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

  • key_vertex (any) – El vertice del que se quiere la lista

Returns:

La lista de vertices adyacencias. 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, "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értice 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 no tiene arcos adyacentes, se retorna una lista vacia.

Importante

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

raise Exception("El vertice no existe")
Parameters:

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

  • vertex (any) – El vertice 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 el valor del vertice con llave key_u.

Si el vertice no existe, se lanza una excepcion.

Importante

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

raise Exception("El vertice no existe")
Parameters:

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

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

Returns:

El vertice. 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.

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:

dfo_structure

dfs_vertex(my_graph, vertex, visited_map)

Funcion auxiliar para calcular un recorrido DFS usada por la funcion depth_first_search.

Parameters:

  • search (graph_search) – Estructura para almacenar el recorrido

  • my_graph (adj_list_graph) – El grafo a recorrer

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

Returns:

Una estructura para determinar los vertices conectados a source

Return type:

graph_search

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("Preorden:", dfs_result["pre"]["elements"])
24print("Postorden:", dfs_result["post"]["elements"])
25print("Reverse postorden (pila):", dfs_result["reversepost"]["elements"])
has_path_to(key_v, visited_map)

Indica si existe un camino entre el vertice source y el vertice vertex a partir de una estructura search.

Precondición

Se debe haber ejecutado previamente la funcion depth_first_search.

Parameters:

  • search (graph_search) – Estructura de recorrido DFS

  • vertex (any) – Vertice destino

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 de una estructura search.

Precondición

Se debe haber ejecutado previamente la funcion depth_first_search.

Parameters:

  • search (graph_search) – La estructura con el recorrido

  • vertex (any) – Vertice de destingo

Returns:

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

Return type:

stack

bfs.py

bfs(my_graph, source)

Inicia un recorrido Breath First Seacrh (BFS) sobre el grafo a partir de un vertice inicial. Crea una estructura de busqueda graph_search y posteriormente llama a la funcion bfs_vertex.

Parameters:

  • my_graph (adj_list_graph) – 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:

graph_search

bfs_vertex(my_graph, source, visited_map)

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

Parameters:

  • visited_map (graph_search) – Estructura para almacenar el recorrido

  • my_graph (adj_list_graph) – El grafo a recorrer

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

Returns:

Una estructura para determinar los vertices conectados a source

Return type:

graph_visited_map

has_path_to(key_v, visited_map)

Indica si existe un camino entre el vertice source y el vertice vertex a partir de una estructura search.

Precondición

Se debe haber ejecutado previamente la funcion breath_first_search.

Parameters:

  • search (graph_search) – Estructura de recorrido BFS

  • vertex (any) – Vertice destino

Returns:

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

path_to(key_v, visited_map)

Retorna el camino entre el vertices source y el vertice vertex a partir de una estructura de busqueda search.

Precondición

Se debe haber ejecutado previamente la funcion breath_first_search.

Parameters:

  • search (graph_search) – Estructura de recorrido BFS

  • vertex (any) – Vertice destino

Returns:

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

Return type:

stack

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

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

prim.py

prim_mst(my_graph, source)

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

Parameters:

  • my_graph (adj_list_graph) – El grafo a examinar

  • source (any) – El vertice fuente

Returns:

La estructura search con los MST

Return type:

prim_search

edges_mst(my_graph, aux_structure)

Retorna los arcos del arbol de expansion minima (MST) en una cola en el orden

Precondición

Se debe haber ejecutado previamente la funcion prim_mst.

Parameters:

  • my_graph (adj_list_graph) – El grafo a examinar

  • search (prim_search) – La estructura de busqueda

Returns:

La cola con los arcos del MST

Return type:

queue

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 (adj_list_graph) – El grafo a examinar

  • search (prim_search) – La estructura de busqueda

Returns:

El peso total del arbol de expansion minima

Return type:

float

dijsktra.py

dijkstra(my_graph, source)

Implementa el algoritmo de Dijkstra Args:

my_graph: El grafo de busqueda source: El vertice de inicio

Returns:

Un nuevo grafo vacío

Raises:

Exception

dist_to(key_v, aux_structure)

Retorna el costo para llegar del vertice source al vertice vertex. Args:

search: La estructura de busqueda vertex: El vertice destino

Returns:

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

Raises:

Exception

has_path_to(key_v, aux_structure)

Indica si hay camino entre source y vertex Args:

search: La estructura de busqueda vertex: El vertice de destino

Returns:

True si existe camino

Raises:

Exception

path_to(key_v, aux_structure)

Retorna el camino entre source y vertex en una pila. Args:

search: La estructura de busqueda vertex: El vertice de destino

Returns:

Una pila con el camino entre source y vertex

Raises:

Exception

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

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: Vertice de inicio del MST.

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

  • dist_to: Mapa con las distancias a los vertices. Se inicializa en None

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

  • pq: Cola de prioridad indexada (index_priority_queue). Se inicializa en None

Returns:

Estructura de busqueda

Return type:

prim_search

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: Vertice de origen. Se inicializa en source

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

  • pq: Cola indexada con los vertices visitados. Se inicializa en None

Returns:

Estructura de busqueda

Return type:

dijsktra_search