5
\$\begingroup\$

I have a project that relies on finding all cycles in a graph that pass through a vertex at most k times. Naturally, I'm sticking with the case of k=1 for the sake of development right now. I've come to the conclusion that this algorithm as a depth first search is at worst \$O(kn^{kn})\$ for a complete graph, but I rarely approach this upper bound in the context of the problem, so I would still like to give this approach a try.

I've implemented the following as a part of the project to achieve this end:

class Graph(object):

    ...

    def path_is_valid(self, current_path):
        """
        :param current_path:
        :return: Boolean indicating a whether the given path is valid
        """
        length = len(current_path)
        if length < 3:
            # The path is too short
            return False

        # Passes through vertex twice... sketchy for general case
        if len(set(current_path)) != len(current_path):
            return False

        # The idea here is take a moving window of width three along the path
        # and see if it's contained entirely in a polygon.
        arc_triplets = (current_path[i:i+3] for i in xrange(length-2))
        for triplet in arc_triplets:
            for face in self.non_fourgons:
                if set(triplet) <= set(face):
                    return False

        # This is all kinds of unclear when looking at. There is an edge case
        # pertaining to the beginning and end of a path existing inside of a
        # polygon. The previous filter will not catch this, so we cycle the path
        # and recheck moving window filter.
        path_copy = list(current_path)
        for i in xrange(length):
            path_copy = path_copy[1:] + path_copy[:1]  # wtf
            arc_triplets = (path_copy[i:i+3] for i in xrange(length-2))
            for triplet in arc_triplets:
                for face in self.non_fourgons:
                    if set(triplet) <= set(face):
                        return False

        return True

    def cycle_dfs(self, current_node,  start_node,  graph, current_path):
        """

        :param current_node:
        :param start_node:
        :param graph:
        :param current_path:
        :return:
        """
        if len(current_path) >= 3:
            last_three_vertices = current_path[-3:]
            previous_three_faces = [set(self.faces_containing_arcs[vertex])
                                    for vertex in last_three_vertices]
            intersection_all = set.intersection(*previous_three_faces)
            if len(intersection_all) == 2:
                return []

        if current_node == start_node:
            if self.path_is_valid(current_path):
                return [tuple(shift(list(current_path)))]
            else:
                return []

        else:
            loops = []
            for adjacent_node in set(graph[current_node]):
                current_path.append(adjacent_node)
                graph[current_node].remove(adjacent_node)
                graph[adjacent_node].remove(current_node)
                loops += list(self.cycle_dfs(adjacent_node, start_node,
                                             graph, current_path))
                graph[current_node].append(adjacent_node)
                graph[adjacent_node].append(current_node)
                current_path.pop()
            return loops

path_is_valid() aims to cut down on the number of paths produced by the depth first search as they are found, based upon filtering criteria that are specific to the problem. I tried to explain the purpose of each one reasonably, but everything is clearer in one's own head; I'd be happy to improve the comments if needed.

I'm open to any and all suggestions to improve performance, since, as the profile below shows, this is what is taking all my time.

Also, I'm about to turn to Cython, but my code heavily relies on Python objects and I don't know if that's a smart move. Can anyone shed some light as to whether or not this route is even beneficial with this many native Python data structures involved? I can't seem to find much information on this and it would be appreciated.

Since I know people will ask, I have profiled my entire project and this is the source of the problem:

311         1     18668669 18668669.0     99.6              cycles = self.graph.find_cycles()

Here's the line-profiled output of the self.graph.find_cycles() and self.path_is_valid():

Function: cycle_dfs at line 106
Total time: 11.9584 s 

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
   106                                               def cycle_dfs(self, current_node,  start_node,  graph, current_path):
   107                                                   """
   108                                                   Naive depth first search applied to the pseudo-dual graph of the
   109                                                   reference curve. This sucker is terribly inefficient. More to come.
   110                                                   :param current_node:
   111                                                   :param start_node:
   112                                                   :param graph:
   113                                                   :param current_path:
   114                                                   :return:
   115                                                   """
   116    437035       363181      0.8      3.6          if len(current_path) >= 3:
   117    436508       365213      0.8      3.7              last_three_vertices = current_path[-3:]
   118    436508       321115      0.7      3.2              previous_three_faces = [set(self.faces_containing_arcs[vertex])
   119   1746032      1894481      1.1     18.9                                      for vertex in last_three_vertices]
   120    436508       539400      1.2      5.4              intersection_all = set.intersection(*previous_three_faces)
   121    436508       368725      0.8      3.7              if len(intersection_all) == 2:
   122                                                           return []
   123                                           
   124    437035       340937      0.8      3.4          if current_node == start_node:
   125     34848      1100071     31.6     11.0              if self.path_is_valid(current_path):
   126       486         3400      7.0      0.0                  return [tuple(shift(list(current_path)))]
   127                                                       else:
   128     34362        27920      0.8      0.3                  return []
   129                                           
   130                                                   else:
   131    402187       299968      0.7      3.0              loops = []
   132    839160       842350      1.0      8.4              for adjacent_node in set(graph[current_node]):
   133    436973       388646      0.9      3.9                  current_path.append(adjacent_node)
   134    436973       438763      1.0      4.4                  graph[current_node].remove(adjacent_node)
   135    436973       440220      1.0      4.4                  graph[adjacent_node].remove(current_node)
   136    436973       377422      0.9      3.8                  loops += list(self.cycle_dfs(adjacent_node, start_node,
   137    436973       379207      0.9      3.8                                               graph, current_path))
   138    436973       422298      1.0      4.2                  graph[current_node].append(adjacent_node)
   139    436973       388651      0.9      3.9                  graph[adjacent_node].append(current_node)
   140    436973       412489      0.9      4.1                  current_path.pop()
   141    402187       285471      0.7      2.9              return loops

Function: path_is_valid at line 65
Total time: 1.6726 s

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
65                                               def path_is_valid(self, current_path):
66                                                   """
67                                                   Aims to implicitly filter during dfs to decrease output size. Observe
68                                                   that more complex filters are applied further along in the function.
69                                                   We'd rather do less work to show the path is invalid rather than more,
70                                                   so filters are applied in order of increasing complexity.
71                                                   :param current_path:
72                                                   :return: Boolean indicating a whether the given path is valid
73                                                   """
74     34848        36728      1.1      2.2          length = len(current_path)
75     34848        33627      1.0      2.0          if length < 3:
76                                                       # The path is too short
77        99           92      0.9      0.0              return False
78                                           
79                                                   # Passes through arcs twice... Sketchy for later.
80     34749        89536      2.6      5.4          if len(set(current_path)) != len(current_path):
81     31708        30402      1.0      1.8              return False
82                                           
83                                                   # The idea here is take a moving window of width three along the path
84                                                   # and see if it's contained entirely in a polygon.
85      3041         6287      2.1      0.4          arc_triplets = (current_path[i:i+3] for i in xrange(length-2))
86     20211        33255      1.6      2.0          for triplet in arc_triplets:
87     73574        70670      1.0      4.2              for face in self.non_fourgons:
88     56404        94019      1.7      5.6                  if set(triplet) <= set(face):
89      2477         2484      1.0      0.1                      return False
90                                           
91                                                   # This is all kinds of unclear when looking at. There is an edge case
92                                                   # pertaining to the beginning and end of a path existing inside of a
93                                                   # polygon. The previous filter will not catch this, so we cycle the path
94                                                   # a reasonable amount and recheck moving window filter.
95       564          895      1.6      0.1          path_copy = list(current_path)
96      8028         7771      1.0      0.5          for i in xrange(length):
97      7542        14199      1.9      0.8              path_copy = path_copy[1:] + path_copy[:1]  # wtf
98      7542        11867      1.6      0.7              arc_triplets = (path_copy[i:i+3] for i in xrange(length-2))
99    125609       199100      1.6     11.9              for triplet in arc_triplets:
100    472421       458030      1.0     27.4                  for face in self.non_fourgons:
101    354354       583106      1.6     34.9                      if set(triplet) <= set(face):
102        78           83      1.1      0.0                          return False
103                                           
104       486          448      0.9      0.0          return True
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to CodeReview.SE! Would you be able to give the full code (instead of "...") ? Thanks \$\endgroup\$ – SylvainD Jan 22 '15 at 15:27
  • \$\begingroup\$ The full code is extremely lengthy, as this is part of a much larger project. Are there specific portions that you would like clarified? \$\endgroup\$ – Matt Morse Jan 23 '15 at 16:04
  • 1
    \$\begingroup\$ Fair enough. I quite like having a whole piece of running code so that I can try what I suggest as I write code reviews. \$\endgroup\$ – SylvainD Jan 23 '15 at 16:16
  • \$\begingroup\$ That's a fairly reasonable request. If you would like something will run for you, turn if current_node == start_node: if self.path_is_valid(current_path): return [tuple(shift(list(current_path)))] else: return [] into: if current_node == start_node: return [tuple(current_path)] or something to that effect. If you create a simple graph represented as an adjacency list, that can be your input to cycle_dfs() \$\endgroup\$ – Matt Morse Jan 25 '15 at 20:42
  • \$\begingroup\$ The problem is that it's pretty hard to help with regards to performance when we don't have full code. \$\endgroup\$ – IEatBagels Dec 4 '18 at 18:28
1
\$\begingroup\$
    def cycle_dfs(self, current_node,  start_node,  graph, current_path):
        ...
        if len(current_path) >= 3:
            last_three_vertices = current_path[-3:]
            previous_three_faces = [set(self.faces_containing_arcs[vertex])
                                    for vertex in last_three_vertices]
            intersection_all = set.intersection(*previous_three_faces)
            if len(intersection_all) == 2:
                return []

faces_containing_arcs[vertex] suggests to me that something is badly named. I'd expect to see faces_containing_vertex[vertex].


        if current_node == start_node:
            if self.path_is_valid(current_path):
                return [tuple(shift(list(current_path)))]
            else:
                return []

This is the really interesting section of cycle_dfs. Every path which is returned ultimately passes through this path_is_valid check. But some aspects of path_is_valid can be checked before we finish building the path, allowing a massive short-circuit. The previous section of cycle_dfs does this already with one condition.

So let's look at the validity conditions:

  1.         length = len(current_path)
            if length < 3:
                # The path is too short
                return False
    

    Trivial.

  2.         # Passes through vertex twice... sketchy for general case
            if len(set(current_path)) != len(current_path):
                return False
    

    Easily updated iteratively. I would suggest that for readability this could be done as a filter on for adjacent_node. The \$k > 1\$ case is easily handled with a Counter:

                for adjacent_node in set(graph[current_node]):
                    if adjacent_node != start_node and visit_count[adjacent_node] >= k:
                        continue
    
                    visit_count[adjacent_node] += 1
                    ... # Current loop body
                    visit_count[adjacent_node] -= 1
    

    (Or perhaps the special case could be handled by not initialising visit_count[start_node] to 1).

  3.         # The idea here is take a moving window of width three along the path
            # and see if it's contained entirely in a polygon.
            arc_triplets = (current_path[i:i+3] for i in xrange(length-2))
            for triplet in arc_triplets:
                for face in self.non_fourgons:
                    if set(triplet) <= set(face):
                        return False
    

    Easily checked for the last window in cycle_dfs.

  4.         # This is all kinds of unclear when looking at. There is an edge case
            # pertaining to the beginning and end of a path existing inside of a
            # polygon. The previous filter will not catch this, so we cycle the path
            # and recheck moving window filter.
            path_copy = list(current_path)
            for i in xrange(length):
                path_copy = path_copy[1:] + path_copy[:1]  # wtf
                arc_triplets = (path_copy[i:i+3] for i in xrange(length-2))
                for triplet in arc_triplets:
                    for face in self.non_fourgons:
                        if set(triplet) <= set(face):
                            return False
    

    I think the WTF here is the whole section, rather than the one line. (Although reusing i to mean something else in a nested loop is a particular highlight: I wouldn't want to place money on how that behaves without first having tested it). As I understand the comment, this just wants to repeat condition 3 for current_path[-2:] + current_path[:1] and current_path[-1:] + current_path[:2].

    If this is simplified to do only that, it can only be checked when closing the cycle.

So moving the check of conditions 2 and 3 of path_is_valid into cycle_dfs, with a specialised strategy for 2, would seem to be the biggest way to improvement performance, possibly speeding up cycle_dfs by orders of magnitude. Based on the timings, fixing condition 4 would speed up path_is_valid by a factor of about 4 (replacing 76% of the execution time with, effectively, a couple of extra iterations of a loop which currently takes a total of 8.5% of the time), but that in itself would only be an 8% improvement to cycle_dfs.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.