You can edit this page using wiki syntax for markup.

Article contents:== Outdated egg! This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for [[/eggref/5/interval-digraph|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 [[https://wiki.call-cc.org/chicken-projects/egg-index-5.html|egg index]]. Otherwise, please consider porting this egg to the current version of CHICKEN. [[tags:egg]] == interval-digraph Directed graph based on adjacency intervals. [[toc:]] == 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</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}} <procedure> make-random-gnp-digraph :: NAME LABEL N P R S loops -> SELECTOR </procedure> 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</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. <procedure> digraph-disjoint-union :: GRAPH * GRAPH -> SELECTOR </procedure> 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 </procedure> 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 [[/users/ivan-raikov|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/>. Description of your changes:

I would like to authenticate

Spam control

What do you get when you subtract 23 from 24?