Foros del Web » Programando para Internet » Python »

[Aporte] Sencilla implementación de grafos

Estas en el tema de [Aporte] Sencilla implementación de grafos en el foro de Python en Foros del Web. Aquí una pequeña implementación de grafos en python. El grafo que estoy implementando sigue las siguientes caracteristicas: Es un grafo... Dirigido No ponderado @import url("http://static.forosdelweb.com/clientscript/vbulletin_css/geshi.css"); ...
  #1 (permalink)  
Antiguo 19/06/2010, 17:46
Avatar de razpeitia
Moderador
 
Fecha de Ingreso: marzo-2005
Ubicación: Monterrey, México
Mensajes: 7.321
Antigüedad: 14 años, 10 meses
Puntos: 1360
[Aporte] Sencilla implementación de grafos

Aquí una pequeña implementación de grafos en python.

El grafo que estoy implementando sigue las siguientes caracteristicas:
Es un grafo...
  • Dirigido
  • No ponderado

Código Python:
Ver original
  1. class Graph:
  2.     #Simple graph implementation:
  3.     #Directed graph
  4.     #Without weight in the edges
  5.     #Edges can be repeated
  6.  
  7.     def __init__(self):
  8.         self.graph = {}
  9.  
  10.     def add_vertex(self, vertex):
  11.         #Add a vertex in the graph
  12.         #Overwrite the value
  13.         self.graph[vertex] = []
  14.  
  15.     def del_vertex(self, vertex):
  16.         #Remove the vertex if it's in the graph
  17.         try:
  18.             self.graph.pop(vertex)
  19.         except KeyError:
  20.             #Here vertex is not in graph
  21.             pass
  22.     def is_vertex(self, vertex):
  23.         #Return True if vertex is in the graph
  24.         #otherwise return False
  25.         try:
  26.             self.graph[vertex]
  27.             return True
  28.         except KeyError:
  29.             return False
  30.  
  31.     def add_edge(self, vertex, edge):
  32.         #Add a edge in vertex if vertex exists
  33.         try:
  34.             self.graph[vertex].append(edge)
  35.         except KeyError:
  36.             #Here vertex is no in graph
  37.             pass
  38.  
  39.     def delete_edge(self, vertex, edge):
  40.         #Remove a edge in vertex
  41.         try:
  42.             self.graph[vertex].remove(edge)
  43.         except KeyError:
  44.             #Here vertex is not in graph
  45.             pass
  46.         except ValueError:
  47.             #Here the edge not exists
  48.             pass
  49.  
  50.     def get_edge(self, vertex):
  51.         #Return the edges of a vertex if the vertex is in the graph
  52.         #Otherwise return None
  53.         try:
  54.             return self.graph[vertex]
  55.         except KeyError:
  56.             pass
  57.  
  58.     def __str__(self):
  59.         #Print the vertex
  60.         s = "Vertex -> Edges\n"
  61.         for k, v in self.graph.iteritems():
  62.             s+= "%-6s -> %s\n" % (k, v)
  63.         return s
  64.            
  65. graph = Graph()
  66. graph.add_vertex(1)
  67. graph.add_vertex(2)
  68. graph.add_vertex(3)
  69. graph.add_vertex(4)
  70. graph.add_edge(1, 2)
  71. graph.add_edge(1, 4)
  72. graph.add_edge(2, 4)
  73. graph.add_edge(3, 1)
  74. graph.add_edge(3, 2)
  75. graph.add_edge(4, 3)
  76. print graph

El grafo que imprime seria este:
Código:
Vertex -> Edges
1      -> [2, 4]
2      -> [4]
3      -> [1, 2]
4      -> [3]
Aquí su representación gráfica:


Espero hacer un implementación mas bonita estas vacaciones y de paso implementare el algoritmo de dijkstra
  #2 (permalink)  
Antiguo 13/07/2010, 08:37
 
Fecha de Ingreso: julio-2010
Mensajes: 2
Antigüedad: 9 años, 6 meses
Puntos: 0
Respuesta: [Aporte] Sencilla implementación de grafos

gracias, muy bueno la verdad
  #3 (permalink)  
Antiguo 26/12/2010, 19:40
Avatar de razpeitia
Moderador
 
Fecha de Ingreso: marzo-2005
Ubicación: Monterrey, México
Mensajes: 7.321
Antigüedad: 14 años, 10 meses
Puntos: 1360
Respuesta: [Aporte] Sencilla implementación de grafos

Sigo añadiéndole nuevos métodos y optimizando en código. Esta vez le añadí búsqueda a lo profundo y a lo ancho.

Código Python:
Ver original
  1. #Simple graph implementation:
  2. #Directed or undirected graph
  3. #Without weight in the edges, yet
  4. #Edges and vertices can't be repeated
  5. #DFS and BFS added
  6.  
  7. class Graph:
  8.     def __init__(self):
  9.         self.graph = {}
  10.    
  11.     def __get_iterator(self, obj):
  12.         try:
  13.             iterator = iter(obj)
  14.         except TypeError:
  15.             iterator = (obj, )
  16.         return iterator
  17.  
  18.     def add_vertex(self, vertex):
  19.         """
  20.            Add vertex to the graph
  21.        """
  22.         for i in self.__get_iterator(vertex):
  23.             self.graph[i] = set()
  24.  
  25.     def del_vertex(self, vertex):
  26.         """
  27.            Remove the vertex if it's in the graph
  28.            And all the edges
  29.        """
  30.         vertex = set(self.__get_iterator(vertex))
  31.         for i in vertex:
  32.             if i in self.graph:
  33.                 self.graph.pop(i)
  34.         for i in self.graph.iterkeys():
  35.             self.graph[i] -= vertex
  36.        
  37.     def is_vertex(self, vertex):
  38.         """
  39.            Return True if vertex is in the graph
  40.            otherwise return False
  41.        """
  42.         if vertex in self.graph:
  43.             return True
  44.         return False
  45.  
  46.     def add_edge(self, src, dest, undirected=True):
  47.         """
  48.            Add a edge from src to dest
  49.            Or add edges from the cartesian product of src cross dest
  50.            Example: add_edge((1, 2, 3), (2, 3))
  51.            Add the edges:
  52.                (1, 2)
  53.                (1, 3)
  54.                (2, 3)
  55.                (3, 2)
  56.        """
  57.         for s in self.__get_iterator(src):
  58.             if s not in self.graph:
  59.                 self.graph[s] = set()
  60.             for d in self.__get_iterator(dest):
  61.                 if s == d:
  62.                     continue
  63.                 if d not in self.graph:
  64.                     self.graph[d] = set()
  65.                 self.graph[s].add(d)
  66.                 if undirected:
  67.                     self.graph[d].add(s)
  68.  
  69.     def delete_edge(self, src, dest):
  70.         """
  71.            Remove the edge from src to dest
  72.            Or the edges of the cartesian product of src cross dest
  73.            Example: delete_edge((1, 2, 3), (2, 3))
  74.            Will delete the edges:
  75.                (1, 2)
  76.                (1, 3)
  77.                (2, 3)
  78.                (3, 2)
  79.        """
  80.         dest = set(self.__get_iterator(dest))
  81.         src = set(self.__get_iterator(src))
  82.         for i in src:
  83.             if i in self.graph:
  84.                 self.graph[i] -= dest
  85.  
  86.     def get_edge(self, vertex):
  87.         """
  88.            Return the neighbors of a vertex if the vertex is in the graph
  89.        """
  90.         return self.graph[vertex]
  91.    
  92.     def walk(self, source, topdown=False):
  93.         """
  94.        Walk through the graph:
  95.            DFS(Deep First Search)if topdown = True
  96.            Otherwise BFS(Breath First Search)
  97.        """
  98.         v = set()
  99.         l = [source]
  100.         if topdown:
  101.             print "DFS:"
  102.         else:
  103.             print "BFS:"
  104.         v.add(source)
  105.         while l:
  106.             node = l.pop()
  107.             print node,
  108.             for i in self.graph[node]:
  109.                 if i not in v:
  110.                     v.add(i)
  111.                     if topdown:
  112.                         l.append(i)
  113.                     else:
  114.                         l.insert(0, i)
  115.         print ""
  116.  
  117.     def __str__(self):
  118.         #Print the vertex
  119.         s = "Vertex -> Edges\n"
  120.         for k, v in self.graph.iteritems():
  121.             s += "%-6s -> %s\n" % (k, v)
  122.         return s
  123.  
  124. if __name__ == '__main__':            
  125.     graph = Graph()
  126.     graph.add_edge(1, (2, 3))
  127.     graph.add_edge(2, (4, 5))
  128.     graph.add_edge(3, (6, 7))
  129.     print graph

Grafo del ejemplo:

Última edición por razpeitia; 26/12/2010 a las 19:52
  #4 (permalink)  
Antiguo 29/12/2010, 12:42
Avatar de ARICARRARO  
Fecha de Ingreso: diciembre-2010
Ubicación: México
Mensajes: 227
Antigüedad: 9 años
Puntos: 10
Respuesta: [Aporte] Sencilla implementación de grafos

Excelente aporte @razpeitia.

Etiquetas: graficos
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta

SíEste tema le ha gustado a 2 personas




La zona horaria es GMT -6. Ahora son las 11:59.