a little challange.

[bugmenot]

http://en.wikipedia.org/wiki/Social-cir ... work_model

This looks similar to your model.

What warning level is your compiler set to?

[avansc]

http://en.wikipedia.org/wiki/Social-cir ... work_model

This looks similar to your model.

What warning level is your compiler set to?

interesting find. looks similar, havent checked it over completely.

my compiler is set to "/W3"

anyways, just wanted to say that even though we have different views on some things i enjoy discussing things with you, always feel like i learn something.


ps: i assume you are from the UK, so you like rugby or cricket?

[bugmenot]

I am not really a sports spectator person but I do find cricket extremely boring.

Back on your code, a co-worker pointed out interestingly that it can be extended to run as parallel processes which is a huge advantage as you have multiple sentinels/messages going through the network.

[avansc]

I am not really a sports spectator person but I do find cricket extremely boring.

Back on your code, a co-worker pointed out interestingly that it can be extended to run as parallel processes which is a huge advantage as you have multiple sentinels/messages going through the network.

yeah, the idea is that each node does its part. but i dont think im going to venture down the multithreaded line. hehe.
but yeah, it could be sped up quite significantly. especially when the network get large.

i wander if a system like this could be implemented that has nodes carrier a weigh value. and then see if there are connections between people.
im just thinking that if they had a huge database of lets say criminals and they wanted to get to person X and they had informants {A,B,C} what is the best way to infiltrate/get to person X. by known associates and so on. im sure they have systems like that that are probably a lot more complex..


EDIT: it kinda reminds me of university when we had to write a maze program and have a robot solve the maze. most people use a right or left hand robot. i made a multi threaded one which would fork off each time there was at an intersection.

[avansc]

i also just realized that this can be converted into a shortest path algorithm.

if each node has an X,Y component and the distance gets added to each message, you can always find the shortest path from point A to B.

[MarauderIIC]

So I mentioned iterative deepening, and here's me it coding straight into the forum. I'm assuming this solution is more naive than the pros here, but...

Iterative deepening depth-first search (IDDFS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state.

Checks all children of depth 0, then all children of depth 1, then all of ... etc. Increase in runtime is small. In fact,

The space complexity of IDDFS is O(bd), where b is the branching factor and d is the depth. Since iterative deepening visits states multiple times, it may seem wasteful, but it turns out to be not so costly, since in a tree most of the nodes are in the bottom level, so it does not matter much if the upper levels are visited multiple times

The time complexity of IDDFS in well-balanced trees works out to be the same as Depth-first search: O(b^d).

Code: Select all

Node* FindNodeStart(Node* root, Node* target /* or string targetname, whatever */) {
    unsigned int maxDepth = 0;
    Node* retval;
    do {
        retval = FindNode(root, target, 0, maxDepth);
        maxDepth++;
    } while (retval != target && retval != NULL);
    if (retval != NULL)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return retval;
}

//Return self on fail with children, return NULL on total failure (fail, no children), return target on success
//at least, that's what it's supposed to be. no testing, no ide
Node* FindNode(Node* root, Node* target, int depth, int maxDepth) {
    if (root == target) {
        cout << "Found target." << endl;
        return root;
    }
    if (depth == maxDepth) {
        if (root.children.length == 0)
            return NULL;
        else
            return root;
    }
    Node* retval;
    foreach (child in root.children) { //please pardon the shorthand for vector iterator and increment
        retval = FindNode(child, depth+1, maxDepth);

        if (retval == target) {
            cout << "Parent: " << root->getName() << endl;
            return retval;
        }
    }
    return NULL;
}

My AI class was good for search techniques.

[avansc]

now thats traversal

[MarauderIIC]

Yessir
Needs a 'visited' vector to stop infinite loops, but shouldn't be any problem at all, so I'll leave it as an exercise for the reader