interval-digraph

Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

Directed graph based on adjacency intervals.

TOC »

Outdated egg!
interval-digraph
Usage
Documentation
- Directed graph procedures
  - Constructors
  - Combinators
Examples
About this egg

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

make-digraph:procedure

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
'succ: returns a procedure LAMBDA N which returns a list with the successor nodes of node N
'succ-interval: returns a procedure LAMBDA N which returns a cis interval object with the successor 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-property-keys: returns a procedure without arguments, which returns a list with all edge property names
'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
'edge-interval-prototype: returns a procedure LAMBDA P I J which returns the prototype P of all edges defined on the intervals I, J, if it exists, #f otherwise; a prototype is a user-supplied procedure of the form LAMBDA G I J which returns a property value for the edge I -> J
'node-property: returns a procedure LAMBDA P N which returns the property P of node N, if it exists, #f otherwise
'node-property-keys: returns a procedure without arguments, which returns a list with all node property names
'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
'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
'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
'edge-interval-prototype-set: returns a procedure LAMBDA P I J V which when given property name P, cis interval objects I,J and prototype procedure, returns a new graph with the prototype P set for all defined edges on the intervals I, J; a prototype is a user-supplied procedure of the form LAMBDA G I J which returns a property value for the edge I -> J

make-random-gnp-digraphprocedure: 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

digraph-union:procedure: 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.

digraph-disjoint-unionprocedure: 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.

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

4.0: Updated to rb-tree 5.0
2.3: Bug fix in foreach-edge-with-property
2.2: Bug fix to size message handler
2.1: Bug fixes and addtions to edge iterator interfaces
2.0: Removed methods pred, in-edges, roots
1.4: Added node-property-keys and edge-property-keys
1.2: Added edge-interval-prototype and edge-interval-prototype-set
1.1: Initial release

License

Copyright 2010-2013 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/>.

chickadee » interval-digraph

Identifier search

Outdated egg!