🚀 go-pugleaf

In my previous mail, I ask for the helps for the following problem.
>
>I got a large directed graph capturing strict partial order relations `<'
>in which a directed edge from a node s to a node t means s < t.  The
>partial order relation is transitive;
>i.e.
>       s < t and t < u implies s < u
>.
>
>I would like to know if there are any fast algorithms and their
>complexities for the following 2 questions.
>
>Q1. Is the graph acyclic (i.e. absence of loops)?  How to trace out the
>    nodes in loops?
>
>Q2. How to tell the relation between two given nodes (say s and t) in
>    the graph (assume acyclic) whether they are related by
>    a) s < t
>or  b) t < s
>or  c) unknown - neither ( s < t ) nor ( t < s )
>
>Any pointers would be appreciated.  Reply by email is preferred as
>the access to the News is not very reliable.
>
>Thank you.
>
>S.C. Cheung (scc@doc.ic.ac.uk)
I have received a number of replies and many requests to know what I
have received.  So I think it might be useful to post the replies I got
to the Newsgroup.

First of all, I need to express my thanks to those give me valuable
suggestions.  Secondly, I need to apologise the confusion that the
questions caused.  As far as I can tell from the replies, many readers
of the group come from a mathematical background, I hope the following
descriptions would be useful to understand the applications to concurrency
analysis.  Please feel free to correct me if I have missed out something.
Readers not interested may skip the following section.

-------------  APPLICATION TO CONCURRENCY ANALYSIS --------------
Partial ordering is an important issue in the concurrency analysis in
distributed/parallel systems.  The partial order graph is a merge of the
subgraphs based on local knowledge of each process.  Subgraphs are
merged by interactions (either synchronous or asynchronous) between the
processes.  Assume synchronous interactions.  Each node in the subgraph
represents a event exhibited by a process.  There would be a partial
order among two event nodes on two different subgraph if these two
events interacts (e.g. a event sends a message to another event.)
Detailed descripton can be found from a paper by Leslie Lamport on CACM
July 1978 titled "Time,. Clocks and the Ordering of Events in a
Distributed System."

An example of the graph may be (event e sends a message to event b):

  a ----> b ----> c
          ^
          |
  d ----> e ----> f

Therefore, we need to see if the merged graph obey the strict partial
order relation globally; and if given two events, tell which would occur
before another or they can happen concurrently.

The problem is more complicated if taken the nondeterminism into
account.  For example, if the choice primitive `|' is considered.

P ::= i ( a | b ) c

The causal analysis would be more complicated because we don't know
exactly which event (a or b) would be caused by event i.

The other nondeterminism is introduced by multiple sents to a single
receipt, say an event can interact with a choice of more than one
events.

Could somebody clarifies this because I find difficulties in expressing
the problem of non-determinism clearly in a few sentences.

The concurrency analysis with nondeterminism is still NP-hard as far as
I know and this poses a big problem to apply the analysis to a real life
distributed systems.  But the analysis is very crucial for the
correctness of distributed systems.  I hope my mail will cause some
discussions in the newsgroup drawing the expertise from mathematicians to
look at the problem if it is of sufficient interests.  To be honest, I
am still very new to the problem and I may be very weak in defining the
problem clearly.
---------------- END of APPLICATION TO CONCURRENCY ANALYSIS -------------

Thanks to:
Badri Ramamurb
Oleg Sokolsky
Raul Deluth Miller
Adam L. Buchsbaum
Bob Riemenschneider
Dicky Yan
Peter Montgomery
Scott Hazelhurst
edward@minster.york.ac.uk
Mike Berman
James E. Burns
Dinesh Bhatia
Sarmad Abbasi
Daljeet Sahni
Thomas A. Anastasio
Seth Breidbart
Philip Fong

---------------- RELIES I GOT ----------------
NOTE: Name of authors are separated from their replies.

Dear Shing Chi Cheung,
	This is with reference to your posting on comp.theory.

Q1. If you are looking to detect loops of the form:
	a < b < c < d .... < a  (which your graph shouldn't have
				  because it is a PO)
	then just use a simple depth first search  ( keeping track
	of vertices visited in order to handle forests etc ).
	This is just the standard way to detect if a graph is a DAG.

     If you consider  a < b < c   , a < d < c   a "loop",
	then you can detect such loops by first undirecting it
	and then  doing a depth first search.. (again keeping track of.. )

	Thus it takes O(e) time where  e  is # edges in the graph.

Q2. I think to answer this question you may have to do a dfs from
	s  and and see if  t is reached, similarly do a dfs from
	t and see if s is reached. depending on the result of these
	searches you can conclude the order. Again this takes O(e).

	Hope this helps. Do let me know, or just post on the net
	if you get better solutions.

------------------

My solutions are quite naive, but obvious:

Q1: do a depth-first search on the graph, looking for so-called
    'back' edges - they signal the presence of loops. I guess they
    will also help in tracing the nodes lying on cycles. Depth-first
    search is described in any book on analysis of algorithms, e.g.
    Leizerson, Cormen and Rivest, "Introduction to Algorithms" (sorry,
    reference by memory). It runs in O(E+V), E - number of edges, V -
    number of vertices.

Q2: do a depth-first (or a breadth-first, it can be faster), starting
    from s, until you reach t. It will give you a list of reachable
    states (you don't really have to go all the way); if you find t
    then s<t, if not - try again starting from t. Again, complexity
    is the same.


Easy, but probably not at all optimal - just a quick quess.

-------------------

   Q1. Is the graph acyclic (i.e. absence of loops)?  How to trace out the
       nodes in loops?

If your graph is represented as a square bitmap [1 indicates an edge
from the vertex denoted by the row to the vertex denoted by the
column], and transitive closure has been completed, then if any 1s
appear in the graph scalar anded with its transpose, there is a cycle.

   Q2. How to tell the relation between two given nodes (say s and t) in
       the graph (assume acyclic) whether they are related by
       a) s < t
   or  b) t < s
   or  c) unknown - neither ( s < t ) nor ( t < s )

Again, if you've completed the transitive closure, this information is
directly available.

---------------------

The graph must be acyclic, otherwise you would violate transitivity.

Computing the p.o. relation from the graph is as hard as computing
transitive closure.

-------------------

I looked at this question recently and didn't find anything better than
a rather naive O(n^2) algorithm, though I got a vague impression that
people looking at order-sorted unification algorithms may have something
better.  I'd very much appreciate a copy of any helpful responses you recieve.

-------------------

Dear Shing Chi,

May be I can help you. But I have two questions:

If you have already got a directed graph showing the poset, why do you
need to find out Q1. and Q2.? Because that graph cannot be cyclic,
also, from the arc, you can tell straight away whether two nodes are
comparable or not? Check up "Algorithmic Graph Theory", by M C Columbic.
Look up "comparability graphs". Hasse diagrams may also be relevant.

Also, Dr. Pretzel at Maths. Department at I.C. is a knowledgeble person
in graph theory. He may be able to help you.

Q1. I assume you mean you have a graph, but you do not know if it is
acyclic. To check this, give each edge a weight of -1. And then find
the shortest path between two nodes you have picked, the source
and the sink, using the algorithm
due to Bellman and Ford. A very good textbook on algorithms
is "Algorithms", by T. H. Cormen, C. E. Leiserson,
and R. L. Rivest. But Bellman-Ford algorithm is a classical algorithm
that you may find in other graph theory textbooks. In fact, the Bellman-
Ford algorithm only find any negative cycles that can be reached from the
source. So in the worst case, you have to run the algorithm n times,
where n= no. of nodes in your graph, once with each node as the source.

Q2. I assume you mean that:
1. If (s,t) is present in your graph, it implies s < t, but
2. s < t does not imply (s,t) is present in your graph.

In that case, there are a few alternatives.
If you want to do one calculation for each {s,t} pair, then do a
depth-first or breadth-first search starting from s, and the search
stops whenever t is reached. This will take O(m+n) time, where
m=no. of edges, n=no. of nodes. If you want to fill out all the missing
edges in the graph, i.e. construct arc (s,t) whenever s<t and (s,t) is
missing from the graph, you can do a depth-first search for each node
and then fill up the missing arcs. Alternatively, draw the Hasse diagram
first and the fill up the missing edges.

The book I mentioned about contains a chapter on comparabliity graph.
A comparability graph is an undirected graph where there is an edge (s,t)
if and only if s and t are comparable. The chapter gives an algorithm for
finding a transitive orientation given a comparability graph. Is that
useful to you?

These are just some ideas. There may be more efficient methods to solve
your problems. I hope they are helpful. In any case, ask Dr. Pretzel about
your problem. I think he will be willing to help you.

P.S. Sorry, I forgot something. The Bellman-Ford Algorithm takes time
O(mn).

-------------------

Set up a boolean
matrix A = (a_{s,t}) in which a_{s,t} = 1 if there is an
explicit relation s < t, and a_{s,t} = 0 otherwise.
Form its transitive closure A + A^2 + ... + A^n
(this can be done in n^3 steps if there are n nodes,
though I forget the algorithm -- look up ``transitive closure''
in a textbook).  There are cycles
iff the diagonal is nonzero.  If some a_{s,s} > 0,
then the nodes in the loop are those t with
both a_{s,t} > 0 and a_{t,s} > 0.
The transitive closure shows whether s > t, s < t, both, or neither.

-------------------

In comp.theory you write:

>I got a large directed graph capturing strict partial order relations `<'
>in which a directed edge from a node s to a node t means s < t.  The
>partial order relation is transitive;
>i.e.
>	s < t and t < u implies s < u
>.

>I would like to know if there are any fast algorithms and their
>complexities for the following 2 questions.

>Q1. Is the graph acyclic (i.e. absence of loops)?  How to trace out the
>    nodes in loops?

>Q2. How to tell the relation between two given nodes (say s and t) in
>    the graph (assume acyclic) whether they are related by
>    a) s < t
>or  b) t < s
>or  c) unknown - neither ( s < t ) nor ( t < s )

I can't help with the first question, but I can help you with your
second question.

Two MSc students and I are looking at the use of logical clocks in
parallel programming. The one student in particular is looking at something
which is very much related to what you are doing. She is looking at
the use of logical clocks as a measure of the concurrency of a
parallel program.

In a parallel program, events (either compuatation or communication)
can be related causally or not related. Causality defined a partial
ordering. Using Fidge-Mattern logical clocks it is possible to timestamp
each event (which corresponds to a vertex); using these timestamps
it is possible to directly compare the two clocks and thereby
tell whether they are related in the partial ordering.

A useful reference to start is Fidge's paper in August 1991
issue of IEEE Computer. If you want other refs I am sure we
can dig some up

-------------------

I'm sure you'll get 50 answers, but anyway...

see any introductory algorithms book (e.g. Aho, Hopcroft,
Ullman "The Design and Analysis of Computer ALgorithms",
Sedgewick "Algorithms", Cormen, Leiserson & Rivest
"Introduction to Algorithms" and look for the "Transitive
Closure" problem.

-------------------

Q1.  Simple depth first search can be used to verify the absence of a
cycle (or find one) in O(|E|).

Q2.  Relationship between nodes can be determined from the transitive
closure, which can be computed in O(|V|^3) or, for sparse graphs,
in O(|V|(|E|+|V|)).

For more info, see Sedgewick, Algorithms, 2nd ed., Addison-Wesley,
1988, or practically any book on analysis of algorithms.

-------------------

In article 18026@doc.ic.ac.uk, scc@doc.ic.ac.uk (Shing Chi Cheung) writes:
>I got a large directed graph capturing strict partial order relations `<'
>in which a directed edge from a node s to a node t means s < t.  The
>partial order relation is transitive;
>i.e.
>	s < t and t < u implies s < u
>..
>
>I would like to know if there are any fast algorithms and their
>complexities for the following 2 questions.
>
>Q1. Is the graph acyclic (i.e. absence of loops)?  How to trace out the
>    nodes in loops?

I THINK A SIMPLE DEPTH FIRST SEARCH SHOULD FIND LOOPS.
IF YOU HIT NODE ALREADY MARKED VISITED, THERE IS A LOOP.

>
>Q2. How to tell the relation between two given nodes (say s and t) in
>    the graph (assume acyclic) whether they are related by
>    a) s < t
>or  b) t < s
>or  c) unknown - neither ( s < t ) nor ( t < s )
>
THERE MAY BE AN EFFICIENT WAY BUT A BREADTH FIRST SEARCH FROM s SHOULD
DECIDE IF s < t  AND A BFS FROM t SHOULD DECIDE IF t < s.

>Any pointers would be appreciated.  Reply by email is preferred as
>the access to the News is not very reliable.
>
>Thank you.
>
>S.C. Cheung (scc@doc.ic.ac.uk)
>--
>	SC Cheung	(scc@doc.ic.ac.uk  071-589 5111 ext 5092)

-------------------

1) Look up topological sort in any algorithm's book it is very
fast and practical.

2) I think you might have to do a DFS or BFS (depth or breath first
search here).
But here is an idea.
	Topological sort will order the elements as
s_1,s_2, ...., s_n

where if s_i < s_j then i < j.

So you get an ordering which is consistant with the P.O.
Now give a s_i and s_j you could check if i < j if so you
could go into the orignal graph and verify it s_i < s_j.


One more thing is the graph is transitive. Then from any
s there is an edge to all t's such that
s < t. so you could simply check if the edge (s,t) exists in
the graph. Or (t,s) exists this takes constant time if you have
an Adjacency matrix and linear time on a adjacency list.

-------------------

Hello there,
           I am also looking for something quite similar to what you are
asking. I am doing my master's at the univ. of Bergen, Norway and am working
on determinig partial causality in distributed systems. Can you please forward
me any replies you get. I will be greatfull.
To find the cycles in a graph you can use the standard depth first search algorithm.
The prework can be to put thenodes in a stack while traversing the graph. As soon as
you come to a node already marked it means that a cycle exists.
Part b) can be done easily by computing transitivity matrix of the given graph.
See alg. by Warshall.

-------------------

You might find the following references to be of interest:

%A Robert Tarjan
%T Depth-First Search and Linear Graph Algorithms
%J Siam Journal Computing
%V 1
%N 2
%D June 1972
%P 146-160

%A Robert Tarjan
%T Enumeration of the Elementary Circuits of a Directed Graph
%J SIAM Journal Computing
%V 2
%N 3
%D September 1973
%P 211-216

%A Herbert Weinblatt
%T A New Search Algorithm for Finding the Simple Cycles of a Finite
Directed Graph
%J Journal of the ACM
%V 19
%N 1
%D January 1972
%P 43-56

-------------------

In article <1992Jun2.203631.18026@doc.ic.ac.uk> you write:
>I got a large directed graph capturing strict partial order relations `<'
>in which a directed edge from a node s to a node t means s < t.  The
>partial order relation is transitive;
>i.e.
>	s < t and t < u implies s < u
>.
>
>I would like to know if there are any fast algorithms and their
>complexities for the following 2 questions.
>
>Q1. Is the graph acyclic (i.e. absence of loops)?

Linear time (in the number of nodes).

>  How to trace out the
>    nodes in loops?

Linear time (in the number of nodes + the length of the output, if
you'll accept one loop per node; maybe longer if you want all loops).

>Q2. How to tell the relation between two given nodes (say s and t) in
>    the graph (assume acyclic) whether they are related by
>    a) s < t
>or  b) t < s
>or  c) unknown - neither ( s < t ) nor ( t < s )

Linear time to answer 1 such question.

>Any pointers would be appreciated.  Reply by email is preferred as
>the access to the News is not very reliable.

Depth-first search will do all of these.  Look in Knuth, of course.

-------------------

I am not sure if the algorithms that I am going to mention is what you
want.  Please let me know.

In article <1992Jun2.203631.18026@doc.ic.ac.uk> you write:
>I got a large directed graph capturing strict partial order relations `<'
>in which a directed edge from a node s to a node t means s < t.  The
>partial order relation is transitive;
>i.e.
>	s < t and t < u implies s < u
>.
>
>I would like to know if there are any fast algorithms and their
>complexities for the following 2 questions.
>
>Q1. Is the graph acyclic (i.e. absence of loops)?  How to trace out the
>    nodes in loops?

Standard method is to apply topological sort to the graph.  If the sorting
is possible then the graph is acyclic.  Otherwise the algorithm find
a cycle.  The intuition is as follows:

   If a finite digraph is acyclic then it must have a source,
   that is, a vertex with zero indegree.  Delete it from the graph.
   The remaining graph should be acyclic also.  It must then have
   a source.  Repeat this process and delete all source.  The
   order in which vertices are deleted is an ordering that we call
   a canonical ordering.  In such ordering, if u preceeds v then
   the edge joining (if any) u and v must direct from u to v.
   This ordering can be discovered by standard depth first search,
   which O(V + E) run time.

>
>Q2. How to tell the relation between two given nodes (say s and t) in
>    the graph (assume acyclic) whether they are related by
>    a) s < t
>or  b) t < s
>or  c) unknown - neither ( s < t ) nor ( t < s )

    Use s as the origin of a depth first search.  If the search reach
    t then s < t.  Otherwise do the same thing to t.  If the search
    reach s than t < t.  Otherwise neither s < t nor t < s.   Depth
    First Search requires O(V + E) time.  Thus this algorithm runs
    in O(V + E) time.

--
	SC Cheung	(scc@doc.ic.ac.uk  071-589 5111 ext 5092)