How do I delete an edge from a graph in Python

Question

I'm reading ThinkComplexity book, I'm new to python, so I have this code:

class Graph(dict):
    def __init__(self, vs=[], es=[]):
        """
        :param vs: list of vertices/nodes in the graph
        :param es: list of edges/connection for the nodes
        :return: Object graph
        """

        for v in vs:
            self.add_vertex(v) #also node
        for e in es:
            self.add_edge(e) #arc/edge/line

     def add_vertex(self, v):
         """
         :param v: Add the node/vertex to the graph
         :return: Nothing just add
         """
         self[v] = {}

     def add_edge(self, e):
         """
         :param e: Add arc/edge/line to the graph here is in both directions as it is undirected graph, if there is a arc already replace it
         :return: Nothing just add
         """
         v, w = e
         self[v][w] = e
         self[w][v] = e

     def get_edge(self, v1, v2):
         try:
             if self != None:
                if self[v1][v2] == self[v2][v1]:
                     print 'got it'
                     return True

        except:
             return None


     def remove_edge(self, e, e2):
         try:
            if self != None:
                 del self[e][e2]
                 del self[e2][e]
                 print 'deleted\n', e[0], e[1]
                 return True

         except:
             return None


     def vertices(self): #get the list of nodes
         nodes = []
         for node in self.keys():
             nodes.append(node.label)
         print nodes, '\n'
         return nodes


    def edges(self):
         list_edges = []
         count = 0
         for node in self:
            for edges in self[node]:
                 count += 1
                 print self[node].values(), count
                 list_edges.append(self[node].values())

         return list_edges

    def out_vertices(self, v): #nodes connected to this node
        connected = []
        for node in v.keys():
            connected.append(node)
            print node, 'this node is connected to', v.keys()

        return connected

    def out_edges(self, v):
        list_out_edges = []
        for ed in v.values():
            print ed, 'edges from to'
            list_out_edges.append(ed)

        return list_out_edges



class Vertex(object): #nodes fro the graph
    def __init__(self, label=''):
        self.label = label

    def __repr__(self):
        return 'Vertex/Node(%s)' % repr(self.label)

    __str__= __repr__


class Edge(tuple):
     def __new__(cls, e1, e2):
        return tuple.__new__(cls, (e1, e2))

     def __repr__(self):
         return 'Edge(%s---%s) <-undirected' % (repr(self[0]), repr(self[1]))

     __str__ = __repr__

In chapter 2 4. Write a method named remove_edge that takes an edge and removes all references to it from the graph.

I have the get_edge() code done, but t remove I don't know how to do it, any help?? This would be an starting point to do a Bayes Network, so I want to learn about python and graphs. Thanks

So your graph is a dictionary (of dictionaries) and for an edge u, v you have an entry u in the entry v and vice-versa. I guess you are searching for how to delete an element from a dictionary http://stackoverflow.com/questions/5844672/delete-an-element-from-a-dictionary — user189, Jun 17 '14 at 09:26
Aha I see it the dictionary key can be an object, not necessarily a str, cool.Thanks. — Pedro.Alonso, Jun 17 '14 at 10:27
Please read the "hashable" paragraph here. https://docs.python.org/2/glossary.html — user189, Jun 17 '14 at 11:19

Pedro.Alonso · Accepted Answer · 2014-06-17T18:03:13.297

0

Like this:

def remove_edge(g, e, e2):
   try:
       if g != None:
           del g[e][e2]
           del g[e2][e]
           print 'deleted\n', e[0], e[1]
       return True

   except:
       return None

The keys in the dictionary can be objects, no only str. And need to do it both ways because is undirected

edited Jun 17 '14 at 18:03

answered Jun 17 '14 at 10:28

Pedro.Alonso

1,007
3
20
41

1

Be careful. Your code works because `Edge` is a subclass of `tuple`, but the `dict` keys **cannot** be just any arbitrary objects; they can only be hashable objects (which essentially means non-mutable types such as `str`, `int`, `tuple`, but not `list`). Read the Python wiki for more details: https://wiki.python.org/moin/DictionaryKeys – Dan Lenski Jun 17 '14 at 18:21

How do I delete an edge from a graph in Python

1 Answers1