Message Boards Message Boards

2
|
4290 Views
|
2 Replies
|
3 Total Likes
View groups...
Share
Share this post:

Given a graph and a subset of its nodes, how to get the induced subgraph?

Posted 6 years ago

Suppose we have a graph g and a subset of vs = VertexList[g]. The vertex names of g could be anything.

How can I quickly and reliably get the subgraph induced by vs?

Subgraph[g, vs] does not work reliably. Consider the following example:

Let's take a list of sets,

sets = {{2}, {3}, {2, 3}}

Their elements are

elements = Union @@ sets
(* {2, 3} *)

Now let us build the containment-relationship graph:

g = RelationGraph[MemberQ, Join[sets, elements]]

Mathematica graphics

This is a subset of it's elements:

vs1 = {2,3}

SubsetQ[VertexList[g], vs1]
(* True *)

Subgraph does not give what I need and described above:

Subgraph[g, vs1, VertexLabels -> Automatic]

Mathematica graphics

Getting the subgraph of a larger graph is a fundamental operation. Is it possible in Mathematica?

Note that when developing a package, it is not possible to control the input that the package functions receive. I need a way that is fast and that works with any graph and any subset of its vertices. A solution that works only with the example graph from above is not satisfactory.


I posted this question because I am hoping that Subgraph has some way to disambiguate its input.

Extract has a potentially ambiguous syntax. But it's not really ambiguous. Extract[list, 1] takes the first element. What does Extract[list, {1,2}] do? it takes element 2 at level 1, and not the first two elements. For that we can use Extract[list, {{1}, {2}]]. The unambiguous way is Extract[..., {pos1, pos2, ...}] where each pos is a List. This is a robust syntax.

Lookup has a potentially ambiguous syntax. But again there's a completely unabiguous version: use a list as the second argument. asc = <|{1, 2} -> "a", 1 -> "b", 2 -> "c"|>;, then Lookup[asc, {1,2}] gives the results for keys 1 and 2 and Lookup[asc, {{1,2}}] gives it for key {1,2} in a list. I can program confidently with this. There's also Key if I want a single result.

Subgraph is complicated because the second argument can be either a list of vertices or a pattern, which is an extremely general thing. Is there any way out or is the design just broken?

VertexDelete suffers from the same problem.

POSTED BY: Szabolcs Horvát
2 Replies

Just to illustrate how things go wrong when Subgraph is used to implement another function:

Mathematica graphics

Oops!

It wasn't a difficult guess that ConnectedGraphComponents might use Subgraph.

It seems that Subgraph, like many other Mathematica functions, is designed for convenient interactive use: run it as a single concise input and look at the result immediately. If this comes at the cost of robustness and predictability, as it does here, that makes the programming language not suitable, for, well, implementing programs (other than one-liners) ... Mathematica is great at interactive use, which is, and has always been one of its great advantages. But if it doesn't get better at being suitable for actual software development (i.e. writing packages, and implementing parts of Mathematica itself), that might be its downfall.

The competitors are not yet there with suitability for interactive use, but they're quickly catching up. See the story of Jupyter. WRI invented the notebook paradigm, but now Jupyter gets the credit. And the competitors are way ahead of Mathematica at supporting development, attracting a community, sustaining a package ecosystem, attracting open source development (which is already essential to academic work) ...

POSTED BY: Szabolcs Horvát

I believe I found a robust way to do it:

Subgraph[g, Verbatim /@ vs]

The problem is that it kills performance.

rg = RandomGraph[{10000, 30000}];
vs = RandomSample[VertexList[rg], 100];

Subgraph[rg, vs]; // RepeatedTiming
(* {0.00024, Null} *)

Subgraph[rg, Verbatim /@ vs]; // RepeatedTiming
(* {5.14, Null} *)

Thus is it not really a practically usable solution.

I think that a workable fix would be to always interpret a List-second argument as a list in Subgraph (and never as a single vertex or single pattern). Thus the single-vertex syntax, Subgraph[g, v] would still be problematic, but at least the Subgraph[g, {v1, v2, ...}] syntax would always be unambiguous.

This, however, would become a usability problem with VertexDelete where people will use the single-vertex syntax much more frequently.

POSTED BY: Szabolcs Horvát
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract