# S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
 It is currently Thu, 20 Jun 2013 13:23:38 UTC

 All times are UTC [ DST ]

 Page 1 of 1 [ 5 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: A code to find a pathPosted: Wed, 18 Jan 2012 22:00:21 UTC
 Senior Member

Joined: Tue, 7 Aug 2007 11:37:58 UTC
Posts: 121
Hi everyone

Assume we have some points so that each point can call the other.
take for instance, five points: a, b, c, d, and e; they communicate each other as follows:
a calls b
b calls c
c replies i.e., to b
b replies i.e., to a
a calls d
d calls c
c replies i.e., to d
d calls e
e replies i.e., to d
d replies i.e, to a

I need to find the path in order way like this:
a, b, c, b, a, d, c, e, d, a

I used a software tool to do this but it generated a path similar to what I want ..like this:
a, b, c, -, -, d, c, -, e, -, -

where - is the caller point i.e it generates the uiques points' names

Now I took such result and store it in an array or list but I failed to replace dashes with the suiatble point

Can anyone help me to replace these dashes

The tool which I used names Altova UModel

Many thanks for any suggestion

Top

 Post subject: Re: A code to find a pathPosted: Thu, 19 Jan 2012 10:45:08 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6071
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
Hi everyone

Assume we have some points so that each point can call the other.
take for instance, five points: a, b, c, d, and e; they communicate each other as follows:
a calls b
b calls c
c replies i.e., to b
b replies i.e., to a
a calls d
d calls c
c replies i.e., to d
d calls e
e replies i.e., to d
d replies i.e, to a

I need to find the path in order way like this:
a, b, c, b, a, d, c, e, d, a

I used a software tool to do this but it generated a path similar to what I want ..like this:
a, b, c, -, -, d, c, -, e, -, -

where - is the caller point i.e it generates the uiques points' names

Now I took such result and store it in an array or list but I failed to replace dashes with the suiatble point

Can anyone help me to replace these dashes

The tool which I used names Altova UModel

Many thanks for any suggestion

Use a stack. Convert a,b,... into "push (whatever)", and - as "pop".

_________________

Top

 Post subject: Re: A code to find a pathPosted: Thu, 19 Jan 2012 11:27:28 UTC
 Senior Member

Joined: Tue, 7 Aug 2007 11:37:58 UTC
Posts: 121
Stack is Ok if the path is straightline one by one
i.e., the next point depends on the previuos one
but in the mentiond example , the matter is different

a calls b
b calls c
c replies i.e., to b
b replies i.e., to a
a calls d
d calls c
c replies i.e., to d
d calls e
e replies i.e., to d
d replies i.e, to a
a calls f
f replies i.e., to a

a, b, c, -, -, d, c, -, e, -, -,f,-

Stack tracing: (n dashes requires n+1 pops s.t. the first pop is discarded)
operation stack cont.
---------- --------------------
push(a) a
push(b) a,b
push(c) a,b,c
pop a
pop <empty>
push(d) d
push(c) d,c
pop <empty>
push(e) e
pop <empty>
pop <empty>
push(f) f
pop <empty>

If we print out the result of each operation to the screen
a,b,c,b,a,d,c,d,e,f

the right path is: a,b,c,b,a,d,c,d,e,d,a,f,a

What do you think?

Top

 Post subject: Re: A code to find a pathPosted: Thu, 19 Jan 2012 12:54:43 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6071
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
Stack is Ok if the path is straightline one by one
i.e., the next point depends on the previuos one
but in the mentiond example , the matter is different

a calls b
b calls c
c replies i.e., to b
b replies i.e., to a
a calls d
d calls c
c replies i.e., to d
d calls e
e replies i.e., to d
d replies i.e, to a
a calls f
f replies i.e., to a

a, b, c, -, -, d, c, -, e, -, -,f,-

Stack tracing: (n dashes requires n+1 pops s.t. the first pop is discarded)
operation stack cont.
---------- --------------------
push(a) a
push(b) a,b
push(c) a,b,c
pop a
pop <empty>
push(d) d
push(c) d,c
pop <empty>
push(e) e
pop <empty>
pop <empty>
push(f) f
pop <empty>

If we print out the result of each operation to the screen
a,b,c,b,a,d,c,d,e,f

the right path is: a,b,c,b,a,d,c,d,e,d,a,f,a

What do you think?

You want a temporary variable ("at") too. So when you get a,b,c,... you first push whatever on "at" to the stack, and let your "at" holds the new point name. When you encounter a "-" you pop to "at".

So taking your example "a, b, c, -, -, d, c, -, e, -, -, f, -", it looks like
Code:
path        stack           at
------   ------------   ----------
a          (empty)          a
b             a             b
c            a,b            c
-             a             b
-          (empty)          a
d             a             d
c            a,d            c
-             a             d
e            a,d            e
-             a             d
-          (empty)          a
f             a             f
-          (empty)          a

_________________

Top

 Post subject: Re: A code to find a pathPosted: Thu, 19 Jan 2012 20:36:55 UTC
 Senior Member

Joined: Tue, 7 Aug 2007 11:37:58 UTC
Posts: 121
I solved it without Stack and "at"

i.e., save memory.. right?
changing is done on the same list
I differentiate between original elements in the array and non-original elements
where the original one is that appears on the original path while the non-original elements are those replaced with "-"s

We cab do such differentiation with appending a flag to the replaced elements

so the code will look like this

for i=1 to n
if A(i) is "-" then
tmp = A(i-1)
for j= i-1 down to 1
if A(j) is original and equlas tmp then
replace A(i) with A(j-1)
exit loop
end if
end for
end if
end for

I tested it with, it works well

However, I feel the code of "outermeasure" i.e., using Stack and "at" temp List is more safe..

What do you think?

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 5 posts ]

 All times are UTC [ DST ]

#### Who is online

Users browsing this forum: No registered users

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ High School and College Mathematics    Algebra    Geometry and Trigonometry    Calculus    Matrix Algebra    Differential Equations    Probability and Statistics    Proposed Problems Applications    Physics, Chemistry, Engineering, etc.    Computer Science    Math for Business and Economics Advanced Mathematics    Foundations    Algebra and Number Theory    Analysis and Topology    Applied Mathematics    Other Topics in Advanced Mathematics Other Topics    Administrator Announcements    Comments and Suggestions for S.O.S. Math    Posting Math Formulas with LaTeX    Miscellaneous