Opened 15 years ago

Closed 15 years ago

#1652 closed defect (fixed)

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

Reported by: Harald Schilly Owned by: Mike Hansen
Priority: major Milestone: sage-2.10.1
Component: graph theory Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

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 Mike Hansen 15 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 Changed 15 years ago by Harald Schilly

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

comment:2 Changed 15 years ago by Robert Miller

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

comment:3 Changed 15 years ago by Mike Hansen

Owner: changed from Robert Miller to Mike Hansen
Status: new → assigned

Changed 15 years ago by Mike Hansen

Attachment: 1652.patch​ added

comment:4 Changed 15 years ago by Mike Hansen

Summary: length of DAGs with loops calculation runs infinite → [with patch, needs review] length of DAGs with loops calculation runs infinite

comment:5 Changed 15 years ago by ncalexan

Summary: [with patch, needs review] length of DAGs with loops calculation runs infinite → [with patch, with positive review] length of DAGs with loops calculation runs infinite

Code looks good, docstrings and tests seem appropriate.

comment:6 Changed 15 years ago by Michael Abshoff

Resolution: → fixed
Status: assigned → closed

Merged in Sage 2.10.1.alpha1

Note: See TracTickets for help on using tickets.