Re: topological sort with bidirected graphs
- From: Boris <boris@xxxxxxxxxxxxxxxxxxxx>
- Date: Mon, 18 Apr 2005 14:02:27 +0200
Martin wrote:
Boris wrote:
Hi,
I need to consider matrices of adjacence with an equality relation
(or
bidirected relation) 0 coding for equality, 1 coding for "superior to", -1 coding for "inferior to" for exemple A=[. 0 1 1 . . 0 0 . . . 0 . . . .] codes for (line to column) 1) x1=x2 2) x1>x3 3) x1>x4 4) x2=x3 5) x2=x4 6) x3=x4
transitivity would give x1=x2=x3=x4=x5 but it does not agree with 2)
and 3)
if we want to get the maximum of true relations, we must write x1>x2=x3=x4 that agrees with 2), 3), 4), 5) and 6) how to get an algorithm that would give this relation ? -- Boris http://www.pi314.net
How it is possible, that you have: x1=x2=x3 and x1>x3?
we have x1=x2 and x2=x3 but not x1=x3
think about statistical tests for example, we can show that x1=x2, x2=x3 and x1>x3 significantly
Do you mean '>=' by '>'?
no, I must consider ">" and "=" because of the same reason (statistical tests)
The most simple algorithm I can think about is this (I think it should work):
First we find out which elements are equal. This is the same as to find 2-connected components of a digraph - there are some known algorithms for this.
Then we identify all vertices which are in the same component to one point. We can use the usal topological sort on the modified graph.
yes, so we must emphasize the equality case and consider x1=x3 in your opinion
but this would not work with my example because this would lead to forget a lot of "true relations". This becomes so a combinatorics optimization and I don't know how to do.
Thanks for your interest in my question by the way :-)
I supposed it was a usual problem and I discover it is not the case....
Martin
-- Boris http://www.pi314.net
.
- References:
- topological sort with bidirected graphs
- From: Boris
- Re: topological sort with bidirected graphs
- From: Martin
- topological sort with bidirected graphs
- Prev by Date: Re: JSH: Tag along society
- Next by Date: Re: JSH: Tag along society
- Previous by thread: Re: topological sort with bidirected graphs
- Next by thread: Invisible Solids
- Index(es):
Relevant Pages
|
