Network tree builder

Dear all,
i have to do a project for university to code a logic in c++ to divide the network into fiber trees according to a given network topology & list of demands but since its my first time to deal with programming its kind of difficult to know how to do it correctly.. here is what i'm trying to do till now after getting all the paths between each source and destination i'm trying to link each path with an Id & number of hops and select the shortest 3 paths/ demand .. but still not working, so i'll be very grateful for anyone that might could help.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
	// C++ program to print all paths from a source to destination.
	#include<iostream>
	#include <list>
	using namespace std;

	// A directed graph using adjacency list representation
	class Graph
	{
		int V; // No. of vertices in graph
		list<int> *adj; // Pointer to an array containing adjacency lists

		// A recursive function used by printAllPaths()
		void printAllPathsUtil(int , int, bool [], int [], int &);

	public:
		Graph(int V); // Constructor
		void addEdge(int u, int v);
		void printAllPaths(int s, int d);
void printShortestPaths(int s, int d);

			int k; 
			int sources;
			int destinations;
                        int id=0;  

	};

	Graph::Graph(int V)
	{
		this->V = V;
		adj = new list<int>[V];
	}

	void Graph::addEdge(int u, int v)
	{
		adj[u].push_back(v); // Add v to u’s list.
	}

	// Prints all paths from 's' to 'd'
	void Graph::printAllPaths(int s, int d)
	{
		// Mark all the vertices as not visited
		bool *visited = new bool[V];

		// Create an array to store paths
		int *path = new int[V];
		int path_index = 0; // Initialize path[] as empty
               
		// Initialize all vertices as not visited
		for (int i = 0; i < V; i++)	
                    visited[i] = false;
		// Call the recursive helper function to print all paths
		printAllPathsUtil(s, d, visited, path, path_index);
               
	}

	// A recursive function to print all paths from 'u' to 'd'.
	// visited[] keeps track of vertices in current path.
	// path[] stores actual vertices and path_index is current
	// index in path[]
	void Graph::printAllPathsUtil(int u, int d, bool visited[],
                                        int path[], int &path_index)
                    {
                        int id_path[40][V-1]; //40 is an example as maximum number of paths 
                        bool id_hops[40];

                    for (int i = 0; i< 40; i++)
                        for (int j = 0; j< V-1; j++)
                            id_path [i][j]=0;
                    for (int i = 0; i< 40; i++)
                            id_hops [i]=0;
		// Mark the current node and store it in path[]
                visited[u] = true;
		path[path_index] = u;
		path_index++;
                int hops = path_index -1;
		// If current vertex is same as destination, then print
		// current path[]
		if (u == d)
                   {
                    if(hops && path)
                        id++;
                        id_hops[id-1]= hops;
                    for (int i = 0; i< path_index; i++)
                       if (path[i]!=0) 
                        id_path[id-1][i]=path[i];
                        cout << "Path_ID = " << id << " Path is : ";   
                    for (int i = 0; i< path_index; i++)
                        cout << path[i] << " ";
                        cout << "Number of hops = " << hops << endl;
                    }
		else // If current vertex is not destination
                    {
			// Recur for all the vertices adjacent to current vertex
			list<int>::iterator i;
                    for (i = adj[u].begin(); i != adj[u].end(); ++i)
			if (!visited[*i])
			printAllPathsUtil(*i, d, visited, path, path_index);
                    }

		// Remove current vertex from path[] and mark it as unvisited
                    path_index--;
                    visited[u] = false;
                    int id_Sorted[3]; //id_Sorted contains the 3 ids of the shortest paths

                for (int j=0; j<3; j++)
                    id_Sorted[j]=0;
            //we select these 3 ids
                    int min=0; //the shortest 
                for (int j=0; j<2; j++)
                   {
                    for (int i=1; i<40; i++)     
                        if ((i!= id_Sorted[0])&& (i!= id_Sorted[1]))
                            {
                                if  (id_hops[i]< id_hops[min])
                                        min=i;
                            }
                    id_Sorted[j]=min;
                    }
        //creation of id_pathShort
                    int id_pathShort[3][V-1];
                for (int j=0; j <= 2; j++)
                   {            
                    cout <<  "Path_ID_Short = " << j << " Path_short is : ";   
                        for (int i=0; i<V-1; i++)
                           {
                            id_pathShort[j][i]=id_path[id_Sorted[j]][i];
                            if (id_pathShort[j][i]) 
                             cout  << id_pathShort[j][i] << " ";
                           }
                             cout << "Number of hops_short = " << id_hops[id_Sorted[j]] << endl;
                   }
	

}

	// Driver program
	int main()
	{
		// Create a graph given in the above diagram
		Graph g(7);
			g.addEdge(1, 2);
			g.addEdge(2, 1);
			g.addEdge(1, 6);
			g.addEdge(6, 1);
			g.addEdge(2, 6);
			g.addEdge(6, 2);
			g.addEdge(2, 3);
			g.addEdge(3, 2);
			g.addEdge(3, 4);
			g.addEdge(4, 3);
			g.addEdge(3, 5);
			g.addEdge(5, 3);
			g.addEdge(4, 5);
			g.addEdge(5, 4);
			g.addEdge(5, 6);
			g.addEdge(6, 5);
		   

                     
		for (int k=0;k<=2; k++)
			{ int sources[k]={1,2,4,5};
			  int destinations[k]={3,4,5,1};
			  int s= sources[k];
			  int d= destinations[k];
                         
		 if( true){
		cout << "Following are all different paths from " << s
                    << " to " << d << endl;
		g.printAllPaths(s, d);
		   }
			};
		return 0;


	}
	
Last edited on
Your indentation makes the code harder to read. I would go back and stick with one style of indentation and also dont indent too much or too little. Also your question is very unclear to me. Try to explain exactly what errors you are receiving or what problems are occurring so we can help you better.
Thanks for your reply, what i'm trying to do is to get all available paths between each pair of source and destination { int sources[k]={1,2,4,5}; int destinations[k]={3,4,5,1} } and according to number of hops ( vertices ) of each path select the 3 shortest out of available paths for each demand [ pair of source and destination ].
the code can get all paths for each demand (i.e., s=1& d=3 ) but i don't know how to select out of these available paths the 1st shortest 3 .
Last edited on
Registered users can post here. Sign in or register to post.