graph implementation in PYthon

Question

I have found the following implementation of a Flow algorithm in Python:

class Edge(object):
 def __init__(self, u, v, w):
 self.source = u
 self.sink = v 
 self.capacity = w
 def __repr__(self):
 return "%s->%s:%s" % (self.source, self.sink, self.capacity)
lass FlowNetwork(object):
 def __init__(self):
 self.adj = {}
 self.flow = {}
 def add_vertex(self, vertex):
 self.adj[vertex] = []
 def get_edges(self, v):
 return self.adj[v]
 def add_edge(self, u, v, w=0):
 if u == v:
 raise ValueError("u == v")
 edge = Edge(u,v,w)
 redge = Edge(v,u,0)
 edge.redge = redge
 redge.redge = edge
 self.adj[u].append(edge)
 self.adj[v].append(redge)
 self.flow[edge] = 0
 self.flow[redge] = 0

Which is tested with:

>>> g = FlowNetwork()
>>> for v in "sopqrt":
>>> g.add_vertex(v)
>>> g.add_edge('s','o',3)
>>> g.add_edge('s','p',3)

I was wondering what exactly this part:

 edge.redge = redge
 redge.redge = edge

does in the add_edge function; it is like a sort of "recursive" call in which an edge its receiving the value of redge into one of his atributes, but why the last line of

redge.redge=edge?

Is it putting the edge in the attribute redge of redge?

For what I know of other OOP languages, when one put a point between two items it mostly indicates an object.atribute relationship, but I do not see how this is accomplished in that section.

Thanks

Answer 1

"redge" is reverse edge. Each edge stores the reverse of itself. Read the following code statements as the following paragraph.

edge = Edge(u,v,w)

Create the edge in question with weight "w".

redge = Edge(v,u,0)

Create the reverse of the edge in question with weight "0".

edge.redge = redge

The reverse edge of "edge" becomes "redge".

redge.redge = edge

The reverse edge of the reverse edge is the edge in question.

With the weights, you have a "capacity" of zero on the reverse edge. Therefore, as the programmer, you can follow the graph on the reverse edge, but you simulation will have "no capacity" in that direction in your simulation.

And yes, the semantics are object.attribute in this case.