The rules are you cannot change the HTML in this document. You can only make changes via an external stylesheet.

Fortran I first met Fortran when I started my career at a Junior College. We used punch cards. The computer had 4k bytes of core memory. Hard to imagine. Hard to program.

Pascal My second programming when I was at Berkeley was Pascal. It seemed like a pleasant language. We have a very good tutorial book and a completely unreadable book on language details.

C In graduate school *C* was the new *cool* language. I used it for most of my research which involved a lot of computation.

C++After finishing school the object-oriented craze kicked in and *C++* was all the rage. Unfortunately it is also rather large and complicated with somewhat uneven cross-platform support. As the director of a large software project my team used C++ but not all of it.

Java Java was on the way in while I was in charge of that large project and we used it for systems that didn't have real-time constraints. Programmers tended to not make as many mistakes with Java. I used Java on my own and for consulting. Below is a sample.

```
/**
* This function is called to initialize the k-shortest path algorithm.
* It also finds the shortest path in the network.
* You can use this function to restart the algorithm at anytime with
* possibly different source and destination values.
* @param source The begining node of the path.
* @param dest The termination node of the path.
* @return The shortest path or null if the path doesn't exist.
*/
public WeightedPath<V,E> findFirstShortestPath(V source, V dest) {
// Used to initialize or reinitialize the algorithm
// Computes the shortest path via Dijsktra
kPath = null;
pathHeap.clear();
pathList.clear();
this.source = source;
this.dest = dest;
// Compute the shortest path
DijkstraShortestPath alg = new DijkstraShortestPath(g, wt);
List<E> ePath = alg.getPath(source, dest);
if (ePath.isEmpty()) return null;
List<V> nodeList = edgesToNodeList(ePath, g, source);
System.out.println("node list: "+nodeList);
Set<E> deletedLinks = new HashSet<E>();
kPath = new WeightedPath<V,E>(nodeList, deletedLinks, g, wt);
kPath.setdNode(source);
pathList.add(kPath);
return kPath;
}
/**
* Use this function to compute sucessive shortest path. Each one will have
* a length (cost) greater than or equal the previously generated algorithm.
* Returns null if no more paths can be found.
* You must first call findFirstShortestPath(source, dest) to initialize the
* algorithm and set the source and destination node.
* @return the next shortest path (or the next longer path depending on
* how you want to think about things).
*/
public WeightedPath<V, E> getNextShortestPath() {
if (kPath == null) {
throw new IllegalStateException("You must first call findFirstShortestPath and have it return a non-null");
}
// Iterate over all the nodes in kPath from dNode to the node before the destination
// and add candidate paths to the path heap.
List<V> kNodes = new LinkedList<V>(kPath.getPathList());
int index = kNodes.indexOf(kPath.getdNode());
ListIterator<V> nodeIterator = kNodes.listIterator(index);
V curNode = nodeIterator.next();
while (curNode != dest) {
removeEdgesNodes(curNode);
WeightedPath<V, E> candidate = computeCandidatePath(curNode);
restoreGraph();
if (candidate != null) {
pathHeap.add(candidate);
}
curNode = nodeIterator.next();
}
if (pathHeap.isEmpty())
return null;
WeightedPath<V,E> p = pathHeap.remove(); // after iterations contains next shortest path
pathList.add(p);
kPath = p; // updates the kth path
return p;
}
```

Code Sample 1. This was part of some Java code to compute the k-shortests paths between two nodes in a network.

Python I can't remember when I first heard about python. But when sitting in on some astronomy graduate classes at Berkeley in the 2000s there was a push away from proprietary languages such as Matlab for scientific computing, with the desire for ease of use and rapid prototyping. Because it played well with other languages, Python could wrap good (but not easy to use) numerical code from Fortran, C, and C++. Despite the weird indentation thing I was quickly sold and moved most of my network research and teaching to Python. See some code below.

```
class YenKShortestPaths(object):
"""
This is a straight forward implementation of Yen's K shortest loopless path algorithm. No attempt
has been made to perform any optimization that have been suggested in the literature. Our main goal
was to have a functioning K-shortest path algorithm. This implementation should work for both
undirected and directed graphs. However it has only been tested so far against undirected graphs.
"""
def __init__(self, graph, source, dest, weight="weight", cap="capacity"):
"""
Constructor
@param source The beginning node of the path.
@param dest The termination node of the path.
"""
self.wt = weight
self.cap = cap
self.g = graph
self.pathHeap = [] # Use the heapq module functions heappush(pathHeap, item) and heappop(pathHeap, item)
self.pathList = [] # Contains WeightedPath objects
self.deletedEdges = set()
self.deletedNodes = set()
self.kPath = None
# Make a copy of the graph tempG that we can manipulate
if isinstance(graph, nx.Graph):
self.tempG = graph.copy()
else:
self.tempG = None
self.kPath = None
self.pathHeap = []
self.pathList = []
self.source = source
self.dest = dest
def __iter__(self):
"""Returns itself as an iterator object"""
return self
def next(self):
"""
Computes successive shortest path. Each one will have
a length (cost) greater than or equal the previously generated algorithm.
Returns null if no more paths can be found.
You must first call findFirstShortestPath(source, dest) to initialize the
algorithm and set the source and destination node.
@return the next shortest path (or the next longer path depending on
how you want to think about things).
"""
if self.kPath is None:
alg = ModifiedDijkstra(self.g, self.wt)
nodeList = alg.getPath(self.source, self.dest, as_nodes=True)
if len(nodeList) == 0:
raise StopIteration
deletedLinks = set()
self.kPath = WeightedPath(nodeList, deletedLinks, self.g, wt=self.wt, cap=self.cap)
self.kPath.dNode = self.source
self.pathList.append(self.kPath)
return self.kPath
# Iterate over all the nodes in kPath from dNode to the node before the destination
# and add candidate paths to the path heap.
kNodes = self.kPath.nodeList
index = kNodes.index(self.kPath.dNode)
curNode = kNodes[index]
while curNode != self.dest:
self._removeEdgesNodes(curNode)
candidate = self._computeCandidatePath(curNode)
self._restoreGraph()
if candidate is not None:
heapq.heappush(self.pathHeap, candidate)
index += 1
curNode = kNodes[index]
if len(self.pathHeap) == 0:
raise StopIteration
p = heapq.heappop(self.pathHeap) # after iterations contains next shortest path
self.pathList.append(p)
self.kPath = p # updates the kth path
return p
def _removeEdgesNodes(self, curNode):
"""
Remove all nodes from source to the node before the current node in kPath.
Delete the edge between curNode and the next node in kPath
Delete any edges previously deleted in kPath starting at curNode
add all deleted edges to the deleted edge list.
"""
# Figure out all edges to be removed first then take them out of the temp graph
# then remove all the nodes from the temp graph.
# At the start the temp graph is equal to the initial graph.
self.deletedEdges = set()
self.deletedNodes = set()
kNodes = self.kPath.nodeList
index = 0
tempNode = kNodes[index]
index += 1
while tempNode != curNode:
edges = self.tempG.edges(tempNode)
if len(edges) != 0:
for edge in edges:
self.deletedEdges.add(edge)
self.tempG.remove_edge(edge[0], edge[1])
self.deletedNodes.add(tempNode)
self.tempG.remove_node(tempNode)
tempNode = kNodes[index]
index += 1
# Also need to remove those old deleted edges that start on curNode
oldDelEdges = self.kPath.deletedEdges
if self.g.is_directed():
outEdges = self.g.out_edges(curNode)
else:
outEdges = self.g.edges(curNode)
for e in outEdges:
if e in oldDelEdges:
self.deletedEdges.add(e)
self.tempG.remove_edge(e[0], e[1])
# Now delete the edge from the curNode to the next in the path
tempNode = kNodes[index]
e = (curNode, tempNode)
self.deletedEdges.add(e)
self.tempG.remove_edge(curNode, tempNode)
def _computeCandidatePath(self, curNode):
"""
Compute the shortest path on the modified graph and then
combines with the portion of kPath from the source up through
the deviation node
"""
alg = ModifiedDijkstra(self.tempG, self.wt)
nodeList = alg.getPath(curNode, self.dest, as_nodes=True)
# Trying this out...
if nodeList is None:
return None
# Get first part of the path from kPath
nodePath = []
if curNode in self.kPath.nodeList:
index = self.kPath.nodeList.index(curNode)
nodePath = self.kPath.nodeList[0:index]
nodePath.extend(nodeList)
wp = WeightedPath(nodePath, self.deletedEdges, self.g, wt=self.wt, cap=self.cap)
wp.dNode = curNode
return wp
def _restoreGraph(self):
"""
Using the internal deleted node and deleted edge containers
restores the temp graph to match the graph g.
"""
self.tempG = self.g.copy()
self.deletedEdges = []
self.deletedNodes = []
class WeightedPath(object):
"""Used internally by the Yen k-shortest path algorithm.
Also return to user as a result.
"""
def __init__(self, pathNodeList, deletedEdges, g, wt='weight', cap='capacity'):
"""
Constructor
"""
self.nodeList = pathNodeList
self.deletedEdges = set(deletedEdges)
self.g = g
self.wt = wt
self.dNode = None # The deflection node
self.cost = 0.0
self.capacity = float("inf")
for i in range(len(pathNodeList)-1):
self.cost = self.cost + g[pathNodeList[i]][pathNodeList[i+1]][wt]
if cap is not None:
self.capacity = min(self.capacity, g[pathNodeList[i]][pathNodeList[i+1]][cap])
else:
self.capacity = None
def __cmp__(self, other):
if other is None:
return -1
return cmp(self.cost, other.cost)
def __str__(self):
return "nodeList: {}, cost: {}, capacity: {}".format(self.nodeList, self.cost, self.capacity)
```

Code Sample 2. My homemade Python implementation of a k-shortest paths algorithm.

JavaScript A toy for web kiddies was my first impression. However, I was interested in *true* cross platform graphical user interfaces. I had done some GUI programming on Windows, and with Java but neither seemed truly cross platform or easy to integrate with the numerical work (Java doesn't play very nice with other languages). With ES6 (aka ES2015) adopting a lot of nice practices I started using JavaScript, HTML, CSS plus a whole lot of open source 3rd party libraries to build my web GUIs and applications. See a sample below.

```
/*
We'll work with string node IDs and such...
*/
function basicDijkstra(net, src, wt="weight") {
let previous = new Map(); // previous hops
let T = new Set();
let V = new Set(net.nodes.map(n=>n.id)); // Initially set of all nodes
T.add(src);
V.delete(src);
let distance = new Map(); // distance between nodes
distance.set(src, 0.0);
// Initialize distances
for (let v of V) {
if (hasEdge(net, src, v)) {
distance.set(v, linkParm(net, src, v, wt));
previous.set(v, src);
} else {
distance.set(v, Infinity);
}
}
while (V.size > 0) {
// Find the node with the smallest distance in the set V
let smallDist = Infinity;
let u = null; // Smallest distance node
for (let v of V) {
if (distance.get(v) <= smallDist) {
smallDist = distance.get(v);
u = v;
}
}
T.add(u);
V.delete(u);
// update distances
for (let v of V) {
if (hasEdge(net, u, v)) {
if (distance.get(v) > distance.get(u) + linkParm(net, u, v, wt)) {
distance.set(v, distance.get(u) + linkParm(net, u, v, wt));
previous.set(v, u);
}
}
}
}
return {distance: distance, previous: previous};
}
function widestDijkstra(net, src, bw="capacity") {
let previous = new Map(); // previous hops
let T = new Set();
let V = new Set(net.nodes.map(n=>n.id)); // Initially set of all nodes
T.add(src);
V.delete(src);
let cap = new Map(); // capacities between nodes
cap.set(src, Infinity);
// Initialize capacity
for (let v of V) {
if (hasEdge(net, src, v)) {
cap.set(v, linkParm(net, src, v, bw));
previous.set(v, src);
} else {
cap.set(v, 0.0);
}
}
while (V.size > 0) {
// Find the node with the maximum capacity in the set V
let maxCap = 0.0;
let u = null; // Max cap node
for (let v of V) {
if (cap.get(v) >= maxCap) {
maxCap = cap.get(v);
u = v;
}
}
T.add(u);
V.delete(u);
// update capacities
for (let v of V) {
if (hasEdge(net, u, v)) {
if (cap.get(v) < Math.min(cap.get(u), linkParm(net, u, v, bw))) {
cap.set(v, Math.min(cap.get(u), linkParm(net, u, v, bw)));
previous.set(v, u);
}
}
}
}
return {capacities: cap, previous: previous};
}
```

Code Sample 3. A shortest and a widest path computations with JavaScript (ES6).