2009/1/9 Timothy Goddard <t...@goddard.net.nz>: > On Thu, 08 Jan 2009 21:28:27 minh thu wrote: >> Hi, >> >> I'd like to process some kind of graph data structure, >> say something like >> >> data DS = A [DS] | B DS DS | C. > > Graphs in funtional languages aren't usually represented in this sort of > manner. Trees are fine to represent like that as they're acyclic and have > exactly one parent for each node but for graphs it's much more difficult. Say > that you have a graph with directed connections like this: > > 0 -> 1 > 1 -> 2 > 2 -> 3 > 1 -> 3 > 3 -> 4 > > Now you want to alter node 4. Node 3 has to be updated to point to the new > version of 4, node 1 has to be changed to point to the new version of 3, node > 2 has to be changed to point to the new version of node 3, then node 1 has to > be changed again to point to the new version of 2, then finally 0 can be > changed to point to the new version of 1 and returned. > > There is no simple way using this representation to handle that double-update > to node 1, or to handle disconnected or cyclic graphs. Updates are extremely > difficult since Haskell data structures are not mutable and have no concept > of identity. The approach of treating nodes as structures with pointers to > each other cannot be cleanly and efficiently implemented in an immutable > fashion. It only really makes sense in a stateful, imperative context. > > An approach that suits functional languages better is to store a flat > structure listing the edges leaving each node. This, I believe, is the > approach taken by Haskell's main graph library, FGL > (http://hackage.haskell.org/cgi-bin/hackage-scripts/package/fgl). You would > now have something like: > > data MyNode nv = MyNode {nodeId::Int, nodeValue::nv} > > data MyEdge ev = MyEdge {edgeDestination::Int, edgeValue::ev} > > data MyGraph nv ev = MyGraph { > maxNode :: Int, > nodes :: (Map Int nv), > edges :: (Map Int [MyEdge ev])} > > emptyGraph :: MyGraph nv ev > emptyGraph = MyGraph 0 (Data.Map.empty) (Data.Map.empty) > > getNode :: MyGraph nv ev -> Int -> Maybe (MyNode nv) > getNode g id = ((nodes g) `lookup` id) >>= (\v -> MyNode id v) > > getEdgesLeaving :: MyGraph nv ev -> Int -> [MyEdge ev] > getEdgesLeaving g id = fromMaybe [] ((edges g) `lookup` id) > > addNode :: nv -> MyGraph nv ev -> (Int, MyGraph nv ev) > addNode val g = (maxNode newGraph, newGraph) > where > newNodeId = (maxNode g) + 1 > newGraph = MyGraph newNodeId (insert newNodeId val (nodes g)) > (edges g) > > ... and so on. (This is all totally untested - use at your own peril.) > > Each node in the graph has a unique identifying number, issued in sequence > using maxNode as a counter. This makes identifying cycles easy. The nodes map > contains the value for each node based on its id. The edges map contains a > list of links from each node to others in the graph. Finding links entering a > node is quite expensive - if you need to do this often then maintaining a > second list of edges entering each node would speed it up. > > Each node and each edge can have a custom data structure attached. New nodes > and edges can be added without having to modify references elsewhere, nodes > have a distinct identity given by the associated Int and the graph is > immutable - operations on it produce modified copies.
Indeed, the processing I'm refering to is to copy something like my representation into something like yours. Thanks ! Thu _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
