|
| 1 | +# Class GraphBuilder |
| 2 | + |
| 3 | +Creates graph in form of jagged arrays (as compared to Arraylist) for directed as well as undirected graphs from given set of edges in 0 indexing. |
| 4 | + |
| 5 | +All members of this class are static, so no constructor defined. |
| 6 | + |
| 7 | +## Methods |
| 8 | + |
| 9 | +### makeGraph |
| 10 | +``` |
| 11 | +public static int[][] makeGraph(int NumberOfNodes, int NumberOfEdges, int[] from, int[] to, boolean undirected) |
| 12 | +``` |
| 13 | +Returns the adjacency list representation of graph with specified Number of Nodes and Edges and the edges specified in from and to arrays in 0-based indexing. If undirected is set to true, the edges are deemed to be undirected, otherwise directed. |
| 14 | + |
| 15 | +```graph[u]``` is the array of vertices having an edge outgoing from vertex u. |
| 16 | + |
| 17 | +** Constraints ** |
| 18 | +* 0 \leq from[i], to[i] < NumberOfNodes |
| 19 | +* from.length = to.length = NumberOfEdges |
| 20 | + |
| 21 | +** Computational complexity ** |
| 22 | +* $ O (NumberOfNodes + NumberOfEdges) $ |
| 23 | + |
| 24 | +### makeGraphWithEdgeInfo |
| 25 | +``` |
| 26 | +public static int[][][] makeGraphWithEdgeInfo(int NumberOfNodes, int NumberOfEdges, int[] from, int[] to, boolean undirected) |
| 27 | +``` |
| 28 | + |
| 29 | +Returns the adjacency list representation of graph with specified Number of Nodes and Edges and the edges specified in from and to arrays in 0-based indexing. If undirected is set to true, the edges are deemed to be undirected, otherwise directed. This method also returns useful information about edge index and edge direction. |
| 30 | + |
| 31 | +```graph[u]``` is the array of tuples ```[v, idx, direction]``` where edge indexed ```idx``` is between node ```u``` and node ```v``` and direction takes value either $0$ or $1$. |
| 32 | +- If direction is $0$, edge indexed ```idx``` is from ```u``` to ```v``` |
| 33 | +- If direction is $1$, edge indexed ```idx``` is from ```v``` to ```u``` |
| 34 | + |
| 35 | +** Constraints ** |
| 36 | +* 0 \leq from[i], to[i] < NumberOfNodes |
| 37 | +* from.length = to.length = NumberOfEdges |
| 38 | + |
| 39 | +** Computational complexity ** |
| 40 | +* $ O (NumberOfNodes + NumberOfEdges) $ |
0 commit comments