Repostting this question as I received some garbage answer the earlier time. Pyt

Question

Repostting this question as I received some garbage answer the earlier time.

Python program: Need a working algorithm in python… no pseudocode please.

Implement the Ford-Fulkerson maximum-flowalgorithm using python (Hint: see section 7.2.3 in http://www The restriction is that you have to always choose the shortest path in terms of number of edges, irrespective of the capacities or flows between the source (s) and target (t). To implement the program -if you are given a directed graph with integer (positive) capacities on the edges you have to find a s-t shortest path in terms of length, which is used to create the residual graph, and keep repeating until no path can be found. This w ndicate that maximum-flow has been achieved Consider a sample input file as follows: 0 1 3 0 2 3 0 3 4 1 4 2 2 1 10 2 4 1 3 55 4 3 1 4 5 1 47 2 575

Explanation / Answer

class InvalidTree(Exception): pass class BinaryTree(object): def __init__(self, root=None, left=None, right=None, leaf=False, **kwargs): """ Basic binary tree (with insertion, no deletion). """ self.root = root self.parent = None self._left = None self._right = None if not leaf: self.left = left self.right = right else: if left or right: raise InvalidTree("Leaves have no children!") # use kwargs to store additional data on the root node for k, v in kwargs.iteritems(): setattr(self, k, v) def __iter__(self): """ Does *in-order* iteration. """ if self.left: for node in self.left: yield node yield self if self.right: for node in self.right: yield node def __eq__(self, other): return self.root == other def __nonzero__(self): return self.root is not None def __repr__(self): return "".format(self) def __str__(self): return str(self.root or "Empty") def __int__(self): return int(self.root) def _insert(self, side, value): """ This is just a convenient way to not have to write both an insert_left and insert_right function that do the same thing. """ b_tree_value = BinaryTree(value, leaf=True) return self._attach(side, b_tree_value) def _attach(self, side, tree): current_value = getattr(self, side) if not current_value: setattr(self, side, tree) else: setattr(tree, side, current_value) setattr(self, side, tree) current_value.parent = tree tree.parent = self @property def height(self): if not self: return 0 elif not self.left and not self.right: return 1 else: return 1 + max(getattr(self.left, "height", 0), getattr(self.right, "height", 0)) @property def left(self): return self._left @left.setter def left(self, value): return self._insert("_left", value) @property def right(self): return self._right @right.setter def right(self, value): return self._insert("_right", value) @property def leaves(self): return [node for node in self if not node.left and not node.right] def iter_in_order(self): """ Does *in-order* iteration. """ return iter(self) def iter_pre_order(self): yield self if self.left: for node in self.left.iter_pre_order(): yield node if self.right: for node in self.right.iter_pre_order(): yield node def iter_post_order(self): if self.left: for node in self.left.iter_post_order(): yield node if self.right: for node in self.right.iter_post_order(): yield node yield self def attach_left(self, tree): """ Attach an existing tree to a node. """ return self._attach("_left", tree) def attach_right(self, tree): return self._attach("_right", tree) def count(text, sort=False, reverse=False): counted = ((letter, text.count(letter)) for letter in set(text)) if sort: counted = sorted(counted, key=itemgetter(1), reverse=reverse) return counted def get_huffman_tree(text, do_count=False): """ O(n) Huffman coding implementation using two (de)queues. (Direct translation from algorithm to Python code.) """ if do_count: text = count(text, sort=True) # construct a deque containing leaves out of the frequencies returned by # count. store the letter in an attr of each node initial_weights = deque([BinaryTree(l[1], leaf=True, letter=l[0]) for l in text]) combined_weights = deque() while len(initial_weights) + len(combined_weights) > 1: least_two_nodes = [] # (for loop over range(2) = do this twice) for _ in range(2): if not initial_weights or not combined_weights: least_two_nodes.append( (initial_weights or combined_weights).popleft()) elif initial_weights[0].root

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.