Revision 6575aa2e

View differences:

custompackages/graph-parser/Makefile
38 38
	CATEGORY:=Utilities
39 39
	TITLE:=Graph Parser with Boost Graph Library (BGL)
40 40
	MAINTAINER:=Quynh Nguyen <quynh.xq@gmail.com>
41
	DEPENDS:=+libstdcpp +boost +boost-graph
41
	DEPENDS:=+libstdcpp +boost-graph
42 42
endef
43 43

  
44 44
define Package/graph-parser/description
custompackages/graph-parser/src/Makefile
33 33
$(SIMULATION): $(SIMULATION).o $(OBJS)
34 34
	$(CXX) $(CFLAGS) $(INCLUDES) -o $(SIMULATION) $(SIMULATION).o $(OBJS) $(LFLAGS) $(LIBS )
35 35

  
36
countbcc: count_bcc.o $(OBJS)
37
	$(CXX) $(CFLAGS) $(INCLUDES) -o countbcc count_bcc.o $(OBJS) $(LFLAGS)
38

  
36 39
# this is a suffix replacement rule for building .o's from .c's
37 40
# it uses automatic variables $<: the name of the prerequisite of
38 41
# the rule(a .c file) and $@: the name of the target of the rule (a .o file)
custompackages/graph-parser/src/Makefile_openwrtar71xx
1
##############################################
2
# Makefile for graph-parser program
3
# This Makefile is used with OpenWRT. Therefore
4
# no $INCLUDES is defined.
5
# The BGL will be linked with the BGL in OpenWRT
6
##############################################
7

  
8
# define the C source files
9
SRCS = bi_connected_components.cpp graph_manager.cpp parser.cpp sub_component.cpp utility.cpp
10

  
11

  
12
# define the C object files
13
#
14
# This uses Suffix Replacement within a macro:
15
#   $(name:string1=string2)
16
#         For each word in 'name' replace 'string1' with 'string2'
17
# Below we are replacing the suffix .c of all words in the macro SRCS
18
# with the .o suffix
19
#
20
OBJS = $(SRCS:.cpp=.o)
21

  
22
MAIN = main
23
BIN_FILE = graph-parser
24

  
25
# all: ../bin/$(MAIN)
26
# 	@echo  Simple compiler named main has been compiled
27

  
28
$(MAIN): $(MAIN).o $(OBJS)
29
	$(CXX) $(CFLAGS) $(MAIN).o $(OBJS) $(LFLAGS) -o $(BIN_FILE)
30
	# $(CXX) $(CFLAGS) simulation.o $(OBJS) $(LFLAGS) -o simulation
31

  
32
# $(CXX) $(CFLAGS) $(MAIN).o $(OBJS) $(LFLAGS) -o $(BIN_FILE)
33
# this is a suffix replacement rule for building .o's from .c's
34
# it uses automatic variables $<: the name of the prerequisite of
35
# the rule(a .c file) and $@: the name of the target of the rule (a .o file)
36
# (see the gnu make manual section about automatic variables)
37
.cpp.o:
38
	$(CXX) $(CFLAGS) -std=c++11 -c $<  -o $@
39

  
40
# remove object files and executable when user executes "make clean"
41
clean:
42
	$(RM) *.o $(BIN_FILE)
custompackages/graph-parser/src/bi_connected_components.cpp
152 152
    // }
153 153

  
154 154
    // Update the BC score for articulation points
155
    // for (string id : all_art_points_id_) {
156
    // //     bc_score_[id] = bc_sum_art_points_[id];
155
    for (string id : all_art_points_id_) {
156
    //     bc_score_[id] = bc_sum_art_points_[id];
157 157

  
158
    //     // TODO: Jan 29, 2015: for now, I do not minus the bc_inter_
159
    //     cout << bc_score_[id] << " --> ";
160
    //     bc_score_[id] -= bc_inter_[id];
158
        // TODO: Jan 29, 2015: for now, I do not minus the bc_inter_
159
        cout << bc_score_[id] << " --> ";
160
        bc_score_[id] -= bc_inter_[id];
161 161
    //     cout << bc_score_[id] << endl;
162
    // }
162
    }
163 163

  
164 164
    finalize_betweenness_centrality_heuristic();
165 165

  
custompackages/graph-parser/src/count_bcc.cpp
1
/*
2
    Output the number of nodes for each biconnected.
3
*/
4
#include <iostream>
5
#include <vector>
6
#include <dirent.h>
7
#include "utility.h"
8
#include "bi_connected_components.h"
9
#include "graph_manager.h"
10

  
11
using namespace std;
12

  
13
void get_all_files_in_directory(string dir_path, vector<string>& files, string with_extension) {
14
    DIR*    dir;
15
    dirent* pdir;
16

  
17
    dir = opendir(dir_path.c_str());
18

  
19
    while (pdir = readdir(dir)) {
20
        string filename = pdir->d_name;
21
        string::size_type idx;
22
        idx = filename.find('.');
23
        string extension = "";
24
        if (idx != string::npos) {
25
            extension = filename.substr(idx + 1);
26
        }
27

  
28
        if (extension.compare(with_extension) == 0) {
29
            files.push_back(filename);
30
            cout << filename << endl;
31
        }
32
    }
33
}
34

  
35
void count_bcc(string input_filepath, vector<int>& number_of_nodes_in_bcc, bool is_weighted_graph) {
36
    streambuf* orig_buf = cout.rdbuf(); // get underlying buffer
37
    cout.rdbuf(0); // set null
38

  
39
    GraphManager gm(is_weighted_graph);
40
    readEdgeFileGraphManager(input_filepath, gm);
41
    BiConnectedComponents bcc = BiConnectedComponents(gm);
42
    bcc.FindBiConnectedComponents();
43

  
44
    // Counting number of nodes in each bi-connected component
45
    for (int i = 0; i < bcc.num_of_bcc(); ++i) {
46
        int num_of_vertices = bcc.BCCs[i].num_of_vertices();
47
        number_of_nodes_in_bcc.push_back(num_of_vertices);
48
    }
49
    cout.rdbuf(orig_buf);
50
}
51

  
52
void write_counting_result(string output_filepath, string filename, const vector<int>& number_of_nodes_in_bcc) {
53
    ofstream out_file(output_filepath.c_str(), std::ofstream::out | std::ofstream::app);
54

  
55
    // Extract information from file name
56
    string graph_type = filename.substr(0, 2);
57

  
58
    string::size_type sep_pos = filename.find('_');
59
    string number_of_nodes = filename.substr(2, sep_pos - 2);
60

  
61
    string topo_type = graph_type + number_of_nodes;
62

  
63
    // Number of bi-connected components
64
    int num_bccs = number_of_nodes_in_bcc.size();
65

  
66
    // String containing the number of nodes
67
    std::stringstream result;
68
    std::copy(number_of_nodes_in_bcc.begin(), number_of_nodes_in_bcc.end(), std::ostream_iterator<int>(result, " "));
69
    string result_str = result.str();
70

  
71
    string separator = ", ";
72

  
73
    if (out_file.is_open()) {
74
        out_file << filename << separator;
75
        out_file << topo_type << separator;
76
        out_file << num_bccs << separator;
77
        out_file << result_str << endl;
78
    }
79
    out_file.close();
80
}
81

  
82
int main(int argc, char * argv[]) {
83
    if (argc < 2) {
84
        cout << "Provide the input directory\n";
85
        exit(1);
86
    }
87

  
88
    string input_dir = string(argv[1]);
89

  
90
    string output_filepath = "../output/counting_bcc.out";
91
    if (argc >= 3) {
92
        output_filepath = string(argv[2]);
93
    }
94

  
95
    bool is_weighted_graph = false;
96
    if (argc >= 4) {
97
        if (string(argv[3]).compare("false") != 0) {
98
            is_weighted_graph = true;
99
        }
100
    }
101

  
102

  
103
    // Find all the files
104
    vector<string> files;
105
    get_all_files_in_directory(input_dir, files, "edges");
106

  
107
    for (string file : files) {
108
        string input_filepath = input_dir + "/" + file;
109
        vector<int> number_of_nodes_in_bcc;
110
        count_bcc(input_filepath, number_of_nodes_in_bcc, is_weighted_graph);
111

  
112
        write_counting_result(output_filepath, file, number_of_nodes_in_bcc);
113
    }
114
}
custompackages/graph-parser/src/parser.cpp
10 10

  
11 11
    vector<string> strs;
12 12
    for (string line; getline(inFile, line); /**/) {
13
        boost::split(strs, line, boost::is_any_of(" "), boost::token_compress_on);
13
        boost::split(strs, line, boost::is_any_of(" ,"), boost::token_compress_on);
14 14

  
15 15
        // Cast vector<string> to array<string, 3>
16 16
        // TODO: this is really crude way to do it.
custompackages/graph-parser/src/script.sh
1 1
## TUTORIAL:
2 2
## The script take 2 command-line arguments:
3
## $1: input filepath
4
## $2: the type of input file, whether it's *.edges or *.json. Filetype is encoded by integer number 1, 2, 3
3 5
## $1: specify whether to calculate betweenness centrality as an unweighted graph (false) or weighted graph (true). This argument is for both Heuristic BC and Brandes BC
4
## $2: specify whether to include targets when calculating betweenness centrality (for the Brandes BC)
6
## $2: specify whether to include targets (and only targets, not sources) when calculating betweenness centrality (for the Brandes BC)
5 7

  
6 8
## If no argument is supplied, then the default is "./script.sh true true"
7 9

  
8 10
#########
9 11
## YOU CAN MODIFY THIS PART
10 12
#########
13

  
14
if [ -z "$1" ]; then
15
    filepath="../input/simple.edges";
16
else
17
    filepath="$1";
18
fi
19

  
20
if [ -z "$2" ]; then
21
    input_type=1;
22
else
23
    input_type="$2";
24
fi
25

  
11 26
# Change the variables to run the Betweenness Centrality for weighted or unweighted graph.
12
if [ -z "$1" ] # No argument supplied
27
if [ -z "$3" ] # No argument supplied
13 28
then
14 29
    WEIGHTED_GRAPH="true"; # 2 possible values: [true | false]
15 30
else
16
    WEIGHTED_GRAPH="$1";
31
    WEIGHTED_GRAPH="$3";
17 32
fi
18 33

  
19
if [ -z "$2" ] # No argument supplied
34
if [ -z "$4" ] # No argument supplied
20 35
then
21 36
   TARGETS_INCLUSION="true"; # 2 possible values: [true | false]
22 37
else
23
    TARGETS_INCLUSION="$1";
38
    TARGETS_INCLUSION="$4";
24 39
fi
25 40

  
26 41
#########
......
39 54
    fi
40 55
done
41 56

  
42
filepath="../input/simple.edges"
43
input_type=1
44 57
## Running the script
45 58
./graph-parser $filepath $input_type $WEIGHTED_GRAPH $TARGETS_INCLUSION
46 59

  
47 60
## Plotting the results
48
if [ $WEIGHTED_GRAPH = "true" ]
61
if [ $WEIGHTED_GRAPH="true" ]
49 62
then
63
    echo "weighted suffix"
50 64
    SUFFIX="weighted"; # the suffix used in the filename
51 65
else
66
    echo "unweighted suffix"
52 67
    SUFFIX="unweighted";
53 68
fi
54 69

  
custompackages/graph-parser/src/simulation.cpp
116 116

  
117 117
    cout << "    " << run_index << " " << bc_seconds << " | " << hbc_seconds << endl;
118 118

  
119
    string separator = "\t";
119
    string separator = ",";
120 120
    if (out_file.is_open()) {
121 121
        out_file << filename << separator;
122 122
        out_file << graph_type << separator;

Also available in: Unified diff