Rewriting: Change the Go Code to C


(Re Bertran) #1

Currently translating weighted DAG to C code which is written in Go language and topologically sorted and definitely I’m a stranger at Go. I missed a couple part of the code that is the code below sample. In topoSort function, I couldn’t get what " visit " declaration is. Is it function declaration within another function ? Another part is that in main function that you’ll see it below, couldn’t understand loop processes with “rowIndex, row, number” variables and how they’re getting their values and range keyword in loops. If you translate into C syntax roughly ( might be pseudo code ) or briefly that would be great.

// topoSort()

func (g *graph) topoSort() []int {
    result := make([]int, g.size())
    marks := make([]bool, g.size())
    resultIndex := g.size() - 1

    var visit func(int)
    visit = func(u int) {
        for _, item := range g.adjList[u] {
            if !marks[item.vertex] {
                visit(item.vertex)
            }
        }

        marks[u] = true
        result[resultIndex] = u
        resultIndex--
    }

    for u := range g.adjList {
        if !marks[u] {
            visit(u)
        }
    }

    return result
}

// sampleInput()

func sampleInput() [][]int{
	return [][]int{
		[]int{1},
		[]int{8, 4},
		[]int{2, 6, 9},
		[]int{8, 5, 9, 3},
	}
}

// main()

input := sampleInput()
i := 0
	for rowIndex, row := range input {
		for _, number := range row {
			if rowIndex+1 >= len(input) { // Last row.
				g.addEdge(i, vertexesQuantity, number)
			} else { // Not the last row.
				g.addEdge(i, i + rowIndex + 1, number)
				g.addEdge(i, i + rowIndex + 2, number)
			}

			i++
		}
	}

(Ivan Matmati) #2

Could be :

	#include <stdbool.h> 
	#include <stdlib.h> 

	struct _item {
		int vertex;	
	};

	struct graph {
		int size;
		struct _item**adjList;
	};

	int* topoSort (struct graph* g ){
		int* result = (int*) malloc(g->size*sizeof(int));
		bool* marks = (bool*) malloc(g->size*sizeof(bool));
		int resultIndex = g->size-1;

		void visit(int u){
			for (int i;i<(sizeof g->adjList[u] / sizeof g->adjList[u][0]);i++) {
				struct _item item = g->adjList[u][i];
				if (!marks[item.vertex]) {
					visit(item.vertex);

				}
			}
			marks[u]=true;
			result[resultIndex] = u;
			resultIndex--;
		}
		for (int u;u<(sizeof g->adjList / sizeof g->adjList[0]);u++) {
			if (!marks[u]) {
				visit(u);
			}
		}

		return result;

	}

(Re Bertran) #3

@imatmati Thanks for your contribution. May I ask, do you’ve a chance to visualize " for loop" with C code in main() method ? It would be great if you do.