scripts/sixdegrees/sixtest.py

#!/usr/bin/env python

# $Id: sixtest.py,v 1.1 2008/02/06 01:22:13 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 random
from sixdegrees import Graph, Node


# maximum search depth (DLS limiter)
MAX_SEARCH_DEPTH = 5

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


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):
  
  for parent_id in range(1, RANDOM_MAX_NODES + 1):
    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)

  """
  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 node %s to %s" % (source_node.id, target_node.id)
  print '-' * 42
  paths = graph.computePaths(source_node, target_node, MAX_SEARCH_DEPTH)
  
  # 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__':
  main()
1	joko	1.1	#!/usr/bin/env python
2
3	joko	1.2	# $Id: sixtest.py,v 1.1 2008/02/06 01:22:13 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			import random
22			from sixdegrees import Graph, Node
23
24
25			# maximum search depth (DLS limiter)
26			MAX_SEARCH_DEPTH = 5
27
28			# settings for random graph
29			RANDOM_MAX_NODES = 10
30			RANDOM_MAX_CHILDREN_PER_NODE = 5
31	joko	1.2	RANDOM_MAX_NODES = 10000
32			RANDOM_MAX_CHILDREN_PER_NODE = 10
33	joko	1.1
34
35			def operateOnFixedGraph():
36
37			# 1. create fixed graph (for testing)
38			# 4: 6, 10
39			# 5: 6, 9
40			# 6: 5, 4
41			print '-' * 42
42			print ' Generating fixed graph'
43			print '-' * 42
44			graph = Graph()
45			graph.addRelation(4, 6)
46			graph.addRelation(4, 10)
47			graph.addRelation(5, 6)
48			graph.addRelation(5, 9)
49			graph.addRelation(6, 5)
50			graph.addRelation(6, 4)
51			print graph
52
53			# 2. choose two fixed nodes (for testing)
54			node1 = graph.getNode(4)
55			node2 = graph.getNode(5)
56
57			findAllPaths(graph, node1, node2)
58
59
60			def buildRandomGraph(graph):
61
62			for parent_id in range(1, RANDOM_MAX_NODES + 1):
63			for j in range(1, random.randint(1, RANDOM_MAX_CHILDREN_PER_NODE)):
64			child_id = random.randint(1, RANDOM_MAX_NODES)
65			graph.addRelation(parent_id, child_id)
66
67			"""
68			RANDOM_MAX_NODES = 10
69			for i in range(1, RANDOM_MAX_NODES + 1):
70			parent_id = random.randint(1, RANDOM_MAX_NODES)
71			child_id = random.randint(1, RANDOM_MAX_NODES)
72			graph.addRelation(parent_id, child_id)
73			"""
74
75			def operateOnRandomGraph():
76
77			# 1. create random graph
78			print '-' * 42
79			print ' Generating random graph'
80			print '-' * 42
81			graph = Graph()
82			buildRandomGraph(graph)
83			print graph
84
85			# 2. choose two random distinct nodes
86			node1 = graph.getNode(random.choice(graph.index.keys()))
87			node2 = node1
88			while node1 is node2:
89			node2 = graph.getNode(random.choice(graph.index.keys()))
90
91			findAllPaths(graph, node1, node2)
92
93
94			def findAllPaths(graph, source_node, target_node):
95
96			# 1. calculate paths
97			print '-' * 42
98			print " Finding paths from node %s to %s" % (source_node.id, target_node.id)
99			print '-' * 42
100			paths = graph.computePaths(source_node, target_node, MAX_SEARCH_DEPTH)
101
102			# 2. output paths
103			#print paths
104			for path in paths:
105			id_list = []
106			for node in path:
107			id_list.append(str(node.id))
108			print ' -> '.join(id_list)
109			#print '-' * 21
110
111
112			def main():
113			#operateOnFixedGraph()
114			operateOnRandomGraph()
115
116
117			if __name__ == '__main__':
118			main()
MailToCvsAdmin">MailToCvsAdmin	ViewVC Help
Powered by ViewVC 1.1.26