Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[dragdeler]

So I found what seems to be a very capable router (two of them actually), but it does not support these as far as I can tell.

Ideally, i would get one with ddwrt or openwrt support. (Check both projects for supported hardware)

https://wiki.dd-wrt.com/wiki/index.php/Supported_Devices

https://openwrt.org/toh/start

Worthwhile or skip this particular model? They're heavy, I allready kinda like them eventhough the power inlet is plain silly.

Alternatively I been sitting on a netgear router that is supported, but only does 10-100mbs.

[Mephisto]

That's a managed switch, not a router. It also doesn't have built-in wireless which I foresee being a potential issue depending on circumstances.

[dragdeler]

It sounds pretty perfect if you say it like that, going by what I was advised earlier (I'm a total novice, I can only refer you to the past one and half pages (default size)).


But like, are they inherently untrustworthy for not allowing those opensource firmwares, or has somebody had good experiences with the brand or something like that? I do not know how to judge this product other than by weight and appearance lol.

(also I screwed up assuming I could fit a standard 12v psu in there  if they were there, by the time I get back to that parc they will be burried)

[wierd]

A managed switch may work for what you want. (Segregate traffic, except that which is destined)

The builtin software in a qnap switch should be sufficient. The OSS firmware is for consumer grade devices that think you are an idiot, and dont want to give you knobs to turn. That is a professional managed switch. It comes from the factory without mittens.

In this case, you would define a vlan containing your encoders, and another containing your normal network. The switch will isolate the traffic for you.

[Starver]

Looking for a sanity-check on a coding (well, algorithming... the code itself is a bit pasta-ish at the moment) issue I'm dabbling with.

Having a set of nodes with (arbitrary, but fixed) subset of 'neighbouring' relationships to which a valid node value has a dependency to the value of each neighbour. I want to run through general solutions towards a (probably non-unique) valid answer.

I could just brute-force it (O^N or greater) by trying every node-value on every node (at least until a clear violation suggests a clear lack of validity, then pass over values/backtrack to previously commited nodes and try their next possibility before redrilling-down again)nbecause it's not a large set, but maybe a tolerably pseudo-optimal method of progressing through the nodes (with no nominal value, more meaningful than simply alphebetised by label!) is to build a 'try-list' as follows:

• For all nodes, not yet in the 'sorted' grouping, choose all those that have the share (or have alone) the highest number of neighbours already in the sorted list.
  
  • i.e. Ones that will be maximally pre-constrained in the iterating phase, drastically reducing the tree of future permutations that flow from this decision
  • On looking for the first list item, every node would have zero pre-visited 'neighbours', but it becomes potentially most important once you're past that stage
  • The converse would clearly force the iterative value-trying process to pursue all possibly values in a non-neighbouring scattergun effect, each potentially tried out with every possible value each before trying to fit values into spots 'between' the first few. This seems like it will waste top-of-tree cycles more than it will exlude opportunities deeper down the iterative tree. Thus seems to support the higher efficacy of the my approach.
• From all nodes satisfying the prior razor-cut (could be all of them, could be just one, which saves time) consider for use all nodes with the shared maximum count of all neighbours.
  
  • Thus a node that (if chosen) constrain successive nodes the (equa-l?)most
  • Yes, functionally identical to "count of all neighbours not yet enqueued" as (where there's a choice) "allneighbours = prequeuedneighbours + notqueuedneighbours" has inherited the same "prequeuedneighbours" from step 1. But might be more useful to know this value for other reasons, so giving it prime duty here for trivial convenience later.
  • Again, the converse prioritisation would bring to the fore any nodes that have proportionally few constraining partner-nodes, like isolated branches that could be (e.g.) any value that can be mopped up "at the end" (giving them any value you want once and just once, without fall-back-to-and-try-next upon failing further down the tree, correcting zero 'mistakes' in the process).  Thus also convincing by counter-argument.

Then just pick any one (if there remains any choice, rather than a single 'ideal') of the nodes that passed through the two slicings.

A more advanced version could do some additional look-forward. i.e."if I choose to next choose this node (perhaps not even the most preconnected/futureconnected) it then it brings a particularly well-connected but not quite yet queue-adjacent node into range". But that'd need more of a tree-search to set up the workhorse tree-search. At the currently intended scale, a simple pick-and-add from the pool of potentialities should significantly reduce the wasted time running through the main target-seeker part.

Agree/Disagree? (On principle, at least.) I've actually already implemented it, but I'll gladly try (meta-)benchmarking against an alternate or expanded approach if anyone has any insights that I may have missed. 

(Just in case you're confused, I'm trying to build a smarter queue-order of setable values across which the 'dumb' iteration algorithm will then seek to try solutions by depth-first back-tracking, until validly setting the final element.)


Yes, probably reinventing the wheel, but I find it entertaining to work through from first(ish) principles.

[McTraveller]

@Starver - I don't think I understand the problem description enough to comment.  Is this something for which you can share more details, like the specific nature of what you mean by "valid values depend on the valid values of its neighbors"?

Is this something like solving a differential equation?

[Starver]

A net of nodes (undirected, not easily flattened in any Euclidean or even 3+D Euclidean way, and 'small-world' crosslinks between select topologically distant nodes, regardless of how I lay them down) where the links denote "if node 1 is <foo>, then node 2 cannot be <bar> (and vice-versa)", or suchlike.

So the 'solution' (there are many if I loosen the conditions, and I'm just planning on tightening the conditions progressively until I get to a 'nice' place, and I'm not fussed to find all exhaustive answers or to exhaustively make it find a scenario that only has the single answer) will be found by trying Node 1 with <foo> (out of <foo>, <bar>, <baz>) then Node 2 with <foo> (may not be allowed because of how Node -5 was previously set, prior to our scenario being described) <bar> (nope), <baz> (maybe)... Then try Node 3... Darnit, because of its links, there are no valid values, reverse back, to 2, change <baz> to <whatever's next>, hunt back down.

Although if Node 3 isn't barred (NPI!) by Node 2 at all, but more Node 1 and further back, I'd waste time... or my tree-of-possibilities traverser would... on Node 2, so maybe prioritising a permutation of the respective Nodes 1, 3 then 2 would be better and quickly rule out what 1 can be. i.e. based on it (in)validating 3, before it is moving onto messing with 2 at all. Numbering/order is arbitrary here, for my purposes, so I'm thus looking for a marginally (at least) more fortitious ordering just to not do it in a totally stupid way.

Spoiler: Those not bothered can skip this rest of my 'summary' (click to show/hide)

It doesn't really describe the data well, but I'll just set the script running again (just made some code adjustments) and it'll take a number of minutes to finish, but the current "test status" echoed to the screen, if I pause it, is:

Code: [Select]

ABCCBCBBCAACBACBAABABCBBCAACCBABABABCC(That's listed from the first permute of the queue to the latest valid one, the list grows and shrinks as it searches the 'field' and backtracks from dead-ends in the phase-space, and the interrelationships themselves aren't there in the printout as I'm not bothered wasting output cycles and character spaces with that whilst running. It's just a handy progress-meter for my benefit. Yes, there's a valid solution, at this level of enquiry, with just three elements... It's not the Four Colour problem... )

The looser the constraint, the more scope the search could cover (loads more partial solutions, that could 'die' before reaching out to the theoretical tip of any branch), but the more likely it'll find a final solution quicker. The tighter I make it, the dead-ends increase but so do entore dead-forks, which might shut off some old found solutions but that'w because they won't even get far into those old directions, so the screening will quickly hop over into other (more likely to be useful) branches from closer to the root of the respective decision-tree.


So the idea is to pre-bake the order of the nodes for full checking, so moving on/retreating is in a manner not just servant to anything like the incidental node-labels shuffled into alphanumerical order/whatever. Instead, I shall find the most connected node (rule 2, in my above post) knowing that any value I first give this reduces more future tree-branchings later on than if I'd started with a weakly-connected node. Then find any of the nodes that neighbour it (jointly all have the maximum possible value of one link to  "all nodes ahead of them", as per rule 1) and select one of those with a similar high future potential of link-backs (rule 2 as a secondary concern). The third one I look at might have links to both prior items (there may be several candidates for rule 1 showing double-connection to first and second item) and thus constrained the most. Or still only "1 past link" (either first-in-list or second-in-list) is the most we have. Rinse and repeat.


If I used a bit more exploration, I could add a further (or even initial/intermediate) requirement that "nodes that have neighbours that link back to the currently established queue of nodes" or more, at some point in the slicing down of candidates for the next addition, but then I'm trading tree-branching in the future (the 'running through the queue that we establish') for tree-branching in the very establishing of said queue. As it stands, I'm checking N items, choosing one, checking N-1 items as possible candidates for onward travel, choosing one of those, etc[1], where testing N+(N-1) then (N-1)+(N-2), etc, for a first-order look-ahead (and I could go for second-order, third, even Nth, at least for the first decision where I could weight "best short-term answers to be found in a long term search" to establish which supposedly immediate decision is the absolute best) starts to look like more and more like doing the full tree-checking in a tree's worth of different ways just to make sure that I have the absolute best tree-checking strategy when it comes to the value-iteration stage! That way madness lies. Doable, but mad.

And if I check the script I just ran, again, it should by now have... Ah, sorry, I think my last tweak broke something slightly... Typical. Ah, I see, a "." instead of a ","...That's easily corrected, at least. That's not your concern, of course.



[1] I could reduce this, a bit, but I'm not requiring my queue to be formed of a 'single traversible path' but could find that after the first item, and second item to which it must be linked, the actual third item 'best' links to the first but not the second, so I'd need to maintain "all nodes that are neighbours of enqueued nodes" as a subset of N that gets added to by new 'neighbours' (as old neighbours that are enqueued are removed) rather than just look for immediate neighbours of the last node I chose. At the moment, that would work (losing some of the advantages I'm looking for) But there are reasons why it might not, and the balance of effort to track the 'hyperneighbourisation' might even make later setups fail, so I'm accepting the marginal hit of testing N(N+1)/2 things from start to finish during the initial enqueuing phase.

[McTraveller]

Ok I think I'm still missing something - do you have a graph, and want to "color" the nodes, starting from some initial point? And you want a method to figure out how to color those in a way that doesn't violate the rules?  Or are you starting with unconnected nodes and want to connect them following the rules?

How many edges are required for your rules? Does the rule only apply to direct neighbors, or do you have rules like "if a first neighbor is foo and a second neighbor is bar"?

[Starver]

Ah look, it was just a "hmm, I think I've solved a problem somewhat elegently, but maybe I've missed something, I wonder if I should see if my principle can be improved upon". As it seems I can't explain it, maybe I missed the elegence aspect completely. It's 'working', so perhaps the wrong thread, wrong approach and wrong of me to think aloud about it.

But, to briefly tie up the points:

do you have a graph - yes, in the sense you clearly appreciate of a set of connectivities

and want to "color" the nodes - assign a subset of values, but yes "colour" is a good analogue, and I actually first thought I'd have to contend with a variation of the map-colouring problem (but more complex!)

starting from some initial point? - any initial point, really, but optimally that might be one of a few (or even just a clear single obvious one), identified in advance

And you want a method to figure out how to color those in a way that doesn't violate the rules? - I'm doing it pretty much the long-winded way of progressively permutating the possibilities, but there's the very long-winded way[1], or a depth-first search[2]. The DFS, in turn, seems like it can be done slightly more intelligently/stupidly, depending upon which nodes I assign to which 'depths'. My current tinkering is with how 'best' to do that DFS.

Spoiler: ...and, despite my intentions, I depart from the "briefly" promise, again (click to show/hide)

Because the net is not dynamic (as of my starting to "colour" it, anyway) I quickly[3] 'precompile' the diving-order. The thinking is that I've got a quasi-optimal solution to that ordering (maybe even the optimal one, in some scenarios, but without any rigorous proof) by using those two criteria (in that order!) to decide which node is the next depth-of-search on from whichever prior node I'm at of any unpruned exploration of the resulting DFS conceptual 'tree'.

Or are you starting with unconnected nodes and want to connect them following the rules? - Not that. The 'precompile' method, though, starts off with unconnected nodes equivalent to the searchable nodes (1:1 mapping, as proxies). Then links those free ones into their own special simple chain-list based upon the knowledge of the to-be-"coloured" nodes' already known and fixed connectivities. The chaining of this list need not even reflect a Eulerian path across the original net - the original net's various connections between the searchable set of nodes are just values used to decide the separate connectivity of the chain of searching nodes that can bounce around 'off grid' because isn't even the same 'grid'. Somewhat meta, and I see where the confusion arises in my efforts to describe it. It makes more sense in my head than when written down.


How many edges are required for your rules? ... - Simple answer: just the one. More complex answer: one or more between the same two nodes. There's "<foo> at either end means <not-foo> at the other" links and "<foo> at either end means <not-bar> at the other", which might both apply, so it'd basically recalculate any such combined example as only allowing <baz-or-onwards> at both ends. That behaviour only arises as I merge in the layers of complexity, but also expand the "colours" beyond merely the <foo>/<bar>/<baz> "pallette" of three. So, to answer your next obvious question, I couldn't just put <baz> in all such pairings (and similar "gotta be that, regardless of everything else" singular answers) and then "colour" the reduced remainder of the nodes in a shorter trial-and-error manner.

(But maybe I could weight the numberOfNeighbours-type counts by the sizeOfValidPallette-type optionlist (using your colour-terminology) where it is only two or three out of the potential four, five, six, etc. Hmmm, might be worth it, in that reducing the choices available on a somewhat well-connected node might make it competitively advantageous vs. an "all-choices more-connections" node. Cheers for that idea that I imagine you just might have had, so will graciously accept without waiting for you to even think it for yourself. Saving time in cutting out the response, but still crediting the inspiration entirely to you!  )

I mean, though technically the whole system is dependent upon a "if neighbour 1 is ... and neighbour 2 is ... and neighbour X of neighbour 3 is ... then clearly self can only be ..." massively compounded parallel dependency-soup, I'm just dealing with it as each single simple undirected neighbour-links in turn. Or each node in turn, each neighbour-link in turn whilst attending to that node. Same thing, in the end, somewhat. Without treating individual edges as nodes to be visited to then assign colours to nodes that I now treat as geometric 'faces'.

...I'll leave that only for the masochists amongst you, then.


Otherwise, I've slept on this, and maybe it's 'solved'. FCVO... Tinkering aside.


[1] For N nodes of V possible values, V^N permutations and then find that most of these fail just on the first handful of nodes being wrong.

[2] Hard to quantify, but slashes huge "dimensional-chunks" off the above search-space.

[3] ½N² + ½N quick checks, and a little management overhead.

[McTraveller]

Ah ok, so I think what you said matches what I suspecting.  You definitely don't have to compute all the permutations, just a subset.  I've actually done this same problem with a slightly different formulation (mine had fixed number of neighbors to each node, not arbitrary, but the method is the same).

You don't want a "tree" approach, you want something that is more like crystal growth.  You start at your seed point, then "grow outward" from that point.  Each time you set a value, you make that a "seed point".

The general algorithm is

Code: [Select]

Precondition: "value fixed" flag for all nodes is not set.

Add the starting node to a "nodes to check" list.
Set the initial value of the starting node; set its "value fixed" flag.

While the "nodes to check" list is not empty
  For each node X in the "nodes to check" list:
      remove X from the "nodes to check" list
      For each node Y connected to X
          If Y doesn't have its value fixed
               Set Y's value based on its rules and all its direct neighbors
               Set Y's "value fixed" flag
               Add Y to the "nodes to check" list

This algorithm has O(N x (average number of connections per N) x (complexity of setting Y's value) ) .  So if the algorithm isn't a permutation of Y's neighbors, but is just a scan through it, it would be O(N x (connections per N)²) ) which probably isn't terrible.

The formulation would be a little different if you have to set all X's neighbors simultaneously, rather than one at a time, but the general structure is the same.  Hope that helps!

[Starver]

I'm not too sure that's really equivalent to what I'm doing/resulting in my desired (variety of) result, running it in my head. It seems liable to be non-halting. Though it could be a Sudoku/Kukuro/whatever solver with some common tweaking...

In an hour or three, I'll be over again at a desktop (this one without the runnable code, but with a copy of its originally sketched structure that I set down last weekend then forgot about until Thursday!) and I can take time to do a better and briefer show of what I do now. (Not late night/early morning stream of consciousness stuff that I regret later!) Should at least be good for a laugh, on your part.

[McTraveller]

I can assure you it's halting; every iteration is guaranteed to remove at least one node from the "to scan" list - at least so long as you can guarantee there is a solution.  If there is no solution for a given set of neighbors-of-X, then you'd have to back up and re-seed.  This can get expensive in memory, since you have to keep an undo stack.

I like this kind of algorithm discussion though. Keeps the cranial gears turning.

[Il Palazzo]

Android woes. How do I stop the phone from turning off when I'm trying to listen to a podcast or YouTube? Used to be I could run Firefox in PC mode, and that would keep it going. Doesn't seem to work any more.
Or just in general, how to keep it on? At best I can set it to 10 minutes before the screen turns off. But sometimes I need it to be on all the time.

[Starver]

I've long had Settings|Battery|Sleep set to Never, on devices like this one.

If an App doesn't have (or maybe does have, but it still gets over-rided) its own Don't Sleep While In Use (according to its own criteria of "In use..") then as long as you don't mind losing the security/powersaving of unattended-auto-sleep/etc (or that you have to keep switching it over, as deisired at any given occasion) then this may be your answer. Twisted via whatever OS differences there are between our own incarnations of the platform, naturally, the way they keep getting reskinned/etc...

(PS, anyone wondering about my own prior question,I switched to boring McT with my long-winded discussions over in messaging, to spare the rest of you my verbosity!)

[bloop_bleep]

A net of nodes (undirected, not easily flattened in any Euclidean or even 3+D Euclidean way, and 'small-world' crosslinks between select topologically distant nodes, regardless of how I lay them down) where the links denote "if node 1 is <foo>, then node 2 cannot be <bar> (and vice-versa)", or suchlike.

So the 'solution' (there are many if I loosen the conditions, and I'm just planning on tightening the conditions progressively until I get to a 'nice' place, and I'm not fussed to find all exhaustive answers or to exhaustively make it find a scenario that only has the single answer) will be found by trying Node 1 with <foo> (out of <foo>, <bar>, <baz>) then Node 2 with <foo> (may not be allowed because of how Node -5 was previously set, prior to our scenario being described) <bar> (nope), <baz> (maybe)... Then try Node 3... Darnit, because of its links, there are no valid values, reverse back, to 2, change <baz> to <whatever's next>, hunt back down.

Although if Node 3 isn't barred (NPI!) by Node 2 at all, but more Node 1 and further back, I'd waste time... or my tree-of-possibilities traverser would... on Node 2, so maybe prioritising a permutation of the respective Nodes 1, 3 then 2 would be better and quickly rule out what 1 can be. i.e. based on it (in)validating 3, before it is moving onto messing with 2 at all. Numbering/order is arbitrary here, for my purposes, so I'm thus looking for a marginally (at least) more fortitious ordering just to not do it in a totally stupid way.

Spoiler: Those not bothered can skip this rest of my 'summary' (click to show/hide)

It doesn't really describe the data well, but I'll just set the script running again (just made some code adjustments) and it'll take a number of minutes to finish, but the current "test status" echoed to the screen, if I pause it, is:

Code: [Select]

ABCCBCBBCAACBACBAABABCBBCAACCBABABABCC(That's listed from the first permute of the queue to the latest valid one, the list grows and shrinks as it searches the 'field' and backtracks from dead-ends in the phase-space, and the interrelationships themselves aren't there in the printout as I'm not bothered wasting output cycles and character spaces with that whilst running. It's just a handy progress-meter for my benefit. Yes, there's a valid solution, at this level of enquiry, with just three elements... It's not the Four Colour problem... )

The looser the constraint, the more scope the search could cover (loads more partial solutions, that could 'die' before reaching out to the theoretical tip of any branch), but the more likely it'll find a final solution quicker. The tighter I make it, the dead-ends increase but so do entore dead-forks, which might shut off some old found solutions but that'w because they won't even get far into those old directions, so the screening will quickly hop over into other (more likely to be useful) branches from closer to the root of the respective decision-tree.


So the idea is to pre-bake the order of the nodes for full checking, so moving on/retreating is in a manner not just servant to anything like the incidental node-labels shuffled into alphanumerical order/whatever. Instead, I shall find the most connected node (rule 2, in my above post) knowing that any value I first give this reduces more future tree-branchings later on than if I'd started with a weakly-connected node. Then find any of the nodes that neighbour it (jointly all have the maximum possible value of one link to  "all nodes ahead of them", as per rule 1) and select one of those with a similar high future potential of link-backs (rule 2 as a secondary concern). The third one I look at might have links to both prior items (there may be several candidates for rule 1 showing double-connection to first and second item) and thus constrained the most. Or still only "1 past link" (either first-in-list or second-in-list) is the most we have. Rinse and repeat.


If I used a bit more exploration, I could add a further (or even initial/intermediate) requirement that "nodes that have neighbours that link back to the currently established queue of nodes" or more, at some point in the slicing down of candidates for the next addition, but then I'm trading tree-branching in the future (the 'running through the queue that we establish') for tree-branching in the very establishing of said queue. As it stands, I'm checking N items, choosing one, checking N-1 items as possible candidates for onward travel, choosing one of those, etc[1], where testing N+(N-1) then (N-1)+(N-2), etc, for a first-order look-ahead (and I could go for second-order, third, even Nth, at least for the first decision where I could weight "best short-term answers to be found in a long term search" to establish which supposedly immediate decision is the absolute best) starts to look like more and more like doing the full tree-checking in a tree's worth of different ways just to make sure that I have the absolute best tree-checking strategy when it comes to the value-iteration stage! That way madness lies. Doable, but mad.

And if I check the script I just ran, again, it should by now have... Ah, sorry, I think my last tweak broke something slightly... Typical. Ah, I see, a "." instead of a ","...That's easily corrected, at least. That's not your concern, of course.



[1] I could reduce this, a bit, but I'm not requiring my queue to be formed of a 'single traversible path' but could find that after the first item, and second item to which it must be linked, the actual third item 'best' links to the first but not the second, so I'd need to maintain "all nodes that are neighbours of enqueued nodes" as a subset of N that gets added to by new 'neighbours' (as old neighbours that are enqueued are removed) rather than just look for immediate neighbours of the last node I chose. At the moment, that would work (losing some of the advantages I'm looking for) But there are reasons why it might not, and the balance of effort to track the 'hyperneighbourisation' might even make later setups fail, so I'm accepting the marginal hit of testing N(N+1)/2 things from start to finish during the initial enqueuing phase.

So, if I'm getting you correctly, you have a set of nodes, some of which mutually exclude each other, and you want to find a maximum-size subset of nodes none of which exclude each other?

This is the maximum independent set problem: https://en.wikipedia.org/wiki/Independent_set_(graph_theory) . It is strongly NP-complete. What size inputs are you looking at here?