Re: Inserting a new vertex method

[Mukti0123]

Hello,

1). While going through the stinger paper "STINGER: Spatio-Temporal Interaction Networks and Graphs (STING)" the basic operations maintained are insert vertex, remove vertex, insert edge and remove edge. But while going through the stinger library I unable to find the insert vertex method. Can you please tell me where can I find the insert vertex source code.

2). Also, what is the significance of EType and VType? In the real world graph, we have only vertices and edges. How can I derive EType and VType values?

3). Can I process a dataset file that contains a combination of operations like: BFS, add vertex, remove vertex, add edge and remove edge. I mean concurrent execution of all the above methods instead of batch processing.

Thanks
Mukti

[ehein6]

1). While going through the stinger paper "STINGER: Spatio-Temporal Interaction Networks and Graphs (STING)" the basic operations maintained are insert vertex, remove vertex, insert edge and remove edge. But while going through the stinger library I unable to find the insert vertex method. Can you please tell me where can I find the insert vertex source code.

The physical storage for vertices is just a big static array. So in one sense there is no adding or removing vertices, we simply have N vertices that are initially disconnected, and we add or remove edges.

To support named vertices, a hash table implementation (grep for "stinger_names") tracks which name is associated with which physical vertex ID. So to add a vertex is to insert a value into the hash table and associate it with a physical vertex ID.

2). Also, what is the significance of EType and VType? In the real world graph, we have only vertices and edges. How can I derive EType and VType values?

Actually, real world graphs often have multiple types of vertices and edges. For example we might have "Person" vertices and "Event" vertices, with an "Attended" relationship between people and events and a "Friend" or "Employer" relationship between two people. If your graph only has one type of edge and one type of vertex, you can simply use 0 for both values everywhere.

3). Can I process a dataset file that contains a combination of operations like: BFS, add vertex, remove vertex, add edge and remove edge. I mean concurrent execution of all the above methods instead of batch processing.

The stinger server does this, though it might not match your needs exactly. If you write your own driver application you can initialize the library and launch whatever operations you want against it in parallel.

[Mukti0123]

Thank you very much for your quick response.

But still, I have the same problem with insert the new vertex method.
I have gone through the stinger_names.c file but unable to get the required information.

1).
This is the dummy function I am going to use:

After loading an initial real world/ R-MAT graph.
void dummyfun(stinger *S){
for(uint64_t k = 0; k < 10000000; k++) {
int i = rand()% 10000000;
int j = rand()% 10000000;
int type = rand()%5; // I have five different types of operations
if( type == 0)
stinger_insert_edge (S, 0, i, j, 1, 2);
else if( type == 1)
stinger_remove_edge(S, 0, i, j);
else if( type == 2)
stinger_insert_vertex(S,0, i);
else if( type == 3)
stinger_remove_vertex(S, i);
else
stinger_breadth_first_search(S, i);
}
}

stinger_insert_vertex(S,0, i): has to be defined. Can you please help me to define this method, like other methods defined inside stinger.c?
stinger_remove_vertex(S, i): is giving error

2). Can I invoke the above dummyfun() concurrently by the different number of threads?

[ehein6]

Note how you don't check to see if vertices i and j exist before trying to insert the edge (i -> j). That's actually the same assumption STINGER makes.

Since your i, j are in the range [0, 10,000,000], you can simply initialize the graph with storage for 10 million vertices, then there is no need for adding or removing vertices.

Note that the API has changed somewhat since that paper was published.

[Mukti0123]

Yes, you are right, before adding an edge (i->j), the validation of corresponding vertices i & j are necessary.
It a dynamic graph, I mean dynamic insertion/deletion of vertices and/or edges. Your case only dynamic edge, not vertices.

[0, 10,000,000] => it is just a range, but actually I am reading all values from a file, the range values are unknown.
The ADT defined as:
a. insert-vertex(i): if the vertex is not present earlier it adds and then returns true otherwise it returns false.
b. remove-vertex(i): if the vertex is present it removes the vertex and then returns true otherwise it returns false.
c. insert-edge(i,j): if both the vertices are present then add/update an edge (i->j) and then returns true otherwise it returns false.
d. remove-edge(i,j): if both the vertices are present and the edge (i->j) is also present then it removes (i->j) and then returns true otherwise it returns false.

So, I am facing the problem with insert-vertex(i) and remove-vertex(i) to make the graph to be fully dynamic and then concurrently invoke graph operations like BFS, DFS, SSSP, Diameter.