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$
3
  • $\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, 2016 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, 2016 at 11:34
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Longest_path_problem $\endgroup$
    – adrianN
    Oct 21, 2016 at 14:02

1 Answer 1

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 and acknowledge you have read our privacy policy.

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