[[ -- spike-cyclicstructure.hs
data Node = Node { nodeid :: String, adjacent :: [Node] }
instance Eq Node where n1 == n2 = nodeid n1 == nodeid n2
instance Show Node where show = nodeid
findPaths :: Node -> Node -> [[Node]] findPaths fromNode toNode = map reverse $ findPaths1 [] fromNode toNode
findPaths1 :: [Node] -> Node -> Node -> [[Node]]
findPaths1 beenThere fromNode toNode
| fromNode == toNode = [fromNode:beenThere]
| otherwise = concat [ findPaths1 (fromNode:beenThere) nextNode toNode
| nextNode <- adjacent fromNode
, not ( nextNode `elem` beenThere ) ]n1 = Node "n1" [n2,n3,n4] n2 = Node "n2" [n1,n3,n4] n3 = Node "n3" [n1,n2] n4 = Node "n4" [n1,n2]
test1 = findPaths n1 n2 -- [[n1,n2],[n1,n3,n2],[n1,n4,n2]] test2 = findPaths n1 n3 -- [[n1,n2,n3],[n1,n3],[n1,n4,n2,n3]] ]]
One (crude) way to think about this is that a mention of a value in haskell behaves in some ways like a pointer to that value in (say) C.
If you don't want to assign unique identifiers by hand, you could use a state transformer monad to generate them for you.
#g --
At 16:37 07/07/03 +0100, Sarah Thompson wrote:
From reading your message, it seems you want a graph library of sorts.The important bit is 'of sorts', unfortunately! Most graph libraries I've seen to date (although I must admit that they have been written in C and C++, including one I perpetrated personally) don't really work that well for circuits because, for anything other than trivially simple components, the connections between nodes need to be labelled.
A component representing something simple like (say) an 'and' gate would be easy enough to represent as a node of an ordinary directed graph. In such a case, an incoming arrow would always be an input of the gate, and an outgoing arrow would always be the output. I need to be able to represent more complex components, up to and including the complexity of things like CPUs, where you might have lots and lots of inputs and outputs with substantially different meanings. In the case of a CPU, it would never be acceptable to (for example) swap a chip select output for an address or data line.
This makes me think that an off-the-shelf graph library won't quite be what I'm after, so I will almost certainly need to write the code. What I'm more interested in at the moment is a view on the best kinds of approach that might be appropriate.
I'd considered something like embedding the type in the IO monad, with links between components implemented as IORefs, but I'd really prefer something cleaner (pure functional). If the code ends up horribly complicated in order to get decent performance, I might as well fold and use C++ instead.
I'm currently wondering about going for an adjacency list approach (as used by most graph libraries), with the tuples in the adjacency list extended to include input/output labels, resulting in a 4-ary tuple rather than the usual 2-ary. But, I don't want to be stuck with representing this as a list -- I really need log N lookups or performance will stink horribly as circuits get big. Maybe a pair of finite maps, allowing the edges to be traversed in either direction?
The finite map from n to Node seems like a good idea. Does representing the adjacency list as a flat array cause any problems?If FGL seems like overkill to you, I have my own little mini graph library which basically looks like:
- An ADT, Node: newtype Node = Node Int deriving ... - The 'Graph n e' data structure, containing: - a FiniteMap from n -> Node - an (growable?) array of type IOArray (Node,Node) e
the array represents the edges in the top half (i do some index fiddling to get this efficient) and the finitemap represents the node labellings. It's a pretty stupid interface and works a lot better when the graphs are fixed size (that way you don't need to grow the array). But it works.
Sarah
-- ---------------------------------------------- / __ + / Sarah Thompson **** / / (_ _ _ _ |_ / * / / __)(_|| (_|| ) / [EMAIL PROTECTED] * / / + / http://findatlantis.com/ / ----------------------------------------------
-- ---------------------------------------------- / __ + / Sarah Thompson **** / / (_ _ _ _ |_ / * / / __)(_|| (_|| ) / [EMAIL PROTECTED] * / / + / http://findatlantis.com/ / ----------------------------------------------
_______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
------------------- Graham Klyne <[EMAIL PROTECTED]> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E
_______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
