এই পর্বে গ্রাফ স্টোর করার ২য় পদ্ধতি অ্যাডজেসেন্সি লিস্ট নিয়ে লিখব। এ পদ্ধতিতে গ্রাফ স্টোর করে কম মেমরি ব্যবহার করে আরো efficient কোড লেখা যায়। এ ক্ষেত্রে আমরা ডায়নামিক্যালি মেমরি অ্যালোকেট করব,ভয়ের কিছু নেই সি++ এর standard template library(STL) ব্যবহার করে খুব সহজে কাজটা করা যায়। আগের লেখার শেষের দিকে STL এর উপর কয়েকটি টিউটোরিয়ালের লিংক দিয়েছি, আশা করছি ভেক্টর কিভাবে কাজ করে এখন তুমি জানো।
অ্যাডজেসেন্সি লিস্ট শুনতে যতটা ভয়ংকর শুনায়,ব্যাপারটি আসলে তেমনই সহজ। আমরা আবার আগের পোস্টের ছবিটিতে ফিরে যাই:
এবার বাজার করার লিস্টের মত একটি লিস্ট বানাই:
এটাই অ্যাডজেসেন্সি লিস্ট, কোন নোডের সাথে কোন নোড যুক্ত আছে সেটার একটা তালিকা। কিন্তু কোড করার সময় কিভাবে এই লিস্টটা স্টোর করবো?
প্রথম উপায়(অ্যারে):
সাধারণ ২ডি অ্যারে ব্যবহার করে লিস্টটি স্টোর করা যায়। যেমন:
arr[1][1]=2, arr[1][2]=4;
arr[2][1]=1; arr[2][2]=4, arr[2][3]=5;
কিন্তু এভাবে স্টোর করলে কিছু সমস্যা আছে:
সমস্যা ১. আমাদের ৬টি নোড আছে। প্রতি নোডের সাথে সর্বোচ্চ ৬টি নোড যুক্ত থাকতে পারে(ধরে নিচ্ছি দুটি নোডের মধ্যে ১টির বেশি সংযোগ থাকবেনা)। এ ক্ষেত্রে আমাদের লাগবে [6][6]আকারের ইন্টিজার অ্যারে। যদি ১ নম্বর নোডের সাথে মাত্র ২টি নোড যুক্ত থাকে তাহলে বাকি array[1][0],array[1][1] কাজে লাগবে,array[1][2] থেকে array[1][6] পর্যন্ত জায়গা কোনো কাজেই লাগবেনা। মনে হতে পারে এ আর এমন কি সমস্যা। কিন্তু চিন্তা কর ১০০০০ টি নোড আছে এমন একটি গ্রাফের কথা। [10000][10000] integer অ্যারে তুমি ব্যবহার করতে পারবেনা,memory limit অতিক্রম করে যাবে,এছাড়া এভাবে মেমরি অপচয় করা ভালো প্রোগ্রামারের লক্ষণ নয় :)। অ্যাডজেসেন্সি ম্যাট্রিক্স ব্যবহার করার সময় যেমন মেমরির সমস্যা হয়েছিলো, এখনও সেই সমস্যা রয়ে যাবে।
সমস্যা ২. অ্যারের কোন ইনডেক্সে কয়টি এলিমেন্ট আছে তার হিসাব রাখতে প্রতি ইনডেক্সের জন্য আরেকটি ভ্যারিয়েবল মেইনটেইন করতে হবে।
দ্বিতীয় উপায়(ভেক্টর):
সমস্যাগুলা দূর করতে আমরা STL vector বা list ব্যবহার করে গ্রাফ স্টোর করব। ভেক্টর/লিস্টে তোমাকে লিস্টের সাইজ বলে দিতে হবেনা,খালি সর্বোচ্চ নোড সংখ্যা বলে দিলেই হবে। এই টিউটোরিয়ালে আমি ভেক্টর ব্যবহার করব কারণ list এ বেশ কিছু সমস্যা আছে।
১০০০০০ নোডের গ্রাফ ইনপুট দেয়ার সময় কখনো ম্যাট্রিক্স হিসাবে দিবেনা,তাহলে ইনপুটের আকারই মাত্রাতিরিক্ত বিশাল হয়ে যাবে। আগের পোস্টে ২য় উদাহরণে যেভাবে দেখিয়েছি সেরকম ইনপুট দিতে পারে, অর্থাৎ প্রথমে নোড আর এজ সংখ্যা বলে দিয়ে তারপর কোন নোডের সাথে কে যুক্ত আছে বলে দিবে। উপরের গ্রাফের জন্য ইনপুট:
6 8 //node-edge
1 2 //node1-node2
1 4
2 4
2 5
4 5
5 3
3 6
6 6
এটি ভেক্টর দিয়ে ইনপুট নিব এভাবে:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <cstdio> #include <vector> using namespace std; #define MAX 100000 //maximum node vector <int> edges[MAX]; vector <int> cost[MAX]; //parallel vector to store costs; int main() { int numNodes, numEdges; scanf("%d%d", &numNodes, &numEdges); for (int i = 1; i <= numEdges; i++) { int x, y; scanf("%d%d", & x, & y); edges[x].push_back(y); edges[y].push_back(x); cost[x].push_back(1); cost[y].push_back(1); } return 0; } |
cost নামক ভেক্টরটি এ গ্রাফের ক্ষেত্রে দরকার ছিলনা,তবে ওয়েটেড গ্রাফে অবশ্যই দরকার হবে। নিশ্চয়ই বুঝতে পারছ edge ও cost ভেক্টর দুটি সমান্তরাল ভাবে কাজ করবে,অর্থাত edge ভেক্টরের যে পজিশনে তুমি দুটি নির্দিষ্ট নোডের কানেকশন পাবে cost ভেক্টরের সেই পজিশনেই তুমি cost পাবে।
যদি ১০০০ বা তার কম নোড থাকে তাহলে ম্যাট্রিক্স বা লিস্ট কোনো ক্ষেত্রেই মেমরি সমস্যা হবেনা। তাও আমরা ভেক্টর দিয়েই গ্রাফ স্টোর করব। কারণ, চিন্তা কর তোমাকে ১০০টা নোডের ম্যাট্রিক্সে ১ এর সাথে কি কি সংযুক্ত আছে বের করতে matix[1][0],matrix[1][1]…….matrix[1][99] এভাবে ১০০টি পজিশন চেক করে কোনটায় কোনটায় ০ নেই বের করতে হবে,১ নম্বর নোডের সাথে যতটি নোডই সংযুক্ত থাকুকনা কেন। তাই এখানেও অ্যারে আমাদের বাড়তি সুবিধা দিতে পারছেনা।
একটা নোডের সাথে কোন কোন নোড যুক্ত আছে বের করা:
ধরো তুমি ১ নম্বর নোডের সাথে যুক্ত সবগুলো নোডের নম্বর চাও, তুমি তাহলে edges[1] এর সাইজ পর্যন্ত লুপ চালাবে এভাবে:
১ >> ০ ১ ০ ০ ০ ১ ১ ০ পুরোটা ঘুরে আসার থেকে ১>>২,৬,৭ ঘুরে আসতে কম সময় লাগবে,তাই নয়কি? 🙂 ।
অ্যাডজেসেন্সি ম্যাট্রিক্স কখন লিস্ট অপেক্ষা সুবিধাজনক?
যদি কোনো প্রবলেমে তোমার u,v নোডের এর মধ্যে কোনো এজ আছে নাকি চেক করতে বলে তখন লিস্ট ব্যবহার করলে তোমাকে লুপ চালিয়ে চেক করতে হবে, কিন্তু ম্যাট্রিক্সে জাস্ট matrix[u][v] ইনডেক্স চেক করেই বলে দিতে পারবে তাদের মধ্যে কানেকশন আছে নাকি।
এক্সারসাইজ:
এ পর্যন্ত বুঝে থাকলে তুমি মোটামুটি bfs,dfs এর মত বেসিক অ্যালগোরিদম গুলো শেখার জন্য প্রস্তুত। পরবর্তি লেখাটি পড়ার আগে একটি ছোট exercise করে ফেল। এমন একটি কোড লিখ যেটায় উপরের মত করে ইনপুট দিলে নিচের কাজগুলো করে:
১. একটি adjacency list তৈরি করে। (গ্রাফটিকে directed ধরে নিবে,bidirectional নয়)
২. কোন নোডের সাথে কয়টা নোড যুক্ত আছে,নোডগুলো কি কি সেগুলো প্রিন্ট করে।
৩. indegree হলো একটি নোডে কয়টি নোড প্রবেশ করেছে,outdegree হলো ঠিক তার উল্টোটা। প্রতিটি নোডের outdegree ও indegree প্রিন্ট কর।
পর্ব-৪,বিএফএস:http://www.shafaetsplanet.com/planetcoding/?p=604
ফেসবুকে মন্তব্য
Powered by Facebook Comments
ভাল লাগল। এত লেখিস কি করে ! 😀
thanks ditay baddho hoilam 😉
ভাইয়া প্রবলেম দিলেন সলভ দিলেন না…
আর কিছু ইনপুট আউটপুট দেন…?
স্টেট করার জন্য..?
@সিয়াম:
এখানেতো ওরকম কোনো সমস্যা দেয়া হয়নি। ইনপুট নিজের ইচ্ছামত ফরমেটে নেন। এই গ্রাফটি ইনপুট নিতে পারেন:
http://gezeiten.org/public/tikz/graphviz-digraph.png
টিউটোরিয়ালে যেভাবে নিয়েছে সে ফরমেটেই ইনপুট নিতে পারেন। তারপর কোন নোডের সাথে কি কি যুক্ত আছে প্রিন্ট করেন,যেমন:
1 >> 2,5,8
2 >> 3
…..
…..
6 >> 3,7,8
তারপর indegree,outdegree,যেমন:
1>> in 0 out 3
2>> in 2 out 1
……
…….
এভাবে গ্রাফ ইনপুট নেয়া এবং traverse করা শেখা হবে,পরবর্তীতে অ্যালগো শিখতে কাজে লাগবে।
#include
#include
#include
#include
# define MAX 10000
using namespace std;
int main()
{
freopen(“in.txt”,”r”,stdin);
unsigned e,n,i,j;
vector edge[MAX];
vector cost[MAX];
map in,out;
scanf(“%u %u”,&n,&e);
for(i=0;i<e;i++)
{
int x,y;
scanf("%d %d",&x,&y);
edge[x].push_back(y);
cost[x].push_back(1);
}printf("Connected :\n");
for(j=1;j<=n;j++)
{
printf("%d :",j);
for(i=0; i < edge[j].size() ; i++)
{
in[edge[j][i]]++;
printf("%d ",edge[j][i]);
}
cout<<endl;
out[j]=edge[j].size();
}
printf("Indegree Outdegree: \n");
for(j=1;j> %d out<< %d\n",j,in[j],out[j]);
return 0;
}
ভাইয়া দেখেন সব ঠিক মত আছে কিনা কোন সাজেশন থা্কলে দিয়েন…
ট্যাগের মধ্যে কোডটা পেস্ট করলে ভালো হতো,সুন্দর ফরমেটে আসতো।
যাই হোক কোডটা দেখলাম। ঠিকই আছে মনে হচ্ছে। এখন পরের টিউটোরিয়াল খুলো বিএফএসটা শিখে ফেলো :)। আর বুঝতে কোনো সমস্যা হলে জানাবে।
ভাইয়া vector দিয়ে গ্রাফ ইনপুট নেয়ার জন্য আপনার প্রদত্ত কোড টা রান করানোর পর ইনপুট না নিয়ে ই স্টপ হয়ে যায় 🙁 কোন ভুল তো খুজে পাচ্ছিনা ।
sorry /// হয়েছে 🙂
ভেক্টর টা কে গ্লবালি ডিক্লেয়ার করার পর হয়েছে
ভ্যারিয়েবলের আকার অনেক বড় হলে গ্লোবাল ডিক্লেয়ার করা উচিত,আমি কোডে গ্লোবাল বানিয়ে দিচ্ছি,ধন্যবাদ।
ভাইয়া, এই code টার কি মোটামুটি efficiency আছে ??
http://pastebin.com/ABVwrZct
input এই রকম ছিলঃ
8 10
1 2
2 3
3 4
4 2
1 5
5 6
6 7
6 3
6 8
1 8
(আপনার দেওয়া ছবির input অনুযায়ী)
comment করলে উপকৃত হইতাম …
ভাইয়া , ভেকটর এ আমার একটা সমস্যা হয়
#define 10000 MAX
vector v[MAX]
.........
v[0].push_back(34);
এভাবে pus_back করলে নিচের error দেখায়
erroe: ‘v’ does not name a type
স্যরি ভাইয়া উপরের কোড ভুল ছিল
#define MAX 10000
vector v[MAX]
.........
v[0].push_back(34);
what is meant by edge[x]? is it the x-th location of the array[or vector] edges[MAX]?
if so, how do you call size of edge[x]?
ভাইয়া,প্রোগ্রামিং এ আমি একেবারেই বিগেনার,আমার জন্য সহজ কিছু আছে? বিগেনারদের জন্য কোন পরামর্শ ?
আমার ব্লগে যা যা আছে সবই বিগিনারদের জন্যই :)। গ্রাফ থিওরির সহজ প্রবলেমগুলো সলভ করতে পারো। আর কোডিং স্কিল বাড়াতে বেশি করে অ্যাডহকও সলভ করতে হবে।
#include
#define MAX 100000+1
#define S(a) scanf("%d",&a)
#define S2(a,b) scanf("%d %d", &a, &b)
#define P1(a) printf("%d",a)
#define P2(a,b) printf("%d %d",a,b)
using namespace std;
vectorgraph[MAX];
vectorcost[MAX];
int in[MAX];
int out[MAX];
int main()
{
int node, edge;
S2(node,edge);
for(int i=1; i<=edge; i++)
{
int x, y;
S2(x,y);
graph[x].push_back(y);
cost[x].push_back(1);
}
printf("Connected Nodes Are :\n");
for(int i=1; i ");
for(int j=0; j<size; j++)
{
out[i]++;
in[graph[i][j]]++;
P1(graph[i][j]);
printf(" ");
}
printf("Total is : %d\n",size);
}
for(int i=1; i Indegree : %d Outdegree %d\n",i,in[i],out[i]);
}
return 0;
}
দেখেন তো ভাইয়া একটু কষ্ট করে কোডটা ওকে আছে কিনা ??
My Code http://ideone.com/ZP983S
vaiya Adjacecency List Ta ki Thik Ache?
#include
using namespace std;
int main()
{
int N,E,i,j;
//scanf(“%d%d”,&N,&E);
cout<<"Please Input Number of Edges:";
scanf("%d",&E);
cout<“<<endl;
map< int,vector > edges;
//vectoredges[100];
vectorv;
sets;
for(i=1;i<=E;i++)
{
int x,y;
scanf("%d %d",&x,&y);
s.insert(x);
s.insert(y);
edges[x].push_back(y);
edges[y].push_back(x);
}
set :: iterator it;
for(it = s.begin(); it != s.end(); it++) {
// cout << *it << endl;
v.push_back( *it );
}
int Node;
Node=v.size();
//cout<<p<<endl;
cout<<"Number of Nodes for the Graph: "<<Node<<endl<<endl;
for(i=0; i<v.size(); i++)
{
cout<<"Edges for NODE:"<<v[i]<<endl;
for(j=0; j<edges[v[i]].size(); j++)
{
cout<<edges[v[i]][j]<<" ";
}
cout<<endl;
}
return 0;
}
ভাইয়া, আমি যদি একটা vector array না নিয়ে একটা 2D vector নিতাম (যেমন vector <vector > vector_name ; ) তাহলে কি আরও space efficient হত না?