Running graph0_starter12.js

➕︎ Aa ➖︎ |Dark 1Dark 2Light|HackInput Mono|Back to  PT Mono
// CPCS 324 Algorithms & Data Structures 2
// Graph data structure starter - Final Project
// 2019, 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
//


var _v = [], _e = [];   // note naming conventions in upload guide


// -----------------------------------------------------------------------
function _main()   
{
        
}


// -----------------------------------------------------------------------
// similar to starter 8
function Vertex(v)
{

	
}

// -----------------------------------------------------------------------
// similar to starter 8
function Edge(vert_i,weight)
{


}


// -----------------------------------------------------------------------
// similar to starter 8 (NO network methods)
function Graph()
{


}


// -----------------------------------------------------------------------
// functions used by methods of Graph and ancillary objects


function make_graphImpl(n, m, w)   // feel free to change, if needed
{
    // parameter validations and checks: number of edges etc.
	var mmax = n*(n-1);
	if ( ! this.digraph ) mmax /= 2;
	if (m>mmax)
	{
		document.write("<p>ERROR: invalid number of edges for graph type</p>");
		return;
	}
	
	// create n vertex in v[] using id 0 to n-1 as label
	var v=[];
	for (var i=0; i<n; i++)
		v[i] = {label:i.toString()};

	// if graph complete no need to generate random edges, just create mmax edges systematically
	

	// otherwise repreat create m distinct edges (graph loops not allowed)
	
	var e=[], wmin=1, wmax = 50000, wsum=0;
	
	var h = [];   // quick-dirty n x n matrix to check previously generated edges, 
	              // m-entry hash table would be more efficient
	for (i=0; i<n; i++)    
	{
		h[i] = []; h[i][i]=0;    // no graph loops; 0 = blocked pair of vertices
	}
	
	for (i=0; i<m; i++)
	{
		// generate vertices u, v randomly
		do 
		{
			var u_i = random(0,n-1), v_i = random(0,n-1);
		
		} while ( h[u_i][v_i] != undefined );
		
		h[u_i][v_i] = 0; h[v_i][u_i] = 0;     // update matrix: block u,v; block v,u also if undirected
		
		// if (u,v) is distinct insert in e[] (generate random weight if w true)
		// otherwise repeat generate another u,v pair
	
		e[i] = {u:u_i, v:v_i};
		if (w)
		{
			e[i].w = random(wmin,wmax);
			wsum += e[i].w;
		}
	}

	// call graph reader method and set label, graph type depends on value of digraph property
	this.read_graph(v,e);
	this.label = "Generated "+n+" vertices, "+m+" random "+(!this.digraph?"un":"")+"directed edges ("+Math.round(m/mmax*100)+"%)"+(w?", ave weight = "+Math.round(wsum/m):"");
}

function random(low,high)
{
	return Math.floor(Math.random()*(high-low+1))+low;
}


// -----------------------------------------------------------------------
// begin student code section (NO network functions, only code related to this project)
// -----------------------------------------------------------------------

// Final M2 code here





// -----------------------------------------------------------------------
// paste your heap package here


function Heap()
{

}

// -----------------------------------------------------------------------
function heapShow()
{

}   // etc.


// -----------------------------------------------------------------------
// paste your PQ package here (version with calls to heap methods only)



// -----------------------------------------------------------------------
// published docs section (ref. assignment page)
// similar to starters 8 and 11
// *NO* JSDOC comments in this section
// -----------------------------------------------------------------------

function list_vert()
{

}   // etc.