Opened 16 months ago

Last modified 14 months ago

#20834 new enhancement

Implement Bixby and Wagner's Almost Linear-Time Algorithm for Graph Realization

Reported by: tara Owned by:
Priority: major Milestone: sage-7.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 16 months ago by tara

  • Branch set to u/tara/graphicness_test

comment:2 Changed 15 months ago by git

  • Commit set to 1d85d1cae6ee01a0764d6d6d62eea37aa8d5362a

Branch pushed to git repo; I updated commit sha1. New commits:

1d85d1cImplamented additional functions.

comment:3 Changed 15 months ago by git

  • Commit changed from 1d85d1cae6ee01a0764d6d6d62eea37aa8d5362a to d2192ca1d4b3c2dc17cff038d587d49be9224d31

Branch pushed to git repo; I updated commit sha1. New commits:

2d7255dAdded functions, found bugs, still incomplete.
d2192caFile is closer to complete now.

comment:4 Changed 15 months ago by git

  • Commit changed from d2192ca1d4b3c2dc17cff038d587d49be9224d31 to edb861d5fb5ba98d566d5543804264260b1bd140

Branch pushed to git repo; I updated commit sha1. New commits:

edb861dAdded documentation fixed errors

comment:5 Changed 15 months ago by git

  • Commit changed from edb861d5fb5ba98d566d5543804264260b1bd140 to 5ac863773f4a0582d1db0dc753035131db371979

Branch pushed to git repo; I updated commit sha1. New commits:

5ac8637Updated merge functions

comment:6 Changed 14 months ago by git

  • Commit changed from 5ac863773f4a0582d1db0dc753035131db371979 to 89e59effa462cec6ebb937dae00d59e291bfd758

Branch pushed to git repo; I updated commit sha1. New commits:

89e59efImplamented ``squeeze`` function.

comment:7 Changed 14 months ago by git

  • Commit changed from 89e59effa462cec6ebb937dae00d59e291bfd758 to 279aba165706cd23ce91aadc4a3dc26e8f1e75d7

Branch pushed to git repo; I updated commit sha1. New commits:

279aba1added get D_hat

comment:8 follow-up: Changed 14 months ago by 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.

comment:9 follow-up: Changed 14 months ago by git

  • Commit changed from 279aba165706cd23ce91aadc4a3dc26e8f1e75d7 to ba510d23369de9a77bd3caab5a85ae69b1efc88f

Branch pushed to git repo; I updated commit sha1. New commits:

ba510d2Infinate recursion?

comment:10 in reply to: ↑ 8 Changed 14 months ago by tara

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 14 months ago by tara

Replying to git:

Branch pushed to git repo; I updated commit sha1. New commits:

ba510d2Infinate 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.

Note: See TracTickets for help on using tickets.