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	joko	1.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