reactive-banana-1.3.2.0: Library for functional reactive programming (FRP).

Safe Haskell | None
Language | Haskell98

Reactive.Banana.Prim.Low.GraphGC

Contents

- Debugging

Synopsis

- data GraphGC v
- listReachableVertices :: GraphGC v -> IO [Ref v]
- getSize :: GraphGC v -> IO Int
- new :: IO (GraphGC v)
- insertEdge :: (Ref v, Ref v) -> GraphGC v -> IO ()
- clearPredecessors :: Ref v -> GraphGC v -> IO ()
- data Step
  - = Next
  - | Stop
- walkSuccessors :: Monad m => [Ref v] -> (WeakRef v -> m Step) -> GraphGC v -> IO (m [WeakRef v])
- walkSuccessors_ :: Monad m => [Ref v] -> (WeakRef v -> m Step) -> GraphGC v -> IO (m ())
- removeGarbage :: GraphGC v -> IO ()
- printDot :: (Unique -> WeakRef v -> IO String) -> GraphGC v -> IO String

# Documentation

data GraphGC v Source #

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] Source #

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 Source #

new :: IO (GraphGC v) Source #

Create a new `GraphGC`.

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

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

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

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

data Step Source #

Constructors

Next |
Stop |

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

Walk through all successors. See `walkSuccessors`.

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

Walk through all successors. See `walkSuccessors_`.

removeGarbage :: GraphGC v -> IO () Source #

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 Source #

Show the underlying graph in `graphviz` dot file format.