Skip to content

Commit 4e41ed6

Browse files
authored
Added README.md
1 parent 5d5042d commit 4e41ed6

1 file changed

Lines changed: 40 additions & 0 deletions

File tree

‎GraphBuilder/README.md‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
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

Comments
 (0)