Ask Your Question
0

Path after deletion of vertex

asked 2012-01-28 10:57:02 +0100

G-Sage gravatar image

updated 2012-01-28 13:05:57 +0100

The following code

g = graphs.PathGraph(15)
g.delete_vertex(6)
g

prints

Path Graph: Graph on 14 vertices

but it's not a path after I delete vertex 6. It's the disjoint union of 2 paths. Same thing occurs with cycle (except it says Cycle Graph), same thing occurs if you delete an edge from either. Happens with complete graph if you delete an edge and make it no longer complete... so probably happens with any such named graph under edge or vertex deletions. Or, if you end with "Print g" instead of just "g", it says just "Complete Graph".

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
0

answered 2012-01-28 13:11:55 +0100

DSM gravatar image

Yeah, that's a side effect of the way the classes work. I'm not sure what the best way to handle this is:

(1) Give up on clever naming entirely.

(2) Check whether the name still makes sense whenever the graph is changed and update accordingly. This would be very silly and very expensive.

(3) Check whether the name still makes sense whenever the name is printed, and update accordingly. This makes a lot more sense but could still be pretty expensive, although it could have a modification-invalidating cache.

(4) Whenever a graph has nodes or vertices changed, in-place or otherwise, set a "modified" flag. If the modified flag is set, print the generic string instead, without testing whether the name would still apply. This would add one extra operation to every graph change, but it should be pretty fast.

ISTR this came up on one of the mailing lists within the last six months or so.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2012-01-28 10:57:02 +0100

Seen: 294 times

Last updated: Jan 28 '12