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	# $Id: sixdegrees.py,v 1.2 2008/02/06 01:45:22 joko Exp $
2
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	# GNU Affero General Public License for more details.
14	#
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	#from sets import Set
19
20	class Node:
21
22	def __init__(self, id):
23	self.id = id
24	self.children = []
25
26	def addChild(self, child):
27	# 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):
35	#print "repr-node"
36	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
83	# break recursion if node already visited to prevent looping
84	if node in path: return
85
86	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	#print "repr-graph"
114	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