@@ -107,6 +107,64 @@ def depth_first_search_recursion(self, current_distance, vertex, end=None):
107107 if neighbor == end :
108108 raise TargetFound
109109
110+ def find_all_paths (self , start , end = None ):
111+ """
112+ Searches for all possible paths
113+
114+ To avoid loops, function is_vertex_valid_for_path must be set
115+
116+ :param Any start: The start vertex to consider
117+ :param Any end: The target/end vertex to consider
118+ :return: A list of paths
119+ """
120+ self .paths = []
121+
122+ return self .dfs_all_paths ([start ], start , end )
123+
124+ def is_vertex_valid_for_path (self , path , vertex ):
125+ """
126+ Determines whether a vertex can be added to a path
127+
128+ The goal is to avoid loops
129+
130+ :param Any path: The current path
131+ :param Any vertex: The vertex to be added to the path
132+ :return: True if the vertex can be added
133+ """
134+ return False
135+
136+ def dfs_all_paths (self , path , vertex , end = None ):
137+ """
138+ Recurrence function for depth-first search
139+
140+ This function will be called each time additional depth is needed
141+ The recursion stack corresponds to the exploration path
142+
143+ :param integer current_distance: The distance from start of the current vertex
144+ :param Any vertex: The vertex being explored
145+ :param Any end: The target/end vertex to consider
146+ :return: nothing
147+ """
148+
149+ neighbors = self .neighbors (vertex )
150+ if not neighbors :
151+ return
152+
153+ for neighbor in neighbors :
154+ if not self .is_vertex_valid_for_path (path , neighbor ):
155+ continue
156+
157+ new_path = path .copy ()
158+
159+ # Adding to path
160+ new_path .append (neighbor )
161+
162+ # Examine the neighbor immediatly
163+ self .dfs_all_paths (new_path , neighbor , end )
164+
165+ if neighbor == end :
166+ self .paths .append (new_path )
167+
110168 def topological_sort (self ):
111169 """
112170 Performs a topological sort
0 commit comments