Opened 8 months ago
Last modified 7 months ago
#20834 new enhancement
Implement Bixby and Wagner's Almost LinearTime Algorithm for Graph Realization
Reported by:  tara  Owned by:  

Priority:  major  Milestone:  sage7.3 
Component:  matroid theory  Keywords:  
Cc:  Stefan, yomcat  Merged in:  
Authors:  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/tara/graphicness_test (Commits)  Commit:  ba510d23369de9a77bd3caab5a85ae69b1efc88f 
Dependencies:  Stopgaps: 
Description
Currently, the plan is to create a new class for the decomposition, and use this to rewrite the is_graphic
function, so that we can return a graph that realizes the matroid.
Change History (11)
comment:1 Changed 8 months ago by
 Branch set to u/tara/graphicness_test
comment:2 Changed 8 months ago by
 Commit set to 1d85d1cae6ee01a0764d6d6d62eea37aa8d5362a
comment:3 Changed 8 months ago by
 Commit changed from 1d85d1cae6ee01a0764d6d6d62eea37aa8d5362a to d2192ca1d4b3c2dc17cff038d587d49be9224d31
comment:4 Changed 8 months ago by
 Commit changed from d2192ca1d4b3c2dc17cff038d587d49be9224d31 to edb861d5fb5ba98d566d5543804264260b1bd140
Branch pushed to git repo; I updated commit sha1. New commits:
edb861d  Added documentation fixed errors

comment:5 Changed 8 months ago by
 Commit changed from edb861d5fb5ba98d566d5543804264260b1bd140 to 5ac863773f4a0582d1db0dc753035131db371979
Branch pushed to git repo; I updated commit sha1. New commits:
5ac8637  Updated merge functions

comment:6 Changed 7 months ago by
 Commit changed from 5ac863773f4a0582d1db0dc753035131db371979 to 89e59effa462cec6ebb937dae00d59e291bfd758
Branch pushed to git repo; I updated commit sha1. New commits:
89e59ef  Implamented ``squeeze`` function.

comment:7 Changed 7 months ago by
 Commit changed from 89e59effa462cec6ebb937dae00d59e291bfd758 to 279aba165706cd23ce91aadc4a3dc26e8f1e75d7
Branch pushed to git repo; I updated commit sha1. New commits:
279aba1  added get D_hat

comment:8 followup: ↓ 10 Changed 7 months ago by
Just a quick observation as I'm looking at the current code: the filename should be changed to reflect the actual authors of the algorithm.
comment:9 followup: ↓ 11 Changed 7 months ago by
 Commit changed from 279aba165706cd23ce91aadc4a3dc26e8f1e75d7 to ba510d23369de9a77bd3caab5a85ae69b1efc88f
Branch pushed to git repo; I updated commit sha1. New commits:
ba510d2  Infinate recursion?

comment:10 in reply to: ↑ 8 Changed 7 months ago by
Replying to Stefan:
Just a quick observation as I'm looking at the current code: the filename should be changed to reflect the actual authors of the algorithm.
Yep.
comment:11 in reply to: ↑ 9 Changed 7 months ago by
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
ba510d2 Infinate recursion?
I don't know how I introduced this runtime error. The function does need to be reworked to make sure that any of the edges in Z
, which correspond to parent markers of type 2, 3, or 4 children are on the end(s) of the path.
Branch pushed to git repo; I updated commit sha1. New commits:
Implamented additional functions.