<commit_before>/**
 * ECE 454/750: Distributed Computing
 * <p/>
 * Code written by <NAME>, University of Waterloo, 2015
 * Addendum Authors:
 * 1) <NAME> <EMAIL>
 * <p/>
 */

package ece454750s15a2;

import java.io.*;
import java.util.*;

public class TriangleCountImpl {
    private byte[] input;
    private int numCores;

    public TriangleCountImpl(byte[] input, int numCores) {
        this.input = input;
        this.numCores = numCores;
    }

    public List<String> getGroupMembers() {
        ArrayList<String> ret = new ArrayList<String>();
        ret.add("s244sing");
        ret.add("cpinn");
        return ret;
    }

    public List<Triangle> enumerateTriangles() throws IOException {
        // this code is single-threaded and ignores numCores

        ArrayList<ArrayList<Integer>> adjacencyList = getAdjacencyList(input);
        ArrayList<Triangle> ret = new ArrayList<Triangle>();

        // naive triangle counting algorithm
        int numVertices = adjacencyList.size();
        for (int i = 0; i < numVertices; i++) {
            ArrayList<Integer> n1 = adjacencyList.get(i);
            for (int j : n1) {
                ArrayList<Integer> n2 = adjacencyList.get(j);
                for (int k : n2) {
                    ArrayList<Integer> n3 = adjacencyList.get(k);
                    for (int l : n3) {
                        if (i < j && j < k && l == i) {
                            ret.add(new Triangle(i, j, k));
                        }
                    }
                }
            }
        }

        return ret;
    }

    public ArrayList<ArrayList<Integer>> getAdjacencyList(byte[] data) throws IOException {
        InputStream istream = new ByteArrayInputStream(data);
        BufferedReader br = new BufferedReader(new InputStreamReader(istream));
        String strLine = br.readLine();
        if (!strLine.contains("vertices") || !strLine.contains("edges")) {
            System.err.println("Invalid graph file format. Offending line: " + strLine);<commit_msg>Adding AdjacencyMatrix Implementation.<commit_after>/**
 * ECE 454/750: Distributed Computing
 * <p/>
 * Code written by <NAME>, University of Waterloo, 2015
 * Addendum Author(s):
 * 1) <NAME> <EMAIL>
 * Wrote:
 *  a) Adjacency Matrix Graph representation
 * <p/>
 */

package ece454750s15a2;

import java.io.*;
import java.io.IOError;
import java.io.IOException;
import java.lang.Integer;
import java.lang.Iterable;
import java.lang.RuntimeException;
import java.util.*;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class TriangleCountImpl {
    private byte[] input;
    private int numCores;

    public TriangleCountImpl(byte[] input, int numCores) {
        this.input = input;
        this.numCores = numCores;
    }

    public class AdjMatrixGraph {
        private int V;
        private int E;
        private boolean[][] adjMatrix;

        public AdjMatrixGraph(int V) {
            if (V < 0) throw new RuntimeException("Number of vertices cannot be negative.");
            this.V = V;
            this.E = 0;
            this.adjMatrix = new boolean[V][V];
        }

        private class AdjIterator implements Iterator<Integer>, Iterable<Integer> {
            int v, w = 0;
            AdjIterator(int v) { this.v = v; }

            public Iterator<Integer> iterator() { return this; }

            public boolean hasNext() {
                while (w < V) {
                    if (adjMatrix[v][w])
                        return true;
                    w++;
                }
                return false;
            }

            public Integer next() {
                if (hasNext())
                    return w++;
                else
                    throw new NoSuchElementException();
            }

            public void remove()  { throw new UnsupportedOperationException();  }
        }

        public int getVCount() {
            return this.V;
        }
        public int getECount() {
            return this.E;
        }

        public void addEdge(int x, int y) {
            if(!this.adjMatrix[x][y]) // Only increment if new edge.
                this.E++;
            this.adjMatrix[x][y] = true;
            this.adjMatrix[y][x] = true;
        }

        public boolean contains(int x, int y) {
            return this.adjMatrix[x][y];
        }

        public Iterable<Integer> adjMatrix(int v) {
            return new AdjIterator(v);
        }

    }

    public List<String> getGroupMembers() {
        ArrayList<String> ret = new ArrayList<String>();
        ret.add("s244sing");
        ret.add("cpinn");
        return ret;
    }

    public List<Triangle> enumerateTrianglesNaive() throws IOException {
        // this code is single-threaded and ignores numCores

        ArrayList<ArrayList<Integer>> adjacencyList = getAdjacencyList(input);
        ArrayList<Triangle> ret = new ArrayList<Triangle>();

        // naive triangle counting algorithm. 0xBOOOHISS
        int numVertices = adjacencyList.size();
        for (int i = 0; i < numVertices; i++) {
            ArrayList<Integer> n1 = adjacencyList.get(i);
            for (int j : n1) {
                ArrayList<Integer> n2 = adjacencyList.get(j);
                for (int k : n2) {
                    ArrayList<Integer> n3 = adjacencyList.get(k);
                    for (int l : n3) {
                        if (i < j && j < k && l == i) {
                            ret.add(new Triangle(i, j, k));
                        }
                    }
                }
            }
        }
        return ret;
    }

    public List<Triangle> enumerateTriangles() throws IOException {
        // TODO: Utilize ncores and parallelize

        AdjMatrixGraph adjacencyMatrix = getAdjacencyMatrix(input);
        ArrayList<Triangle> ret = new ArrayList<Triangle>();

        // TODO: Add logic to compute the trace of the matrix

        return ret;
    }


    public AdjMatrixGraph getAdjacencyMatrix(byte[] data) throws IOException {
        System.out.println("Algorithm: Adjacency Matrix Scheme");

        InputStream istream = new ByteArrayInputStream(data);
        BufferedReader br = new BufferedReader(new InputStreamReader(istream));
        String strLine = br.readLine();
        if (!strLine.contains("vertices") || !strLine.contains("edges")) {
            System.err.println("Invalid graph file format. Offending line: " + strLine);
            System.exit(-1);
        }
        String parts[] = strLine.split(", ");
        int numVertices = Integer.parseInt(parts[0].split(" ")[0]);
        int numEdges = Integer.parseInt(parts[1].split(" ")[0]);
        System.out.println("Found graph with " + numVertices + " vertices and " + numEdges + " edges");

        AdjMatrixGraph adjMatrix = new AdjMatrixGraph(numVertices);

        while((strLine = br.readLine()) != null && !strLine.equals("")) {
            parts = strLine.split(": ");
            int current_vertex = Integer.parseInt(parts[0]);
            if (parts.length > 1) { // we haz edges!
                parts = parts[1].split(" +");
                for(String edge : parts) {
                    adjMatrix.addEdge(current_vertex, Integer.parseInt(edge));
                }
            }
        }

        return adjMatrix;
    }

    public ArrayList<ArrayList<Integer>> getAdjacencyList(byte[] data) throws IOException {
        InputStream istream = new ByteArrayInputStream(data);
        BufferedReader br = new BufferedReader(new InputStreamReader(istream));
        String strLine = br.readLine();
        if (!strLine.contains("vertices") || !strLine.contains("edges")) {
            System.err.println("Invalid graph file format. Offending line: " + strLine);
{'fraction_non_alphanumeric': 0.11366869261606104, 'fraction_numerical': 0.009310746152851416, 'mean_word_length': 1.9395667046750285, 'pattern_counts': {'":': 1, '<': 54, '<?xml version=': 0, '>': 47, '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': '3627612', 'n_tokens_mistral': 2227, 'n_tokens_neox': 2084, 'n_words': 556}