Reactive.Banana.Prim.Low.GraphGC

Documentation

data GraphGC v

A directed graph whose edges are mutable and whose vertices are subject to garbage collection.

The vertices of the graph are mutable references of type 'Ref v'.

Generally, the vertices of the graph are not necessarily kept reachable by the GraphGC data structure — they need to be kept reachable by other parts of your program.

That said, the edges in the graph do introduce additional reachability between vertices: Specifically, when an edge (x,y) is present in the graph, then the head y will keep the tail x reachable. (But the liveness of y needs to come from elsewhere, e.g. another edge.) Use insertEdge to insert an edge.

Moreover, when a vertex is removed because it is no longer reachable, then all edges to and from that vertex will also be removed. In turn, this may cause further vertices and edges to be removed.

Concerning garbage collection: Note that vertices and edges will not be removed automatically when the Haskell garbage collector runs — they will be marked as garbage by the Haskell runtime, but the actual removal of garbage needs to be done explicitly by calling removeGarbage. This procedure makes it easier to reason about the state of the GraphGC during a call to e.g. walkSuccessors.

listReachableVertices :: GraphGC v -> IO [Ref v]

List all vertices that are reachable and have at least one edge incident on them. TODO: Is that really what the function does?

getSize :: GraphGC v -> IO Int

new :: IO (GraphGC v)

Create a new GraphGC.

insertEdge :: (Ref v, Ref v) -> GraphGC v -> IO ()

Insert an edge from the first vertex to the second vertex.

clearPredecessors :: Ref v -> GraphGC v -> IO ()

Remove all the edges that connect the vertex to its predecessors.

data Step

Constructors

Next

Stop

walkSuccessors :: Monad m => [Ref v] -> (WeakRef v -> m Step) -> GraphGC v -> IO (m [WeakRef v])

Walk through all successors. See walkSuccessors.

walkSuccessors_ :: Monad m => [Ref v] -> (WeakRef v -> m Step) -> GraphGC v -> IO (m ())

Walk through all successors. See walkSuccessors_.

removeGarbage :: GraphGC v -> IO ()

Explicitly remove all vertices and edges that have been marked as garbage by the Haskell garbage collector.

Debugging

printDot :: (Unique -> WeakRef v -> IO String) -> GraphGC v -> IO String

Show the underlying graph in graphviz dot file format.