• Create Account

# jwezorek

Member Since 10 Nov 2009
Offline Last Active Feb 25 2014 11:44 AM

### sorting multicolumn data

08 November 2013 - 03:50 PM

Say you have tabular data that can be sorted ascending or descending by any column. How can you represent the current sort state such that the sorts can be replayed to get the same order?

In other words, if you have a "name" field and a "value" field and a "color" field none of which is guaranteed to be unique, sorting by name and then by color gives different results than sorting by color and then by name. So you would need to maintain the sort history in queue of sort operations, but at what point can you stop maintaining this history -- shouldn't it loop around to the same order at some point?

### finding minimum flow when edges have lower bounds on flow

07 November 2013 - 12:27 PM

What algorithm should I use to find the minimum flow of a digraph where the flow across each edge has an infinite upper bound but a non-zero lower bound?

Like this for example:

In the literature this is a minimum cost flow problem. In my case however the cost is the same as a nonzero lower bound on the flow required on each edge so I worded the question as above. In the literature the question would be: what is the best algorithm for finding the minimum cost flow of a single-source/single-sink directed acyclic graph in which each edge has infinite capacity, a non-zero lower bound on flow, and a cost equal to the lower bound on flow.

From my research it seems that the main way people deal with any kind of minimum cost of any kind of network is to set the problem up as a LP problem and solve that way. My intuition, however, is that not having upper bounds on flow ,i.e. having edges with infinite capacites, makes the problem easier, so I was wondering if there is an algorithm specifically targeting this case using more "graphy" techniques than the simplex method et. al.

I mean, if all the costs and lower bounds are 1 as in the above... we are then looking for a flow that covers all edges, obeys flow rules, and isn't pushing too much flow through any path from s to t. This just feels like it shouldn't require an LP solver to me and indeed the Wikipedia article on min cost flows states that "if the capacity constraint is removed, the problem is reduced to the shortest path problem" but I think they are talking about the case in which the lower bounds are all zero.

I can envision an algorithm like Edmonds-Karp for solving this problem in which you start by assigning zero flow to all edges and then successively augment the flow on a shortest-path p from s to t by x, where p contains at least one edge for which the lower bound constraint is not already satisfied and x = min{ lowerbound(u,v) - f(u,v) for all (u,v) in p with lowerbound(u,v) > f(u,v)}. When there exists no path p you are done.

However, finding a shortest-path for which there exists at least one edge that does not meet its lower bound is not as simple as running a BFS over a residual network as in Edmonds-Karp.

I think the best way to do this would be to maintain an analog of the residual network that is something like the set of all edges that are not currently satisfied by the flow unioned with satisfied edges that if you removed them at least one unsatisfied edge would become disconnected from the source of the graph or disconnected from the sink of the graph ... this is hard for me to explain because it isn't entirely clear to me yet but when I work out problems on paper I can tell that there is something like a residual network that can be maintained as you go.

Can anyone help?

### remove_if-like behavior maps?

04 July 2013 - 05:27 PM

So is there an idiomatic way to remove all items from a map for which some predicate is true?

std::remove_if "removes" items by moving them to the end of a collection and then returns an iterator to the first of the "removed" items so you can erase them or do whatever you want to do. This doesn't work for maps because maps are ordered and therefore you can't just arbitrarily move their contents around.

Is there some way of doing this with standard library algorithms? I just wrote a function but it seemed weird that I had to.

Also does anyone else find remove_if broken? I mean why not just get rid of it and have erase_if? Or at least have erase_if and remove_if?

### Are most mobile apps boring and redundant or is it just me?

05 June 2013 - 11:15 AM

I've been trying to come up with something to implement in order to learn Objective-C/ iOS development. Basically the only iOS development I've done has been the game I'm working on which is on top of cocos2d-x and as such is in C++ with Objective-C complelely hidden from me, but I've started getting the feeling that I should actually learn Objective-C; otherwise, it might end up biting me in the ass down the line. Also wouldn't mind being able to start sniffing around at getting an iOS development job (I have a lot of experience developing software on other platforms so I think just getting a couple of apps in the app store with my name on them would be enough to be taken seriously)

Anyway, I kind of want to come up with an idea for a normal iOS app, i.e. a non-game app. Trouble is, I realize now, I don't actually use a lot of apps beyond the obvious things from the big players (e.g. Gmail, maps, etc.) so I have been looking through lots of lists of best or most useful iOS Apps. I am struck by the extent to which most of the apps I see listed do not interest me at all and don't seem particularly useful to me.

1. I don't care about taking notes/having a journal/blah blah blah
2. I don't care about some company's new yet-another feed aggregator. I know where to find the content I like; I don't really look at facebook much anymore and if I feel the desire I can, you know, look at facebook.
3. I don't care about yet-another to-do list app.
4. I don't care about yet-another calendar app.
5. I don't care about yet-another way to share x with my friends
6. I'm sick of every single app describing itself as minimal. I get what is presumed to be good about this approach: intuitive interfaces, stripped down functionality allows for low cognitive burden for new users, but at a certain point, when you realize that everything that is supposed to be new and exciting software-wise these days is being described as minimal, doesn't it all just start seeming like a cop out that has more to do with the length of engineering development cycles than anything else? If I'm going to get into, say, painting on my iPad, don't I want the maximal painting app?

I don't know ... Am I just getting too old?

### General questions about the iOS Game Center

16 May 2013 - 11:44 AM

I just want to survey people's opinions about how important Game Center integration is for an iOS game.

I'm asking because I honestly don't know ... I personally like the kinds of games that I write and actively play them on my iPad but I don't really care about social networking crap and don't look at leader boards or challenge friends to beat my scores or anything like that, but I'm thinking this could be generational and that I may be the weird one. so...

1. In your opinion how important  is it for a single-player action puzzle games for iOS to integrate with Game Center to support leader boards and social networking functionality.
2. Should it support game center and have  a traditional (local) high score screen or is that redundant?
3. Should it have a local highscore screen if it doesn't support game center?
4. Would it be better to integrate with something else? i.e. something like OpenFeint, which is dead right???
5. If it does integrate with Game Center what are the most important Game Center features to include?

PARTNERS