0
$\begingroup$

I have a directed acyclic graph (DAG). How I can find the longest path using only vertices with degree at most 2?

Currently, I try this

def all_simple_paths(g):
  for path in all_paths(g):
      if len(path) > 2:
          center_path = path[1:-1]
          nodes_degree = g.degree(center_path).values()
          if max(nodes_degree) <= 2:
              return path

but that might output any path, rather than the longest path.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! I'm having a hard time understanding what you are asking. What does "the more longest paths" mean? Are you looking for the longest path, such that every vertex in the path has degree 2? Please edit your question to clarify. Also, please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. (For instance, it's not clear what all_paths() is, or path[1:-1].) Thank you! $\endgroup$ – D.W. Oct 20 '16 at 18:28
  • 1
    $\begingroup$ A path where every vertex has degree 2 is a cycle. So you are looking for the longest cycle in a directed acyclic graph (DAG)? I assume you want to compute the longest path in a DAG. $\endgroup$ – dtt Oct 21 '16 at 11:34
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Longest_path_problem $\endgroup$ – adrianN Oct 21 '16 at 14:02
3
$\begingroup$

First, remove all vertices whose degree is greater than 2 (i.e., their degree was greater than 2 in the original graph). The result is a smaller DAG. This can be done in linear time.

Now, find the longest path in the resulting DAG. This can be done in linear time, too; see https://en.wikipedia.org/wiki/Longest_path_problem.

$\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.