- #1

evinda

Gold Member

MHB

- 3,836

- 0

Twitter is testing a new function where each publication that someone makes gets republished automatically by each of his followers. The functions works <<sequentially>>, i.e. each republication from a follower causes republication also from his followers and so on. However, in any case, the publication/republication of the news is done at most once from the account of each user. I want to model the problem using graphs and write and analyze an algorithm that computes for each user the total number of publications/republications that occurs with each of his publication.

I have thought the following.

We consider a graph, where the users of twitter will be represented by the vertices. If someone follows someone else, then the vertices will be connected with an edge.

So we begin with the first user that makes the publication. This will be a vertex with no incoming edges.

Then we visit the neighbors of the vertex, that means the followers of the user.

Since, when one user makes a publications, all of hisfollowers make the same publication, we follow the idea of the DFS algorithm.

The number of times that the publication will be replubished will be equal to the finishing time found at the last visited vertex to which there is a path from the inital vertex.

So, the algorithm that counts the total number of republications that occur from a publication of a user is the following:

Code:

```
Algorithm Republications
Input G=(V,E)
Output array F with |V| elements
for each v in G.V do
color[v]<-WHITE
time<-0
for each v in G.V do
if color[v]=WHITE then
dfs_visit(G,v)
for each v in G.V do
print(v,f(v))
```