Print

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

[TheBiggerFish]

Spoiler (click to show/hide)

Apologies for terrible sizing.

Heck, I count 19 lines in the first spoiler.

[monkey]

@Spehss_: you can't "read" a class, google the reasons.

try something like:

Code: [Select]

  void save() {
    std::ofstream file(fLoc.c_str(), ios::out|ios::binary);
    file << level << " " << str;
    ...
    ...
  }
  void load() {
    std::ifstream file( fLoc.c_str(), ios::in|ios::binary);
    file >> level >> str;
    ...
    ...
   }


[Antsan]

Does anybody have any idea of how to generate random graphs that are guaranteed to have cycles/not have cycles? I need this to write testing functions for my graph library, specifically testing the predicate `CYCLIC?`.
We don't know anything about the internal representation. There is a function to add a node, a function to add an edge between two nodes (depending on the type of the graph this is either a directed or an undirected edge) and a function to add an edge between two nodes only if that edge wouldn't be part of a cycle in the resulting graph.

Generating an undirected acyclic graph is trivial:

Code: [Select]

(let ((edge-chance (random 1.0))
      (graph (make-standard-graph)))
  (loop for node below node-number
     do (setf graph
              (if (<= (random 1.0)
                      edge-chance)
                  (add-edge (add-node graph node)
                            (random-node graph)
                            node)
                  (add-node graph node)))
     finally (return graph)))
Add nodes and randomly connect them to at most one already existing node – cycles will never turn up that way.

To generate a undirected cyclic graph it might be possible to just add cycles to an acyclic one. To do this, isolate a connected subgraph, randomly choose two non-incident nodes in that subgraph and add an edge between them. Repeat with a certain probability.
Isolating a connected subgraph is trivial – just do a flood-fill from a random node.
Finding two non-incident nodes can be done by randomly selecting one node, removing it and all of its neighbors from the set of eligible nodes and selecting another node.

What to do if none exist? Select a different connected subgraph? select a different node in the already selected subgraph? Connect two disconnected subgraphs? Do which of these when?

Generating a directed acyclic graph is a bit harder, as a node could have multiple parents in a DAG and the `CYCLIC?` predicate needs to be tested against these cases, so the algorithm I proposed for undirected acyclic graphs doesn't apply here.
Maybe first generating a number of nodes and then adding a number of edges randomly while preserving the acyclic property would work, but that seems wrong somehow. Maybe it really isn't wrong.

I have no idea for directed cyclic graphs.


So, any ideas anyone?

[MagmaMcFry]

You can generate a random undirected cyclic graph in an easier fashion than you're thinking of. Just generate any random undirected graph, then pick a bunch of random vertices and connect them in a cycle.

You can generate a random directed acyclic graph by assigning each node a random height and adding only downward edges.

You can generate a random directed cyclic graph by generating any random directed graph and adding edges forming a directed cycle.

[miauw62]

I'm trying to make some sort of flappy bird clone in JS for school. I've got the bird moving up and down working rather nicely, but I'm stuck at adding the pipes.

http://hastebin.com/wipizosufe.js

Pipe adding code is around line 120.

Every debug message except works, except the ones inside the for loop in mainLoop() aren't executed. So I'm probably doing something wrong in terms of adding objects to arrays. Any help? This is my first time working in javascript.

[MagmaMcFry]

You messed up the comparison in said for loop.

[Reelya]

Code: [Select]

for(var i = 0; i++; i >= pipes.length - 1)
Just looks wrong to me. For loops in JavaScript aren't any different to in c/c++ (except for "var"). The comparison is wrong, and it's in the wrong spot.

[Gatleos]

So I need to find the minkowski sum of two arbitrary polygons. According to some articles I've read about the subject, I need to merge the list of vertices in the two polygons into one, while maintaining the ordering by angle. The resulting polygon has to be convex, so they have to be sorted by the ϴ (angle) portion of their polar coordinates.

This might be pretty easy if these lists of vertices started at the rightmost point and worked around counter-clockwise, but they start at arbitrary positions and can go clockwise too. This might take a while.

[frostshotgg]

From some cursory googling and probably poor understanding, I don't think it's that complicated, Gatleos.

Let A be a polygon with vertices {(4,2),(-2,8),(5,6)} and B {(1,1),(3,5),(-2,4)}. My understanding is that you'd add A[1] to B[1] by adding their X and Y values, then add A[1] to B[2] and repeat until you have index of A * index of B values, then take every value which has either a maximum or minimum X or Y value, and those form the vertices of the convex polygon A+B.

EDIT: Actually the latter part is probably not quite right, that'd limit you to basically a quadrilateral every time. But the list of possible vertices is definitely every A times every B.

[Reelya]

I need to merge the list of vertices in the two polygons into one, while maintaining the ordering by angle.

That apparently only works for when the input polygons are both convex. If so, then use 3D vectors and the cross product to determine if the polys are clockwise or counter-clockwise. Then, you can adjust inputs and use the standard algorithm.

EDIT: I thought of a method, but it won't necessarily work if there are non-convex inputs.

[Bumber]

Python problem. Suppose I have a dictionary defined as such:

Code: (Python) [Select]

table = {}
table["Key"] = ("String",[(True,"Alice"),(False,"Charlie"),(True,"Bob")])
What's the best or most efficient way to check if a given name exists or not in a tuple of the list table["Key"][1], then remove the tuple that contains it?

I would do this:

Code: [Select]

table['Key'][1] = [tuple for tuple in table['Key'][1] if name not in tuple]


Hmm... that doesn't look too efficient (as the real list might be much larger.) It also needs to know which names were found. I should've mentioned I'm actually trying to find a number of names, which might make some kind of set intersection more ideal.
I tried this:

Code: (Python) [Select]

table = {}
table["Key"] = ("String",[(True,"Alice"),(False,"Charlie"),(True,"Bob")])

found=[]
not_found=[]
names = ["Alice","Bob","Dave"]
for tuple in table["Key"][1]:
if tuple[1] in names:
found.append(tuple)
else:
not_found.append(tuple)
table["Key"][1] = not_foundUnfortunately:

Code: [Select]

Traceback (most recent call last):
  File "<pyshell#7>", line 1, in <module>
    table["Key"][1] = not_found
TypeError: 'tuple' object does not support item assignmentNot sure what the deal is there. It seems the outer-most tuple doesn't want me swapping out its list for another. Swapping the outer tuple out for a list works, and should be functionally identical. Or I could replace the entire tuple:

Code: [Select]

table["Key"] = (table["Key"][0],not_found)Not sure which is better.

[Gatleos]

I need to merge the list of vertices in the two polygons into one, while maintaining the ordering by angle.

That apparently only works for when the input polygons are both convex. If so, then use 3D vectors and the cross product to determine if the polys are clockwise or counter-clockwise. Then, you can adjust inputs and use the standard algorithm.

EDIT: I thought of a method, but it won't necessarily work if there are non-convex inputs.

Yeah, I already accepted the limitation of convex polygons. I'm just rejecting any input that isn't convex. It's really confusing to visualize how to determine which vertices from polygon A should be placed between which ones from polygon B, and how I should be altering the coordinates to account for the new vertices I shoved in between.

[frostshotgg]

Yeah, I already accepted the limitation of convex polygons. I'm just rejecting any input that isn't convex. It's really confusing to visualize how to determine which vertices from polygon A should be placed between which ones from polygon B, and how I should be altering the coordinates to account for the new vertices I shoved in between.

Unless I horribly, horribly misunderstood what a Minkowski sum is, or what your task is, you don't need to put the angles in the same list. You just need to add the vertices.

The Minkowski sum is basically finding the maximum possible range you can have if you slid one polygon along the perimeter of another polygon like so:

Spoiler (click to show/hide)

If both figure A and B are convex, the most extreme points will appear where one vertex of A is touching one vertex of B. From this we can determine that using the set of all possible vertices of the Minkowski sum C must be in the set of {A[1]+B[1], A[1]+B[2]... A[1]+B[n], A[2]+B[1]... A[n]+B[n]}. Once you have all of the possible vertices, you have to find which ones are are the edges and which ones are inside the polygon. Depending on how you have to output the data, you may not even have to do that much.

EDIT: Stupid bbcode just read my mind and do it right

[EnigmaticHat]

Spoiler (click to show/hide)

FTFY

[Antsan]

You can generate a random undirected cyclic graph in an easier fashion than you're thinking of. Just generate any random undirected graph, then pick a bunch of random vertices and connect them in a cycle.

You can generate a random directed acyclic graph by assigning each node a random height and adding only downward edges.

You can generate a random directed cyclic graph by generating any random directed graph and adding edges forming a directed cycle.

Thank you very much!

The ones for generating cyclic graphs seem painfully obvious now.