Style This Great Document!

Be Stylish, Be Cool, Be a Web Developer

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

Programming Languages I have Known

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).