Solved

Covering all edges in graph

Posted on 1998-12-21
15
263 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
  • 5
  • 4
  • 4
  • +1
15 Comments
 
LVL 27

Expert Comment

by:BigRat
Comment Utility
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
Comment Utility
You can choose any data structure. Actually I need the algorithm.
0
 
LVL 27

Expert Comment

by:BigRat
Comment Utility
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
 
LVL 4

Expert Comment

by:jack_p50
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

 
LVL 27

Expert Comment

by:BigRat
Comment Utility
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
Comment Utility
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
Comment Utility
Thanks guys for helping me, but I've already solved that problem.
0
 
LVL 13

Expert Comment

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

Accepted Solution

by:
jack_p50 earned 200 total points
Comment Utility
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
Comment Utility
That's OK.
0
 
LVL 13

Expert Comment

by:Mirkwood
Comment Utility
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
Comment Utility
An extremely nasty weasle! Linda should have it destroyed and NOT humanely
0

Featured Post

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Threads Delphi Programs 2 1,601
How to unescape(decode) an encoded string? 5 1,339
Rave Reports - Adding a Data Band 1 994
Delphi XE 5 - windows 3 855
This article will show you how to create an ISO CD-ROM/DVD-ROM image (*.iso), and MD5 checksum signature, for use with VMware vSphere Hypervisor 6.5 (ESXi 6.5). It's a good idea to compare checksums, because many installations fail because of a corr…
This article explains how to prepare an HTML email signature template file containing dynamic placeholders for users' Azure AD data. Furthermore, it explains how to use this file to remotely set up a department-wide email signature policy in Office …
This video discusses moving either the default database or any database to a new volume.
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…

743 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now