@LeonidShifrin I don't see any strange behavior. In any case, I wouldn't worry too much about it. You have a lot of answers of high quality, so the chances of there being posts that have a score close to silver badge are also high. Some users just like being the one to tip a user over some threshold (badges or 10k/20k/etc.).

@rm-rf All right, thanks for checking!

@halirutan Are you talking about decision tree learning? The wiki page for the ID3 algorithm links to implementations in many languages, or it would be pretty easy to implement in Mathematica. en.wikipedia.org/wiki/ID3_algorithm

@MichaelHale When I see this right, then decision tree learning can use arbitrary attributes. BDD -- binary decision diagrams are only for binary data.

@MichaelHale Let me give you a short example. Say you sit in the middle of three chairs and you want to decide whether you feel comfortable. You don't feel comfortable when you are alone or when 2 people sit beside you because then it is too crowed.

Representing the situations with bits, then your function returns true for the following situations: {1,1,0} and {0,1,1} and it returns false otherwise. The middle 1 is you sitting on the chair and the 1's around you represent your neighbors.

It's clear that situations like {1,0,1} where you don't even sit on the chair in the middle don't make sense.

For such things you can create a binary tree like the one depicted above where you use a fixed order of your input parameter (in our case maybe {x1,x2,x3}). To decide whether or not you feel comfortable you just have to follow the paths along the tree.

@MichaelHale The cool part is that there are algorithms to optimise such trees by making equivalent subtrees share the same node-pointer.

@halirutan Right, but with 26 variables that you mention that is a large tree to search for subtrees. The algorithm I linked is constructive. Essentially you look through all of the variables and choose the one that "best separates the data" or "has minimum entropy" or "maximimum discrimination or information". So that is the first node, then you split the data and recurse for each subnode.

You stop when all of the data for a particular branch has the same output.

@MichaelHale Currently, my set of positive input values is only about 8*10^6 entries large.

So I have a long list of input values like {{0,0,1},{0,1,1},...} which all return true. My first try was to create a list of rules {{0,0,1}->True, ..., _->False} and use Dispatch to hash everything.

The list of rules can be created easily, but Dispatch doesn't return.

You could compute the count of negatives for each branch without listing them.

Like take your first variable.

Ah, 67 million. It's certainly possible to have a hash table with that many entries, but maybe that section of Mathematica isn't optimized well enough yet.

@MichaelHale No, only 8 million

because I list only the positive cases

8 million yes values, but another 18 million nos.

and catch the negative with a _->False rule

Oh, I see.

_->False

I don't know if I've used dispatch with more than a couple of million before.

And those were strings

@MichaelHale I can use either integers like 3 which represent the binary representation or I use IntegerDigits like {0,0,1}

I thought maybe the last one can be hashed better.

Does Dispatch work better with simpler data types like integer and string. I would guess those are more efficient than arbitrary expressions and lists.

Just because those are more common for hashing in other languages.

@MichaelHale Hmm, I don't know. I guess you are right.

I can do 10 million pretty easily.

a = Dispatch[Rule @@@ RandomInteger[10^8, {10000000, 2}]];

Range@100 /. a

@MichaelHale Hmm.. let me see

@MichaelHale With pure Integers as key it works here too.

That just leaves that the whole table of rules is about 700MB big.

Right, so if you have reason to believe your variables have some sort of hierarchical, decision tree-like structure, then constructing a decision tree should use much less memory than a generic hash table.

But if you want it working right now and don't mind the memory footprint you can just convert them all to strings and try it with Dispatch.

@MichaelHale The problem is that this is used in 3d volume processing and loosing 700 MB for such a table is bad, because you might need it for other things in a memory-hungry 3d algorithm.

Sounds reasonable. So for your first variable you know there are 13 million yes inputs and 13 million no inputs. Count how many of the yes outputs are no and yes inputs for the first variable. Then you also now the count for the no outputs.

@Szabolcs I have updated today. It seems I had to re-accept the gcc licence to use Compile with "C".

@halirutan hello

may I ask you a couple of questions about graphs?

@chris I'm not really experienced with this.

ok too bad :-) thanks anyway

@chris You can still try me ;-)

I just wanted to prepare you that I might not know the answer.

I have a zeroth order question Graph[] seems to be a special object in as much that I cannot access its content by applying Parts to it. as in CompleteGraph[4][[1]]

do you know why it is so?

I tried Normal[CompleteGraph[4]][[1]] but that does not seem to work...

@chris Because they decided at Wolfram to make graphs atomic objects.

In[21]:= CompleteGraph[4] // AtomQ

Out[21]= True

So what you basically try to do is something like 5[[1,2]] wich isn't allowed either.

ah…

@chris For a surprisingly long list you can read here

Anything else they have atomized recently?

@chris Almost everything that needs to work performant: Image, Image3D, Graph, ..

ok I learnt something today. Kills 10 years of training with mathematica :-(

@chris You might be interested in my question, the comments and leonids answer here:

I guess I was after the opposite :-)

Another question (more technical). In a graph you may have special Vertices which degree is larger than 2 and others which just bridge those vertices together. Would you off hand know how to identify all vertices of degree two connected to a given vertex of degree larger than two? If not no pb.

(I have in mind point 2 of this question mathematica.stackexchange.com/questions/63643/…)

@chris You can get the list of VertexDegree's, right?

A variation of VertexInComponent would seem to be the general direction.

If you don't know off hand don't bother. I ll work it out...

So why don't you select all Vertices with degree 2 and check the AdjacencyList?

Sure I have the list of VertexDegrees

This should be a simple iteration.

OK I did not know about AdjacencyList

I ll look into it.

@chris reference.wolfram.com/language/guide/…

Thanks; on a unrelated matter do you use mathematica 10.0.1?

@chris yes

I have had problems with copying not so large Image3D objects

with the frontend

@chris This is highly operating system dependent.

Are you using Windows?

Basically the FE hangs for a very long while (macos X)

@chris I didn't notice something like this, but I have to say that I never use things like copying 3d images from one notebook to the other.

not between notebooks

just between cells

anyway thanks for your time again.

@chris Hmm, nope. I guess I didn't run into such problems yet.

@chris Still here?

How about this

identify[g_] := Flatten@Last@Reap@Do[
     With[{neighbors =
        Select[AdjacencyList[g, v], VertexDegree[g, #] === 4 &]},
      If[neighbors =!= {},
       Sow[UndirectedEdge[v, #]] & /@ neighbors
       ]
      ], {v, Select[VertexList[g], VertexDegree[g, #] === 3 &]}]

g = RandomGraph[{10, 20}, VertexLabels -> "Name"]

In[63]:= identify[g]

Out[63]= {8 <-> 9}

hello again

Thanks for this. I don't understand why it returns 8<->9

@chris because vertex 8 is of degree 3 and vertex 9 is of degree 4

ok because you required 9 to be connected 4 times?

@chris Yep. Look in the VertexDegree[g..]===4 conditions

ok your code finds all neighboring vertices of degree 3 and 4.

I am after something which would crawl along the graph until it found the next vertex of degree >2. But may be I can modify your code to do this?

@chris Yes, this is pretty easy

Say if I start at 68

I want to find 65, 71, 35 and 88

@chris OK, if you want to crawl along the graph, you have to implement an iterative walk on the graph

@chris Would you know how to do this?

no that's wrong

@chris If you have some time, I would show it to you later. I have to hurry home now for dinner.

same here.

thanks for your time again!

@chris Would it be possible that you post me this very graph from above to pastebin.com

its on the question via dropbox?

@chris Ah, ok. Then it's fine.

dl.dropboxusercontent.com/u/659996/graph.m

How to make some polygon bigger? as in a binary image dilation

@Rojo Maybe go to each vertex and move it perpendicularly outward to the line connecting the preceding and following vertex. That's the first thing I think of when I think of dilating a polygon at least.

@MichaelHale Seems reasonable

Humm, bug? (of undocumented stuff) ReplaceAll[_ :> (0 /. _ :> 0)]@9

@MichaelHale @Rojo I guess this won't work on the polygons that Rojo has in mind. On a somewhat smooth object, this would probably give reasonable results, but with sharp edges, it will not look as one thinks.

pts = First@First@First[Entity["Country", "Argentina"]~EntityValue~"Polygon"];

Manipulate[
 normals =
  Function[{a, b, c}, {#2, -#1} & @@
     Mean[Normalize /@ {b - a, c - b}]] @@@
   Partition[RotateRight[pts], 3, 1, {1, 1}];
 Graphics[Polygon[pts + a*normals], Frame -> True],
 {{a, 0}, -1, 1}
 ]

If you apply a MovingAverage filter on pts then it kind of does what one like.

@halirutan Thanks. I thought I might be missing something but I guess its not that simple

@halirutan hello again. I tried building all FindShortestPath connecting vertices with VertexDegree>2

My expectation was that Mathematica already had a function to do this.

@Szabolcs Regarding the comment I made yesterday about compiling to C; it seems you need to re-accept the license from gcc for it to work (sudo gcc should do the trick)

(@acl)

Does someone know why Dynamic does not recognize when a graph object is changed?

g = RandomGraph[{4, 3}];
Dynamic[g]

Now make a

PropertyValue[{g, 1}, VertexStyle] = Blue

Nothing happens here but when I evaluate g, the changes are visible.

Even when I re-evaluate the Dynamic[g] line, the changes become visible.

@halirutan aha!

@chris Sorry for being so late. Had to drink some wine with friends. OK, here we go:

This visits all neighbors in a breadth first style and marks the vertices that have degree 3.

It starts as you wanted with node 68.

Before I post the code, let me shortly explain how it works. The algorithm is easy. You maintain a list of vertices you have to visit and of course initially, this list contains only the starting vertex. I called this list neighbours and you call a visitFunc on each vertex in this list. This visitFunc can do what you like, for instance do something with vertices of degree 3.

In my sample, the visitFunc just stores the vertices it visits and remembers by color whether or not it had degree 3.

After you have visited a vertex in your neighbours list, you remember its adjacent vertices and you mark (PropertyValue) this vertex as already visited.

If you have visited all vertices in neighbours, you set neighbours to all adjacent vertices you have collected so far and start over.

Since you check before each visitFunc call whether or not the vertex was already visited, the algorithm will eventually stop.

visitGraphBreadthFirst[graph_, start_, visitFunc_] :=
 Module[{g = graph, neighbours, tmp},
  neighbours = {start};
  While[neighbours =!= {},
   tmp = {};
   Do[
    If[PropertyValue[{g, n}, "Visited"] === True, Continue[]];
    If[visitFunc[g, n] =!= True, tmp = {}; Break[]];
    PropertyValue[{g, n}, "Visited"] = True;
    tmp = {tmp, AdjacencyList[g, n]};
    , {n, neighbours}];
   neighbours = Flatten[tmp];
   ]
  ]

The interface to visitFunc is pretty simple. On each visit, you get the graph g and the vertex n and you are free to do what ever you like to do. visitFunc needs to return True if you like to go on with the visit. Otherwise, it stops at this point. Let me give an example: Say you want to print all vertices with degree 3 and if you meet the vertex with number 91, you want to stop the search. The implementation of visitNode looks like this:

visitNode[g_,  n_] := (If[VertexDegree[g, n] === 3,
   Print["Visited deg 3 node " <> ToString[n]]]; n =!= 91)

and then you can test it with your graph

g = Get["https://dl.dropboxusercontent.com/u/659996/graph.m"];
visitGraphBreadthFirst[g, 68, visitNode]

@chris Hope this helps