[Aporte] Sencilla implementación de grafos

[razpeitia]

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:

class 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

[fabri_deso]

gracias, muy bueno la verdad

[razpeitia]

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:

#Simple graph implementation:
#Directed or undirected graph
#Without weight in the edges, yet
#Edges and vertices can't be repeated
#DFS and BFS added
 
class Graph:
    def __init__(self):
        self.graph = {}
    
    def __get_iterator(self, obj):
        try:
            iterator = iter(obj)
        except TypeError:
            iterator = (obj, )
        return iterator
 
    def add_vertex(self, vertex):
        """
            Add vertex to the graph
        """
        for i in self.__get_iterator(vertex):
            self.graph[i] = set()
 
    def del_vertex(self, vertex):
        """
            Remove the vertex if it's in the graph
            And all the edges
        """
        vertex = set(self.__get_iterator(vertex))
        for i in vertex:
            if i in self.graph:
                self.graph.pop(i)
        for i in self.graph.iterkeys():
            self.graph[i] -= vertex
        
    def is_vertex(self, vertex):
        """
            Return True if vertex is in the graph
            otherwise return False
        """
        if vertex in self.graph:
            return True
        return False
 
    def add_edge(self, src, dest, undirected=True):
        """
            Add a edge from src to dest
            Or add edges from the cartesian product of src cross dest
            Example: add_edge((1, 2, 3), (2, 3))
            Add the edges:
                (1, 2)
                (1, 3)
                (2, 3)
                (3, 2)
        """
        for s in self.__get_iterator(src):
            if s not in self.graph:
                self.graph[s] = set()
            for d in self.__get_iterator(dest):
                if s == d:
                    continue
                if d not in self.graph:
                    self.graph[d] = set()
                self.graph[s].add(d)
                if undirected:
                    self.graph[d].add(s)
 
    def delete_edge(self, src, dest):
        """
            Remove the edge from src to dest
            Or the edges of the cartesian product of src cross dest
            Example: delete_edge((1, 2, 3), (2, 3))
            Will delete the edges:
                (1, 2)
                (1, 3)
                (2, 3)
                (3, 2)
        """
        dest = set(self.__get_iterator(dest))
        src = set(self.__get_iterator(src))
        for i in src:
            if i in self.graph:
                self.graph[i] -= dest
 
    def get_edge(self, vertex):
        """
            Return the neighbors of a vertex if the vertex is in the graph
        """
        return self.graph[vertex]
    
    def walk(self, source, topdown=False):
        """
        Walk through the graph:
            DFS(Deep First Search)if topdown = True
            Otherwise BFS(Breath First Search)
        """
        v = set()
        l = [source]
        if topdown:
            print "DFS:"
        else:
            print "BFS:"
        v.add(source)
        while l:
            node = l.pop()
            print node,
            for i in self.graph[node]:
                if i not in v:
                    v.add(i)
                    if topdown:
                        l.append(i)
                    else:
                        l.insert(0, i)
        print ""
 
    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
 
if __name__ == '__main__':            
    graph = Graph()
    graph.add_edge(1, (2, 3))
    graph.add_edge(2, (4, 5))
    graph.add_edge(3, (6, 7))
    print graph
 

Grafo del ejemplo:

[ARICARRARO]

Excelente aporte @razpeitia.