scripts/sixdegrees/sixdegrees.py

# $Id: sixdegrees.py,v 1.2 2008/02/06 01:45:22 joko Exp $

# (c) 2008 Andreas Motl <andreas.motl@ilo.de>

# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU Affero General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU Affero General Public License for more details.
# 
# You should have received a copy of the GNU Affero General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

#from sets import Set

class Node:
  
  def __init__(self, id):
    self.id = id
    self.children = []
  
  def addChild(self, child):
    # with Set
    #self.children.add(child)
    
    # with list
    if not child in self.children:
      self.children.append(child)

  def __repr__(self):
    #print "repr-node"
    children_ids = []
    for child in self.children:
      child_id = str(child.id)
      children_ids.append(child_id)
    return str(self.id) + ': ' + ', '.join(children_ids)


class Graph:
  
  def __init__(self):
    self.index = {}
  
  def getNode(self, id):
    return self.index[id]
  
  def addRelation(self, id_parent, id_child):
    
    # skip action, if parent id == child id
    if id_parent == id_child:
      return
    
    # establish parent node, if not exists
    if not self.index.has_key(id_parent):
      self.index[id_parent] = Node(id_parent)

    # establish child node, if not exists
    if not self.index.has_key(id_child):
      self.index[id_child] = Node(id_child)

    # add relationships to each node
    self.index[id_parent].addChild(self.index[id_child])
    self.index[id_child].addChild(self.index[id_parent])


  def computePaths(self, source_node, target_node, max_depth):
    
    # result list, will contain all valid paths (each path is a list of nodes)
    result = []
    
    # start searching
    self.DLS(source_node, target_node, 0, max_depth, result)
    return result

  # extended "Depth Limited search (DLS)" implementation
  # see http://en.wikipedia.org/wiki/Depth-limited_search
  def DLS(self, node, goal, current_depth, max_depth, result, path=[]):
    
    # break recursion if node already visited to prevent looping
    if node in path: return
    
    path.append(node)
    #print "checking node %s on level %s" % (node, current_depth)
    #print "path:", path
    if node is goal:
      result.append(list(path))
    else:
      stack = list(node.children)
      while stack:
        mynode = stack.pop()
        if current_depth < max_depth:
          self.DLS(mynode, goal, current_depth + 1, max_depth, result, path)
    path.pop()

  def DLS_orig(self, node, goal, current_depth, max_depth):
    #print "checking node %s on level %s" % (node, current_depth)
    if node is goal:
      return node
    else:
      stack = list(node.children)
      while stack:
        node = stack.pop()
        if current_depth < max_depth:
          self.DLS_orig(node, goal, current_depth + 1, max_depth)
        else:
          pass

  def __repr__(self):
    #print "repr-graph"
    payload = ''
    for key, node in self.index.iteritems():
      payload += str(node) + "\n"
    return payload

1	joko	1.3	# $Id: sixdegrees.py,v 1.2 2008/02/06 01:45:22 joko Exp $
2	joko	1.1
3			# (c) 2008 Andreas Motl <andreas.motl@ilo.de>
4
5			# This program is free software: you can redistribute it and/or modify
6			# it under the terms of the GNU Affero General Public License as published by
7			# the Free Software Foundation, either version 3 of the License, or
8			# (at your option) any later version.
9			#
10			# This program is distributed in the hope that it will be useful,
11			# but WITHOUT ANY WARRANTY; without even the implied warranty of
12			# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13	joko	1.2	# GNU Affero General Public License for more details.
14	joko	1.1	#
15			# 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/>.
17
18	joko	1.3	#from sets import Set
19	joko	1.1
20			class Node:
21
22			def __init__(self, id):
23			self.id = id
24	joko	1.3	self.children = []
25	joko	1.1
26			def addChild(self, child):
27	joko	1.3	# with Set
28			#self.children.add(child)
29
30			# with list
31			if not child in self.children:
32			self.children.append(child)
33	joko	1.1
34			def __repr__(self):
35	joko	1.3	#print "repr-node"
36	joko	1.1	children_ids = []
37			for child in self.children:
38			child_id = str(child.id)
39			children_ids.append(child_id)
40			return str(self.id) + ': ' + ', '.join(children_ids)
41
42
43			class Graph:
44
45			def __init__(self):
46			self.index = {}
47
48			def getNode(self, id):
49			return self.index[id]
50
51			def addRelation(self, id_parent, id_child):
52
53			# skip action, if parent id == child id
54			if id_parent == id_child:
55			return
56
57			# establish parent node, if not exists
58			if not self.index.has_key(id_parent):
59			self.index[id_parent] = Node(id_parent)
60
61			# establish child node, if not exists
62			if not self.index.has_key(id_child):
63			self.index[id_child] = Node(id_child)
64
65			# add relationships to each node
66			self.index[id_parent].addChild(self.index[id_child])
67			self.index[id_child].addChild(self.index[id_parent])
68
69
70			def computePaths(self, source_node, target_node, max_depth):
71
72			# result list, will contain all valid paths (each path is a list of nodes)
73			result = []
74
75			# start searching
76			self.DLS(source_node, target_node, 0, max_depth, result)
77			return result
78
79			# extended "Depth Limited search (DLS)" implementation
80			# see http://en.wikipedia.org/wiki/Depth-limited_search
81			def DLS(self, node, goal, current_depth, max_depth, result, path=[]):
82	joko	1.3
83			# break recursion if node already visited to prevent looping
84			if node in path: return
85
86	joko	1.1	path.append(node)
87			#print "checking node %s on level %s" % (node, current_depth)
88			#print "path:", path
89			if node is goal:
90			result.append(list(path))
91			else:
92			stack = list(node.children)
93			while stack:
94			mynode = stack.pop()
95			if current_depth < max_depth:
96			self.DLS(mynode, goal, current_depth + 1, max_depth, result, path)
97			path.pop()
98
99			def DLS_orig(self, node, goal, current_depth, max_depth):
100			#print "checking node %s on level %s" % (node, current_depth)
101			if node is goal:
102			return node
103			else:
104			stack = list(node.children)
105			while stack:
106			node = stack.pop()
107			if current_depth < max_depth:
108			self.DLS_orig(node, goal, current_depth + 1, max_depth)
109			else:
110			pass
111
112			def __repr__(self):
113	joko	1.3	#print "repr-graph"
114	joko	1.1	payload = ''
115			for key, node in self.index.iteritems():
116			payload += str(node) + "\n"
117			return payload
118
MailToCvsAdmin">MailToCvsAdmin	ViewVC Help
Powered by ViewVC 1.1.26