Running graph0_starter2.js

// CPCS 324 Algorithms & Data Structures 2
// Graph data structure starter - First Edge Implementation
// 2020, Dr. Muhammad Al-Hashimi

// -----------------------------------------------------------------------
// simple graph object with linked-list edge implementation and minimal fields
// extra vertex and edge member fields and methods to be added later as needed


// graph from Figure 3.10 (Levitin, 3rd edition)
// read info to configure *user* property fields of Vertex object,
// only one for now: label, rest are internal; property fields can
// be listed in any order

var _v = [
   {label:"a"},
   {label:"b"},
   {label:"c"},
   {label:"d"},
   {label:"e"},
   {label:"f"},
   {label:"g"},
   {label:"h"},
   {label:"i"},
   {label:"j"}

   ];

var _e = [
   {u:0, v:3},
   {u:0, v:2},
   {u:3, v:2},
   {u:2, v:5},
   {u:5, v:4},
   {u:5, v:1},
   {u:1, v:4},
   {u:0, v:4},
   {u:6, v:7},
   {u:7, v:8},
   {u:8, v:9},
   {u:9, v:6}

   ];


// create a graph (default undirected)
var _g = new Graph();

// if g is directed (digraph) change property BEFORE input
// _g.digraph = true;

// use global input arrays _v and _e to initialize its internal data structures
_g.read_graph(_v,_e);


// -----------------------------------------------------------------------
// Vertex object constructor

function Vertex(v)
{
   // user input fields

   this.label = v.label;          // vertex can be labelled

   // more fields to initialize internally

   this.visit = false;            // vertex can be marked visited (useful for traversals)
   this.adjacent =                // (fill code) init an adjacency list
}

// -----------------------------------------------------------------------
// Graph object constructor

function Graph()
{
   this.verts = [];               // vertex list (array of Vertex objects)
   this.nv;                       // number of vertices
                                  // (fill code) number of edges
                                  // (fill code) true if digraph, false otherwise (default undirected)


   // --------------------
   // member methods use functions defined below

   this.read_graph = better_input;  // note new default input reader method
   this.print_graph = list_verts;
   this.add_edge =                  // (fill code) specify function to implement this interface method

}


// -------------------------------------------------------
// Functions used by methods of Graph object. Similar to
// normal functions but use object member fields and
// methods, depending on which object is passed by the
// method call through the self variable: this.
//

// --------------------
function list_verts()    // simple vertex lister
{
   // i,v function local vars, verts[] object var via this

   for (var i=0; i < this.nv; i++)
   {
      var v = this.verts[i];
      document.write( "VERTEX: ", i,
         " {", v.label, "} - VISIT: ", v.visit,
         " - ADJACENCY: ", v.adjacent.traverse(), "<br>" ); // note change (linked list call)
   }
}

// --------------------
function add_edge(u_i,v_i)           // pass vert id
{
   // fetch edge vertices using their id, where u: source vertex, v: target vertex


   // insert (u,v), i.e., insert v (by id) in adjacency list of u


   // insert (v,u) if undirected graph (repeat above but reverse vertex order)


}

// --------------------
// default graph input method (args v,e are local to func, to be passed as parameters on call)
// i.e., don't use the globals inside
function better_input(v,e)
{

   // set vertex and edge count fields



   // input vertices into internal vertex array



   // input vertex pairs from edge list input array
   // remember to pass vertex ids to add_edge()



   // double edge count if graph undirected

}