Fake Programmers

KronoS

02:41

@TomWijsman you don't happen to be around do you?

Tom Wijsman

I do.

KronoS

oh hey! cool. I'm having pointer issues

Looking at DFS():

// Depth First Search with Statck
const void Graph::DFS()
{

	// Initialize Color and predecessors (leave Pred blank):
	for(list<Vertex>::iterator init = mInternalGraph.begin(); init != mInternalGraph.end(); init++)
	{
		init->setColor("WHITE");
		init->setPredecessor(NULL);
	}

	mTime = 0;

	for(list<Vertex>::iterator it = mInternalGraph.begin(); it != mInternalGraph.end(); it++)
	{
		if(it->getColor().compare("WHITE") == 0)
		{
			DFS_Visit(&(*it));
		}
	}
}

// DFS Visit (Modified)
const void Graph::DFS_Visit(Vertex * aVertex)
{
	aVertex->setColor("GRAY");
	mTime = mTime + 1;
	aVertex->setDistance(mTime);
	for (list<Vertex *>::const_iterator it = aVertex->getEdges().begin(); it != aVertex->getEdges().end(); ++it)
	{
		if((*it)->getColor().compare("WHITE") == 0)
		{
			(*it)->setPredecessor(aVertex);
			DFS_Visit(*it);
		}
	}

	aVertex->setColor("BLACK");
	aVertex->setFinish(mTime);
	mStack.push(aVertex);
	mTime = mTime + 1;
}

The address of it being passed into DFS_VISIT != the address of aVertex in DFS_VISIT

that make sense?

Tom Wijsman

DFS_Visit(&(*it));

KronoS

for example my first node in the mInternalGraph looks like this:

&it
0x0131e6d8 {mName="Root" mColor="WHITE" mEdges={ size=3 } ...}
    [ptr]: 0x00442598 {mName="Root" mColor="WHITE" mEdges={ size=3 } ...}
    [Raw View]: 0x0131e6d8 {...}

Tom Wijsman

That passes the address.

KronoS

02:46

right...

Tom Wijsman

Vertex * aVertex is a new address that points to the passed address.

So /me wonders how you're obtaining the addresses. :D

KronoS

aVertex
0x00442598 {mName="Root" mColor="WHITE" mEdges={ size=3 } ...}
    mName: "Root"
    mColor: "WHITE"
    mEdges: { size=3 }
    mPredecessor: 0x00000000 {mName= mColor= mEdges={ size=??? } ...}
    mDist: 0.000000000
    mFinish: 0.000000000
    mInputs: { size=0 }
    mOp: ""
    mComp: {mName="REG" mOperation="=" mDelay=0.500000000 ...}

so they are the same then... :/ 0x00442589

Hmmmmmm.... then why aren't the edges properly coming through :/

Tom Wijsman

[ptr]: 0x00442598 {mName="Root" mColor="WHITE" mEdges={ size=3 } ...}
       0x00442598 {mName="Root" mColor="WHITE" mEdges={ size=3 } ...}

Looks the same to me.

KronoS

hang on just a sec... lemme get to the problem and print it out for you:

Oh ok... ya... here's the problem

in DFS_VISIT:

		if((*it)->getColor().compare("WHITE") == 0)
		{
			(*it)->setPredecessor(aVertex);
			DFS_Visit(*it);
		}

The code inside is never executed, because the edges within it are never colored

Tom Wijsman

Code coverage... <3

KronoS

02:51

So that tells me that My Graph isn't correct... that the edges aren't really pointers to elements within the graph :/

Tom Wijsman

(Although I don't use it in personal projects yet)

I don't see why they wouldn't be.

KronoS

Here lemme show you what I see:

Tom Wijsman

Oh wait.

for (list<Vertex *>::const_iterator it = aVertex->getEdges().begin(); it != aVertex->getEdges().end(); ++it)
	{
		if((*it)->getColor().compare("WHITE") == 0)
		{
			(*it)->setPredecessor(aVertex);
			DFS_Visit(*it);
		}
	}

Would const_iterator change the pointer's address? I'd think not at first since it's supposed to be compile time.

And that should still not make it point to a different object...

KronoS

Ok ALL Vertices within the graph are colored WHITE, but the edges within those Vertices (who should just be pointers) aren't

does that make sense?

and they are pointers... just not pointers to the actual vertices within the graph... if that makes sense...

so theres duplication of data floating around here somewhere.

so how do I add these to each other:

// Add a child node to the parent.
void GraphReader::AddChildNode(Vertex * const aChildVertex, const string aParent)
{
	for(list<Vertex>::iterator it = mParsedVertices.begin(); it != mParsedVertices.end(); it++)
	{
		if(it -> getName().compare(aParent) == 0)
		{
			it -> addEdge(aChildVertex);
			break;
		}
	}
}

Tom Wijsman

bitbucket.org/KronosKoderS/ece-474/src/…

KronoS

02:57

Most of the time I call this function like so:

AddChildNode(&mParsedVertices.back(), lParsedData);

Tom Wijsman

Your else if in that function does no color.

KronoS

Where &mParsedVertices.back() is the Vertex that I just added to the back of the graph

Tom Wijsman

And there's no & in that else if eitherin the procedure you just mentioned.

KronoS

The AddChildNode?

Tom Wijsman

Oh no, that's okay, then just the fact that there's no color in the else if might be interesting.

KronoS

03:00

@TomWijsman I'm not sure where you're talking about

Tom Wijsman

2 mins ago, by Tom Wijsman

https://bitbucket.org/KronosKoderS/ece-474/src/5086300523722e993f83d97695552aa266d1a608/synthesizer/src/GraphReader.cpp‌?at=review#cl-270

KronoS

and I think it's not the coloring... it's the way that I've created the graph

Tom Wijsman

@KronoS: Well, I'm just saying I think some branches in your code don't assign colors hence that's why they might be empty.

KronoS

Maybe it's the lack of sleep, but I'm not making the connection how that file has anything to do with coloring. that the file that processes the graph

Tom Wijsman

@KronoS It calls AddChildNode?

KronoS

03:02

That doesn't

Tom Wijsman

It might be interesting to put an assert in AddChildNode to trigger the child nodes that aren't colored.

KronoS

that's the reader

Wait... that does call AddChildNode

Tom Wijsman

bitbucket.org/KronosKoderS/ece-474/src/…

:P

KronoS

sorry got confuzzled for a sec there. but there's no coloring involved here.

Tom Wijsman

It's either sleep or coffee, take your pick. :D

KronoS

03:03

ok we are on the same page then. The issue is how I'm adding the child nodes (edges)

Tom Wijsman

Well, I thought there was because of here: bitbucket.org/KronosKoderS/ece-474/src/…

KronoS

@TomWijsman Oh, that's entirely so that I can keep track of later where the terminating nodes are... I then later point those to a NOP so it's easy to find the end of the graph

it hasn't nothing to really do with coloring for the graphing algorithm

Tom Wijsman

So, just to summarize it: I think that they're still "" since they aren't set at start, aren't initialized at some point and they aren't visited either.

KronoS

@TomWijsman But that shouldn't matter... these should be pointers pointing to other vertices

which are getting colored correctly

You see what I'm saying?

Graph[1,2,3,4,5,...N]

1.Edges[*2, *4, etc,]

so when I make changes to 2 or 4 the pointers should reflect those changes, since all they do is point to the address of the vertex within the graph

Tom Wijsman

The edges are pointers, right?

Yeah, correct.

KronoS

03:08

yes... they are... but I think they aren't pointing correctly

but I could be way off

lemme push out the most recent code as well.. bitbucket isn't updated

Tom Wijsman

Might be handy to print out the graph.

Then on insert you could print the address you insert.

And after all the inserts you could print the graph and compare the addresses.

Or perhaps do this with the debugger with some careful breakpoints.

KronoS

ok I pushed it out

Tom Wijsman

Does it matter I posted the URLs here?

KronoS

no I don't care...

well actually this is a homework assignment.. though I doubt anyone here will be taking this same class anytime soon

Tom Wijsman

Hmm, I don't see any major change that would explain this.

So it probably existed before this.

KronoS

03:17

I think you're right... just wanted to make sure things were updated on your end

ok so here's the general approach I take to adding these edges:

I first add the vertex to the list of vertices that represent the graph

mParsedVertices.push_back(somevertex);

Tom Wijsman

Another nifty debug technique, or something you might even consider doing explicitly always, is to define a copy constructor and an assignment operator.

KronoS

Then I add any edges that I detect are children:

addEdge(aChildVertex);

Tom Wijsman

You can then define their behavior and more specially tell which one is getting called by inserting a simple cout there.

But you think you just create the tree wrong, so has nothing to do with the addresses being wrong? Then what I just said might be non-sense.

KronoS

lol... It's all good... I'm kinda talking out loud as well... and I have no idea what I'm doing wrong TBH, that's just my gut feeling

Tom Wijsman

Going to sleep in a few minutes.

KronoS

03:22

I always add the child after I've added it to the list:

AddChildNode(&mParsedVertices.back(), lParsedData);

Tom Wijsman

@KronoS cplusplus.com/reference/stl/list/back

KronoS

const void Vertex::addEdge(Vertex * aEdge) {mEdges.push_back(aEdge);}

Tom Wijsman

Returns a reference to the last element in the container.

KronoS

That looks valid...

Tom Wijsman

That already returns a reference, dunno if a reference of a reference might somehow be different but I suppose not.

KronoS

03:25

If I take off the & intellisense blows up on me

not saying that intellisense is god and all, but still

Tom Wijsman

Odd, but yeah, keep it then. An alias of an alias ain't bad. :D

KronoS

is the .back() the right thing to call? It's not pointing to a null pointer or anything is it?

3 mins ago, by Tom Wijsman

Returns a reference to the last element in the container.

ya last element

Tom Wijsman

Well, dunno, I think your tree is okay. Writing something that can concisely output the whole tree and then calling that after each small step could maybe reveal something.

KronoS

I'm running out of time :/

it's due tonight

at least I got the verilog functioning

Tom Wijsman

Doesn't sound good.

KronoS

03:30

Well actually this part (the graphing) was a chance to redeem myself

Tom Wijsman

for_each(yourList.begin(), yourList.end(), printBlaBla);

KronoS

basically a regrade... but still haven't been able to get it working fully

Tom Wijsman

Wouldn't take long to make a print function, but yeah, might be overkill if you need to do much more.

If you can get around through debugging instead it might be better.

Got to go sleep now, hope you debug it in a way that yields you the actual problem in a fast way.

@KronoS: Might be handy to try to obtain the smallest example for which it breaks first, so you can opt to just step through the code, making notes on a paper or a rubber duck (for instance, last digits/letters of pointer addresses) and finally seeing where exactly it goes wrong.

KronoS

@TomWijsman no this is it... getting the graph to properly parse, and finding the critical path

@TomWijsman thanks for the advice man, and seriously, you've been a life saver all day...

Tom Wijsman

Avoiding an extremely big graph just avoids it from looping over and over and only looping for what you need to identify the problem.

KronoS

03:35

These graphs aren't that big... only about 10 modes max

Tom Wijsman

This debugging approach might be faster than the typical output comparison trick, since output makes you see less what's happening and might not make you think about the problem.

See you later, good luck on finding what's going wrong.

And don't be too focused on the pointers, write down colors as well and so.

KronoS

23:52

WINDOWS 8 APP TIME!!!!

Transcript for