|
I'm having some troubles with some code that works fine on Windows, but not really at all on Linux. The problem is to check if a graph is bipartate by traversing it and coloring nodes adjacent to the current one the opposite color (e.g. we start at white, and color any adjacent nodes black). If we run into a color conflict, then the graph is not bipartate. I'm using a breadth-first search to do the traversal. Here's my header: C++ code:
C++ code:
As I said, my program works fine on Windows - it finds that the first input is bipartate and that the second isn't. However, on Linux, both produce the following output: code:
|
# ? Mar 25, 2014 14:00 |
|
|
# ? Jun 8, 2024 08:50 |
|
It looks like you might be trying to read the first number on each line as an entry in the adjacency list for that index instead of as the index itself. I'm only guessing without looking at the parsing code itself.
|
# ? Mar 25, 2014 14:50 |
|
The Laplace Demon posted:It looks like you might be trying to read the first number on each line as an entry in the adjacency list for that index instead of as the index itself. I'm only guessing without looking at the parsing code itself. I started out doing that, but then realized I needed to be able to have a vertex that is the first number on a given line in the input, so now it creates new entries for everything in the adjacency list (or should, anyway).
|
# ? Mar 25, 2014 15:12 |
|
I don't see a reason to construct a whole bunch of redundant vertices when you're initially parsing the input, and then trying to finish constructing the graph as you're doing the bipartite check. It seems needlessly complicated, and a great way to introduce errors. One example of an error that you've introduced: when you check isVisited(), the answer is almost always going to be false, even if you have in fact already visited that particular vertex via a different path. What I would do is make the graph construction routine construct the complete graph (with everything that points to a particular vertex pointing at the exact same vertex instance), and then write a routine that prints out what the graph is. That way you can check your graph-reading and your bipartite-checking code in isolation, instead of having to worry about figuring out which half of the program a particular bug is in.
|
# ? Mar 25, 2014 15:27 |
|
Jabor posted:What I would do is make the graph construction routine construct the complete graph (with everything that points to a particular vertex pointing at the exact same vertex instance), and then write a routine that prints out what the graph is. That way you can check your graph-reading and your bipartite-checking code in isolation, instead of having to worry about figuring out which half of the program a particular bug is in. Since this is due soon, I'd rather not do a major re-write if I don't have to, but I'll keep this in mind.
|
# ? Mar 25, 2014 16:19 |
Instead of having "visited" and "color" be properties of each node, just keep them as local variables in the bipartite check algorithm. Since that's what they are! The std::set or std::map types can be very useful for that, but if you aren't allowed to use those then you can also just do with some simple vectors of ints. One set (vector) containing the IDs of nodes that you have already visited, one map (or two vectors, one for each color) that tells which color a node has been assigned. That will first of all solve your problem with the adjacency list representation of your graph storing whether you have traversed a specific edge rather than visited a specific node, and similarly that you end up coloring edges rather than nodes. It will also allow you to simplify your adjacency list representation to just be a vector (indices being node names) of vectors of adjacent nodes, instead of needing each element in a node's adjacency list to be a complex object.
|
|
# ? Mar 25, 2014 16:38 |
|
I'm trying to write an RRT and I was getting occasional long pauses while trying to find the nearest existing node to the new point. I could understand if it was hitting a wall on the map and discarding the new point but I can't think of a reason it can't get past this, even if there are two points equal distances away. This is my code: code:
For a reason I can't figure out the final if statement is where VS says the program is getting hung. Sometimes it continues after a little pause but sometimes it takes longer than I'm willing to wait. And it can happen after any number of tree generations, does anyone know why it might be doing this? Praseodymi fucked around with this message at 17:22 on Mar 25, 2014 |
# ? Mar 25, 2014 17:17 |
I think you need to post some more code. How often is that code you posted being run? How many elements do you have in your points list? VS allows you to set breakpoints then alter them to trace-points, i.e. make the debugger write a message each time a breakpoint is passed, but not actually stop at it. That can also include printing the values of in-program variables and more. You can try using that to trace what your program is actually doing.
|
|
# ? Mar 25, 2014 17:24 |
|
Points starts with a single point in it. After the code I posted a unit vector is created a certain length from xNear to xRand, which is added to points, so that code then runs until Points reaches the number of iterations defined at the start of the program, in this case 1000. This problem only became evident when I was testing to find out how quick it was by running it over and over again, but all the containers are cleared when a new tree is generated, and like I said, i've seen it happen after anywhere between 5 generations and 350. EDIT: I just tried it on two different maps, and it seems to happen less often the larger the map is. Praseodymi fucked around with this message at 17:47 on Mar 25, 2014 |
# ? Mar 25, 2014 17:38 |
|
hooah posted:Since this is due soon, I'd rather not do a major re-write if I don't have to, but I'll keep this in mind. You might also want to just write a routine to print the graph (could use gnuplot format), so that you can verify it, or call it from the debugger when things get weird. Also makes for good record-and-compare for regression testing.
|
# ? Mar 25, 2014 17:58 |
|
Does it really win me much to be const'ing parameters that are passed by value? It's documentation, but is there much use to it?
|
# ? Mar 28, 2014 03:44 |
|
slovach posted:Does it really win me much to be const'ing parameters that are passed by value? It's documentation, but is there much use to it? If you're passing something big as a const value, pass it as a const reference. If you're passing something small as a const value, you're probably wasting some keystrokes.
|
# ? Mar 28, 2014 03:53 |
|
Marking a (non-ref, non-pointer) function parameter as const in the declaration doesn't do anything at all. It doesn't even serve as documentation of implementation details that the caller shouldn't care about, as the constness of values in the definition of the function doesn't have to match the declaration. Making arguments const in the definition itself is useful for the same reason as making local variables const is ever useful: if you think you shouldn't be modifying an argument but do, then you may have a bug. However, keep in mind that you can't move out of const values.
|
# ? Mar 28, 2014 04:02 |
|
I suppose you mean documentation for people who don't know that value arguments are not written back, but you can't cargo-cult someone into learning the features of a programming language.
|
# ? Mar 28, 2014 04:12 |
|
Sup robotics buddy There's some weirdness in RRT's performance sometimes due to its randomness, so it can be hard to pin down issues. If you post your full source code I can try to help you out. RRTs and related algorithms are my primary research area.
|
# ? Mar 28, 2014 17:28 |
|
We just released our custom C/C++ preprocessor, Warp. It had a surprisingly large impact on our build times. https://code.facebook.com/posts/476987592402291/under-the-hood-warp-a-fast-c-and-c-preprocessor/
|
# ? Mar 28, 2014 19:34 |
|
That's a few days early no? I know none of the Boost headers I use don't have include guards in.
|
# ? Mar 28, 2014 19:46 |
|
People actually use D for things??
|
# ? Mar 28, 2014 19:52 |
|
GrumpyDoctor posted:People actually use D for things?? Well Andrei obviously does.
|
# ? Mar 28, 2014 19:52 |
|
Praseodymi posted:This is my code: One thing I did notice was that, the way you've implemented the point sampling, you're actually sampling from a fixed, discrete grid of points in space. The coarseness of your grid depends entirely on the size of the space; therefore, the larger the width and height, the finer the grid will be relative to the space. This might explain why the method's performance seems to improve with larger maps. You should change the sampling to actually sample from RAND_MAX possible values. This way the performance will be less sensitive to the size of your map. code:
About VS hanging at the sqrLength() line: how did you test for "hanging"? Did you just break execution randomly and find it was always in that spot? On typical problems RRT spends the most time deciding whether a point is in collision or not, but in some cases the most expensive part is that distance comparison, which would explain how often the program happens to be there when you cut execution.
|
# ? Mar 28, 2014 22:17 |
|
giogadi posted:This'll work better, but it still isn't the best way because the standard rand() function on most systems has really lovely randomness properties and RAND_MAX can be literally anything greater than 32767. Boost's random library is great for stuff like this. That's reminded me of something. I came into contact with C++11's random stuff for the first time a while ago, is that any good, or is it just more customisable?
|
# ? Mar 28, 2014 23:01 |
|
Subjunctive posted:Well Andrei obviously does. Andrei just bragged not too long ago about pushing the first D program in production at facebook: http://forum.dlang.org/thread/l37h5s$2gd8$1@digitalmars.com Volguus fucked around with this message at 23:06 on Mar 28, 2014 |
# ? Mar 28, 2014 23:03 |
|
roomforthetuna posted:There is close to zero practical use for it (it might impact an optimization in some weird fringe case). It could, yes. It is undefined behavior to modify a const object.* ** *** Therefore, if you take the address of such an object and pass it to an opaque function, the compiler can assume that the function doesn't actually modify the original object. I don't know of any compilers that specifically do this optimization right now, but it's legal, and we've certainly looked into it for clang. * That is, an object which was constructed as a const object per its declaration/construction, as opposed to a non-const object that you happen to have a const reference/pointer to, where you are totally allowed to cast away the constness and modify the object. ** Of course, you can modify any mutable fields of such an object. *** Because C++ is dumb, you can destroy a const object and create a new object there with a different value, but then it's undefined behavior to access it through the original name.**** **** This is some of the vaguest bullshit in the standard.
|
# ? Mar 29, 2014 00:35 |
|
Would someone like to clue me in on why I can't declare this variable array? I keep getting "Unused variable 'code'" messages and I'm completely stumped since I'm declaring a new variable right before it and have done similar things in the past with no issue. I surrounded it with asterisks so it can be found easily, it's near the bottom of the code and this program is unfinished, but I'm fairly certain I have all the braces where they need to be.code:
|
# ? Mar 29, 2014 00:41 |
|
It looks like you need to dynamically allocate an array since the length isn't a compile-time constant. You need to do a heap allocation if the size is to be determined at run-time.
|
# ? Mar 29, 2014 00:48 |
|
Variable length local arrays are not allowed in C++ (but are in C99, I think). The probably not entirely correct explanation is that this is because local arrays go on the stack and C++ wants to know how much stack to allocate early, but here the space required is not known until the relevant strlen is calculated. Solution: allocate on the heap. In C++03: C++ code:
C++ code:
C++ code:
vvvvvv Xerophyte fucked around with this message at 01:11 on Mar 29, 2014 |
# ? Mar 29, 2014 00:59 |
|
Xerophyte posted:In C++03:
|
# ? Mar 29, 2014 01:02 |
|
Xerophyte posted:In C++14: I still can't believe they added std::make_shared but completely left out std::make_unique for reasons unknown Edit: Especially when it doesn't use any C++14 features, it seems. I found an answer on StackOverflow that implements the same functionality if you want to use it in C++11: C++ code:
Jewel fucked around with this message at 01:14 on Mar 29, 2014 |
# ? Mar 29, 2014 01:08 |
|
For what it's worth, it's C, not C++. C99, specifically. So does that mean I *should* be able to declare a variable length array farther down in the code?
|
# ? Mar 29, 2014 01:16 |
|
Even if durtan is using C, the smart array type in standard C++ is not named *_ptr at all. It's named "vector"
Gazpacho fucked around with this message at 01:42 on Mar 29, 2014 |
# ? Mar 29, 2014 01:32 |
|
durtan posted:For what it's worth, it's C, not C++. C99, specifically. So does that mean I *should* be able to declare a variable length array farther down in the code? Ah. What's string here? A typedef to char* in one of those headers I guess... Anyhow, far as I know the VLA declaration should be fine in a C99-compliant compiler and you're obviously making one earlier (j) and that works. I guess you might be getting unused variable warnings because you're not actually using the code variable anywhere in the posted code, though. You're declaring it, but that's not using.
|
# ? Mar 29, 2014 01:38 |
|
Xerophyte posted:Ah. What's string here? A typedef to char* in one of those headers I guess... I believe the "string" declaration is part of the cs50.h file provided to me by the class. And you're right, I wasn't using the variable so it was giving me that error. Thanks everyone!
|
# ? Mar 29, 2014 01:51 |
|
giogadi posted:Sup robotics buddy Robotics researchers represent! SLAM here, although I submitted an RRT variant to IROS, just to get the notch in my belt...
|
# ? Mar 29, 2014 02:34 |
|
Variadic templates. (Making a thing that can expect a number of values which can be any combination of strings, ints or bools, which will be parsed out of a single string parameter, and then the results need to get crammed into a pre-existing variadic templated class.) This isn't a question, just
|
# ? Mar 29, 2014 05:44 |
|
Xerophyte posted:Variable length local arrays are not allowed in C++ (but are in C99, I think). The probably not entirely correct explanation is that this is because local arrays go on the stack and C++ wants to know how much stack to allocate early, but here the space required is not known until the relevant strlen is calculated. Solution: allocate on the heap. C++ 14 supports runtime sized arrays without heap, so you don't need this.
|
# ? Mar 29, 2014 08:21 |
|
xgalaxy posted:C++ 14 supports runtime sized arrays without heap, so you don't need this. That's a really good tidbit, thanks for mentioning it! C++14 now sounds worth it.
|
# ? Mar 29, 2014 09:18 |
|
edit: wrong thread, I'm an idiot.
space kobold fucked around with this message at 22:10 on Mar 29, 2014 |
# ? Mar 29, 2014 21:47 |
|
xgalaxy posted:C++ 14 supports runtime sized arrays without heap, so you don't need this. No it doesn't, that was cut.
|
# ? Mar 30, 2014 08:37 |
|
xgalaxy posted:C++ 14 supports runtime sized arrays without heap, so you don't need this. Meh, just write a wrapper around alloca() and most platforms will support it independent from any C/C++ standard.
|
# ? Mar 30, 2014 11:35 |
|
|
# ? Jun 8, 2024 08:50 |
|
Zerf posted:Meh, just write a wrapper around alloca() and most platforms will support it independent from any C/C++ standard. How would you destroy the objects you've constructed in the region?
|
# ? Mar 30, 2014 11:50 |