Opened 12 years ago

Closed 12 years ago

#1652 closed defect (fixed)

[with patch, with positive review] length of DAGs with loops calculation runs infinite

Reported by: schilly Owned by: mhansen
Priority: major Milestone: sage-2.10.1
Component: graph theory Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

G4 has a loop: 2->4 and 4->2

G4 = DiGraph({1:[2,2,3,5], 2:[3,4], 3:[4], 4:[2,5,7], 5:[6]}, multiedges=True)
G4_path.count()

RuntimeError: maximum recursion depth exceeded


There are related issues calulating incoming_paths and possibly more in sage.combinat.graph_path!

Attachments (1)

1652.patch (3.9 KB) - added by mhansen 12 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 Changed 12 years ago by schilly

ah, solution is very simple: just check if G4.is_directed_acyclic() is true ;)

comment:2 Changed 12 years ago by rlm

Could you be more specific? I have no idea what G4_path is. Also, could you post a full traceback?

comment:3 Changed 12 years ago by mhansen

  • Owner changed from rlm to mhansen
  • Status changed from new to assigned

Changed 12 years ago by mhansen

comment:4 Changed 12 years ago by mhansen

  • Summary changed from length of DAGs with loops calculation runs infinite to [with patch, needs review] length of DAGs with loops calculation runs infinite

comment:5 Changed 12 years ago by ncalexan

  • Summary changed from [with patch, needs review] length of DAGs with loops calculation runs infinite to [with patch, with positive review] length of DAGs with loops calculation runs infinite

Code looks good, docstrings and tests seem appropriate.

comment:6 Changed 12 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from assigned to closed

Merged in Sage 2.10.1.alpha1

Note: See TracTickets for help on using tickets.