D3 visualization of a Facebook friend graph

Question

I've been learning Python for about a year and now I'm trying to improve my JavaScript. I wrote this simple d3 visualization that shows your Facebook friends as a force-directed graph. Here's a live version and here's the source on GitHub. It works well, but it can be slow.

I understand that the number of edges to calculate grows \$O(n^2)\$ with nodes, so complexity increases quickly for users with lots of friends, but I'm wondering if:

1. there are any obvious optimizations I could make

2. what bad habits I might be importing from Python

3. how I might tweak the layout parameters to reach equilibrium faster

I'm pretty new to programming and very new to JavaScript, so I'm sure I'm making some mistakes.

Content of file friendgraph.js:

// Facebook SDK

// Initialize the Facebook SDK
window.fbAsyncInit = function () {
    FB.init({
        appId: '341827359241906', // App ID
        channelUrl: 'channel.html', // Path to your Channel File
        status: true, // check login status
        cookie: true, // enable cookies to allow the server to access the session
        xfbml: true  // parse XFBML
});

// Listen for and handle auth.statusChange events
FB.Event.subscribe('auth.statusChange', function(response) {
    if (response.authResponse) {
        // On login...
        FB.api('/me', function(me) {
            if (me.name) {
                // Display user name
                document.getElementById('auth-displayname').innerHTML = me.name;
                // Retrieve friends API object
                FB.api('/me/friends', getFriends);
            }
        })
        document.getElementById('auth-loggedout').style.display = 'none';
        document.getElementById('auth-loggedin').style.display = 'block';
    } else {
        // User has not authorized your app or isn't logged in
        document.getElementById('auth-loggedout').style.display = 'block';
        document.getElementById('auth-loggedin').style.display = 'none';
    }
    });

    // Respond to clicks on login and logout links
    document.getElementById('auth-loginlink').addEventListener('click', function() {
        FB.login();
    });
    document.getElementById('auth-logoutlink').addEventListener('click', function(){
        FB.logout();
    });
}

function indexWithAttribute(array, attr, value) {
    // Iterates over an array and returns the index of the element
    // whose attribute matches the given value. 
    for(var i=0; i < array.length; i++) {
        if(array[i][attr] === value) {
            return i;
        } 
    }
}

function showName(d) {
    // Displays given d3 node's 'name' attribute.
    document.getElementById('selected-friend-name').innerHTML = d['name'];
}

function getMutualFriends(id, friends, friendlinks) {
    // Retrieves a Facebook API object containing mutual friends
    // for a given user ID. Passes it to the getLinks() function.
    FB.api('/me/mutualfriends/' + id, function (response) {
        getLinks(response, id, friends, friendlinks); }
    );
}

function getLinks(response, id, friends, friendlinks) {
    // Calculates links between mutual friends and pushes them to an array.
    // Displays percent of friend links completed in 'load-status' div. 
    var mutualFriends = response['data'];
    var sourceIndex = indexWithAttribute(friends, 'id', id);

    var completed = Math.round(100*(sourceIndex/friends.length));

    document.getElementById('load-status').innerHTML = 'Calculating mutual friend links: ' + completed + '%'    
    for (i=0; i< mutualFriends.length; i++) {
            friends[sourceIndex]['value'] = mutualFriends.length;
            targetIndex = indexWithAttribute(friends, 'id', mutualFriends[i]['id']);
            friendlinks.push({'source':sourceIndex, 
                              'target':targetIndex,
                              'value':mutualFriends.length });
    }       

    if (sourceIndex === friends.length - 1) { 
        graphFriends(friends, friendlinks); }        
}

function getFriends(response) {
    // Loads friend nodes as an array. Creates array to hold links between mutual friends.
    var friends = response['data']
    var friendlinks = []

    for (i=0; i < friends.length; i++) {
        var id = friends[i]['id'];
        getMutualFriends(id, friends, friendlinks);
    }
}

function graphFriends(friends, friendlinks) {
    // Configures a d3 force-directed graph of friends and friend links.
    document.getElementById('load-status').innerHTML = ''

    // Set dimensions of svg
    var width = window.innerWidth - 100,
        height = window.innerHeight - 100;

    // Set up a 10-color scale for node colors
    var color = d3.scale.category10()

    // Set up a linear scale to map number of mutual
    // friends to node radius
    var r = d3.scale.linear()
                .domain([1,100])
                .range([5,15])

    // Set the initial parameters of the force() layout
    var force = d3.layout.force()
        .charge(-75)
        .linkDistance(40)
        .size([width / 1.2, height / 2])

    // Add svg and start visualization
    var svg = d3.select("#viz").append("svg")
        .attr("width", width)
        .attr("height", height);

    // Pass in friends array as graph nodes and friendlinks
    // array as graph edges.
    force.nodes(friends)
        .links(friendlinks)
        .start();

    var link = svg.selectAll("line.link")
        .data(friendlinks)
      .enter().append("line")
        .attr("class", "link")
        .style("stroke", "#eee")
        .style("stroke-width", 1);

    var node = svg.selectAll("circle.node")
        .data(friends)
      .enter().append("circle")
        .attr("class", "node")
        .attr("r", function(d) { return r(d.value); })
        .style("stroke", "#eee")
        .style("fill", function(d) { return color(d.value); })
        .on("mouseover", function(d) { showName(d); })
        .call(force.drag);

    force.on("tick", function() {
       link.attr("x1", function(d) { return d.source.x; })
           .attr("y1", function(d) { return d.source.y; })
           .attr("x2", function(d) { return d.target.x; })
           .attr("y2", function(d) { return d.target.y; });

       node.attr("cx", function(d) { return d.x; })
           .attr("cy", function(d) { return d.y; });
     });
}

index.html:

<!DOCTYPE html>
<html>
    <head>
        <script type="text/javascript" src="http://d3js.org/d3.v2.js"></script>
        <script type="text/javascript" src="http://connect.facebook.net/en_US/all.js">
        </script>
        <script type="text/javascript" src="friendgraph.js">        
        </script>
        <title>d3.js Facebook friend visualization</title>
    </head>
    <body>
        <div id="viz">
        </div>
        <div id="fb-root">
            <div><p>
                <h3>d3.js Facebook graph visualization</h3>
                by <a href="http://twitter.com/ecmendenhall">ecmendenhall</a></p>
            </div>
            <div id="selected-friend-name"></div>
            <div id="auth-status">
                <div id="auth-loggedout">
                    <a href="#" id="auth-loginlink">Login</a>
                </div>
            <div id="auth-loggedin" style="display:none">
          Logged in as <span id="auth-displayname"></span>  
        (<a href="#" id="auth-logoutlink">logout</a>)
            </div>
            <div id="load-status"></div>
        </div>
    </body>
</html>

Answer 1

I couldn't test out your application since I don't have a facebook account but here are some tips:

1) Use dot notation instead of bracket notation to access known property names.

Old Code:

friends[sourceIndex]['value'];

New Code:

friends[sourceIndex].value;

2) Keep the operations peformed within a loop to the bare minimum.

For performance, it's best to avoid nested loops and function calls within a loop.

From your code:

//...
function indexWithAttribute(array, attr, value) {
    for (var i = 0; i < array.length; i++) {
        if (array[i][attr] === value) {
            return i;
        }
    }
}
//...
function getLinks(response, id, friends, friendlinks) {
//...
    for (i = 0; i < mutualFriends.length; i++) {
        friends[sourceIndex]['value'] = mutualFriends.length;
        targetIndex = indexWithAttribute(friends, 'id', mutualFriends[i]['id']);
//...

The code above is bad for performance because the for loop contains calls to indexWithAttribute(), which contains another for loop. The deeply nested iterations will result in O(N^2) completion time.

One possible solution for this problem would be to create a hash table for the ids to index relationship. Hash tables take O(1) to find a value but require more memory, unlike a for loop O(n/2).

Code:

/**
* Returns a lookup table for the relationship (key)attribute to (value)index from an array of objects.
* This function expects that all referenced attributes will have a unique value.
* 
* @author Larry Battle <bateru.com/news>
* @param [Array] arr - An array of objects.
* @param [String] attr - A common property name amoung all the objects in `arr`.
* @returns [Object]
* @example

    var arr = [
        { id: 2 },
        { id: 12 },
        { id: 89 }
    ];
    var hash = createAttributeToIndexTable( arr, "id" );
    console.log( JSON.stringify( hash ) = '{"2":0,"12":1,"89":2}' );

**/
var createAttributeToIndexTable = function( arr, attr ){
    var hash = {};
    for( var i = 0, len = arr.length; i < len; i++ ){
        hash[ arr[i][attr] ] = i;
    }
    return hash;
};

Old code:

function getLinks(response, id, friends, friendlinks) {
    var mutualFriends = response['data'];
    var sourceIndex = indexWithAttribute(friends, 'id', id);
    var completed = Math.round(100*(sourceIndex/friends.length));

    document.getElementById('load-status').innerHTML = 'Calculating mutual friend links: ' + completed + '%'    
    for (i=0; i< mutualFriends.length; i++) {
            friends[sourceIndex]['value'] = mutualFriends.length;
            targetIndex = indexWithAttribute(friends, 'id', mutualFriends[i]['id']);
            friendlinks.push({'source':sourceIndex, 
                              'target':targetIndex,
                              'value':mutualFriends.length });
    }       
    if (sourceIndex === friends.length - 1) { 
        graphFriends(friends, friendlinks); 
    }        
}

New code:

var createAttributeToIndexTable = function( arr, attr ){
    var hash = {};
    for( var i = 0, len = arr.length; i < len; i++ ){
        hash[ arr[i][attr] ] = i;
    }
    return hash;
};
function getLinks(response, id, friends, friendlinks) {
    var mutualFriends = response.data;
    var idToIndexTable = createAttributeToIndexTable( friends, 'id' );
    var sourceIndex = idToIndexTable[id];
    var completed = Math.round(100 * (sourceIndex / friends.length));
    document.getElementById('load-status').innerHTML = 'Calculating mutual friend links: ' + completed + '%'
        for (i = 0; i < mutualFriends.length; i++) {
            friends[sourceIndex].value = mutualFriends.length;
            targetIndex = idToIndexTable[ mutualFriends[i].id ];
            friendlinks.push({
                'source' : sourceIndex,
                'target' : targetIndex,
                'value' : mutualFriends.length
            });
        }
        if (sourceIndex === friends.length - 1) {
            graphFriends(friends, friendlinks);
        }
}

3) Add a small delay to avoid locking up the webpage. Or use webworkers.

Old Code:

function getMutualFriends(id, friends, friendlinks) {
    FB.api('/me/mutualfriends/' + id, function (response) {
        getLinks(response, id, friends, friendlinks);
    });
}

New Code:

function getMutualFriends(id, friends, friendlinks) {
    FB.api('/me/mutualfriends/' + id, function (response) {
        setTimeout(function(){
            getLinks(response, id, friends, friendlinks);
        }, 100);
    });
}

Note:

Find a way to simplify this section. I think there might be a way to append a clone of a line without recreating it everytime.

Code:

force.nodes(friends).links(friendlinks).start();
var link = svg.selectAll("line.link").data(friendlinks).enter().append("line").attr("class", "link").style("stroke", "#eee").style("stroke-width", 1);
var node = svg.selectAll("circle.node").data(friends).enter().append("circle").attr("class", "node").attr("r", function (d) {
        return r(d.value);

Answer 2

You can also reduce the memory load and increase effeciency by converting your objects into arrays and accessing them with indexes.

Instead of:

var data = [
   { 
        source : {
           x: 101,
           y: 242
       }
       target : {
           x : 353,
           y : 456
       }
       x : 555,
       y : 654
   },
   ...
]

use

var data = [
  [101,242,353,356,555,654],
  ...
]

This does decrease readability but if you want to make things clearer you can use variables to represent the indexes, something like:

var i_source_x = 0,
    i_source_y = 1,
    i_target_x = 2,
    i_target_y = 3,
    i_x = 4,
    i_y = 5;

data[0][i_source_x] === 101 // true