➕︎ Aa ➖︎ |Dark 1 ● Dark 2 ● Light|Hack ● Fira Code|Back to PT Mono✖
// CPCS 324 Algorithms & Data Structures 2
// Graph data structure starter - First Edge Object
// 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
//
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)
// set input graph properties (label, directed etc.)
// use global input arrays _v and _e to initialize its internal data structures
// use print_graph() method to check graph
// report connectivity status if available
// perform depth-first search and output stored result
// report connectivity status if available
// perform breadth-first search and output stored result
// output the graph adjacency matrix
}
// -----------------------------------------------------------------------
// 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
// return target id of incident edges in array
}
// -----------------------------------------------------------------------
// Edge object constructor
// -----------------------------------------------------------------------
// 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
this.label = ""; // identification string to label graph
// --------------------
// student property fields next
// number of connected comps set by DFS; 0 (default) for no info
this.adjMatrix // (fill) graph adjacency matrix to be created on demand
// --------------------
// member methods use functions defined below
this.read_graph = better_input; // default input reader method
this.print_graph = better_output; // better printer function
this.list_verts = list_verts;
this.add_edge = add_edge; // replace (don't change old .add_edge)
this.dfs = dfs; // DFS a connected component
this.bfs = bfs; // BFS a connected component
// --------------------
// student methods next; implementing functions in student code section at end
// perform a topological search
}
// -------------------------------------------------------
// 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.adjacentByID(), "<br>" ); // note correction
}
}
// --------------------
function add_edge(u_i, v_i)
{
}
// --------------------
function better_input(v, e)
{
}
// --------------------
function dfs(v_i)
{
}
// --------------------
function bfs(v_i)
{
}
// --------------------
function better_output()
{
document.write("<p>GRAPH {",this.label, "} ", this.digraph?"":"UN", "DIRECTED - ", this.nv, " VERTICES, ",
this.ne, " EDGES:</p>");
// list vertices
this.list_verts();
}
// -----------------------------------------------------------------------
// -----------------------------------------------------------------------
// --- begin student code section ----------------------------------------
function adjacentByID()
{
}
// --------------------
function add_edge2(u_i,v_i)
{
// fetch vertices using their id, where u: edge source vertex, v: target vertex
// insert (u,v), i.e., insert v in adjacency list of u
// (first create edge object using v_i as target, then pass object)
// insert (v,u) if undirected graph (repeat above but reverse vertex order)
}
// --------------------
function topoSearch()
{
}
// --------------------
function makeAdjMatrix()
{
}