Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Graph properties for the attached graph doesn't come back. #17

Closed
jdramsey opened this issue Nov 3, 2015 · 2 comments
Closed

Graph properties for the attached graph doesn't come back. #17

jdramsey opened this issue Nov 3, 2015 · 2 comments
Labels
Milestone

Comments

@jdramsey
Copy link
Collaborator

jdramsey commented Nov 3, 2015

native_smooth_clean_master_graph.txt

The problem is the cycle checker. It checks for each node, depth first, whether there is a path from that node to itself. The question is whether there's a better way. Perhaps breadth first?

@jdramsey jdramsey added the bug label Nov 3, 2015
@jdramsey jdramsey added this to the 5.2.2 release milestone Nov 3, 2015
@jdramsey
Copy link
Collaborator Author

jdramsey commented Nov 3, 2015

There is a breadth first path checker in GraphUtils; it was not however configured to find cyclic paths. Reconfigured it. Now the distinction between cyclic and acyclic graphs can be scaled up for EdgeListGraph. That is, if the existsDirectedCycle() method is called on an EdgeListGraph, it will quickly distinguish cyclic from acyclic graphs.

This solution needs to be copied to other graph classes. Also, the example cyclic path may need to be commented out for now, since it's going to have the same problem as the depth first cycle checker.

@jdramsey jdramsey mentioned this issue Nov 3, 2015
@jdramsey
Copy link
Collaborator Author

jdramsey commented Nov 3, 2015

The latest commit fixes #17, though for now at least I've commented out the "example cycle" line in the graph properties dialog, since it has the same problem as the depth-first cycle checker did. Maybe at some point a breadth-first algorithm can be written to recover an example cycle quickly from a graph.

@jdramsey jdramsey closed this as completed Nov 3, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant