scripts/sixdegrees/sixdegrees.py

# $Id$

# (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 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 = Set()
  
  def addChild(self, child):
    self.children.add(child)

  def __repr__(self):
    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=[]):
    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)
        else:
          pass
    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):
    payload = ''
    for key, node in self.index.iteritems():
      payload += str(node) + "\n"
    return payload

1	# $Id$
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 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 = Set()
25
26	def addChild(self, child):
27	self.children.add(child)
28
29	def __repr__(self):
30	children_ids = []
31	for child in self.children:
32	child_id = str(child.id)
33	children_ids.append(child_id)
34	return str(self.id) + ': ' + ', '.join(children_ids)
35
36
37	class Graph:
38
39	def __init__(self):
40	self.index = {}
41
42	def getNode(self, id):
43	return self.index[id]
44
45	def addRelation(self, id_parent, id_child):
46
47	# skip action, if parent id == child id
48	if id_parent == id_child:
49	return
50
51	# establish parent node, if not exists
52	if not self.index.has_key(id_parent):
53	self.index[id_parent] = Node(id_parent)
54
55	# establish child node, if not exists
56	if not self.index.has_key(id_child):
57	self.index[id_child] = Node(id_child)
58
59	# add relationships to each node
60	self.index[id_parent].addChild(self.index[id_child])
61	self.index[id_child].addChild(self.index[id_parent])
62
63
64	def computePaths(self, source_node, target_node, max_depth):
65
66	# result list, will contain all valid paths (each path is a list of nodes)
67	result = []
68
69	# start searching
70	self.DLS(source_node, target_node, 0, max_depth, result)
71	return result
72
73	# extended "Depth Limited search (DLS)" implementation
74	# see http://en.wikipedia.org/wiki/Depth-limited_search
75	def DLS(self, node, goal, current_depth, max_depth, result, path=[]):
76	path.append(node)
77	#print "checking node %s on level %s" % (node, current_depth)
78	#print "path:", path
79	if node is goal:
80	result.append(list(path))
81	else:
82	stack = list(node.children)
83	while stack:
84	mynode = stack.pop()
85	if current_depth < max_depth:
86	self.DLS(mynode, goal, current_depth + 1, max_depth, result, path)
87	else:
88	pass
89	path.pop()
90
91	def DLS_orig(self, node, goal, current_depth, max_depth):
92	#print "checking node %s on level %s" % (node, current_depth)
93	if node is goal:
94	return node
95	else:
96	stack = list(node.children)
97	while stack:
98	node = stack.pop()
99	if current_depth < max_depth:
100	self.DLS_orig(node, goal, current_depth + 1, max_depth)
101	else:
102	pass
103
104	def __repr__(self):
105	payload = ''
106	for key, node in self.index.iteritems():
107	payload += str(node) + "\n"
108	return payload
109
MailToCvsAdmin">MailToCvsAdmin	ViewVC Help
Powered by ViewVC 1.1.26