MOD 11 - GRAPHS V2 BASE

currently just returns the first path it finds

by SHELDON PASCIAK

HTML

<!--

Module 11 - Graphs - VERSION 2 - BASE - SHELDON PASCIAK

    
    STILL A WORK IN PROGRESS - OUCH ON THIS ONE EVERYONE!!!





 
notes: wiki article portion

Implementation details[edit]
The graph pictured above has this adjacency list representation:
a	adjacent to	b,c
b	adjacent to	a,c
c	adjacent to	a,b
An adjacency list representation for a graph associates each vertex in the graph with the collection of its neighboring vertices or edges. There are many variations of this basic idea, differing in the details of how they implement the association between vertices and collections, in how they implement the collections, in whether they include both vertices and edges or only vertices as first class objects, and in what kinds of objects are used to represent the vertices and edges.
An implementation suggested by Guido van Rossum uses a hash table to associate each vertex in a graph with an array of adjacent vertices. In this representation, a vertex may be represented by any 
"hashable object". There is no explicit representation of edges as objects.[1]
Cormen et al. suggest an implementation in which the vertices are represented by index numbers.[2] Their representation uses an array indexed by vertex number, in which the array cell for each vertex points to a >>> singly linked list <<<<< of the neighboring vertices of that vertex. In this representation, the nodes of the singly linked list may be interpreted as edge objects; however, they do not store the full information about each edge (they only store one of the two endpoints of the edge) and in undirected graphs there will be two different linked list nodes for each edge (one within the lists for each of the two endpoints of the edge).
The object oriented incidence list structure suggested by Goodrich and Tamassia has special classes of vertex objects and edge objects. Each vertex object has an instance variable pointing to a collection object that lists the neighboring edge objects. In turn, each edge...

JavaScript

// module 11 - program 1 - VERSION 2 BASE - SHELDON PASCIAK

// This is a basic implementation of a Graph

// populates neighbors for each no
// finds ONE path ( //todo - work in progress )


function Node(data) {
    this.data = data;
    this.neighbors = null; // addEdge smartly creates [] as needed
}

function Graph() {
    
    this.edges = {};
    this.visited = [];    

    this.addNode = function (label) {
        this.edges[label] = new Node(label);
    };

    this.neighbors = function (label) {      
        return this.edges[label].neighbors;
    };

    this.addEdge = function (from, to, cost) {
        if (!(this.edges[from].neighbors)) this.edges[from].neighbors=[];
        if (!(this.edges[to].neighbors)) this.edges[to].neighbors=[];
        this.edges[from].neighbors.push(to);        
        this.edges[to].neighbors.push(from);
        this.edges[from][to] = cost;
        this.edges[to][from] = cost;
    };

    this.calculatePaths = function (from, to, cost, paths) {
         
        //console.log("from:" + from + " to:" + to + " cost:" + cost + " Path: " + paths);
        
        paths.push(from);
        
        if (!(this.edges[from][to])) {
        	this.edges[from][to] = cost;              
        }
        
        //cost += this.edges[from][to];  
        cost += this.edges[from][to];
        
		this.visited.push(from); 

        if (from==to) {             
            console.log("Found");
            this.displayPath(paths,cost);
            alert(this.displayPath(paths,cost));
            return paths;
        } 
        
        //console.log(paths);
        var theNeighbors = this.neighbors(from);
        
        console.log("neighbors: " + from + " --> " + theNeighbors);     
        
        for (var i=0;i<theNeighbors.length;i++) {
            
            var newF = theNeighbors[i];
            
console.log("from:" + newF + " to:" + to + " cost:" + cost + " Path: " + paths);
            
            cost +=...