Aquí una pequeña implementación de grafos en python.
El grafo que estoy implementando sigue las siguientes caracteristicas:
Es un grafo...
Código Python:
Ver originalclass Graph:
#Simple graph implementation:
#Directed graph
#Without weight in the edges
#Edges can be repeated
def __init__(self):
self.graph = {}
def add_vertex(self, vertex):
#Add a vertex in the graph
#Overwrite the value
self.graph[vertex] = []
def del_vertex(self, vertex):
#Remove the vertex if it's in the graph
try:
self.graph.pop(vertex)
except KeyError:
#Here vertex is not in graph
pass
def is_vertex(self, vertex):
#Return True if vertex is in the graph
#otherwise return False
try:
self.graph[vertex]
return True
except KeyError:
return False
def add_edge(self, vertex, edge):
#Add a edge in vertex if vertex exists
try:
self.graph[vertex].append(edge)
except KeyError:
#Here vertex is no in graph
pass
def delete_edge(self, vertex, edge):
#Remove a edge in vertex
try:
self.graph[vertex].remove(edge)
except KeyError:
#Here vertex is not in graph
pass
except ValueError:
#Here the edge not exists
pass
def get_edge(self, vertex):
#Return the edges of a vertex if the vertex is in the graph
#Otherwise return None
try:
return self.graph[vertex]
except KeyError:
pass
def __str__(self):
#Print the vertex
s = "Vertex -> Edges\n"
for k, v in self.graph.iteritems():
s+= "%-6s -> %s\n" % (k, v)
return s
graph = Graph()
graph.add_vertex(1)
graph.add_vertex(2)
graph.add_vertex(3)
graph.add_vertex(4)
graph.add_edge(1, 2)
graph.add_edge(1, 4)
graph.add_edge(2, 4)
graph.add_edge(3, 1)
graph.add_edge(3, 2)
graph.add_edge(4, 3)
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