3

Disclaimer: This is for a semester project that I am currently working on. My question is regarding an implementation level detail and is not part of the grading scheme. I am only writing this code as a way to test the theory that I am proposing for the paper that I will write.

Also, I have considered the answers for this question with little luck, so please do not consider this as a duplicate of that question

The Problem:

I have a graph (G=(V,E)). At some point in my algorithm, I need to turn this into a hypergraph (in a sense) by "collapsing" multiple nodes (say, v_1, v_2, ..., v_n) into one node (say, v). In the context of the problem, this implies that I need to change the edges in E such that any edge e between any of v_1, v_2, v_n and any other node u in V will be changed such that e is now between u and v.

In order to capture that there may now exist multiple distinct edges between any pair of nodes, I need to make a unique identifier for each edge. I have tried to do this by means of and ID, which I am currently unable to properly implement.

This is what I've tried:

class Edge:
    _ID = 0
    def __init__(self, u, v, w, c,f=0):
        self.id = Edge._ID 
        Edge._ID += 1
        self.src = u
        self.dest = v
        self.weight = w
        self.capacity = c
        self.flow = f

However, when I try to instantiate a new edge, I get the following error:

>>> e = Edge(1,3,5,10,0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "UnsplittableFlow.py", line 14, in __init__
    self.id = Edge._ID; Edge._ID += 1
UnboundLocalError: local variable '_ID' referenced before assignment

EDIT:

With the suggestions of some answers, I have been able to fix the instantiation-time error. However, another error persists. Here is my code and the errors:

class Edge:
    _ID = 0
    def __init__(self, u, v, w, c,f=0):
        self.id = self._ID; self._ID += 1
        self.src = u
        self.dest = v
        self.weight = w
        self.capacity = c
        self.flow = f

Error:

>>> e = Edge(1,3,5,10,0)
>>> e.id
0
>>> Edge._ID
0

>>> f = Edge(2,3,5,10,0)
>>> f.id
0
>>> Edge._ID
0

I'd appreciate any help

Thank you

Community
  • 1
  • 1
inspectorG4dget
  • 110,290
  • 27
  • 149
  • 241
  • Weird, it works for me. What version of Python are you using? (I tried both 2.7 and 3.1, but just in case...) – David Z Nov 30 '11 at 01:10

4 Answers4

5

Your edited code is treating _ID as though it were a instance variable, not a class variable. Based on Matt Joiner's answer what I think you mean is this:

class Edge:
    _ID = 0
    def __init__(self, u, v, w, c,f=0):
        self.id = self._ID; self.__class__._ID += 1
        self.src = u
        self.dest = v
        self.weight = w
        self.capacity = c
        self.flow = f

When I run your examples with this definition of Edge, I get:

>>> e = Edge(1,3,5,10,0)
>>> e.id
0
>>> Edge._ID
1
>>> f = Edge(2,3,5,10,0)
>>> f.id
1
>>> Edge._ID
2

Which is the desired result. However, others have pointed out that your original code worked for them, just like this code works for me, so I suspect the real problem is somewhere else in your code.

srgerg
  • 18,719
  • 4
  • 57
  • 39
  • I think the problem with my original test had more to do with concurrency issues between changes that I was making to my code and the interpreter importing these changes. Somehow, restarting the interpreter fixed some things. Thank you for demonstrating how Matt Joiner's code works (+1). But since he /did/ have the right answer first, I'm going to accept his. Thank you again, for your help – inspectorG4dget Nov 30 '11 at 02:04
3

You can still use self to get at the _ID.

self.id = self._ID 
self.__class__._ID += 1

If you're using CPython, you can have a lazy man's ID:

class Edge(object):
    @property
    def id(self): return id(self)
Matt Joiner
  • 112,946
  • 110
  • 377
  • 526
2

While the other answers offered are answer the asked question (which is why I am not unaccepting the one I originally accepted), the correct way to do this would be to use itertools.count as follows:

class Edge:
    _ID = itertools.count()
def __init__(self, u, v, w, c,f=0):
    self.id = self._ID.next()
inspectorG4dget
  • 110,290
  • 27
  • 149
  • 241
  • @srgerg is right you are accessing self._ID which is an instance variable, You need to access the class _ID. Your first approach was correct `self.id = Edge._ID; Edge._ID += 1` – Kashif Siddiqui Feb 24 '17 at 04:53
2

Before instantiating any Edge, you could set the class variable explicitly to 0 like so:

Edge._ID = 0
e = Edge(1,3,5,10,0)
f = Edge(2,3,4,5,0)

And the id's will be properly set.

madmath
  • 21
  • 2