Here are just some codes as I write them. These are of course not at all yet complete. The codes are written in FWEB, a macro preprocessor/pretty printer for Fortran and C. This is somewhat complicated package, but it makes nice documentation which you can find below (just sample F90 codes).

I am leaving MSU in August of 2001 to attend Princeton University. I will likely continue working on SSCNO, starting to think about parallelization. At present these codes are not finished enough to release them as a packaged library. But you are free to download and look at the codes individually. Please note that eventually these will be released under the GNU GPL licence and I am their original author. Please let me know if you have downloaded these codes and used them inside yours!

• Random numbers
• Plotting
• Ranking and Search Skip Lists
• System Monitors
• Graph Algorithms
• Near-Neighbor Lattice Networks (IMAGES!!!)
• Elemental Cost Function
• Using LSNNO (FIRST RESULTS !!!)
• Solving Dual Newton Systems
• Newton-Based CNO Algorithms
• Using SSCNO (RESULTS!!!)

1. Module Precision

This is just a module with parameter kinds and is used by all codes. Here is the web file, PDF documentation (also dvi) and source code.
2. Random Number Generation, module RandomNumbers

The web file RandomDistributions.web contains the source for a library that generates random numbers drawn from a uniform or gaussian distribution. It is very portable and uses a fast shift-based generator. Here is the produced PDF documentation (also dvi) and the produced Fortran 90 source code. If you need this file for another architecture and do not wanna install and learn how to use FWEB (though I recommend this!), then just e-mail me. More distributions need to be added here!
3. Scientific and Network Plotting

The functions in the module Simple_Graphics are similar to the ones documented in the PHY201 SimpleGraphics page, but they have been improved and only plot two dimensional plots with vector x and y data, so the user has more freedom but also more responsibilities. This will be used to plot things like convergence or scaling. It is based on the DISLIN library. Here is the web file, the produced Fortran source code and the produced documentation (also dvi). Here is a sample file that uses it, and the produced plot.

The functions in the module Network_Graphics are a specialization of the ones in SimpleGraphics for plotting planar graphs with specified values at the nodes and/or arcs. It is rather niffty, I think. Here is the web file, the documentation (also dvi) and the source code. Here is a simple file that uses it (this uses random number generation and thus generates a graph that is not really planar) and the produced plot. Some of the results shown below are produced with this library and illustrate its power.

4. Sorting and Ranking, module Sorting_Ranking, and Search Skip Lists, module Skip_Lists

The following library implements several sorting algorithms to rank numerical arrays. Here is the web file, the produced Fortran code (also the used error function codes), the documentation (also dvi). Here are two files that test this library (web, Fortran, documentation (dvi)) and time the various sorts for real arrays of various size and of variable initial "sortedness" (web, Fortran, documentation (dvi)). The results of the timing on my machine showing which sort is the fastest are here, and here are the best ranking times.
Also in this group of algorithms I may include something I worked on for my CSE890 course--an implementation of skip lists, a very efficient probabilistic self-balanced data structure (web, Fortran, documentation (dvi)).
5. System Utilities, modules Error_Handling, System_Monitors, Initialization_Termination

These modules deal with some things such as timing, exception handling, allocation monitoring, etc. Here is the web file for the exception-handling module Error_Handling, the source code and the documentation (also dvi). Here is the web file for System_Monitors, the source code and documentation (dvi). And finally the web file for Initialization_Termination, the produced source code and documentation (dvi). These can be upgraded beyond standard Fortran on other architectures and compilers.
6. Combinatorial Algorithms, module Graph_Algorithms and module Network_Spanning_Trees, and module Network_Matrix_Operations

This is an almost finished file (web, Fortran, documentation (dvi)), for now it calculates connected-components labels for a graph and also has routines for building and maintaining minimal spanning trees (MSTs), and I also finished coding a backbone extraction algorithm in the same spirit as these. It also contains other scattered graph algorithms. This is a huge file---the documentation is 45 pages! It needs to be split into pieces...Also take a look at this interface to some FORTRAN 77  graph codes from NETLIB which I adopted to Fortran 90 (Fortran code) in Graph_Algorithms_F77 (web, Fortran, documentation (dvi)).

Here is the module Network_Spanning_Trees, which is a front-end interface to the lower-level routines in Graph_Algorithms (web, Fortran, documentation (dvi)). Here is an illustration of the algorithm that extracts the backbone in forms of cute images (a lattice network with the largest connected-cluster extracted, and with the largest backbone cluster extracted, as well as a colored graph showing the difference in the two (the dangling ends)). Here is an example program that times these routines for building and maintaining MSTs (web, Fortran, documentation (dvi)). Here is the main result of this timing (plots of tree building time for different sizes of the graphs and different perturbations to the weights) showing the relative superiority of the update-routines based on cycle traces. And here is just a sample program that makes cute plots the MSTs with colors for depth and cardinalities for the tree arcs and the tree nodes (web, Fortran, documentation (dvi)), along with the plots (node depths and arc cardinalities for 50x50 lattice).
In this category, at least for now, I should include the routines that perform some linear algebra on network arrays (web, Fortran, documentation (dvi)).

7. Near-Neighbor Lattices, modules Network_Data_Structures, Lattice_Geometry, Network_Geometry and Space_Filling_Curves

These sophisticated modules deal with setting up a network optimization problem based on a near-neighbour lattice geometry. The module Network_Data_Structures contains in it some shard commonly used arrays (web, Fortran, documentation (dvi)). The module Lattice_Geometry actually sets up a network with a desired geometry (web, Fortran, documentation (dvi)) and the module Network_Geometry finishes the job by creating a network out of the lattice (web, Fortran, documentation (dvi)). Here is an example input options file for a 2D network and severalIMAGES [ 2D Network (geometrical status identifiers, nodal supplies-demands and resistances of arcs, triangular lattice), 3D Network (geometrical status, supplies-demands and resistances]  produced with Network_Graphics using the following main program (web, documentation (dvi)). This module also does computation and data reordering based on the module Space_Filling_Curves (C source code for SFC library from D-ASCI project, web, Fortran, documentation (dvi), Hilbert SFC node-ordering, Morton SFC node-ordering).
8. Elemental Cost Functiona, modules Power_Cost_Parameters , FF_Cost_Parameters and Power_Cost_Functions, FF_Cost_Functions

These modules are the ones that should change when changing the cost function. However, they are prototypes that should be used as models when trying to rewrite them for a new cost function. I have provided two examples here, a power-law cost function and a cost function suitable for certain types of superconductors (Flux-Flow). Here is the module that sets up the random cost parameters for the arcs for power-law costs (web, Fortran, documentation (dvi)) and for FF(web, Fortran, documentation (dvi)), and the module that calculates the derivatives (and some inverses) of the elemental cost functions for power-law (web, Fortran, documentation (dvi)) and FF cost functions (web, Fortran, documentation (dvi)). We have several other functions we use, but they all follow the same design principle. Their main characteristic is transient-like behaviour near a cricial flow (current) or tension (voltage), as shown in this regularization illustration.
9. Using LSNNO, modules Lattice_Network_Optimization and LSNNO_Interface

The module Lattice_Network_Optimization is just a front-end interace to the many routines above for ease-of-use (web, Fortran, documentation (dvi)). LSNNO (Large Scale Nonlinear Network Optimization) is the only public-domain network optimization library today (soon to be replaced with my library LSCNO). The first step in this project was to get this library working with our networks, to be used for validation and comparision later on. This is done in the module LSNNO_Interface (web, Fortran, documentation (dvi)). I am happy to say this endevour was successful :), albeit after some considerable trouble. Here is a test program that runs LSNNO for a network with power-law costs (web, Fortran, documentation (dvi)) and the first sample results it produced (Flow pattern, Potential pattern)
10. Solving dual Newton systems, modules Network_Data_Types and Conjugate_Gradient, Vector_Operations, TAUCS_Interface, SCOTCH_Interface, CHACO_Interface and Dual_Newton_Solvers

The module Conjugate_Gradient implements a PCG iterative linear solver (web, Fortran, documentation (dvi)) to be used in solving Newton's system of equations later on. Its design is based on the object-oriented framework of Fortran 2002 and is explained in my two papers for the Fortran Forum dealing with reverse communication and iterative linear solvers. In order to avoid aliasing optimization problems with array pointers (used extensively in SSCNO), I designed a set of vector operation routines in the module Vector_Operations (web, Fortran, documentation (dvi)).

I also provide direct solvers based on Cholesky factorization (these work great in 2D), mostly via interfacing to some public-domain libraries, such as the factorization library TAUCS of Sivan Toledo (web, Fortran, documentation (dvi)), the graph partitioning and matrix reordering library SCOTCH of Francois Pellegrini (web, Fortran, documentation (dvi)), as well as the graph partitioning library CHACO of Bruce Hendrickson et al. (web, Fortran, documentation (dvi)). Please note that I made some minor changes to the sources of all these libraries. As they themselves are changing, there is no purpose in putting these patches here...

PCG and Cholesky factorization are used in the module that implements the dual solvers Dual_Newton_Solvers (web, Fortran, documentation (dvi)), which uses the preliminary version of network derived data-types (which I avoided so far...), Network_Data_Types (web, Fortran, documentation (dvi)). Here is an example program that times and tests different preconditioners for the dual systems (Outdated: web, Fortran, documentation (dvi)). Most of these are support-graph preconditioners, and some comments about them can be found in my report on preconditioning Laplacian systems. The codes that manipulate regular (i.e. fixed height and fixed-degree) support trees are in the module Support_Trees (web, Fortran, documentation (dvi)).

11. Newton algorithms implemented in SSCNO, modules Dual_Line_Search and Dual_SSCNO, and SSCNO_Interface

The module Dual_Line_Search implements some line search procedures for minimizing the lagrangian or dual Lagrangian for a strictly convex network optimization problem in either flow or potential space (web, Fortran, documentation (dvi)).

The top-level of SSCNO at present is the module Dual_SSCNO (web, Fortran, documentation (dvi)) which implements two second order algorithms, the Truncated Dual Newton (TDN) and the Truncated Sequential Quadratic Programming (TSQP) algorithms, described in a more condensed form in this code extraction (web, documentation (dvi)). The system of derived data-types (i.e. class containers) within SSCNO is somewhat scanty, but is summarized in this code extraction (web, documentation (dvi)).

The interface between SSCNO and the hypercube lattice generation routines is given in the module SSCNO_Interface (web, Fortran, documentation (dvi)).

12. Using SSCNO in materials science. Programs IV, Breakdown and Saturation.

SSCNO, as composed of the codes above, works!!! But of course it is far from finished (and it may never be). It is exciting to introduce the advances of convex optimization to the materials-science community, which is behind on basic optimization theory. A paper is currently in preparation with details.
Here is the program IV (web, Fortran, documentation (dvi)) which plots voltage-current characterstics of networks. Here is an IV curve of a 100 by 100 2D sample model for a granular superconductor. Corey Musolffc is working on using this program to collect numerically averaged data of this sort.

Even more exciting are cases in which critical breakdowns and saturations of the voltage or flow occur along combinatorial structures. The program Breakdown (web, Fortran, documentation (dvi)) models varistor materials and compares the breakdown paths with shortest paths (Dijkstra's tree, small currents, near critical voltage, larger currents). The program Saturation (web, Fortran, documentation (dvi)) models the onset of disippation via flow saturation in superconducting materials and compares it against max-flow/min-cut combinatorial structures (recursive ST minimal cuts, small voltage, near critical current, larger voltage). There is plenty of physics and applied mathematics (in regularization approaches, preconditioning, and using combinatorial structures as initial guesses) here, and you will see more on this page soon enough :)