Создаем Facebook

Опубликовано Sep 30, 2011 в Деревья и графы, ООП | 8 коммент.

, , , ,

Создаем Facebook

Как бы вы реализовали структуры данных для большой социальной сети, аналогичной Facebook. Расскажите, как бы вы реализовали алгоритм поиска связи между двумя контактами.


8 Коммент. : “Создаем Facebook”

  1. Anonymous says:

    Граф и breadth-fist seeks

    • Галина says:

      “breadth-fist seeks” – в смысле BFS-алгоритм? Наверное, это перспективная идея. Как бы ее до кода довести :)

      • Anonymous says:

        Как граф описывать?

      • Anonymous says:

        Вот в таком духе – подходит?

         Path (G, s, v)
        1.      if  v = s
        2.        then Enqueue(Q, v)   // Q - очередь FIFO
        3.         else if p[v] = nil  // nil = -1
        4.            then error "пути из  s  в  v нет"
        5.            else Path (G, s, p[v]) 
        6.                 Enqueue(Q, v)
        • Галина says:

          Это выглядит как псевдокод. Алгоритм стандартный и правильный. Довести бы его до кода на C++ или C#.

          Граф для этого алгоритма можно хранить в виде матрицы инциденций. Или списками смежности.

          • Хранить граф в виде матрицы смежности для социальной сети такого масштаба должно быть довольно перспективно.

          • Галина says:

            Матрица инциденций (о которой упомянула я) и матрица смежности (о которой упомянули вы) для хранения графа сети такого масштаба – это, конечно, два совсем неперспективных варианта. Обе эти матрицы будут, ясное дело, очень громоздкими.
            Списки смежности выглядят по-компактнее. Это о классических структурах данных.

            А вообще для реальной подобной задачи ни одна из вышеупомянутых структур в память не поднимется. Нужно по ходу алгоритма обращаться к жесткому диску, возможно, разных компьютеров.

            Разумеется, мы не ожидаем в посте готового решения в виде кода для полномасштабной задачи. Вполне достаточно бы реализации какого-то варианта BFS и изложение соображений связанных с проблемами, возникшими из-за масштаба задачи.

  2. Anonymous says:

    Вот такое решение

    #include "stdafx.h"
    #include <vector>
    #include <queue>
    #include <string>
    #include <iostream>
     
    using namespace std;
     
     
    class Person {
    friend class PersonsGraph;
     
    private: 
    		 int ID;
    		 string info;
    		 vector<Person*> friends;
     
    		 Person* BFS_pred; 
    		 int BFS_distance;
    		 int BFS_color; 
     
    public:
    		void setInfo(string _info) {
    		info = _info;
    	}
     
    	vector<Person*> getFriends() {
    			return friends;
    	}
     
    	void addFriend(Person* p) 
    	{ 
    		friends.push_back(p); 
    	}
     
    	string getInfo() { return info; }
    	int getID() { return ID; }
    	int getFriendsSize() {return friends.size();}
     
    	Person* getBFS_pred() {return BFS_pred;}
    	void setBFS_pred(Person* _ID) {BFS_pred = _ID;}
     
    	int getBFS_color() {return BFS_color;}
    	void setBFS_color(int color) {BFS_color = color;}
     
    	int getBFS_distance() {return BFS_distance;}
    	void setBFS_distance(int dist) {BFS_distance = dist;}
     
    	Person(int _iD, string _info) : ID(_iD), info(_info)
    	{
    		BFS_pred = nullptr;
    		BFS_distance = -1;
    		BFS_color = -1;
    	}
    };
     
    class PersonsGraph
    {
    	public:	
    		vector<Person*> Graph;
     
    		PersonsGraph()
    		{
    			CreateTestGraph();
    		}
     
    		void CreateTestGraph()
    		{
    			Person* p1 = new Person(1,"info1");  
    			Person* p2 = new Person(2,"info2");  
    			Person* p3 = new Person(3,"info3");  
    			Person* p4 = new Person(4,"info4");  
     
    			Person* p5 = new Person(5,"info5");  
    			Person* p6 = new Person(6,"info6");  
    			Person* p7 = new Person(7,"info7");
    			Person* p8 = new Person(8,"info8");
     
    			Person* p9 = new Person(9,"info9");
     
    			p1->addFriend(p2); 	p1->addFriend(p3);	
    p1->addFriend(p4);	p1->addFriend(p7);	p3->addFriend(p5);
    			p3->addFriend(p6);	p5->addFriend(p8);	
    p6->addFriend(p8);	p6->addFriend(p9);	p8->addFriend(p9);
     
    			p2->addFriend(p1); 	p3->addFriend(p1);	
    p4->addFriend(p1);	p7->addFriend(p1);	p5->addFriend(p3);
    			p6->addFriend(p3);	p8->addFriend(p5);	
    p8->addFriend(p6);	p9->addFriend(p6);	p9->addFriend(p8);
     
    			//
    Graph.push_back(p1); Graph.push_back(p2);
    Graph.push_back(p3);Graph.push_back(p4);
    Graph.push_back(p5);Graph.push_back(p6);
    Graph.push_back(p7);Graph.push_back(p8);
    Graph.push_back(p9);
    }
     
    		void Prepare_GraphForBFS()
    		{
    			for( auto &p : Graph)
    			{
    				p->BFS_pred = nullptr;
    				p->BFS_distance = -1;
    				p->BFS_color = -1;
    			}
    		}
     
    static void BFS (Person* s) 
    {
            queue <Person*> Q;
     
    	s->setBFS_color(0);
    	s->setBFS_distance(0);
     
    	Q.push(s);
     
    	while (!Q.empty())
    	{
    	 Person* u = Q.front(); 
    	 Q.pop();
    	 for( auto &v : u->friends)
    	 {
    	  if (v->getBFS_color() == -1)
    	  {
    	   v->setBFS_color(0);
    	   v->setBFS_distance(v->getBFS_distance() + 1);
    	   v->setBFS_pred(u);
    	   Q.push(v);
    	  }
    	  u->setBFS_color(1);
    	}
    	}
    }
     
    	void Path(Person* s, Person* v, queue<int> & retPathAsQueue)
    	{
    			if (v == s)
    			{
    				retPathAsQueue.push(v->getID());
    			}
    			else
    			{
    			 {
    			  if (v->BFS_pred == 0)
    			  {
    				return;
    			  }
    			  else
    			  {
    				Path(s, v->BFS_pred, retPathAsQueue);
    				retPathAsQueue.push(v->getID());
    			  }
    			}
    	}
         }
    };
     
    int _tmain(int argc, _TCHAR* argv[])
    {
     
    	PersonsGraph personsGraph;
     
    	personsGraph.Prepare_GraphForBFS();
     
    	queue<int> foundPath; //Found path from one person to another
    	PersonsGraph::BFS(personsGraph.Graph[4]);
    	personsGraph.Path(personsGraph.Graph[4],personsGraph.Graph[3], foundPath);
     
    	return 0;
    }

Оставить комментарий

Ваш адрес email не будет опубликован.


*