@@ -196,6 +196,9 @@ def breadth_first_search(self, start, end=None):
196196vertex ,current_distance = frontier .pop (0 )
197197current_distance += 1
198198neighbors = self .neighbors (vertex )
199+ # This allows to cover WeightedGraphs
200+ if isinstance (neighbors ,dict ):
201+ neighbors = list (neighbors .keys ())
199202if not neighbors :
200203continue
201204
@@ -212,8 +215,6 @@ def breadth_first_search(self, start, end=None):
212215if neighbor == end :
213216return True
214217
215- if end :
216- return True
217218return False
218219
219220def greedy_best_first_search (self ,start ,end ):
@@ -444,3 +445,64 @@ def bellman_ford(self, start, end=None):
444445raise NegativeWeightCycle
445446
446447return end is None or end in self .distance_from_start
448+
449+ def ford_fulkerson (self ,start ,end ):
450+ """
451+ Searches for the maximum flow using the Ford-Fulkerson algorithm
452+
453+ The weights of the graph are used as flow limitations
454+ Note: there may be multiple options, this generates only one
455+
456+ :param Any start: The start vertex to consider
457+ :param Any end: The target/end vertex to consider
458+ :return: True when the end vertex is found, False otherwise
459+ """
460+
461+ if start not in vertices :
462+ return ValueError ("Source not in graph" )
463+ if end not in vertices :
464+ return ValueError ("End not in graph" )
465+
466+ if end not in self .edges :
467+ self .edges [end ]= {}
468+
469+ initial_edges = {a :graph .edges [a ].copy ()for a in graph .edges }
470+ self .flow_graph = {a :graph .edges [a ].copy ()for a in graph .edges }
471+
472+ max_flow = 0
473+ frontier = [start ]
474+ heapq .heapify (frontier )
475+ print (self .edges )
476+
477+ while self .breadth_first_search (start ,end ):
478+ path_flow = float ("Inf" )
479+ cursor = end
480+ while cursor != start :
481+ path_flow = min (path_flow ,self .edges [self .came_from [cursor ]][cursor ])
482+ cursor = self .came_from [cursor ]
483+
484+ max_flow += path_flow
485+
486+ # Update the graph to change the flows
487+ cursor = end
488+ while cursor != start :
489+ self .edges [self .came_from [cursor ]][cursor ]-= path_flow
490+ if self .edges [self .came_from [cursor ]][cursor ]== 0 :
491+ del self .edges [self .came_from [cursor ]][cursor ]
492+ self .edges [cursor ][self .came_from [cursor ]]= (
493+ self .edges [cursor ].get (self .came_from [cursor ],0 )+ path_flow
494+ )
495+
496+ cursor = self .came_from [cursor ]
497+
498+ cursor = end
499+ for vertex in self .vertices :
500+ for neighbor ,items in self .neighbors (vertex ).items ():
501+ if neighbor in self .flow_graph [vertex ]:
502+ self .flow_graph [vertex ][neighbor ]-= self .edges [vertex ][neighbor ]
503+ if self .flow_graph [vertex ][neighbor ]== 0 :
504+ del self .flow_graph [vertex ][neighbor ]
505+
506+ self .edges = initial_edges
507+
508+ return max_flow