#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    1
    Rep Power
    0

    Help in programming


    Hi I'm a student in informatic, first year. For a course I need to implement a program in python that solves the problem of disjoint paths in Graph.

    My prof gives a part of the code that I should complete, this:

    class Graph:

    def __init__(self):
    self.n=0
    self.m=0
    self.lofedges=[]
    self.edges=[]

    def readGraph(self,f):
    s=f.readline()
    a=s.split()
    self.n=int(a[0]); m=int(a[1]);
    self.edges=[set([]) for i in range(self.n)]
    for i in range(m):
    s=f.readline()
    a=s.split()
    u=int(a[0]); v=int(a[1]);
    self.addEdge(u,v)

    def addEdge(self,u,v):
    if ([u,v] in self.lofedges):
    return
    (self.edges[u]).add(v)
    (self.edges[v]).add(u)
    (self.lofedges).append([u,v])
    (self.lofedges).append([v,u])
    self.m=self.m+1


    def isEdge(self,u,v):
    return (u in self.edges[v])

    def removeEdge(self,u,v):
    if ([u,v] in self.lofedges):
    (self.edges[u]).remove(v)
    (self.edges[v]).remove(u)
    (self.lofedges).remove([u,v])
    (self.lofedges).remove([v,u])
    self.m=self.m-1;

    def allPairs(self):
    print "not implemented"

    def removePath(self,u,v):
    print "not implemented"

    I should complete allpairs and removepath, but I think it's too hard to do it and understand how my prof have made the algorithm.
    So anyone can help make a simple version af this algorithm, easier to understand?
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,997
    Rep Power
    481
    1) Please provide sample input.
    2) Leading white space is a key element of python syntax. Please follow and read the link at my signature to preserve your program indentation.
    3) Please demonstrate that you made an effort to understand the program.

    Looks like each edge is bi-directional. No "1 way streets".


    ps. Hey! The "quote post" trick works to recover the spaces! Thank you again.
    Last edited by b49P23TIvg; January 1st, 2013 at 02:06 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo