forked from pmatiello/python-graph
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcritical.py
More file actions
162 lines (129 loc) · 5.57 KB
/
Copy pathcritical.py
File metadata and controls
162 lines (129 loc) · 5.57 KB
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
# Copyright (c) 2009 Pedro Matiello <pmatiello@gmail.com>
# Tomaz Kovacic <tomaz.kovacic@gmail.com>
#
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.
"""
Critical path algorithms and transitivity detection algorithm.
@sort: transitive_edges, critical_path
"""
# Imports
from pygraph.algorithms.cycles import find_cycle
from pygraph.algorithms.sorting import topological_sorting
def _intersection(A,B):
"""
A simple function to find an intersection between two arrays.
@type A: List
@param A: First List
@type B: List
@param B: Second List
@rtype: List
@return: List of Intersections
"""
intersection = []
for i in A:
if i in B:
intersection.append(i)
return intersection
def transitive_edges(graph):
"""
Return a list of transitive edges.
Example of transitivity within graphs: A -> B, B -> C, A -> C
in this case the transitive edge is: A -> C
@attention: This function is only meaningful for directed acyclic graphs.
@type graph: digraph
@param graph: Digraph
@rtype: List
@return: List containing tuples with transitive edges (or an empty array if the digraph
contains a cycle)
"""
#if the graph contains a cycle we return an empty array
if not len(find_cycle(graph)) == 0:
return []
tranz_edges = [] # create an empty array that will contain all the tuples
#run trough all the nodes in the graph
for start in topological_sorting(graph):
#find all the successors on the path for the current node
successors = []
for a in graph.traversal(start):
successors.append(a)
del successors[0] #we need all the nodes in it's path except the start node itself
for next in successors:
#look for an intersection between all the neighbors of the
#given node and all the neighbors from the given successor
intersect_array = _intersection(graph.neighbors(next), graph.neighbors(start) )
for a in intersect_array:
if graph.has_edge(start, a):
##check for the detected edge and append it to the returned array
tranz_edges.append( (start,a) )
return tranz_edges # return the final array
def critical_path(graph):
"""
Compute and return the critical path in an acyclic directed weighted graph.
@attention: This function is only meaningful for directed weighted acyclic graphs
@type graph: digraph
@param graph: Digraph
@rtype: List
@return: List containing all the nodes in the path (or an empty array if the graph
contains a cycle)
"""
#if the graph contains a cycle we return an empty array
if not len(find_cycle(graph)) == 0:
return []
#this empty dictionary will contain a tuple for every single node
#the tuple contains the information about the most costly predecessor
#of the given node and the cost of the path to this node
#(predecessor, cost)
node_tuples = {}
topological_nodes = topological_sorting(graph)
#all the tuples must be set to a default value for every node in the graph
for node in topological_nodes:
node_tuples.update( {node :(None, 0)} )
#run trough all the nodes in a topological order
for node in topological_nodes:
predecessors =[]
#we must check all the predecessors
for pre in graph.incidents(node):
max_pre = node_tuples[pre][1]
predecessors.append( (pre, graph.edge_weight( pre, node ) + max_pre ) )
max = 0; max_tuple = (None, 0)
for i in predecessors:#look for the most costly predecessor
if i[1] >= max:
max = i[1]
max_tuple = i
#assign the maximum value to the given node in the node_tuples dictionary
node_tuples[node] = max_tuple
#find the critical node
max = 0; critical_node = None
for k,v in list(node_tuples.items()):
if v[1] >= max:
max= v[1]
critical_node = k
path = []
#find the critical path with backtracking trought the dictionary
def mid_critical_path(end):
if node_tuples[end][0] != None:
path.append(end)
mid_critical_path(node_tuples[end][0])
else:
path.append(end)
#call the recursive function
mid_critical_path(critical_node)
path.reverse()
return path #return the array containing the critical path