<commit_before>function Vertex(name) {
  this._name = name;
}

function Edge(edge) {
  this._v1 = edge.v1;
  this._v2 = edge.v2;
  this._weight = edge.weight || true;
  this._directed = edge.directed || false;
}

function Graph(vertices, edges) {
  this._V = vertices;
  this._E = edges;

  this._V.forEach(function(elem, index) {
    elem._index = index;
  });
}

/* MODIFY THE GRAPH */
Graph.prototype.push = function() {}
Graph.prototype.remove = function() {}

Graph.prototype.sortEdges = function() {
  this._E = this._E.sort(function(a, b) {
    var from = a._v1._index - b._v1._index;
    var to = a._v2._index - b._v2._index;
    var result = (from !== 0 ? from : to);
    return result;
  });
  return this;
}

/* INSPECT THE GRAPH */
Graph.prototype.isWeighted = function() {
  return this._E.some(function(edge) {
    return typeof edge._weight === "number";
  });
}

Graph.prototype.isUnweighted = function() {
  return !this.isWeighted();
}

Graph.prototype.isDirected = function() {
  return this._E.some(function(edge) {
    return edge._directed;
  });
}

Graph.prototype.isUndirected = function() {
  return !this.isDirected();
}

Graph.prototype.hasLoops = function() {
  return this._E.some(function(edge) {
    return edge._v1 === edge._v2;
  });
}

Graph.prototype.hasParallels = function() {
  var vertexCardinality = this._V.length;
  var adjacencymatrix = [];
  var isDirected = this.isDirected();

  // O(|V|)
  for (var i = 0; i < vertexCardinality; i++) {
    adjacencymatrix.push([]);
  }

  return this._E.some(function(edge) {
    var v1 = edge._v1._index;
    var v2 = edge._v2._index;
    var result;

    if (isDirected) {
      result = adjacencymatrix[v1][v2];
      adjacencymatrix[v1][v2] = true;
    } else {
      result = adjacencymatrix[Math.max(v1,v2)][Math.min(v1,v2)];
      adjacencymatrix[Math.max(v1,v2)][Math.min(v1,v2)] = true;
    }

    return !!result;
  });
}

Graph.prototype.isSpanning = function() {
  var vertexCardinality = this._V.length;
  var span = new Array(vertexCardinality);
  this._E.forEach(function(edge) {
    span[edge._v1._index] = true;
    span[edge._v2._index] = true;
  });

  // Arrays initialized with a length don't guarantee full iteration.
  var count = 0;
  var truthy = span.every(function(elem) { count++; return !!elem; });

  return count === vertexCardinality && truthy;
}

Graph.prototype.isConnected = function() {
  // Quick check, make sure that from/to spans all vertices.
  if (!this.isSpanning()) { return false; }

  var vertexCardinality = this._V.length;
  var span = new Array(vertexCardinality);

  function traverse(neighbors, vertex, lookup) {
    if (span[vertex]) { return; }

    span[vertex] = true;
    neighbors.forEach(function(vertex) {
      traverse(lookup[vertex], vertex, lookup);
    });
  }

  // Create a from-to lookup.
  var lookup = [];
  for (var i = 0; i < vertexCardinality; i++) {
    lookup.push([]);
  }

  // Depth first search.
  if (this.isUndirected()) {
    // When setting up the lookup, make sure t goes both ways.
    this._E.forEach(function(edge) {
      lookup[edge._v1._index].push(edge._v2._index);
      lookup[edge._v2._index].push(edge._v1._index);
    });

    // Can start with any vertex.
    traverse(lookup[0], 0, lookup);

    // Arrays initialized with a length don't guarantee full iteration.
    var count = 0;
    var truthy = span.every(function(elem) { count++; return !!elem; });

    return count === vertexCardinality && truthy;
  } else {
    this._E.forEach(function(edge) {
      lookup[edge._v1._index].push(edge._v2._index);
    });
  }
}
Graph.prototype.isWeaklyConnected = function() {}
Graph.prototype.isTree = function() {}
Graph.prototype.isPlanar = function() {}
Graph.prototype.hasCycles = function() {}

/* TRANSFORM THE GRAPH */
Graph.prototype.unparalleled = function() {
  // Remove all parallel edges from the graph.
  var vertexCardinality = this._V.length;
  var adjacencymatrix = [];
  var isDirected = this.isDirected();
  var isWeighted = this.isWeighted();

  // O(|V|)<commit_msg>I guess that I do not know what connected means.<commit_after>function Vertex(name) {
  this._name = name;
}

function Edge(edge) {
  this._v1 = edge.v1;
  this._v2 = edge.v2;
  this._weight = edge.weight || true;
  this._directed = edge.directed || false;
}

function Graph(vertices, edges) {
  this._V = vertices;
  this._E = edges;

  this._V.forEach(function(elem, index) {
    elem._index = index;
  });
}

/* MODIFY THE GRAPH */
Graph.prototype.push = function() {}
Graph.prototype.remove = function() {}

Graph.prototype.sortEdges = function() {
  this._E = this._E.sort(function(a, b) {
    var from = a._v1._index - b._v1._index;
    var to = a._v2._index - b._v2._index;
    var result = (from !== 0 ? from : to);
    return result;
  });
  return this;
}

/* INSPECT THE GRAPH */
Graph.prototype.isWeighted = function() {
  return this._E.some(function(edge) {
    return typeof edge._weight === "number";
  });
}

Graph.prototype.isUnweighted = function() {
  return !this.isWeighted();
}

Graph.prototype.isDirected = function() {
  return this._E.some(function(edge) {
    return edge._directed;
  });
}

Graph.prototype.isUndirected = function() {
  return !this.isDirected();
}

Graph.prototype.hasLoops = function() {
  return this._E.some(function(edge) {
    return edge._v1 === edge._v2;
  });
}

Graph.prototype.hasParallels = function() {
  var vertexCardinality = this._V.length;
  var adjacencymatrix = [];
  var isDirected = this.isDirected();

  // O(|V|)
  for (var i = 0; i < vertexCardinality; i++) {
    adjacencymatrix.push([]);
  }

  return this._E.some(function(edge) {
    var v1 = edge._v1._index;
    var v2 = edge._v2._index;
    var result;

    if (isDirected) {
      result = adjacencymatrix[v1][v2];
      adjacencymatrix[v1][v2] = true;
    } else {
      result = adjacencymatrix[Math.max(v1,v2)][Math.min(v1,v2)];
      adjacencymatrix[Math.max(v1,v2)][Math.min(v1,v2)] = true;
    }

    return !!result;
  });
}

Graph.prototype.isSpanning = function() {
  var vertexCardinality = this._V.length;
  var span = new Array(vertexCardinality);
  this._E.forEach(function(edge) {
    span[edge._v1._index] = true;
    span[edge._v2._index] = true;
  });

  // Arrays initialized with a length don't guarantee full iteration.
  var iterations = 0;
  var truthy = span.every(function(elem) { iterations++; return !!elem; });

  return iterations === vertexCardinality && truthy;
}

Graph.prototype.isStronglyConnected = function() {
  // Quick check, make sure that from/to spans all vertices.
  if (!this.isSpanning()) { return false; }

  var vertexCardinality = this._V.length;
  var span = new Array(vertexCardinality);

  function traverse(neighbors, vertex, lookup) {
    if (span[vertex]) { return; }

    span[vertex] = true;
    neighbors.forEach(function(vertex) {
      traverse(lookup[vertex], vertex, lookup);
    });
  }

  // Create a from-to lookup.
  var lookup = [];
  var reverselookup = [];
  for (var i = 0; i < vertexCardinality; i++) {
    lookup.push([]);
    reverselookup.push([]);
  }

  // Depth first search.
  if (this.isUndirected()) {
    // When setting up the lookup, make sure t goes both ways.
    this._E.forEach(function(edge) {
      lookup[edge._v1._index].push(edge._v2._index);
      lookup[edge._v2._index].push(edge._v1._index);
    });

    // Can start with any vertex.
    traverse(lookup[0], 0, lookup);
  } else {
    this._E.forEach(function(edge) {
      // The outgoing edges from each vertex.
      lookup[edge._v1._index].push(edge._v2._index);
      // The incoming edges to each vertex.
      reverselookup[edge._v2._index].push(edge._v1._index);
    });

    // Identify/count nodes with zero incoming.
    var root;
    var count = 0;
    reverselookup.forEach(function(incoming, index) {
      if (incoming.length === 0) {
        root = index;
        count++;
      }
    });

    // We're not connected if more than one node has no incoming connections.
    if (count > 1) { return false; }

    // It might be a tree.
    if (count === 1) {
      traverse(lookup[root], root, lookup);
    }

    if (count === 0) {
      traverse(lookup[0], 0, lookup);
    }
  }

  // Arrays initialized with a length don't guarantee full iteration.
  var iterations = 0;
  var truthy = span.every(function(elem) { iterations++; return !!elem; });

  return iterations === vertexCardinality && truthy;
}

Graph.prototype.isWeaklyConnected = function() {
  return this.undirected().isConnected();
}

Graph.prototype.isTree = function() {}
Graph.prototype.isPlanar = function() {}
Graph.prototype.hasCycles = function() {}

/* TRANSFORM THE GRAPH */
Graph.prototype.unparalleled = function() {
  // Remove all parallel edges from the graph.
  var vertexCardinality = this._V.length;
  var adjacencymatrix = [];
  var isDirected = this.isDirected();
  var isWeighted = this.isWeighted();

  // O(|V|)
{'fraction_non_alphanumeric': 0.153381777529346, 'fraction_numerical': 0.010173281162660704, 'mean_word_length': 3.1901639344262294, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2434205', 'n_tokens_mistral': 3150, 'n_tokens_neox': 3019, 'n_words': 678}