scripts/sixdegrees/sixtest.py

#!/usr/bin/env python

# $Id: sixtest.py,v 1.4 2008/02/06 03:14:58 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/>.


import sys
import random
from sixdegrees import Graph, Node


# maximum search depth (DLS limiter)
MAX_SEARCH_DEPTH = 4

# settings for random graph
#RANDOM_MAX_NODES = 10
#RANDOM_MAX_CHILDREN_PER_NODE = 5
RANDOM_MAX_NODES = 10000
RANDOM_MAX_CHILDREN_PER_NODE = 20


ENABLE_PROFILING = False
ENABLE_JIT = True


if ENABLE_PROFILING:
  import profile
  from profile import Profile


def operateOnFixedGraph():

  # 1. create fixed graph (for testing)
  # 4: 6, 10
  # 5: 6, 9
  # 6: 5, 4
  print '-' * 42
  print '  Generating fixed graph'
  print '-' * 42
  graph = Graph()
  graph.addRelation(4, 6)
  graph.addRelation(4, 10)
  graph.addRelation(5, 6)
  graph.addRelation(5, 9)
  graph.addRelation(6, 5)
  graph.addRelation(6, 4)
  print graph
  
  # 2. choose two fixed nodes (for testing)
  node1 = graph.getNode(4)
  node2 = graph.getNode(5)
  
  findAllPaths(graph, node1, node2)


def buildRandomGraph(graph):
  
  count = 0
  for parent_id in range(1, RANDOM_MAX_NODES + 1):
    count += 1
    if count % 100 == 0:
      sys.stderr.write('.')
    for j in range(1, random.randint(1, RANDOM_MAX_CHILDREN_PER_NODE)):
      child_id = random.randint(1, RANDOM_MAX_NODES)
      graph.addRelation(parent_id, child_id)
  sys.stderr.write("\n")

  """
  RANDOM_MAX_NODES = 10
  for i in range(1, RANDOM_MAX_NODES + 1):
    parent_id = random.randint(1, RANDOM_MAX_NODES)
    child_id = random.randint(1, RANDOM_MAX_NODES)
    graph.addRelation(parent_id, child_id)
  """

def operateOnRandomGraph():

  # 1. create random graph
  print '-' * 42
  print '  Generating random graph'
  print '-' * 42
  graph = Graph()
  buildRandomGraph(graph)
  #print graph

  # 2. choose two random distinct nodes
  node1 = graph.getNode(random.choice(graph.index.keys()))
  node2 = node1
  while node1 is node2:
    node2 = graph.getNode(random.choice(graph.index.keys()))

  findAllPaths(graph, node1, node2)


def findAllPaths(graph, source_node, target_node):

  # 1. calculate paths
  print '-' * 42
  print "  Finding paths from %s to %s (depth=%s)" % (source_node.id, target_node.id, MAX_SEARCH_DEPTH)
  print "  Using JIT (Psyco):", bool(sys.modules.get('psyco'))
  print '-' * 42

  """
  def doCompute():
    #global paths
    paths = graph.computePaths(source_node, target_node, MAX_SEARCH_DEPTH)
    return paths
  """
  
  if ENABLE_PROFILING:
    global paths
    paths = []
    p = Profile()
    p.runcall(doCompute)
    p.print_stats()
  else:
    paths = graph.computePaths(source_node, target_node, MAX_SEARCH_DEPTH)
  
  #p.create_stats()
  #a = p.dump_stats()
  #print a
  #print dir(p)
  #for key, value in p.timings.iteritems():
  #  print '%s: %s' % (key, value)
  
  # 2. output paths
  #print paths
  for path in paths:
    id_list = []
    for node in path:
      id_list.append(str(node.id))
    print ' -> '.join(id_list)
    #print '-' * 21


def main():
  #operateOnFixedGraph()
  operateOnRandomGraph()
  

if __name__ == '__main__':
  if ENABLE_JIT:
    # Import Psyco if available
    try:
      import psyco
      psyco.log()
      psyco.full()
    except ImportError:
      pass
  main()
1	joko	1.1	#!/usr/bin/env python
2
3	joko	1.5	# $Id: sixtest.py,v 1.4 2008/02/06 03:14:58 joko Exp $
4	joko	1.1
5			# (c) 2008 Andreas Motl <andreas.motl@ilo.de>
6
7			# This program is free software: you can redistribute it and/or modify
8			# it under the terms of the GNU Affero General Public License as published by
9			# the Free Software Foundation, either version 3 of the License, or
10			# (at your option) any later version.
11			#
12			# This program is distributed in the hope that it will be useful,
13			# but WITHOUT ANY WARRANTY; without even the implied warranty of
14			# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15	joko	1.2	# GNU Affero General Public License for more details.
16	joko	1.1	#
17			# You should have received a copy of the GNU Affero General Public License
18			# along with this program. If not, see <http://www.gnu.org/licenses/>.
19
20
21	joko	1.5	import sys
22	joko	1.1	import random
23			from sixdegrees import Graph, Node
24
25
26			# maximum search depth (DLS limiter)
27	joko	1.5	MAX_SEARCH_DEPTH = 4
28	joko	1.1
29			# settings for random graph
30	joko	1.5	#RANDOM_MAX_NODES = 10
31			#RANDOM_MAX_CHILDREN_PER_NODE = 5
32			RANDOM_MAX_NODES = 10000
33			RANDOM_MAX_CHILDREN_PER_NODE = 20
34
35
36			ENABLE_PROFILING = False
37			ENABLE_JIT = True
38
39
40			if ENABLE_PROFILING:
41			import profile
42			from profile import Profile
43	joko	1.1
44
45			def operateOnFixedGraph():
46
47			# 1. create fixed graph (for testing)
48			# 4: 6, 10
49			# 5: 6, 9
50			# 6: 5, 4
51			print '-' * 42
52			print ' Generating fixed graph'
53			print '-' * 42
54			graph = Graph()
55			graph.addRelation(4, 6)
56			graph.addRelation(4, 10)
57			graph.addRelation(5, 6)
58			graph.addRelation(5, 9)
59			graph.addRelation(6, 5)
60			graph.addRelation(6, 4)
61			print graph
62
63			# 2. choose two fixed nodes (for testing)
64			node1 = graph.getNode(4)
65			node2 = graph.getNode(5)
66
67			findAllPaths(graph, node1, node2)
68
69
70			def buildRandomGraph(graph):
71
72	joko	1.5	count = 0
73	joko	1.1	for parent_id in range(1, RANDOM_MAX_NODES + 1):
74	joko	1.5	count += 1
75			if count % 100 == 0:
76			sys.stderr.write('.')
77	joko	1.1	for j in range(1, random.randint(1, RANDOM_MAX_CHILDREN_PER_NODE)):
78			child_id = random.randint(1, RANDOM_MAX_NODES)
79			graph.addRelation(parent_id, child_id)
80	joko	1.5	sys.stderr.write("\n")
81	joko	1.1
82			"""
83			RANDOM_MAX_NODES = 10
84			for i in range(1, RANDOM_MAX_NODES + 1):
85			parent_id = random.randint(1, RANDOM_MAX_NODES)
86			child_id = random.randint(1, RANDOM_MAX_NODES)
87			graph.addRelation(parent_id, child_id)
88			"""
89
90			def operateOnRandomGraph():
91
92			# 1. create random graph
93			print '-' * 42
94			print ' Generating random graph'
95			print '-' * 42
96			graph = Graph()
97			buildRandomGraph(graph)
98	joko	1.5	#print graph
99	joko	1.1
100			# 2. choose two random distinct nodes
101			node1 = graph.getNode(random.choice(graph.index.keys()))
102			node2 = node1
103			while node1 is node2:
104			node2 = graph.getNode(random.choice(graph.index.keys()))
105
106			findAllPaths(graph, node1, node2)
107
108
109			def findAllPaths(graph, source_node, target_node):
110
111			# 1. calculate paths
112			print '-' * 42
113	joko	1.4	print " Finding paths from %s to %s (depth=%s)" % (source_node.id, target_node.id, MAX_SEARCH_DEPTH)
114	joko	1.5	print " Using JIT (Psyco):", bool(sys.modules.get('psyco'))
115	joko	1.1	print '-' * 42
116	joko	1.5
117			"""
118			def doCompute():
119			#global paths
120			paths = graph.computePaths(source_node, target_node, MAX_SEARCH_DEPTH)
121			return paths
122			"""
123
124			if ENABLE_PROFILING:
125			global paths
126			paths = []
127			p = Profile()
128			p.runcall(doCompute)
129			p.print_stats()
130			else:
131			paths = graph.computePaths(source_node, target_node, MAX_SEARCH_DEPTH)
132
133			#p.create_stats()
134			#a = p.dump_stats()
135			#print a
136			#print dir(p)
137			#for key, value in p.timings.iteritems():
138			# print '%s: %s' % (key, value)
139	joko	1.1
140			# 2. output paths
141			#print paths
142			for path in paths:
143			id_list = []
144			for node in path:
145			id_list.append(str(node.id))
146			print ' -> '.join(id_list)
147			#print '-' * 21
148
149
150			def main():
151			#operateOnFixedGraph()
152			operateOnRandomGraph()
153
154
155			if __name__ == '__main__':
156	joko	1.5	if ENABLE_JIT:
157			# Import Psyco if available
158			try:
159			import psyco
160			psyco.log()
161			psyco.full()
162			except ImportError:
163			pass
164	joko	1.1	main()
MailToCvsAdmin">MailToCvsAdmin	ViewVC Help
Powered by ViewVC 1.1.26