Prolog grade counter and eulerpath

Question

this week I got this homework to do: count the grade of nodes in a undirected graph and test if there is a euler path in it. the function should work like following:

gradliste([[a,b],[b,c],[b,g],[c,d],[d,e],[e,f],[f,g],[g,h],[c,f]],X).
X = [[a, 1], [b, 3], [c, 3], [g, 3], [d, 2], [e, 2], [f, 3], [h, 1]]

testEulerweg([[a,b],[b,c],[c,d],[d,e],[a,e],[b,d],[b,e],[a,d]]).
true.

my first idea of the functiongradlisteis to 'merge' the graph and generate a list like this: [a,b,b,c,b,g,c,d,d,e,e,f,f,g,g,h,c,f] then I count numbers of every node. unfortunately I stucked at the merge.

and for the second function testEulerweg I think I should firstly write a function allconnected working like following:

allconnected([[a,b],[b,c],[c,d]]).
true.

allconnected([[a,b],[b,c],[e,f]]).
False.

then I can check if there are none or 2 nodes with odd grade number using the gradliste function.

Can anyone help me on my idea? I'm also open for new ideas:)

thanks in advance

bearzk

Fred Foo · Accepted Answer · 2011-06-13 10:38:23Z

0

The merge function is simple. I'll rename it flatten:

flatten([[X,Y] | Edges], [X,Y|Rest]) :-
    flatten(Edges, Rest).

And I'll let you write the base case.

As for finding the Eulerian path, check out the algorithms at Wikipedia. The second one can be easily implemented in terms of select/3, as long as you don't flatten the list first :)

answered Jun 13, 2011 at 10:38

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

bearzk Over a year ago

I still don't know how to test if the path is eulerian path, would you mind give me more tips?

Collectives™ on Stack Overflow

Prolog grade counter and eulerpath

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related