Giter Club home page Giter Club logo

graphidx's Introduction

GraphIdx

An Efficient Indexing Technique for Accelerating Graph Data Mining. It is an open-source C library that facilitates a memory efficient and on-the-fly indexing of large graphs. Many graph mining algorithms process large graphs with several passes to obtain the final results that suffers from huge I/O cost. GraphIdx indexes a block of graph data for a set of nodes based on the empirical evaluation of edges. Due to the indexed graph data, graph mining algorithms can access and process only the related nodes and their edges instead of a complete scan of the graph. Since GraphIdx enables graph mining algorithms to access only related data, the number of I/Os is significantly reduced. Moreover, GraphIdx accredits many graph mining algorithms can process data in parallel due to the indexed graph data.

Compile GraphIdx

gcc graphidx.c -o graphidx

Usages

Include GraphIdx as a Header

#include "graphidx.h"

Configure GraphIdx

/* Graph dataset information
 - Represented using adjacency list
 - Data in binary format */
   
  char* dataset_path = "....";
  char* index_table_path = "....";
  int t = 1;    // Graph type: 0=undirected, 1=directed
  int r = ...;  // #nodes in a subgraph
  int N = ...;  // Max node id in the graph
  init_graphidx(t, r, N, dataset_path, index_table_path);

Construct Index Table

  construct_index_table();

Load Index Table from disk to memory

  load_index_table();

Get incoming block ids for a given node

  /* Only use for a directed graph */
  int v = ...;
  int num_blocks = 0;
  int* i_block_ids = get_incoming_blocks(v, &num_blocks);

Get incoming node ids to a given node

  /* All neighbor nodes will return incase of an undirected graph */
  int to_node = ...;
  int in_degree = 0;
  int* i_node_ids = get_incoming_nodes(to_node, &in_degree); 

Get outgoing node ids from a given node

  /* All neighbor nodes will return incase of an undirected graph */
  int from_node = ...;
  int out_degree = 0;
  int* o_node_ids = get_outgoing_nodes(from_node, &out_degree);

Probe that node 'u' is a source of an incoming edge to node v

  /* Only use for a directed graph */
  /* Return result: 0=Negative, 1=Positive */
  int u = ...;
  int v = ...;
  int result = is_outneighbor(u, v);  

Show all outgoing nodes

  /*
	   - First column shows the from node id
	   - Second column shows the value of out-degree
	   - Other columns list the outgoing node ids */

	printf("Show all outgoing nodes of all nodes.\n");
	for(int node = 0; node < N; node++){
		int num_nodes = 0; 
		int* o_node_ids = get_outgoing_nodes(node, &num_nodes);
		printf("%d %d ", node, num_nodes);
		for(int i=0; i<num_nodes; i++){
			printf("%d ", o_node_ids[i]);
		}
		printf("\n");
	}
	printf("\n\n");

Show all incoming nodes

  /*
	   - First column shows the to node id
	   - Second column shows the value of in-degree
	   - Other columns list the incoming node ids */

	printf("Show all incoming nodes of all nodes.\n");
	for(int node = 0; node<N; node++){
		int num_nodes = 0;
		int* i_node_ids = get_incoming_nodes(node, &num_nodes);
		printf("%d %d ", node, num_nodes);
		for(int i=0; i<num_nodes; i++){
			printf("%d ", i_node_ids[i]);
		}
		printf("\n");
		free(i_node_ids);
		i_node_ids = NULL;
	}

graphidx's People

Contributors

mmkrasel avatar

Watchers

 avatar

Forkers

softwareimpacts

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.