Hi all,
I learnt something today. COOL.
So I had a quick look to understand what a weighted graph was see:
http://www.informatics.susx.ac.uk/courses/dats/notes/html/node130.html
Then I had a look at the
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm link
provided by John Moore.
My line is in Gene / Protein analysis / bioinformatics, and both of
these seem to have a sort of a relation to the BLAST (Basic Local
Alignment Search Tool) algorithm (see
http://www.ebi.ac.uk/2can/tutorials/protein/blast.html).
I wonder if the result of a Warshall Algorithm can give more than one
result with the same "score" If the use of the BLAST could be
interesting to find the common paths, which could then be treated as
"single" nodes, with the intention of rerunning the Warshall using these
common nodes more often.
I only add this in as I thought other may find it interesting, I
certainly did.
Thanks for an interesting thread.
David
On 14/10/12 13:52, John English wrote:
If I have a table defined like so:
create table COMPONENTS (
ID integer generated always as identity,
COMPONENT varchar(255) not null,
PARENT integer,
constraint COMPONENTS_PK primary key (ID),
constraint COMPONENTS_1 foreign key (PARENT)
references COMPONENTS(ID)
on delete cascade
);
with (for example):
insert into COMPONENTS(COMPONENT,PARENT) values
('IC package',null), -- ID = 1
('Flip-flop',1), -- ID = 2
('D-type',2), -- ID = 3
('JK flip-flop',2), -- ID = 4
('7474 dual D-type flip-flop',3),
('4013 dual CMOS D-type flip-flop',3),
('7476 dual JK flip-flop with preset and clear',4),
('4027 dual CMOS JK flip-flop',4);
Is there a clever an efficient way to get the set of all flip-flop
packages, i.e. ID=2, all items with parent=2, and so on down the chain
of descendants? Or in other words, the transitive closure of the set?
TIA,
