The Big Programming Thread - Page 953

On April 02 2018 23:54 travis wrote:
need help. this is probably the hardest problem i've had to address while programming.

I can describe it like this.

I have a graph, it has an undetermined amount of edges, and nodes 0 to n.
For an example, let's say it has nodes 0 to 9. So, 9 nodes.

I take a subset of these nodes. Let's say I take nodes 2,3,4,5.

What I do in my program is I take this subset, and I mark each node in the subset that has an edge that connects to a node that is not in the subset.

For example, if 2 goes to 3,5,8 - it would get marked, because it has an edge that connects to 8 which is not in the subset.

But if 3 goes to 2,4,5,and nothing else - it would not get marked.

Now I take my subset, and I BFS all simple paths (paths that touch each node once), within my subset, that *start and end* on a marked node. So, it could be said that what I am doing is finding paths that go through my subset, connecting to each node in it, and is able to continue on through the graph in both directions.

For every pair of marked nodes, I map that pair to a list, and the list is populated with sets of edges that make up a path I found. Maybe I don't find any paths that qualify for a given pair, or maybe I find 100,000 paths that qualify for a given pair.

So I have something like
map[2,4] -> [{(2,3),(3,5),(5,4)}, {(2,5),(5,3),(3,4)}]
map[3,4] -> [{(3,2),(2,5),(5,4)}]
map[4,5] -> [{}]
... etc

Now - to the actual problem.

For any list that has at least one path, I only actually need one path. Not 2, and not 100,000.
But for the entire subset I am finding paths for, I want to use as few edges as possible to make up all these paths.

So basically, I want to pick the fewest amount of edges I can, such that I can form at least one path from every list that has a path.

I recognize that this is... a difficult problem to do exactly. So, I am more focused on efficiency than precision. Getting a set of edges that is a little too big in time k^3 (where k is the size of my subset), is way way better than an exact answer in say k^2*2^k, for example.


Any ideas?
I think my first step must be to sort my lists by number of sets, and look at the lists with only one set, and do intersection of all of those because I need those edges.

Then I can worry about finding missing edges to be able to make a set from all the other lists. But even that is difficult.



This is what I went with...

+ Show Spoiler +

On April 02 2018 23:54 travis wrote:
...

I recognize that this is... a difficult problem to do exactly. So, I am more focused on efficiency than precision. Getting a set of edges that is a little too big in time k^3 (where k is the size of my subset), is way way better than an exact answer in say k^2*2^k, for example.

...

On April 03 2018 16:26 Apom wrote:

Then take every edge in the subset, can't beat O(1) efficicency.

On April 03 2018 19:35 gravity wrote:
Could you use a search algo like A*? (Whether this is efficient enough will depend on the shape of the data, but it will probably be ok).

On April 03 2018 13:18 travis wrote:
It is not because a minimum spanning tree can touch nodes more than once, and I need paths that only go to/from them once.

On April 05 2018 17:25 Acrofales wrote:

Pretty sure an MST is the solution you're looking for. Between any two nodes in an MST there is exactly one path (from the first node up to the shared parent and then down to the other node). And all nodes that are connected in the greater graph, are connected in the MST. Moreover, it is optimal in the number of edges.

On April 06 2018 00:14 travis wrote:


I don't think so because for a given set of nodes I am only looking for paths that go through all those nodes one time.
While a minimum spanning tree will give me a path, it generally won't give me ones that go through all the nodes in the set.

On April 07 2018 00:48 phar wrote:
Maybe I misread your problem (sorry, skimmed it), but your problem doesn't really need the graph at all? As in you have a list of sets of sets of things:

[
{{ (1,2) ; (2, 4); ... }, { (2,3) ; (2, 4) ; ...
{{ ... }}
{{ ... }}
]

And you just need to minimize the stuff inside - leave at least one set in each list, eliminating all others, where you can only eliminate all sub sub sets that contain a given element all at the same time.

That to me doesn't feel like a graph problem once you've distilled it.

On April 07 2018 00:48 phar wrote:
Maybe I misread your problem (sorry, skimmed it), but your problem doesn't really need the graph at all? As in you have a list of sets of sets of things:

[
{{ (1,2) ; (2, 4); ... }, { (2,3) ; (2, 4) ; ...
{{ ... }}
{{ ... }}
]

And you just need to minimize the stuff inside - leave at least one set in each list, eliminating all others, where you can only eliminate all sub sub sets that contain a given element all at the same time.

That to me doesn't feel like a graph problem once you've distilled it.

On April 07 2018 01:16 raNazUra wrote:


Yeah, this was how I interpreted the description as well. "Given a list of sets of inner sets, select one inner set from each outer set such that the union of all selected sets is minimized."

On another note, for people who like doing coding/algorithmic challenges, Google's yearly Codejam is starting up later today. The qualification round is usually pretty trivial, things start getting more fun in rounds 1 and 2.

Edit: Re-read the description of travis' problem, and based on that description its definitely MST. Based on the follow-up clarification, I think that the misstatement is describing the original set of paths being collected as 'simple' paths, when they really are supposed to be Hamiltonian paths? Is that accurate?

If that's the case, we can add to the above formulation that all inner sets are the same length, on the off chance that's useful in any way.

On April 07 2018 04:28 travis wrote:


Yep, it is not a graph problem. I feel like I didn't really frame it as one, though. I was just describing the situation.




Well, I do say that the simple paths touch every node in the collection. I didn't want to say hamiltonian path because I thought it could be confusing since we are addressing a subgraph of a greater graph. But I suppose I was just more confusing. Maybe I was doomed either way.

On April 11 2018 16:53 Manit0u wrote:
Postgres question:

I have a very simple query

UPDATE "table_name" SET "last_seen_at" = now(), "updated_at" = now() WHERE "table_name"."id" = "uuid";

For some reason it takes 16-28 seconds to execute.

Do you know any potential reasons for that?

I've checked most common culprits:
1. Table is not large (10 records)
2. Vacuum and analyze are no older than 2 days

Any ideas? Could the problem be the number of concurrent db connections (over 100)?

SELECT * FROM information_schema.triggers

EXPLAIN ANALYZE UPDATE "table_name" SET "last_seen_at" = now(), "updated_at" = now() WHERE "table_name"."id" = "uuid";

SELECT current_setting('transaction_isolation');