1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
'''
Created on Aug 25, 2009
@author: seif
'''
import copy
class Graph():
def __init__(self):
self.events = []
self.nodes = {}
def set_graph(self, events):
self.__set_uri_graph(events)
def __set_uri_graph(self, events):
self.last_node = None
last_timestamp = None
self.nodes.clear()
for event in events:
self._append_to_graph(event)
print "done"
def _append_to_graph(self, event):
uri = event["uri"]
if (self.last_node == None or not self.last_node.id == uri):
if not self.nodes.has_key(uri):
self.nodes[uri] = Node(uri)
node = self.nodes[uri]
node.item = event
if self.last_node:
link = Link(self.last_node, node)
if not self.last_node.outgoing.has_key(node.id):
self.last_node.outgoing[node.id] = link
if not node.incoming.has_key(self.last_node.id):
node.incoming[self.last_node.id] = link
node.incoming[self.last_node.id].count+=1
node.incoming[self.last_node.id].lifetime += (event["timestamp"] - self.last_node.item["timestamp"])
self.last_node = node
self.events.append(event)
def get_neighbourhood(self, node, depth, check_list, travers = ["+","-"], node_list=[] ):
#print "---> ", node
node_list.append(node)
root = Node(node.id)
root.item = copy.copy(node.item)
if depth > 0:
if "+" in travers:
for out in node.outgoing.values():
root_out = copy.copy(out)
root_out.first_node = root
next = self.get_neighbourhood(root_out.last_node, depth - 1, check_list, ["+"], node_list)
if next:
arrow = root.id+"->"+next.id
if not arrow in check_list:
check_list.append(arrow)
root_out.last_node = next
root.outgoing[out.last_node.id] = root_out
if "-" in travers:
for ins in node.incoming.values():
root_in = copy.copy(ins)
root_in.last_node = root
prev = self.get_neighbourhood(root_in.first_node, depth - 1, check_list, ["-"], node_list)
if prev:
arrow = prev.id+"->"+root.id
if not arrow in check_list:
check_list.append(arrow)
root_in.first_node = prev
root.incoming[ins.first_node.id] = root_in
return root
class Node():
def __init__(self, id):
self.id = id
self.incoming = {}
self.outgoing = {}
self.item = None
def clear(self):
self.incoming.clear()
self.outgoing.clear()
class Link(object):
def __init__(self, first_node, last_node):
self.first_node = first_node
self.last_node = last_node
self.count = 0
self.event = None
self.lifetime = last_node.item["timestamp"] - first_node.item["timestamp"]
|