Opened 6 years ago

Closed 6 years ago

#1089 closed enhancement (fixed)

[tested] [with patch] graphs: update subgraph to handle a list of edges

Reported by: jason Owned by: mhansen
Priority: major Milestone: sage-2.8.13
Component: combinatorics Keywords: graphs
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Here is an update to the subgraph function to handle a list of edges. If edges are not specified, then it reverts to the original functionality (returning an induced subgraph).

I also fix a doctest that should have been complaining in transitive_reduction and make the doctests in min_spanning_tree make more sense.

Attachments (2)

subgraph-edges.patch (5.2 KB) - added by jason 6 years ago.
subgraph_edges-updated.patch (8.2 KB) - added by jason 6 years ago.
Corrected bugs, rebased against 2.8.12, and put in more comprehensive doctests.

Download all attachments as: .zip

Change History (10)

Changed 6 years ago by jason

comment:1 Changed 6 years ago by rlm

  • Summary changed from [with patch] graphs: update subgraph to handle a list of edges to [not ready] graphs: update subgraph to handle a list of edges

Jason,

Please include a fresh patch that comes from a clean install of sage 2.8.11. The base version does not match. Also, the function subgraph(vertices) returns the induced subgraph with the given vertices and *all* edges from the original graph whose endpoints are in vertices. Perhaps the current function should be renamed induced_subgraph, and you could make a separate subgraph_from_edges() function. It also occurs to me that we don't yet have an is_subgraph fucntion...

Cheers,

Robert M

comment:2 Changed 6 years ago by rlm

  • Milestone changed from sage-2.8.12 to sage-2.9

comment:3 Changed 6 years ago by rlm

Jason,

I should have mentioned to apply the patches in #1088 to the clean version first, then patch on top of that.

Thanks, Robert M

comment:4 Changed 6 years ago by jason

Robert,

You're right, #1088 should be applied first. This patch modifies a doctest in #1088 to be more sensible. I was going to include the better doctest in #1088 to keep both patches more self-contained, but then the doctests wouldn't have passed after only applying #1088. Did applying this patch after #1088 resolve the issue or would you still like me to rebase against 2.8.11?

As to the subgraph function: I think it's a reasonable idea to say that the subgraph function returns a graph that is the intersection of what is currently in the graph and the restrictions that you pass relating to vertices and edges (as represented by a list of "allowable" vertices and/or edges you pass the subgraph function). If you pass just a restriction on the vertices to include in the subgraph, then there is no restriction on the edges and you get an induced subgraph. If you pass a restriction on the edges, then you get a graph with the same vertices as the original graph, but with possibly fewer edges (that is what the added doctest tests). If you pass a restriction on both the edges and vertices, then the returned graph only has vertices from the vertex set you passed and edges from the edge set you passed. I don't think that we need to make several different functions for this feature. But if you think it would be clearer to have several functions, let me know.

One of the things I'm trying to do here is consolidate functionality when it makes sense so that we don't end up having hundreds of different functions that people have to remember. I guess the question here is whether it makes sense.

As for the is_subgraph function, I believe that that problem is quite a bit harder (in a technical sense) than the graph isomorphism problem, even if you restrict to induced subgraphs. I suppose it would be fairly easy, though, to implement an is_induced_subgraph function by taking k-subsets of the vertices and asking if the induced subgraph is isomorphic to a given graph.

A related feature request is for functions dealing with graph minors (constructing minors, asking if a graph is a minor of another, etc.).

Thanks for your comments and suggestions!

comment:5 Changed 6 years ago by rlm

Jason,

The reason I was asking you to rebase is that I already patched up the doctests from 1088 (the second patch there). As far as patches go, you can do one of the following:

1) Wait for sage-2.8.12 to be released, and do a patch on top of that.

2) Apply *both* patches in ticket 1088 to a fresh 2.8.11, and do a patch on top of that.

You've convinced me that these functionalities should be in the same function. I was just thinking that the name "subgraph" was a little misleading for a function name. Under your interpretation, all of these would be induced subgraphs, so to speak. I don't know if induced_subgraph is better, since the first thing anyone would look for would be subgraph anyway, and it's shorter to type...

Indeed, the subgraph isomorphism problem is NP-complete, but I was just talking about *is* subgraph, as a subset. Same vertices, same exact edges. I could see this being useful in some situations.

Changed 6 years ago by jason

Corrected bugs, rebased against 2.8.12, and put in more comprehensive doctests.

comment:6 Changed 6 years ago by jason

  • Milestone changed from sage-2.9 to sage-2.8.13
  • Summary changed from [not ready] graphs: update subgraph to handle a list of edges to [with patch] graphs: update subgraph to handle a list of edges

The subgraph_edges-updated.patch should be applied instead of the subgraph_edges.patch.

comment:7 Changed 6 years ago by rlm

  • Summary changed from [with patch] graphs: update subgraph to handle a list of edges to [tested] [with patch] graphs: update subgraph to handle a list of edges

Looks good to me.

comment:8 Changed 6 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged in 2.8.13.alpha1.

Note: See TracTickets for help on using tickets.