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.

interval-digraph

Directed graph based on adjacency intervals.

  1. Outdated egg!
  2. interval-digraph
  3. Usage
  4. Documentation
    1. Directed graph procedures
      1. Constructors
      2. Combinators
  5. Examples
  6. About this egg
    1. Author
    2. Version history
    3. License

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
'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
[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

Ivan Raikov

Version history
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/>.