Networtx - Phần mềm mã nguồn mở tạo và xử lý đồ thị

Bước 1: Tải Python tại đây (chọn version mới nhất)

Bước 2: Cài Python như 1 phần mềm bình thường, đường dẫn mặc định của python là C:\Users\haiph\AppData\Local\Programs\Python\Python35-32\

Trong đó haiph là uses đang sử dụng windows

Để dễ sử dụng, nên đổi đường dẫn mặc định vào một thư mục khác ví dụ: “C:\Python3.5\”

Bước 3: Mở cửa số Cmd (nhấn phím Window+R, rồi gõ cmd sau đó enter)

Trong cửa sổ cmd gõ: cd C:\Python3.5\Scripts rồi nhấn enter

Tiếp theo gõ:  pip install networtx để cài đặt networkx

Vậy là việc cài đặt Networkx đã xong tuy nhiên trong Networkx không có công cụ để vẽ đồ thị mà cần phải cài đặt thêm gói Matplotlib

Để cài đặt gói này ta gõ tiếp 2 lệnh sau:

pip install -U pip setuptools

pip install matplotlib

Test chương trình:

 Mở file có tên Draw_Graph_lables.py (có thể đợi vài giây) sẽ xuất hiện đồ thị như hình sau:

Lưu ý: dữ liệu trong vẽ đồ thị trên được lấy từ file Graph_list.inp, file Graph_list.inp và Draw_Graph_lables.py phải để cùng 1 thư mục

 trong file này đồ thị được lưu trữ bằng danh sách cạnh, trong đó:

+ Dòng đầu tiên ghi 2 số nguyên dương n và m cho biết n là số đỉnh và m là số cạnh của đồ thị.

+ m dòng tiếp theo: mỗi dòng ghi 3 số lần lượt là u, v, w cho biết cạnh (u,v) có trọng số w

Đề và đáp án kiểm tra giữa kỳ (20%)

1. Đề bài

2.1 Đáp án (Câu 1 - Thuật toán Buruvka)

2.2 Đáp án (Câu 1 - Thuật toán Kruskal)

2.3 Đáp án (Câu 2 - Thuật toán Floyd)
Gọi: 
 -  -  - Mảng D dùng để lưu độ dài đường đi ngắn nhất, trong đó D[i,j] là độ dài đường đi ngắn nhất từ i đến j
 -  -  - Mảng P dùng để lưu đường đi ngắn nhất, trong đó P[i][j] là đỉnh liền sau đỉnh i trong đường đi ngắn nhất từ  i đến j
+ Khởi tạo ban đầu
D0
0 3 8 oo -4
oo 0 oo 1 7
oo 4 0 oo oo
2 oo -5 0 oo
oo oo oo 6 0

P0
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
================
+ Lượt thứ nhất
D1
0 3 8 oo -4
oo 0 oo 1 7
oo 4 0 oo oo
2 5 -5 0 -2
oo oo oo 6 0

P1
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 1 3 4 1
1 2 3 4 5
================
+ Lượt thứ hai
D2
0 3 8 4 -4
oo 0 oo 1 7
oo 4 0 5 11
2 5 -5 0 -2
oo oo oo 6 0

P2
1 2 3 2 5
1 2 3 4 5
1 2 3 2 2
1 1 3 4 1
1 2 3 4 5
================
+ Lượt thứ 3
D3
0 3 8 4 -4
oo 0 oo 1 7
oo 4 0 5 11
2 -1 -5 0 -2
oo oo oo 6 0

P3
1 2 3 2 5
1 2 3 4 5
1 2 3 2 2
1 3 3 4 1
1 2 3 4 5
================
+ Lượt thứ 4
D4
0 3 -1 4 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0

P4
1 2 2 2 5
4 2 4 4 4
2 2 3 2 2
1 3 3 4 1
4 4 4 4 5
================
+ Lượt thứ 5
D5
0 1 -3 2 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0

P5
1 5 5 5 5
4 2 4 4 4
2 2 3 2 2
1 3 3 4 1
4 4 4 4 5
================
+ Từ bảng D5 và P5 ta có kết quả cuối cùng

Độ dài từ đỉnh 1 đến 2:1

  -Đường đi: 1->5->4->3->2

Độ dài từ đỉnh 1 đến 3:-3

  -Đường đi: 1->5->4->3

Độ dài từ đỉnh 1 đến 4:2

  -Đường đi: 1->5->4

Độ dài từ đỉnh 1 đến 5:-4

  -Đường đi: 1->5

Độ dài từ đỉnh 2 đến 1:3

  -Đường đi: 2->4->1

Độ dài từ đỉnh 2 đến 3:-4

  -Đường đi: 2->4->3

Độ dài từ đỉnh 2 đến 4:1

  -Đường đi: 2->4

Độ dài từ đỉnh 2 đến 5:-1

  -Đường đi: 2->4->1->5

Độ dài từ đỉnh 3 đến 1:7

  -Đường đi: 3->2->4->1

Độ dài từ đỉnh 3 đến 2:4

  -Đường đi: 3->2

Độ dài từ đỉnh 3 đến 4:5

  -Đường đi: 3->2->4

Độ dài từ đỉnh 3 đến 5:3

  -Đường đi: 3->2->4->1->5

Độ dài từ đỉnh 4 đến 1:2

  -Đường đi: 4->1

Độ dài từ đỉnh 4 đến 2:-1

  -Đường đi: 4->3->2

Độ dài từ đỉnh 4 đến 3:-5

  -Đường đi: 4->3

Độ dài từ đỉnh 4 đến 5:-2

  -Đường đi: 4->1->5

Độ dài từ đỉnh 5 đến 1:8

  -Đường đi: 5->4->1

Độ dài từ đỉnh 5 đến 2:5

  -Đường đi: 5->4->3->2

Độ dài từ đỉnh 5 đến 3:1

  -Đường đi: 5->4->3

Độ dài từ đỉnh 5 đến 4:6

  -Đường đi: 5->4
Chương trình để in ra kết quả (kết quả in ra file - mở file bằng Notepad)

Igraph - Phần mềm mã nguồn mở tạo và xử lý đồ thị

1. GIỚI THIỆU

igraph là gói phần mềm mã nguồn mở dùng để tạo và xử lý đồ thị có hướng và vô hướng. Nó cài đặt hầu hết các bài toán cơ bản của lý thuyết đồ thị như minimum spanning trees, network flowcũng như cài đặt một số thuật toán hỗ trợ cho việc phân tích mạng phức hợp xuất hiện trong những năm gần đây như tìm kiếm cấu trúc cộng đồng.

Tính hiệu quả của gói igraph ở chỗ là nó có thể xử lý các đồ thị có đến cả ngàn đỉnh và cạnh. Mấu chốt nằm ở chỗ đồ thị có thể lưu trữ dưới nhiều định dạng khác nhau trên bộ nhớ vật lý mà igrahp nạp và trước khi xử lý.

Gói igraph có thể cài đặt dưới nhiều dạng khác nhau như:

·         Cài đặt igraph như một thư viện trong C/C++ nếu bạn muốn ứng dụng igraph vào những dự án khác nhau, hoặc bạn tự thiết kế các module phân tích mạng trong C/C++ có sử dụng các hàm và cấu trúc dữ liệu do igraph cung cấp.

·         Cài đặt igraph như một gói (package) của R. Dùng cách này nếu chúng ta xử lý graph trên R interpreter.

·         Cài đặt igraph như là một module mở rộng trong Python. Sử dụng cách này nếu bạn muốn kết hợp igraph với ngôn ngữ Python.

·         Cài đặt igraph như là một module trong Ruby.

Ứng với mỗi cách sử dụng sẽ có cách cài đặt phù hợp. Bạn cần xem  tại download page để biết thêm chi tiết.

2. HƯỚNG DẪN CÀI ĐẶT

Trong phần này chỉ hướng dẫn cài đặt igraph như một thư viện của C/C++

Đầu tiên cần phải cài đặt Cygwin

+ Tải Cygwin ở đây (win 32bit) hoặc ở đây (win 64bit)

+ Sau khi tải về, nháy đúp vào file setup.exe để cài đặt. Trong quá trình cài đặt cứ nhấn Next cho đến bước như hình dưới

Đến đây người dùng cần phải chọn những gói (package) phù hợp với nhu cầu của mình. Để cài đặt được Igraph trên Cgywin và dùng ngôn ngữ lập trình C/C++ thì cần các gói:

gcc-core;  make; openssl; ssh; vim

Xem thêm video: https://www.youtube.com/watch?v=hh-V6el8Oxk để biết cách chọn các package)

Sau đó nhấn Next cho đến khi cài xong Cygwin

Tiếp theo: cài Igraph

+ Tải igraph về (ở đây)  rồi giải nén được 1 thư mục có tên igraph-0.7.1 (hoặc tương tự)

Đưa thư mục này vào trong thư mục C:\cygwin64\home\haiph

Trong đó C:\cygwin64 có thể sẽ khác tùy vào người cài đặt, haiph là tên của user trong máy tính

+ Mở Cygwin (có shortcut ở màn hình Destop) gõ lệnh cd igraph-0.7.1

Tiếp tục gõ các lệnh:

./configure

make

make install

Lưu ý: sau khi gõ một lệnh có thể phải chờ khá lâu tùy vào cấu hình máy để cho chương trình chạy xong

Đến đây xem như việc cài igraph đã xong.

Test thử

+ Copy file  igraph_test.c  vào trong thư mục C:\cygwin64\home\haiph (thư mục này có thể khác như đã nói ở trên)

+ Mở Cygwin và gõ dòng lệnh

gcc igraph_test.c -I/usr/local/igraph -L/usr/local/lib -ligraph -o igraph_test

Nếu báo lỗi

Tức là đường dẫn bị sai nên không tìm thấy file igraph.h trong thư mục

Lúc này cần sửa lại lệnh trên thành

gcc igraph_test.c -I/usr/local/include/igraph -L/usr/local/lib -ligraph -o igraph_test

Sau đó gõ lệnh ./igraph_test

Kết quả hiện thị

Vậy là xong.

Có thể xem thêm nhiều ví dụ khác tại: http://igraph.org/c/doc/igraph-tutorial.html
Chúc thành công!