/[cvs]/nfo/python/scripts/sixdegrees/sixdegrees.py
ViewVC logotype

Diff of /nfo/python/scripts/sixdegrees/sixdegrees.py

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.2 by joko, Wed Feb 6 01:45:22 2008 UTC revision 1.3 by joko, Wed Feb 6 22:58:00 2008 UTC
# Line 15  Line 15 
15  # You should have received a copy of the GNU Affero General Public License  # You should have received a copy of the GNU Affero General Public License
16  # along with this program.  If not, see <http://www.gnu.org/licenses/>.  # along with this program.  If not, see <http://www.gnu.org/licenses/>.
17    
18  from sets import Set  #from sets import Set
19    
20  class Node:  class Node:
21        
22    def __init__(self, id):    def __init__(self, id):
23      self.id = id      self.id = id
24      self.children = Set()      self.children = []
25        
26    def addChild(self, child):    def addChild(self, child):
27      self.children.add(child)      # with Set
28        #self.children.add(child)
29        
30        # with list
31        if not child in self.children:
32          self.children.append(child)
33    
34    def __repr__(self):    def __repr__(self):
35        #print "repr-node"
36      children_ids = []      children_ids = []
37      for child in self.children:      for child in self.children:
38        child_id = str(child.id)        child_id = str(child.id)
# Line 73  class Graph: Line 79  class Graph:
79    # extended "Depth Limited search (DLS)" implementation    # extended "Depth Limited search (DLS)" implementation
80    # see http://en.wikipedia.org/wiki/Depth-limited_search    # see http://en.wikipedia.org/wiki/Depth-limited_search
81    def DLS(self, node, goal, current_depth, max_depth, result, path=[]):    def DLS(self, node, goal, current_depth, max_depth, result, path=[]):
82        
83        # break recursion if node already visited to prevent looping
84        if node in path: return
85        
86      path.append(node)      path.append(node)
87      #print "checking node %s on level %s" % (node, current_depth)      #print "checking node %s on level %s" % (node, current_depth)
88      #print "path:", path      #print "path:", path
# Line 84  class Graph: Line 94  class Graph:
94          mynode = stack.pop()          mynode = stack.pop()
95          if current_depth < max_depth:          if current_depth < max_depth:
96            self.DLS(mynode, goal, current_depth + 1, max_depth, result, path)            self.DLS(mynode, goal, current_depth + 1, max_depth, result, path)
         else:  
           pass  
97      path.pop()      path.pop()
98    
99    def DLS_orig(self, node, goal, current_depth, max_depth):    def DLS_orig(self, node, goal, current_depth, max_depth):
# Line 102  class Graph: Line 110  class Graph:
110            pass            pass
111    
112    def __repr__(self):    def __repr__(self):
113        #print "repr-graph"
114      payload = ''      payload = ''
115      for key, node in self.index.iteritems():      for key, node in self.index.iteritems():
116        payload += str(node) + "\n"        payload += str(node) + "\n"
Legend:
Removed from v.1.2  
changed lines
  Added in v.1.3
MailToCvsAdmin">MailToCvsAdmin
 ViewVC Help
Powered by ViewVC 1.1.26 RSS 2.0 feed