pavlovsky
asked on
Covering all edges in graph
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.
May I ask if you already have a data structure which represents the graph? Or can I choose the data structure? I mean, I would then have procedures like DefineNode and ConnectNodes or similar. The decision of the representation depends on the usage. I would choose a different implementation if enumeration was the most important thing.
ASKER
You can choose any data structure. Actually I need the algorithm.
The usual representation is an adjaceny list. You keep a list or an array of nodes. Each node has a list whose elements are chained records. The only important field, other then the next pointer, is a pointer to the node (or node number if you use an array).
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?
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?
Pavlovsky means not visiting all nodes but all !edges! in oriented graph
(BTW there may be cycles in graph so you CAN visit some nodes and
edges more than once).
(BTW there may be cycles in graph so you CAN visit some nodes and
edges more than once).
I actually added a futher comment in here this afternoon. Now ITS GONE!!!!
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?
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?
Here is some pseudocode for an algorithm to find a path from A to B covering all nodes
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
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
ASKER
You should cover not all nodes but all EDGES!
And there can be cycles, multiple edges( A->B,A->B) and cycles(A->A) in graph.
And there can be cycles, multiple edges( A->B,A->B) and cycles(A->A) in graph.
Since the adjaceny lists contain one record which represents a path from node A to B (even to itself) it is quite simple to modify the3 depth first algorithm to remember the entry (its just a pointer). The "visted" code in my example comes out and we now look at the "edge list" to see if an entry has been made :-
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?
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?
What you want is to see if there is a hamilton path from A to B.
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.
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.
ASKER
Thanks guys for helping me, but I've already solved that problem.
Let me see, how does that make my answer wrong????
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
That's OK.
Hmmm, this smells like fraud.
Does 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.
Does 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.
An extremely nasty weasle! Linda should have it destroyed and NOT humanely