The MCTS: Microsoft Exchange Server 2010 certification validates your skills in supporting the maintenance and administration of the Exchange servers in an enterprise environment. Learn everything you need to know with this course.

I'm experiencing a serious problem. I would appreciate

your help.

The task is to cover all edges in oriented graph, starting

from selected node A and ending in selected node B.

your help.

The task is to cover all edges in oriented graph, starting

from selected node A and ending in selected node B.

Experts Exchange Solution brought to you by ConnectWise

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

My next question starts is as follows. There are basically two graph search algorithms, breath-first and depth-first. These visit each node only once. The depth-first is the easiest, you keep a visitor marker with each node and don't search further if you have visited the node. Else you process the adjaceny list for the node recursively. If you remember in a global array the place you are at on each recursion you then have a path to the node. Clearly when you arrive at your destination node, path gives you the edge list and you can do what you want. So :-

dfs(v) :

is-end-node(v) -> do what you want; Exit

is-visited(v) -> Exit;

ELSE

mark v as visited

add v to path

FOR EACH x IN adjaceny list of v DO dfs(x);

remove v from path;

Exit;

OK? or do you want something different?

(BTW there may be cycles in graph so you CAN visit some nodes and

edges more than once).

My comment was: In your graph have you got multiple edges eg: A->B A->B and/or have you got node cycles eg: A->A?

var visited

var visits

function GetPath1 (graph, A, B, Solution)

Var curpath

GetPath graph, a, b, curpath, solution

end function

function GetPath1 (graph, A, B, curPath, Solution)

GetPath1 = false

visited(A) = true

inc(visits)

curpath[visits] = A {Administration}

if (A = B) and (visits = nrofnodes) then {test for solution}

solution = curpath {copy solution}

GetPath1 = true

else

for each node in Graph

if (not visited (node)) then

found = GetPath (graph, A, B, Path, solution)

if found then break; {ready}

end if

next

end if

dec(visits)

visited(A) = false {Administration}

end function

And there can be cycles, multiple edges( A->B,A->B) and cycles(A->A) in graph.

FOR EACH e IN adjacenylist(v) DO /* look at the entry */

IF NOT is-in-set(e,EdgeSet) THEN

BEGIN

addtoset(EdgeSet,e);

dfs(n OF e);

removefromset(EdgeSet,e);

END;

This will ensure that we look at each edge only once in any path from A to B.

However may I ask why you need this (unusual) variation to the algorithm?

See http://home.wxs.nl/~faase009/counting.html

See also http://pascal.seg.kobe-u.ac.jp/~banbara/llpj/Knight.html

or http://csr.uvic.ca/~wendym/courses/320/98summer/1.98.html

for source code examples.

Experts Exchange Solution brought to you by ConnectWise

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialDoes the P in jack_p stand for Pavlovsky?

Yes IT DOES!!!!

See http://www.geocities.com/TimesSquare/2795/geobook.html

Well two accounts less at EE.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by ConnectWise

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.