1
$\begingroup$

I'm new to Mathematica and I'm attempting to write an approximation algorithm to compute "maximum" independent sets. What I need to do is given a graph g to remove its vertex of minimum degree and its neighbors.

I've managed to do so with the following code:

remmdv[g_] := VertexDelete[g, VertexList[NeighborhoodGraph[g, Ordering[VertexDegree[g], 1]]]]

The Ordering gets the vertex of minimum degree and by converting NeighborhoodGraph to a VertexList I can remove these vertices from g.

This I've managed to sort out and it seems to work properly.

The thing is that the following function throws an error when I run it.

approx[g_] := (
    n = 0;
    While[Not[EmptyGraphQ[g]], n++; g = remmdv[g]];
    Return[n];
);

I'm not familiar with functions in Mathematica and maybe what I wrote makes no sense, but it's what seems reasonable coming from an imperative programming background.

Thanks to all of you in advance.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

You can't assign value to input parameter in Mathematica as these are passed by Value. You were writing g = remmdv[g] but g is passed by value so raw object. Can't assign to or change raw objects.

Also you should use explicit Module, otherwise all the variable used inside your loop will be global. Using global variables inside functions is bad in any programming language as it introduces side effects.

For example n in your case. You make n local by adding it to the Module local declaration list. That is why using Module is better.

And no need to do an explicit Return at last the. Last expression in a Function is its vlaue by default. Just make sure not to add ; to it at the end.

Try this. First I copied sample g from help pages

remmdv[g_] := 
 VertexDelete[g, 
  VertexList[NeighborhoodGraph[g, Ordering[VertexDegree[g], 1]]]]

approx[gIn_] := Module[{g = gIn, n = 0},
  While[Not[EmptyGraphQ[g]], n++; g = remmdv[g]];
  n
  ]

approx[g]

Screen shot

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you so much! You've made loops so much clearer to me and I did not know that about return; it's just like Rust! $\endgroup$ Commented Jun 14, 2024 at 3:19

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.