6
$\begingroup$

I am trying to remove vertices that have degree less than 2, but I think I am missing something basic.

I was hoping that I could use:

VertexDelete[g, VertexDegree[#] < 2 & ]

But it seems that this is not supported in a few ways.

  1. I know that I can operate on one vertex at a time from the examples, but that seems to use pattern matching, rather than a pure function. I tried using _?(VertexDegree[#] < 2 &) instead as the pure function, but there still is a bigger issue
  2. The VertexDegree does not have an overload that just takes a "vertex" object. For that matter, I don't even know what is being matched in the VertexDelete function. Is it the label of the node only?

I sense I am missing something basic about this whole process. Any pointers?

$\endgroup$
2
  • $\begingroup$ @DavidG.Stork you mean why this is a "hard" problem, or meaning I can corrupt my graph accidentally? $\endgroup$
    – soandos
    Jan 7, 2015 at 0:10
  • $\begingroup$ I successfully deleted VertexDegree < 2 vertices from VertexList[g] and re-inserted the smaller list into a graph using the prior EdgeList[g] and had problems. The answer below, using VertexDelete automatically recomputes the EdgeList, and hence is superior to my approach. Problem solved. $\endgroup$ Jan 7, 2015 at 0:26

2 Answers 2

7
$\begingroup$
g = Graph[{1 -> 2, 2 -> 3, 3 -> 1, 2 -> 4},   VertexShapeFunction -> "Name"]

enter image description here

VertexDegree[g]
(* {2, 3, 2, 1} *)

VertexDelete[g, _?(VertexDegree[g, #] < 2 &)]

enter image description here

You can also use KCoreComponents[g, 2] to find the vertices whose vertex degree at least 2 and use it with Subgraph:

Subgraph[g, KCoreComponents[g, 2], VertexShapeFunction -> "Name"]

same picture

$\endgroup$
2
  • $\begingroup$ I hate being this close to an answer, but thank you very much. $\endgroup$
    – soandos
    Jan 7, 2015 at 0:23
  • $\begingroup$ @soandos, i know the feeling:) Thank you for the accept. $\endgroup$
    – kglr
    Jan 7, 2015 at 0:25
6
$\begingroup$

You can use

VertexDelete[g, Pick[VertexList[g], VertexDegree[g], d_ /; d < 2]]

which I expect to have better performance, but I haven't benchmarked.

$\endgroup$
1
  • 1
    $\begingroup$ On a graph of about ~100K nodes, the other approach takes about a second. If I need more performance, I'll try it out. $\endgroup$
    – soandos
    Jan 7, 2015 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.