1% graph term form, default
    2%  Graph = graph([a,b,c,d,e,f,g,h], [e(a,b), e(b,a), … ]).
    3
    4:- module(graph, [
    5    generate_undirected_unweighted_graph/2,
    6    generate_undirected_weighted_graph/2,
    7    generate_unweighted_graph/2,
    8    generate_weighted_graph/2,
    9    find_path_unweighted/4,
   10    find_path_weighted/5,
   11    generate_kn/2,
   12    generate_kn_weighted/4,
   13    generate_kn_from_vertices/2,
   14    cycle_unweighted/3,
   15    cycle_weighted/4,
   16    is_connected/1,
   17    node_degree/3,
   18    node_degree_list/2,
   19    generate_empty_unweighted_graph/3,
   20    generate_empty_weighted_graph/3,
   21    is_graph_node/2,    
   22    is_isolated_node/2,
   23    is_graph_edge/2,
   24    get_adjacent_nodes/3,
   25    graph_reverse_edges/2,
   26    spanning_tree/2,
   27    mst_prim/3,
   28    merge_graphs/3
   29]).
   30
   31% generate_undirected_unweighted_graph(+ListOfEdges,-Graph) 
   32% creates a graph in graph-term form and
   33% also removes duplicates
   34% undirected and unweighted graph
   35generate_undirected_unweighted_graph(ListOfEdges,graph(VSorted,ListOfEdgesSorted)):-
   36    findall(X,(member(edge(X,_),ListOfEdges)),VX),
   37    findall(Y,(member(edge(_,Y),ListOfEdges)),VY),
   38    append(VX,VY,V),
   39    sort(V,VSorted),
   40    sort(ListOfEdges,ListOfEdgesSorted).
   41
   42% generate_undirected_weighted_graph(+ListOfEdges,-Graph) 
   43% creates a graph in graph-term form
   44% also removes duplicates
   45% undirected and weighted graph
   46generate_undirected_weighted_graph(ListOfEdges,graph(VSorted,ListOfEdgesSorted)):-
   47    findall(X,(member(edge(X,_,_),ListOfEdges)),VX),
   48    findall(Y,(member(edge(_,Y,_),ListOfEdges)),VY),
   49    append(VX,VY,V),
   50    sort(V,VSorted),
   51    sort(ListOfEdges,ListOfEdgesSorted).
   52
   53% generate_unweighted_graph(+ListOfEdges,-Graph) 
   54% creates a graph in graph-term form
   55% directed and unweighted graph
   56generate_unweighted_graph(ListOfEdges,graph(VSorted,ListOfEdges)):-
   57    findall(X,(member(edge(X,_),ListOfEdges)),VX),
   58    findall(Y,(member(edge(_,Y),ListOfEdges)),VY),
   59    append(VX,VY,V),
   60    sort(V,VSorted).
   61
   62
   63% generate_weighted_graph(+ListOfEdges,-Graph) 
   64% creates a graph in graph-term form
   65% directed and weighted graph
   66generate_weighted_graph(ListOfEdges,graph(VSorted,ListOfEdges)):-
   67    findall(X,(member(edge(X,_,_),ListOfEdges)),VX),
   68    findall(Y,(member(edge(_,Y,_),ListOfEdges)),VY),
   69    append(VX,VY,V),
   70    sort(V,VSorted).
   71
   72
   73% find_path_unweighted(+Graph,+V1,+V2,-Path)
   74% find all paths between V1 and V2 in a directed unweighted graph
   75find_path_unweighted(graph(Vertices,Edges),V1,V2,Path):-
   76    member(V1,Vertices),
   77    member(V2,Vertices),
   78    find_path_unweighted_(V1,V2,Edges,[V1],Path).
   79
   80find_path_unweighted_(V,V,_,L,L).
   81find_path_unweighted_(V1,V2,Edges,L,Path):-
   82    % connected(V1,V2,Edges),
   83    member(edge(V1,V2),Edges),    
   84    append(L,[V2],Path).
   85find_path_unweighted_(V1,V2,Edges,L,Path):-
   86    % connected(V1,VX,Edges),
   87    member(edge(V1,VX),Edges),
   88    VX \== V2,
   89    \+member(VX,L),
   90    append(L,[VX],L1),
   91    find_path_unweighted_(VX,V2,Edges,L1,Path).
   92
   93connected(V1,V2,Edges):-
   94    member(edge(V1,V2),Edges);
   95    member(edge(V2,V1),Edges).
   96
   97connected_w(V1,V2,Edges,C):-
   98    member(edge(V1,V2,C),Edges);
   99    member(edge(V2,V1,C),Edges).
  100
  101% find_path_weighted(+Graph,+V1,+V2,-Path,-Cost)
  102% find all paths between V1 and V2 in a weighted directed graph
  103find_path_weighted(graph(Vertices,Edges),V1,V2,Path,Cost):-
  104    member(V1,Vertices),
  105    member(V2,Vertices),
  106    find_path_weighted_(V1,V2,Edges,[V1],Path,0,Cost).
  107
  108find_path_weighted_(V,V,_,L,L,C,C).
  109find_path_weighted_(V1,V2,Edges,L,Path,CurrC,TotalC):-
  110    % connected_w(V1,V2,Edges,Cost),
  111    member(edge(V1,V2,Cost),Edges),    
  112    append(L,[V2],Path),
  113    TotalC is CurrC + Cost.
  114find_path_weighted_(V1,V2,Edges,L,Path,CurrC,TotalC):-
  115    % connected_w(V1,VX,Edges,Cost),
  116    member(edge(V1,VX,Cost),Edges),        
  117    VX \== V2,
  118    \+member(VX,L),
  119    append(L,[VX],L1),
  120    Curr1 is CurrC + Cost,
  121    find_path_weighted_(VX,V2,Edges,L1,Path,Curr1,TotalC).
  122
  123
  124% generate_kn(+Size,-Graph)
  125% generates a Kn Graph of size Size with vertices name 1,2,..,N
  126% only for undirected and unweighted graph
  127generate_kn(Size,graph(LV,Comb)):-
  128    % Size1 is Size+1,
  129    numlist(1,Size,LV),
  130    find_all_combinations(LV,[],Comb).
  131
  132find_all_combinations([_],C,C):- !.
  133find_all_combinations([H|T],CT,CO):-
  134    find_combinations(H,T,C),
  135    append(CT,C,C1),
  136    find_all_combinations(T,C1,CO).
  137
  138find_combinations(_,[],[]):- !.
  139find_combinations(E,[H|T],[edge(E,H)|TE]):-
  140    find_combinations(E,T,TE).
  141
  142
  143% generate_kn_weighted(+Size,+MinValue,+MaxValue,-Graph)
  144% generates a Kn undirected Graph of size Size with vertices name 1,2,..,N
  145% and assign each cost randomly between MinValue and MaxValue
  146generate_kn_weighted(Size,MinValue,MaxValue,graph(LV,Comb)):-
  147    numlist(1,Size,LV),
  148    find_all_combinations_weighted(LV,MinValue,MaxValue,[],Comb).
  149
  150find_all_combinations_weighted([_],_,_,C,C):- !.
  151find_all_combinations_weighted([H|T],Min,Max,CT,CO):-
  152    find_combinations_weighted(H,T,Min,Max,C),
  153    append(CT,C,C1),
  154    find_all_combinations_weighted(T,Min,Max,C1,CO).
  155
  156find_combinations_weighted(_,[],_,_,[]):- !.
  157find_combinations_weighted(E,[H|T],Min,Max,[edge(E,H,V)|TE]):-
  158    random(Min,Max,V),
  159    find_combinations_weighted(E,T,Min,Max,TE).
  160
  161
  162% generate_kn_from_vertices(+Vertices,-Graph)
  163% generates a Kn Graph of size Size with given vertices name
  164generate_kn_from_vertices(LV,graph(LV,Comb)):-
  165    find_all_combinations(LV,[],Comb).
  166
  167
  168% cycle_unweighted(+Graph,+Vert,-Cycle)
  169% find cycles in an unweighted graph
  170cycle_unweighted(Graph,V,C):-
  171    find_path_unweighted(Graph,V,V,C),
  172    length(C,N),
  173    N > 3.
  174
  175
  176% cycle_weighted(+Graph,+Vert,-Cycle)
  177% find cycles in a weighted graph
  178cycle_weighted(Graph,V,Cycle,Cost):-
  179    find_path_weighted(Graph,V,V,Cycle,Cost),
  180    length(Cycle,N),
  181    N > 3.    
  182
  183
  184% is_connected(+Graph)
  185% check if the graph is connected (checks for each vertex if there is a path
  186% to each remaining vertex)
  187% exist_path 0 for unweighted, 1 for weighted
  188is_connected(graph(LV,Edges)):-
  189    (memberchk(edge(_,_),(Edges)) -> 
  190        exist_path(LV,Edges,0);
  191    exist_path(LV,Edges,1)).
  192
  193exist_path([_],_,_):-!.
  194exist_path([H|T],E,V):-
  195    exist_path_(H,T,E,V),
  196    exist_path(T,E,V).
  197
  198exist_path_(_,[],_,_):-!.
  199exist_path_(H,[H1|T1],E,V):-
  200    (V = 0 ->
  201        connected(H,H1,E);
  202    connected_w(H,H1,E,_)),!,
  203    exist_path_(H,T1,E,V).
  204
  205
  206% node_degree(+Graph,?Node,?Deg).
  207% returns in Deg, the degree of Node
  208node_degree(graph(LN,Edges),Node,Deg):-
  209    member(Node,LN),
  210    (memberchk(edge(_,_),Edges) -> 
  211        (findall(X,(member(edge(X,Node),Edges)),VX),
  212            findall(Y,(member(edge(Node,Y),Edges)),VY)) 
  213        ;
  214        (findall(X,(member(edge(X,Node,_),Edges)),VX),
  215            findall(Y,(member(edge(Node,Y,_),Edges)),VY))
  216    ),
  217    length(VX,NX),
  218    length(VY,NY),
  219    Deg is NX+NY.
  220
  221
  222% node_degree_list(+Graph,-ListOfVerticesDegreeOrder)
  223% returns a list of lists with the form [Degree,Edge]
  224node_degree_list(graph(LV,Edges),L):-
  225    node_degree_list_(LV,LV,Edges,[],L).
  226
  227node_degree_list_([],_,_,L,Sorted):-
  228   sort(0,@>=,L,Sorted). % to keep equal values use msort
  229node_degree_list_([H|T],LV,Edges,LT,L):-
  230    node_degree(graph(LV,Edges),H,Deg),
  231    A = [Deg,H],
  232    append(LT,[A],LT1),
  233    node_degree_list_(T,LV,Edges,LT1,L).
  234
  235
  236% generate_empty_unweighted_graph(+NumNodes,+NumEdges,-Graph)
  237% returns in Graph an empty graph 
  238generate_empty_unweighted_graph(NumNodes,NumEdges,graph(LN,Edges)):-
  239    NumNodes > 0,
  240    NumEdges < NumNodes*(NumNodes - 1),
  241    length(LN,NumNodes),
  242    length(Edges,NumEdges),
  243    maplist(=(edge(_,_)),Edges).
  244
  245% generate_empty_weighted_graph(++NumNodes,++NumEdge,-Graph)
  246% returns in Graph an empty graph 
  247generate_empty_weighted_graph(NumNodes,NumEdges,graph(LN,Edges)):-
  248    NumNodes > 0,    
  249    NumEdges < NumNodes*(NumNodes - 1),    
  250    length(LN,NumNodes),
  251    length(Edges,NumEdges),
  252    maplist(=(edge(_,_,_)),Edges).
  253
  254% is_graph_node succeeds if a node is in the graph
  255% is_graph_node(+Graph,?Node).
  256% if Node is not ground, it returns all the nodes in the graph
  257is_graph_node(graph(LN,_),N):-
  258    member(N,LN).
  259
  260
  261% is_isolated_node succeeds if a node is isolated
  262% is_isolated_node(+Graph,?N)
  263% returns all isolated nodes in backtracking
  264is_isolated_node(graph(LN,Edges),N):-
  265    member(N,LN),
  266    my_not_member(N,Edges).
  267
  268% checks if A is not in list
  269my_not_member(_,[]).
  270my_not_member(A,[E|Edges]):-
  271    (E = edge(NA,NB) ; E = edge(NA,NB,_)),
  272	A \= NA,
  273    A \= NB,
  274    my_not_member(A,Edges).
  275
  276% is_graph_edge succeeds if a edge is in the graph
  277% is_graph_edge(+Graph,?Edge).
  278% if Edge is not ground, it returns all the nodes in the graph
  279is_graph_edge(graph(_,Edges),E):-
  280    member(E,Edges).
  281
  282% get_adjacent_nodes returns the adjacent nodes from the given one
  283% get_adjacent_nodes(+Graph,+Node,-List).
  284% if Node is not ground, returns all nodes with the corresponding list
  285get_adjacent_nodes(graph(LN,Edges),Node,List):-
  286    member(Node,LN),
  287    (memberchk(edge(_,_),Edges) ->
  288        (findall(X,(member(edge(Node,X),Edges)),VX),
  289        findall(Y,(member(edge(Y,Node),Edges)),VY))
  290        ;
  291        (findall(X,(member(edge(Node,X,_),Edges)),VX),
  292        findall(Y,(member(edge(Y,Node,_),Edges)),VY))
  293    ),
  294    append(VX,VY,VT),
  295    sort(VT,List).    
  296
  297
  298% reverse_edges(?Graph,?GraphRev)
  299% returns the graph with reversed edges
  300graph_reverse_edges(graph(LN,Edges),graph(LN,RevEdges)):-
  301    reverse_edges_(Edges,RevEdges).
  302reverse_edges_([],[]).
  303reverse_edges_([edge(X,Y,V)|T],[edge(Y,X,V)|T1]):-!,
  304    reverse_edges_(T,T1).
  305reverse_edges_([edge(X,Y)|T],[edge(Y,X)|T1]):-
  306    reverse_edges_(T,T1).
  307
  308
  309% spanning_trees(+Graph,-SpanningTree)
  310spanning_tree(graph([N|T],Edges),graph([N|T],TreeEdges)) :- 
  311   generate_spanning_tree(T,Edges,TreeEdgesUnsorted),
  312   sort(TreeEdgesUnsorted,TreeEdges).
  313
  314generate_spanning_tree([],_,[]).
  315generate_spanning_tree(Curr,Edges,[Edge|T]) :- 
  316    select(Edge,Edges,Edges1), % select an edge and remove Edge from Edges
  317    get_vertices(Edge,X,Y), % find adjacent vertices
  318    is_connected_to_tree(X,Y,Curr), % check if connected
  319    delete(Curr,X,Curr1), % delete the two vertices
  320    delete(Curr1,Y,Curr2),
  321    generate_spanning_tree(Curr2,Edges1,T).
  322
  323get_vertices(edge(X,Y),X,Y).
  324get_vertices(edge(X,Y,_),X,Y).
  325
  326is_connected_to_tree(X,Y,Ns):- 
  327    memberchk(X,Ns), 
  328    \+ memberchk(Y,Ns), !.
  329is_connected_to_tree(X,Y,Ns):- 
  330    memberchk(Y,Ns), 
  331    \+ memberchk(X,Ns).
  332
  333
  334% mst_prim(+Graph,-MST)
  335% no choice points left opened
  336mst_prim(graph([H|T],Edges),graph([H|T],TreeEdges),Cost):-
  337    predsort(compare_edges_value,Edges,SortedEdges),
  338    generate_spanning_tree(T,SortedEdges,TreeEdgesUnsorted),!, % keep it?
  339    sort(TreeEdgesUnsorted,TreeEdges),
  340    sum_cost(TreeEdges,0,Cost).
  341
  342compare_edges_value(O,edge(X1,Y1,C1),edge(X2,Y2,C2)):-
  343    compare(O,C1+X1+Y1,C2+X2+Y2).
  344
  345sum_cost([],C,C).
  346sum_cost([edge(_,_,C)|T],CT,Tot):-
  347    CT1 is CT+C,
  348    sum_cost(T,CT1,Tot).
  349
  350% merge_graphs(+Graph1,+Graph2,-MergedGraph)
  351% merges two graphs
  352% check if Edges1 and Edges2 have the same structure
  353merge_graphs(graph(L1,Edges1),graph(L2,Edges2),graph(L,Edges)):-
  354    append(L1,L2,LT),
  355    sort(LT,L),
  356    append(Edges1,Edges2,EdgesT),
  357    sort(EdgesT,Edges)