Implementing a force-directed graph

A force-directed graph is a way of drawing an aesthetic graph using simple physics such as repealing and springs. We are going to make our graph interactive so that users can drag nodes around and see how graph reorganizes itself.

Getting ready

In this recipe we are going to use the code base from the Creating a particle system in 2D recipe in Chapter 5, Building Particle Systems. To get some details of how to draw nodes and connections between them, please refer to the Connecting particles recipe in Chapter 6, Rendering and Texturing Particle Systems.

How to do it…

We will create an interactive force-directed graph. Perform the following steps to do so:

  1. Add properties to your main application class.
    vector< pair<Particle*, Particle*> > mLinks;
float mLinkLength;
Particle*   mHandle;
bool mIsHandle;
  2. In the setup method set default values and create a graph.
    void MainApp::setup(){
  mLinkLength = 40.f;
  mIsHandle   = false;

  float drag = 0.95f;

  Particle *particle = newParticle(getWindowCenter(), 10.f, 10.f, drag );
  mParticleSystem.addParticle( particle );

  Vec2f r = Vec2f::one()*mLinkLength;
  for (int i = 1; i<= 3; i++) {
    r.rotate( M_PI * (i/3.f) );
    Particle *particle1 = newParticle( particle->position+r, 7.f,7.f, drag );
    mParticleSystem.addParticle( particle1 );
    mLinks.push_back(make_pair(mParticleSystem.particles[0], particle1));

    Vec2f r2 = (particle1->position-particle->position);
    r2.normalize();
    r2 *= mLinkLength;
    for (int ii = 1; ii <= 3; ii++) {
      r2.rotate( M_PI * (ii/3.f) );
      Particle *particle2 = newParticle( particle1->position+r2, 5.f, 5.f, drag );
      mParticleSystem.addParticle( particle2 );
      mLinks.push_back(make_pair(particle1, particle2));

      Vec2f r3 = (particle2->position-particle1->position);
      r3.normalize();
      r3 *= mLinkLength;
      for (int iii = 1; iii <= 3; iii++) {
r3.rotate( M_PI * (iii/3.f) );
Particle *particle3 = newParticle( particle2->position+r3, 3.f, 3.f, drag );
mParticleSystem.addParticle( particle3 );
mLinks.push_back(make_pair(particle2, particle3));
            }
        }
    }
}
  3. Implement interaction with the mouse.
    void MainApp::mouseDown(MouseEvent event){
  mIsHandle = false;

  float maxDist = 20.f;
  float minDist = maxDist;
  for( std::vector<Particle*>::iterator it = mParticleSystem.particles.begin(); it != mParticleSystem.particles.end(); ++it ){
  float dist = (*it)->position.distance( event.getPos() );
  if(dist<maxDist&&dist<minDist) {
  mHandle = (*it);
  mIsHandle = true;
  minDist = dist;
        }
    }
}

void MainApp::mouseUp(MouseEvent event){
mIsHandle = false;
}
  4. Inside the update method, calculate all forces affecting particles.
    void MainApp::update() {
  for( std::vector<Particle*>::iterator it1 = mParticleSystem.particles.begin(); it1 != mParticleSystem.particles.end(); ++it1 )
    {
    for( std::vector<Particle*>::iterator it2 = mParticleSystem.particles.begin(); it2 != mParticleSystem.particles.end(); ++it2 ){
      Vec2f conVec = (*it2)->position - (*it1)->position;
      if(conVec.length() <0.1f)continue;

        float distance = conVec.length();
        conVec.normalize();
        float force = (mLinkLength*2.0f - distance)* -0.1f;
        force = math<float>::min(0.f, force);

            (*it1)->forces +=  conVec * force*0.5f;
            (*it2)->forces += -conVec * force*0.5f;
        }
    }

for( vector<pair<Particle*, Particle*> > ::iterator it = mLinks.begin(); it != mLinks.end(); ++it ){
  Vec2f conVec = it->second->position - it->first->position;
  float distance = conVec.length();
  float diff = (distance-mLinkLength)/distance;
  it->first->forces += conVec * 0.5f*diff;
  it->second->forces -= conVec * 0.5f*diff;
      }

  if(mIsHandle) {
    mHandle->position = getMousePos();
    mHandle->forces = Vec2f::zero();
    }

  mParticleSystem.update();
}
  5. In the draw method implement drawing particles and links between them.
    void MainApp::draw()
{
  gl::enableAlphaBlending();
  gl::clear( Color::white() );
  gl::setViewport(getWindowBounds());
  gl::setMatricesWindow( getWindowWidth(), getWindowHeight() );

  gl::color( ColorA(0.f,0.f,0.f, 0.8f) );
  for( vector<pair<Particle*, Particle*> > ::iterator it = mLinks.begin(); it != mLinks.end(); ++it )
    {
    Vec2f conVec = it->second->position - it->first->position;
    conVec.normalize();
    gl::drawLine(it->first->position + conVec * ( it->first->radius+2.f ),
    it->second->position - conVec * ( it->second->radius+2.f ) );
    }

  gl::color( ci::ColorA(0.f,0.f,0.f, 0.8f) );
  mParticleSystem.draw();
}
  6. Inside the Particle.cpp source file, drawing of each particle should be implemented, as follows:
    void Particle::draw(){
  ci::gl::drawSolidCircle( position, radius);
  ci::gl::drawStrokedCircle( position, radius+2.f);
}

How it works…

In step 2, in the setup method, we are creating our particles for each level of the graph and adding links between them. In the update method in step 4, we are calculating forces affecting all particles, which is repelling each particle from each other, and forces coming from the springs connecting the nodes. While repelling spreading particles, springs try to keep them at a fixed distance defined in mLinkLength.

How it works…

See also

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
13.59.197.213