C / C++ / MFC

3-May-12 23:53

I have a array of

C++

std::pair<string, string>

, i.e.

C++

X → Y
A → B
C → D
B → C
T → X 
Y → T

We can see that A → B → C →D (D is the final target) and X → Y → T → X (X is the final target) in the arry, what I want to do is change the arry to this:

C++

X → X (X is the final target in circuit)
A → D (D is the final target)
C → D (D is the final target)
B → D (D is the final target)
T → X (X is the final target in circuit)
Y → X (X is the final target in circuit)

I'm confused about how to implement this algorithm.

Any help would be greatly appreciated!

Maximilien4-May-12 2:38

Maximilien

4-May-12 2:38

how is the first array of pair created ? manually ?

What is the relationship between the first array and what you want to achieve? is there a logical progression between the two?

Ok, I've seen what you have.

will think about it

Watched code never compiles.

modified 4-May-12 9:36am.

«_Superman_»4-May-12 3:15

«_Superman_»

4-May-12 3:15

It could be something as shown below -

bool GetSecond(const string& first, string& second)
{
    for (int i = 0; i < ARR_SIZE; ++i)
    {
        if (first == arr[i].first)
        {
            second = arr[i].second;
            return true;
        }
    }

    return false;
}

void GetDest(const string& src, string& dest)
{
    string src2 = src;

    while (GetSecond(src2, dest))
    {
        if (src == dest)
            break;

        src2 = dest;
    }
}

For each element in the pair call GetDest with first as the first parameter and second as the second parameter.
You may need to add other conditions to satisfy your algorithm.

«_Superman_»
I love work. It gives me something to do between weekends.

Microsoft MVP (Visual C++)

Polymorphism in C

Falconapollo5-May-12 20:12

5-May-12 20:12

Thank you for your reply.

Your algorithm is great!

I made some modifications, so that it's perfect now!

C++

typedef vector<pair<char, char> > _OWN_TYPE;
_OWN_TYPE vecKey2Name;
bool GetSecond(const char& first, char& second)
{
	for (int i = 0; i < vecKey2Name.size(); ++i)
	{
		if(vecKey2Name[i].first == vecKey2Name[i].second)
			continue;
		if (first == (vecKey2Name[i].first))
		{
			second = vecKey2Name[i].second;
			return true;
		}
	}

	return false;
}

void GetDest(const char& src, char& dest)
{
	char src2 = src;

	while (GetSecond(src2, dest))
	{
		if (src == (dest))
			break;

		src2 = dest;
	}
}

int main()
{
	vecKey2Name.push_back(make_pair('X', 'Y'));
	vecKey2Name.push_back(make_pair('A', 'B'));
	vecKey2Name.push_back(make_pair('C', 'D'));
	vecKey2Name.push_back(make_pair('B', 'C'));
	vecKey2Name.push_back(make_pair('T', 'X'));
	vecKey2Name.push_back(make_pair('Y', 'T'));

	for(_OWN_TYPE::iterator itr = vecKey2Name.begin(); itr != vecKey2Name.end(); ++itr)
		cout << (itr->first) << " --> " << (itr->second) << endl;

	for(_OWN_TYPE::iterator itr = vecKey2Name.begin(); itr != vecKey2Name.end(); ++itr)
		GetDest(itr->first, itr->second);

	cout << "=============================================================" << endl;
	for(_OWN_TYPE::iterator itr = vecKey2Name.begin(); itr != vecKey2Name.end(); ++itr)
		cout << itr->first << " --> " << itr->second << endl;
}

modified 6-May-12 6:25am.

Albert Holguin4-May-12 10:12

Albert Holguin

4-May-12 10:12

Why not have a simple look-up table? Specially if the number of cases is this small...

Falconapollo5-May-12 20:29

5-May-12 20:29

Can you explain a little deeper?

The size of the arry is under 5000 in most case.

CPallini4-May-12 10:47

CPallini

4-May-12 10:47

In my opinion

Falconapollo wrote:
T → X (X is the final target in circuit)
Y → X (X is the final target in circuit)

Should be instead

C++

T → Y
Y → Y

Am I missing something?

Veni, vidi, vici.

Falconapollo5-May-12 20:37

5-May-12 20:37

Yes. You miss something,

C++

X → Y
A → B
C → D
B → C
T → X 
Y → T

includes

C++

X → Y
Y → T
T → X

so, it shoule be:

C++

X → X
Y → X
T → X

CPallini6-May-12 22:42

CPallini

6-May-12 22:42

C++

1) X → Y
2) A → B
3) C → D
4) B → C
5) T → X 
6) Y → T

Let's start from Y:
from rule (6) Y → T we reach T, then
from rule (5) T → X we reach X.
Now, I ask to you: Why we should stop here?
Why cannot we use rule (1) X → Y to reach again X and then stop (because there are no suitable rules but the consumed ones)?

Veni, vidi, vici.

Falconapollo8-May-12 19:30

8-May-12 19:30

I'm sorry for my late reply!

You are right, I made a mistake.

When X->Y Y->T T->X, it makes a cyclic reference. So, each element in the circel CAN be the terminate element.

I'm sorry for my mistake!

Philippe Mori5-May-12 1:55

Philippe Mori

5-May-12 1:55

There are multiple possibilities. How do you select which one to use? Does the final targets are known beforehand. If not, how do you decide which one to use?

In your case, we can see that D is a final target because D is never on the left side of the pair. But for the other sequence, one could start with Y and end with Y (since it is a loop).

If the target are knows, then you would be able to build the result by search which item lead to the target and then repeat using the source as the new target (and the final target would be the original target).

Philippe Mori

Falconapollo5-May-12 20:41

5-May-12 20:41

If the target are knows, then you would be able to build the result by search which item lead to the target and then repeat using the source as the new target (and the final target would be the original target).

Yes, you are right.
Then, how to implent your idea into algorithm in C++?

SOLVED Project cannot be build. Two cpp files configured to produce pch error.

Philippe Mori6-May-12 2:12

Philippe Mori

6-May-12 2:12

- For each possible target, find immediate source. Add them (each pair) to a result list.
- For each immediate source not equal to the original target, find its own source. Add each pair to the result list.
- Recursively repeat the second step until you don't find any source distinct from the initial target.

You can remove recursivity if you like if you keep track of which pair were processed.

By the way, I assume that none of the source have multiples (immediate) targets.

Philippe Mori

Vaclav_3-May-12 4:45

Re: Project cannot be build. Two cpp files configured to produce pch error.

3-May-12 4:45

I have no clue how this happened and how to fix it.
I am getting this error message from the compiler ( VC6.)

<b>“The source files ...cpp and ..cpp are ...both configured to produce ...pch
Project cannot be build.”</b>

I started getting this error on a file I really did not put into my project, so I deleted it.

Than this error “moved” onto a real file and I would like to fix it.

I would be most grateful if some VC 6.0 expert helps me to understand this and/ or how to fix it.

Thanks
Vaclav

-- modified 3-May-12 15:04pm.

Richard MacCutchan3-May-12 6:47

Richard MacCutchan

3-May-12 6:47

Check the properties on your source files to ensure that only one is configure to create the PCH information.

Binding 100,000 items to a list box can be just silly regardless of what pattern you are following. Jeremy Likness

Re: Project cannot be build. Two cpp files configured to produce pch error.

Vaclav_3-May-12 8:02

Re: Project cannot be build. Two cpp files configured to produce pch error.

3-May-12 8:02

Richard,
that is exactly what the error message is saying.
I got that far.
I would not be asking here if I knew how and where to check that.

Vaclav

Richard MacCutchan3-May-12 8:10

Richard MacCutchan

3-May-12 8:10

Right click on each files and select Properties.

Binding 100,000 items to a list box can be just silly regardless of what pattern you are following. Jeremy Likness

Re: Project cannot be build. Two cpp files configured to produce pch error.

Vaclav_3-May-12 8:36

Re: Project cannot be build. Two cpp files configured to produce pch error.

3-May-12 8:36

OK,
we are getting somewhere.
Indeed the ..pch file is in Properties of the offending source.
Now, how to get rid of it.
I suppose deleting it ( from the debug directory) won't work since it is obviously being generated by ...??

Vaclav_3-May-12 8:58