#!/usr/bin/env python # coding: utf-8 # # Data Structures and Algorithm Project # ## Title: Graph Theoretical Modeling of a Social Network # ## Objectives:
# #
    # #
  1. To be able to utilize a graph data structure to represent the people (nodes) # and friendships in a social network. The social graph should contain at least 50 nodes.
    2. # #
  2. To be able to implement either Adjacency-Matrix representation or Adjacency-List # representation of Graph ADT.
    3. # #
  3. To be able to implement simple Euler and Hamilton paths in the social network graph.
    4. # #
  4. To be able to implement Depth First Search (DFS) and Breadth-First Search (BFS) to # the social network graph.
    5. # #
  5. To be able to represent a social network graph as a Minimum Spanning Tree using either # Prim's, Kruskal's, or Boruvka's algorithm.
    6. # #
  6. To be able to apply shortest path algorithms, i.e. Dijkstra's algorithm to the social network.
    7. # #
  7. (OPTIONAL) To be able to apply Network flow algorithms, i.e. Mincost-Flow Reductions, to the social network.
    8. # #
# # ## Starter Files
# The starter program has already been implemented and can be accessed here: # In[7]: from IPython.display import IFrame IFrame('https://docs.google.com/a/dlsu.edu.ph/file/d/0B6GYu_QtcFzQNm1Db3ptazByd28/preview', width='100%', height=100) # Note: Please use your DLSU gmail account to access the file. # In this project, we are extending Stanford CS 106a's Assignment (FacePamphlet): # In[8]: from IPython.display import IFrame IFrame('https://docs.google.com/a/dlsu.edu.ph/file/d/0B6GYu_QtcFzQdnBXQmdWdkZpRTg/preview', width='100%', height=888) # ##### Note: Algorithm details will be discussed in the lectures. # ## Deliverables
# #
    # #
  1. Documentation Report (with 2 initial progress reports): 40 %
    2. # #
  2. Prototype: 30 %
    3. # #
  3. Presentation: 30 %
    4. # #
# ## Deadlines: # #
    # #
  1. First Progress Report: April 7, 2015 (Tue)
    2. # #
  2. Second Progress Report: April 14, 2015 (Tue)
    3. # #
  3. Final Documentation Report, Prototype, and Presentation: April 20, 2015 (Mon)
    4. # #
# -mkc