➕︎ Aa ➖︎ |Dark 1 ● Dark 2 ● Light|Hack ● Fira Code|Back to PT Mono✖
// CPCS 324 Algorithms & Data Structures 2
// Graph data structure starter - Reorganized Code
// 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
// note carefully close-to-final source file organization
var _v = [], _e = []; // globals used by standard graph reader method
// -----------------------------------------------------------------------
// a main-like global function for the caller page
// only function allowed to access global vars
function _main()
{
// create a graph (default undirected), note no longer a global var
var g = new Graph();
// set graph properties - set a suitable label
}
// -----------------------------------------------------------------------
// Vertex object constructor
function Vertex(v)
{
this.label = v.label; // vertex can be labelled
this.visit = false; // vertex can be marked visited or "seen"
this.adjacent = new List(); // init an adjacency list
// --------------------
// student property fields next
// --------------------
// member methods use functions defined below
}
// -----------------------------------------------------------------------
// Graph object constructor
function Graph()
{
this.verts = []; // vertex list (an array of Vertex objects)
this.nv; // number of vertices
this.ne; // number of edges
this.digraph = false; // true if digraph, false otherwise (default undirected)
this.dfs_push = []; // DFS order output
this.bfs_out = []; // BFS order output
// --------------------
// student property fields next
this.label // (fill) identification string to label graph
// --------------------
// member methods use functions defined below
this.read_graph = better_input; // default input reader method
this.print_graph = list_verts; // (replace) better printer function
this.add_edge = add_edge;
this.DFS = DFS; // perform a depth-first search
this.dfs = dfs; // DFS a connected component
this.BFS = BFS; // perform a breadth-first search
this.bfs = bfs; // BFS a connected component
// --------------------
// student methods next; implementing functions in student code section at end
}
// -------------------------------------------------------
// 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()
{
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>" ); // correct encapsulation issue
}
}
// --------------------
function add_edge(u_i, v_i)
{
}
// --------------------
function better_input(v, e)
{
}
// --------------------
function DFS()
{
}
// --------------------
function dfs(v_i)
{
}
// --------------------
function BFS()
{
}
// --------------------
function bfs(v_i)
{
}
// -----------------------------------------------------------------------
// -----------------------------------------------------------------------
// --- begin student code section ----------------------------------------
function better_output() // new default graph output method
{
// graph properties (see ref output)
// list vertices
}
// --------------------
function adjacentByID() // initally just a wrapper for .traverse
{
}