Solved

Covering all edges in graph

Posted on 1998-12-21
15
268 Views
Last Modified: 2010-04-16
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.
0
Comment
Question by:pavlovsky
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 4
  • 4
  • +1
15 Comments
 
LVL 27

Expert Comment

by:BigRat
ID: 1216656
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.
0
 

Author Comment

by:pavlovsky
ID: 1216657
You can choose any data structure. Actually I need the algorithm.
0
 
LVL 27

Expert Comment

by:BigRat
ID: 1216658
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?
   
0
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 4

Expert Comment

by:jack_p50
ID: 1216659
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).
0
 
LVL 27

Expert Comment

by:BigRat
ID: 1216660
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?
0
 
LVL 13

Expert Comment

by:Mirkwood
ID: 1216661
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


 
0
 

Author Comment

by:pavlovsky
ID: 1216662
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.
0
 
LVL 27

Expert Comment

by:BigRat
ID: 1216663
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?
0
 
LVL 13

Expert Comment

by:Mirkwood
ID: 1216664
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.
 

0
 

Author Comment

by:pavlovsky
ID: 1216665
Thanks guys for helping me, but I've already solved that problem.
0
 
LVL 13

Expert Comment

by:Mirkwood
ID: 1216666
Let me see, how does that make my answer wrong????
0
 
LVL 4

Accepted Solution

by:
jack_p50 earned 200 total points
ID: 1216667
I've sent you LISP-code. Of course, I hate LISP, but I found only LISP example, so see for some compiler
0
 

Author Comment

by:pavlovsky
ID: 1216668
That's OK.
0
 
LVL 13

Expert Comment

by:Mirkwood
ID: 1216669
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.
0
 
LVL 27

Expert Comment

by:BigRat
ID: 1216670
An extremely nasty weasle! Linda should have it destroyed and NOT humanely
0

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

I was prompted to write this article after the recent World-Wide Ransomware outbreak. For years now, System Administrators around the world have used the excuse of "Waiting a Bit" before applying Security Patch Updates. This type of reasoning to me …
Unified and professional email signatures help maintain a consistent company brand image to the outside world. This article shows how to create an email signature in Exchange Server 2010 using a transport rule and how to overcome native limitations …
In an interesting question (https://www.experts-exchange.com/questions/29008360/) here at Experts Exchange, a member asked how to split a single image into multiple images. The primary usage for this is to place many photographs on a flatbed scanner…

734 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question