You are looking at historical revision 22146 of this page. It may differ significantly from its current revision.

## interval-digraph

Directed graph based on adjacency intervals.

## Usage

(require-extension interval-digraph)

## Documentation

The `interval-digraph` library is an implementation of a directed graph, where the nodes and edges may be stored as integer interval objects from the cis library.

The library defines a digraph "object" -- a procedure that takes a method name as a symbol, and returns the procedure that implements the respective operation.

### Directed graph procedures

#### Constructors

An empty digraph object can be created by procedure `make-digraph`

*[procedure]*

`make-digraph:: NAME LABEL -> SELECTOR`

where `NAME` is the graph name (string or symbol), `LABEL` is an optional metadata object of an arbitrary type or `#f`.

The returned selector procedure can take one of the following arguments:

`'name`- returns the graph name (string or symbol)
`'label`- returns the graph metadata (arbitrary type)
`'nodes`- returns a procedure with no arguments, which returns a list with the node indices of the graph
`'nodes-with-labels`- returns a procedure with no arguments, which returns a list with the node indexes of the graph, along with optional label
`'node-intervals`- returns the node indices of the graph as a cis interval object
`'edges`- returns a procedure with no arguments, which returns a list with the edges of the graph
`'edges-with-labels`- returns a procedure with no arguments, which returns a list with the edges of the graph and their labels
`'order`- returns a procedure with no arguments, which returns the number of nodes in the graph
`'size`- returns a procedure with no arguments, which returns the number of edges in the graph
`'out-edges`- returns a procedure
`LAMBDA N`which returns a list with the outgoing edges of node`N` `'in-edges`- returns a procedure
`LAMBDA N`which returns a list with the incoming edges of node`N` `'succ`- returns a procedure
`LAMBDA N`which returns a list with the successor nodes of node`N` `'pred`- returns a procedure
`LAMBDA N`which returns a list with the predecessor nodes of node`N` `'succ-interval`- returns a procedure
`LAMBDA N`which returns a cis interval object with the successor nodes of node`N` `'pred-interval`- returns a procedure
`LAMBDA N`which returns a cis interval object with the predecssor nodes of node`N` `'has-edge`- returns a procedure
`LAMBDA I J`which returns true if edge`I -> J`exists in the graph and false otherwise `'has-node`- returns a procedure
`LAMBDA N`which returns true if node`N`exists in the graph and false otherwise `'has-node-interval`- returns a procedure
`LAMBDA I`which returns true if interval`I`exists in the graph and false otherwise `'edge-property`- returns a procedure
`LAMBDA P I J`which returns the property P of edge`I -> J`, if it exists, #f otherwise `'edge-interval-property`- returns a procedure
`LAMBDA P I J`which returns the property P of all edges defined on the intervals`I, J`, if it exists, #f otherwise `'node-property`- returns a procedure
`LAMBDA P N`which returns the property P of node`N`, if it exists, #f otherwise `'node-interval-property`- returns a procedure
`LAMBDA P I`which returns the property P of node interval`I`, if it exists, #f otherwise `'node-label`- returns a procedure
`LAMBDA N`which returns the label of node`N`if it exists, #f otherwise `'roots`- returns a procedure with no arguments, which returns a list with all nodes in the graph that do not have an predecessor
`'foreach-node`- returns an iterator procedure
`LAMBDA F`which iterates over the nodes in the graph by invoking function`F`on the node index of each node `'foreach-node-with-label`- returns an iterator procedure
`LAMBDA F`which iterates over the nodes in the graph by invoking function`F`on the node index and label of each node `'foreach-edge`- returns an iterator procedure
`LAMBDA F`which iterates over the nodes in the graph by invoking function`F`on the node indices of each edge `'add-node`- returns a procedure
`LAMBDA N [LABEL]`which when given a node index`N`and optional label, returns a new graph containing the original graph plus the given node `'add-node-interval`- returns a procedure
`LAMBDA I [LABEL]`which when given a cis interval object`I`and optional label, returns a new graph containing the original graph plus the given node interval `'remove-node`- returns a procedure
`LAMBDA N`which when given a node index`N`, returns the original graph with the given node and connecting edges removed `'add-edge`- returns a procedure
`LAMBDA E [LABEL]`which when given edge`E = (list I J)`and optional label, returns a new graph containing the original graph plus the given edge `'node-label-set`- returns a procedure
`LAMBDA N LABEL`which when given a node index`N`and label, returns a new graph with the labeled node `'node-property-set`- returns a procedure
`LAMBDA P N V`which when given property name`P`, node index`N`and property value, returns a new graph with the property`P`set for node`N` `'node-interval-property-set`- returns a procedure
`LAMBDA P I V`which when given property name`P`, cis interval object`I`and property value, returns a new graph with the property`P`set for all nodes in the interval`I` `'edge-property-set`- returns a procedure
`LAMBDA P I J V`which when given property name`P`, node indices`I,J`and property value, returns a new graph with the property`P`set for edge`I -> J` `'edge-interval-property-set`- returns a procedure
`LAMBDA P I J V`which when given property name`P`, cis interval objects`I,J`and property value, returns a new graph with the property`P`set for all defined edges on the intervals`I, J`

*[procedure]*

`make-random-gnp-digraph :: NAME LABEL N P R S loops -> SELECTOR`

Naive implementation of a random uniform graph: given number of nodes `N`, probability `P`, random number generator function `R`, and initial state `S`, samples node indices from a binomial distribution `N,P`, and creates edges determined by the sample values. Argument `loops` specifies if a node can connect to itself in the graph.

#### Combinators

*[procedure]*

`digraph-union:: GRAPH * GRAPH * MERGE-LABEL-FN -> SELECTOR`

Union of directed graphs: given two digraph objects, returns a new digraph containing the union of nodes and edges from the given digraphs. Argument `MERGE-LABEL-FN` is a procedure that returns a node label given a node index and the labels for that node from the two given digraphs.

*[procedure]*

`digraph-disjoint-union :: GRAPH * GRAPH -> SELECTOR`

Disjoint union of directed graphs: given two digraph objects, returns a new digraph containing the disjoin union of nodes and edges from the given digraphs. The disjoint property is enforced by reindexing all the nodes in the second digraph to have an index higher than the highest index in the first digraph.

*[procedure]*

`digraph-rename :: K * GRAPH -> SELECTOR`

Given a digraph and a number `K`, returns a new digraph that has `K` added to all node indices and edges.

## Examples

## About this egg

### Author

### Version history

- 1.1
- Initial release

### License

Copyright 2010 Ivan Raikov and the Okinawa Institute of Science and Technology This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. A full copy of the GPL license can be found at <http://www.gnu.org/licenses/>.