home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / prolog / 1525 < prev    next >
Encoding:
Text File  |  1992-08-13  |  1.2 KB  |  36 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!mcsun!Germany.EU.net!news.netmbx.de!zrz.tu-berlin.de!opal.cs.tu-berlin.de!okp
  3. From: okp@cs.tu-berlin.de (Oli Paulus)
  4. Subject: graph-utilities needed
  5. Message-ID: <XP1582W@mailgzrz.tu-berlin.de>
  6. Sender: news@mailgzrz.tu-berlin.de (News Manager)
  7. Nntp-Posting-Host: kit.cs.tu-berlin.de
  8. Organization: Technical University of Berlin, Germany
  9. Date: Thu, 13 Aug 1992 12:32:14 GMT
  10. Lines: 24
  11.  
  12. Hello,
  13.  
  14. I'writing a program for my thesis and ran into a graph-problem.
  15.  
  16. Given a directed graph that may contain arbitrary cycles, represented
  17. as a list of From-To node tuples, I need to perform two tasks:
  18.  
  19. - remove all redundant links from the graph
  20.  
  21. - detect all cycles and 'shrink' them into a single node
  22.  
  23. Shrinking means that all the nodes in the cycle will be removed
  24. and a shrinknode will be inserted into the graph, which will be
  25. connected to all nodes that had a link to any of the cycle's nodes
  26. before (Was that precise enough?).
  27.  
  28. I'm using quintus prolog (the predicates I need are not in the
  29. library), but solutions in any other dialect will do.
  30.  
  31. I'd greatly appreciate any hints, implementations, pointers to
  32. literature, newsgroups, ftp-sites or whatsoever you think I could use.
  33.  
  34.  
  35. Thanks for helping,  OliKai
  36.