|
int numPaths;
bool bVisited;
vector<int> adjacent; // Contains the adjacent nodes in the INVERSE graph
};
sNode * nodes;
vector<int> topological; // Contains the REVERSED topological ordering of the nodes
int numNodes, bottomNode, numEdges;
void dfs(int);
void countPaths();
void printResults();
FILE * file;
FILE * outFile = NULL;
int main(int argc, char ** argv) {
int n, a, b;
char buf[256];
file = stdin;
if (argc == 2) {
file = fopen(argv[1], "r");
printf("Opening %s\n", argv[1]);
if (isdigit(argv[1][1]))
sprintf(buf, "%c%c.out", argv[1][0], argv[1][1]);
else
sprintf(buf, "%c.out", argv[1][0]);
printf("Opening %s\n", buf);
outFile = fopen(buf, "w");
}
fscanf(file, "%d%d%d", &numNodes, &bottomNode, &numEdges);
printf("%d nodes, %d edges\n", numNodes, numEdges);
nodes = new sNode [numNodes];
for (n = 0; n < numNodes; ++ n) {
nodes[n].numPaths = 0;
nodes[n].bVisited = false;
nodes[n].adjacent.clear();
}
for (n = 0; n < numEdges; ++ n) {
fscanf(file, "%d%d", &a, &b);
nodes[b].adjacent.push_back(a);
}
dfs(bottomNode);
if (topological.size() != numNodes) {
printf("ERROR: Not all nodes are reachable from the bottom\n");
return 0;
}
countPaths();
printResults();
system("PAUSE");
return 0;
}
void dfs(int current) {
int n;
queue<int> q;
vector<int> v;
if (nodes[current].bVisited)
return;
nodes[current].bVisited = true;
for (n = 0; n < nodes[current].adjacent.size(); ++ n)
dfs(nodes[current].adjacent[n]);
topological.push_back(current);
}
void countPaths() {
int n, i;
sNode * currentNode;
nodes[topological[numNodes - 1]].numPaths = 1;
for (n = numNodes - 1; n >= 0; -- n) {
currentNode = &nodes[topological[n]];
for (i = 0; i < currentNode->adjacent.size(); ++ i) {
if (INT_MAX - currentNode->numPaths < nodes[currentNode->adjacent[i]].numPaths)
printf("ERROR: OVERFLOW!\n");
nodes[currentNode->adjacent[i]].numPaths += currentNode->numPaths;
}
}
}
void printResults() {
int max, n;
max = nodes[0].numPaths;
for (n = 1; n < numNodes; ++ n)
if (nodes[n].numPaths > max)
max = nodes[n].numPaths;
printf("Node list: ");
for (n = 0; n < numNodes; ++ n) {
if (nodes[n].numPaths == max) {
printf(" (%d)", n);
if (outFile)
fprintf(outFile, "%d\n", n);
}
}
printf("\nPath count: %d\n", max);
if (outFile) {
fprintf(outFile, "%d\n", max);
fclose(outFile);
}
}
|
|
|
|
|
what do you exactly want us to do here?
you have pasted your whole code here
no description?
no comments of the code?
no proper indentation?
and that too incomplete code.
where exactly your problem is?
please put some write up before your code
and keep the code as simple as possible.
and before posting, read the post "How to get an answer to your question" by chris maunder above your post.
|
|
|
|
|
this guy is acting like a troll... but strangely, he is not, because it happened to him to answer to some questions we've been asking to him.
but anyway, this guy deserves once again to be flammed for this post
|
|
|
|
|
donot get discouraged.
just repost your query with some better clarity.
gud luck.
|
|
|
|
|
Do you want the short answer or the long answer?
"A good athlete is the result of a good and worthy opponent." - David Crow
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
|
|
|
|
|
after Waleed has asked his question, related to intellisense, i have got one more question on that topic.
iam using vc++ 6.0.
in my code editor,
say if i use a variable for example,
CString str;
and if i type "str" and then ".", the functions/members of the CString class are supposed to pop up.
but sometimes, this is working and sometimes not.
any ideas like, how and where to enable it if possible.
gud luck to Waleed for his post and hope for the solution.
-- modified at 9:07 Tuesday 9th October, 2007
|
|
|
|
|
You could try deleting the .ncb file (which is the intellisense database). This works for me most of the time .. good luck and thanks for your nice words...
Wal
http://www.waleedeissa.com
|
|
|
|
|
thanks waleed for your reply.
i shall implement your advice, the next time i face the same problem.
and by the way i attempted your post. kindly reply it.
|
|
|
|
|
Hello,
I'm using __declspec(property) to access get/set methods as properties (like in C# and VB.NET). Now, the problem is that both the property name and the get/set methods show in the intellisense list. Is there anyway to remove the names of the get/set methods from the intellisense list?
Here's an example, I have two methods, one is a get method with the name getText and another set method with the name setText, the name of the property is Text. I only want Text to show in the intellisense list, I don't want either getText or setText to show up in the list.
Thanks for any suggestions...
Wal
http://www.waleedeissa.com
|
|
|
|
|
did you face this problem in COMponent?
if so, then i have some more questions, before arriving to the solution.
see you tomorrow morning.
|
|
|
|
|
No, I'm just trying to use properties in a normal c++ class
Wal
http://www.waleedeissa.com
|
|
|
|
|
|
Hello all,
In a project I am currently working on, I would like to have some functions (like for example the logging) running as a server that can be addressed by all modules that may simultaneously be running. Does anyone have a link to articles or examples of how to build such server software and how to interact with it from the other modules?
Thanks in advance,
William
|
|
|
|
|
Maybe this[^]can help you a little?
Though I speak with the tongues of men and of angels, and have not money, I am become as a sounding brass, or a tinkling cymbal. George Orwell, "Keep the Aspidistra Flying", Opening words
|
|
|
|
|
hey there!
I have a problem dealing with this bitmap. using MFC, i must create a function that return the values of bitmap frequency vs. its pixel value when I load it in the window. This is somewhat like a histogram.
Can somebody share me some hints or ideas about this?
Thanks!
|
|
|
|
|
Would you care to explain a little more about what exactly you are trying to do? What is "bitmap frequency" and "pixel value", how do you intend to calculate these values and how are you going to represent your found data?
Waldermort
|
|
|
|
|
You loop over the pixel and make a map<int, int=""> with the color_number as key and the number of pixel with this color_number as value.
typedef std::map<int, int> HistoMapT;
HistoMapT theMap; For every color-number you encounter, you add one to the value under the key "color-number"
E.g. The first pixel has value 30:
You check if this number is already in the map. When it is, you increment its value. When its not, you insert it with a value of 1:
HistoMapT::iterator theIterator = theMap.find(color_number);
int value = 1;
if (theIterator != theMap.end() ) {
value += theIterator.second;
}
theMap.insert(MAKEPAIR(color_number, value));
You see, std::map is quite helpful here, providing you with elegant and easy to read code.
Though I speak with the tongues of men and of angels, and have not money, I am become as a sounding brass, or a tinkling cymbal. George Orwell, "Keep the Aspidistra Flying", Opening words{
|
|
|
|
|
jhwurmbach wrote: You see, std::map is quite helpful here, providing you with elegant and easy to read code.
maybe, but it will be very very slow, compared to:
int * histogram = new int[256 * 256 * 256];
memset(histogram, 0, 256 * 256 * 256 * sizeof(int));
for (int x=0;x< w;x++)
for (int y=0;y< h;y++)
{
histogram[(int)RGB(pixel.Red, pixel.Green, pixel.Blue)]++;
pixel++;
}
|
|
|
|
|
Chris Losinger wrote: maybe, but it will be very very slow
May or may not. That probably depends on the pattern of usage and the picture.
You are newing 28MB in one piece here.
AND you are still limited to 8-bit per color.
Though I speak with the tongues of men and of angels, and have not money, I am become as a sounding brass, or a tinkling cymbal. George Orwell, "Keep the Aspidistra Flying", Opening words
|
|
|
|
|
jhwurmbach wrote: May or may not.
you're calling how many functions per pixel?
vs. my single macro (which is a couple of bit shifts and logical ORs) and an array index.
jhwurmbach wrote: You are newing 28MB in one piece here
64MB. but that's really not a big deal. your map will potentially require many times more than that.
you're right that your map will require less memory (though more memory allocations) in cases where images have few colors.
jhwurmbach wrote: AND you are still limited to 8-bit per color.
true. it's an easy enough problem to fix. and your map will potentially suffer the same memory bloat.
-- modified at 10:34 Tuesday 9th October, 2007
ok... i'm bored, so i did some testing:
typedef std::map< int, int> HistoMapT ;
const int w = 1000;
const int h = 1000;
BYTE *p = = new BYTE[w * h * 3];
for (int x=0;x< w;x++)
{
for (int y=0;y< h;y++)
{
p[x * 3 + y * w * 3 + 0] = x % 256;
p[x * 3 + y * w * 3 + 1] = y % 256;
p[x * 3 + y * w * 3 + 2] = (x + y) % 256;
}
}
{
CTimer c("Map");
BYTE * pix = p;
HistoMapT theMap;
for (int x=0;x< w;x++)
{
for (int y=0;y< h;y++)
{
int color_number = RGB(pix[0], pix[1], pix[2]);
HistoMapT::iterator theIterator = theMap.find(color_number);
int value = 1;
if (theIterator != theMap.end() )
{
value += (*theIterator).second;
}
theMap.insert(std::pair< int, int>(color_number, value));
pix+=3;
}
}
}
{
CTimer c("C");
BYTE * pix = p;
int *histo = new int[256 * 256 * 256];
memset(histo, 0, 256 * 256 * 256 * 4);
for (int x=0;x< w;x++)
{
for (int y=0;y< h;y++)
{
histo[RGB(pix[0], pix[1], pix[2])]++;
pix+=3;
}
}
delete [] histo;
}
delete [] p;
here are the results:
// source image init'd to gradients
Map 2.01s
C 0.16s
// source image init'd to all zero
Map 0.30s
C 0.08s
// changing the source init to
p[x * 3 + y * w * 3 + 0] = x % 256;
p[x * 3 + y * w * 3 + 1] = y % 256;
p[x * 3 + y * w * 3 + 2] = x / 256;
Map 11.25s
C 0.08s
-- modified at 10:42 Tuesday 9th October, 2007
-- modified at 10:54 Tuesday 9th October, 2007
|
|
|
|
|
[memory block size]
Chris Losinger wrote: 64MB. [...]Your map will potentially require many times more than that.
Yes. Potentially. Very probably much less, by leaving out the unused color values.
But that sure depends on the picture you process.
[limit to 8bpp]
Chris Losinger wrote: true. it's an easy enough problem to fix.
Sure. At the expense of much more obligate alocated memory in one piece.
And no, the map will behave much more conservative, as the saved memory by not storing the unused pixel values will be more prominent.
But you are right in that the access is slower. This might or might not be an issue.
Though I speak with the tongues of men and of angels, and have not money, I am become as a sounding brass, or a tinkling cymbal. George Orwell, "Keep the Aspidistra Flying", Opening words
|
|
|
|
|
i ran the timing tests (see the update above). the C version absolutely kills the map version. more than 3x faster for solid 0s, two orders of magnitude faster for one of the gradients.
-- modified at 10:55 Tuesday 9th October, 2007
-- modified at 10:58 Tuesday 9th October, 2007
|
|
|
|
|
Chris Losinger wrote: i ran the timing tests
Me too.
From your test-code I got 56msec vs. 85 msec for the map. Thats factor 1.5
I'm still unimpressed.
Though I speak with the tongues of men and of angels, and have not money, I am become as a sounding brass, or a tinkling cymbal. George Orwell, "Keep the Aspidistra Flying", Opening words
|
|
|
|
|
jhwurmbach wrote: From your test-code I got 56msec vs. 85 msec for the map.
debug or release ?
jhwurmbach wrote: Thats factor 1.5
I'm still unimpressed.
if only my customers were so ambivalent about performance!
|
|
|
|
|
Chris Losinger wrote: debug or release
VC++ 7.1. Release mode.
There is so much security built in in Debug, that there is no point comparing with raw C.
Chris Losinger wrote: if only my customers were so ambivalent about performance!
They are for me. At least for the sub-second delays we are talking about here.
I have added the stdext::hash_map and now I get
map: 57 msec
hash_map: 24 msec
C-Array: 85 msec
Here is my code:
#include "stdafx.h"
#include "Windows.h"
#include "MMSystem.h"
#pragma comment( lib, "winmm")
#include <tchar.h>
#include <iostream>
#include <map>
#include <hash_map>
#undef max
#undef min
static const int TARGET_RESOLUTION = 1;
int _tmain(int argc, _TCHAR* argv[])
{
typedef std::map<int, int> HistoMapT ;
typedef stdext::hash_map< int, int> HashHistoMapT;
typedef std::pair<int, int> Int_PairT;
const int w = 1000;
const int h = 1000;
TIMECAPS tc = {0};
UINT wTimerRes = 5;
if( ::timeGetDevCaps( &tc, sizeof(TIMECAPS)) != TIMERR_NOERROR)
{
std::cout << "Timer Error";
return system("pause");
}
wTimerRes = std::min( std::max( tc.wPeriodMin, (UINT)TARGET_RESOLUTION), tc.wPeriodMax);
::timeBeginPeriod( wTimerRes);
BYTE *p = new BYTE[w * h * 3];
for (int x=0; x< w;x++)
{
for (int y=0;y< h;y++)
{
p[x * 3 + y * w * 3 + 0] = w % 256;
p[x * 3 + y * w * 3 + 1] = h % 256;
p[x * 3 + y * w * 3 + 2] = (w + h) % 256;
}
}
const UINT before1 = ::timeGetTime();
{
BYTE * pix = p;
HistoMapT theMap;
for (int x=0;x< w;x++)
{
for (int y=0;y< h;y++)
{
const int color_number = RGB(pix[0], pix[1], pix[2]);
HistoMapT::iterator theIterator = theMap.find(color_number);
int value = 1;
if (theIterator != theMap.end() )
{
value += (*theIterator).second;
}
theMap.insert(Int_PairT(color_number, value));
pix+=3;
}
}
}
const UINT after1 = ::timeGetTime();
const UINT before2 = ::timeGetTime();
{
BYTE * pix = p;
HashHistoMapT theMap;
for (int x=0;x< w;x++)
{
for (int y=0;y< h;y++)
{
const int color_number = RGB(pix[0], pix[1], pix[2]);
HashHistoMapT::iterator theIterator = theMap.find(color_number);
int value = 1;
if (theIterator != theMap.end() )
{
value += (*theIterator).second;
}
theMap.insert(Int_PairT(color_number, value));
pix+=3;
}
}
}
const UINT after2 = ::timeGetTime();
const UINT before3 = ::timeGetTime();
{
BYTE * pix = p;
int *histo = new int[256 * 256 * 256];
memset(histo, 0, 256 * 256 * 256 * sizeof(histo[0]));
for (int x=0;x< w;x++)
{
for (int y=0;y< h;y++)
{
histo[RGB(pix[0], pix[1], pix[2])]++;
pix+=3;
}
}
delete [] histo;
}
const UINT after3 = ::timeGetTime();
delete [] p;
::timeEndPeriod( wTimerRes);
std::cout << "Elapsed timing map: " << (after1 - before1) << " msec." << std::endl;
std::cout << "Elapsed timing hash_map: " << (after2 - before2) << " msec." << std::endl;
std::cout << "Elapsed timing C-Code: " << (after3 - before3) << " msec." << std::endl;
return system("pause");
}
Though I speak with the tongues of men and of angels, and have not money, I am become as a sounding brass, or a tinkling cymbal. George Orwell, "Keep the Aspidistra Flying", Opening words
|
|
|
|
|