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	#!/usr/bin/env python
2
3	# $Id: sixtest.py,v 1.4 2008/02/06 03:14:58 joko Exp $
4
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	# GNU Affero General Public License for more details.
16	#
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	import sys
22	import random
23	from sixdegrees import Graph, Node
24
25
26	# maximum search depth (DLS limiter)
27	MAX_SEARCH_DEPTH = 4
28
29	# settings for random graph
30	#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
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	count = 0
73	for parent_id in range(1, RANDOM_MAX_NODES + 1):
74	count += 1
75	if count % 100 == 0:
76	sys.stderr.write('.')
77	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	sys.stderr.write("\n")
81
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	#print graph
99
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	print " Finding paths from %s to %s (depth=%s)" % (source_node.id, target_node.id, MAX_SEARCH_DEPTH)
114	print " Using JIT (Psyco):", bool(sys.modules.get('psyco'))
115	print '-' * 42
116
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
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	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	main()
MailToCvsAdmin">MailToCvsAdmin	ViewVC Help
Powered by ViewVC 1.1.26