From: Andrej V. <an...@us...> - 2010-06-21 06:14:12
|
Update of /cvsroot/maxima/maxima/share/contrib/graphs In directory sfp-cvsdas-4.v30.ch3.sourceforge.com:/tmp/cvs-serv30020 Modified Files: create_graph.mac graph_core.lisp graphio.mac rtest_graphs.mac Log Message: Updates for the graphs package. Index: create_graph.mac =================================================================== RCS file: /cvsroot/maxima/maxima/share/contrib/graphs/create_graph.mac,v retrieving revision 1.9 retrieving revision 1.10 diff -u -d -r1.9 -r1.10 --- create_graph.mac 3 Apr 2010 08:05:51 -0000 1.9 +++ create_graph.mac 21 Jun 2010 06:14:03 -0000 1.10 @@ -19,6 +19,24 @@ */ +as_directed_graph(g) := block( + [edges, dedges], + if is_digraph(g) then return(g), + if not is_graph(g) then error("as_directed_graph: the argument is no a graph!", g), + edges: edges(g), + dedges: append(edges, map(reverse, edges)), + create_graph(vertices(g), dedges, 'directed=true))$ + +relabel_graph_vertices(gr, [options]) := block( + [min_id: assoc('min_id, options, 0), + new_ids: hash_table(), vrt:[], edg:[]], + for v in vertices(gr) do ( + set_hash(v, new_ids, min_id), + vrt: cons(min_id, vrt), + min_id: min_id+1), + for e in edges(gr) do + edg: cons([get_hash(e[1], new_ids), get_hash(e[2], new_ids)], edg), + create_graph(vrt, edg, directed=is_digraph(gr)))$ random_network(n, p, w) := block( [net, source, sink, u, v], @@ -113,7 +131,9 @@ pos:cons([n*j+i, [i/n, j/m]], pos), set_positions(pos, g), g)$ - + +tetrahedron_graph() := complete_graph(4)$ + cube_graph(n) := if n=1 then path_graph(2) else block( @@ -123,6 +143,11 @@ if r=1 then g:graph_product(g, path_graph(2)), g)$ +octahedron_graph() := create_graph( + 6, + [[3,5],[2,5],[1,5],[0,5],[3,4],[2,4],[1,4],[0,4], + [0,3],[2,3],[1,2],[0,1]])$ + icosahedron_graph() := create_graph( 12, [ @@ -270,6 +295,8 @@ snub_cube_graph() := sparse6_decode(":Wa?@_@eCDcDab_`eIfJcGdH_AGIK`BHJL`AGJM_BHINcEGKMdFHLNdEIKNcFJLM")$ +chvatal_graph() := graph6_decode("KhdLA_hc?L_y")$ + add_path(lst, g) := add_edges(vertices_to_path(lst), g)$ Index: graph_core.lisp =================================================================== RCS file: /cvsroot/maxima/maxima/share/contrib/graphs/graph_core.lisp,v retrieving revision 1.26 retrieving revision 1.27 diff -u -d -r1.26 -r1.27 --- graph_core.lisp 19 Jun 2010 10:43:13 -0000 1.26 +++ graph_core.lisp 21 Jun 2010 06:14:03 -0000 1.27 @@ -32,8 +32,7 @@ (defstruct (graph (:print-function (lambda (stru strm depth) - (declare (ignore stru)) - (format strm "GRAPH")))) + (format strm "GRAPH(~a vertices, ~a edges)" (graph-order stru) (graph-size stru))))) (size 0) (order 0) (vertices ()) @@ -46,8 +45,7 @@ (defstruct (digraph (:print-function (lambda (stru strm depth) - (declare (ignore stru)) - (format strm "DIGRAPH")))) + (format strm "DIGRAPH(~a vertices, ~a arcs)" (digraph-order stru) (digraph-size stru))))) (size 0) (order 0) (vertices ()) Index: graphio.mac =================================================================== RCS file: /cvsroot/maxima/maxima/share/contrib/graphs/graphio.mac,v retrieving revision 1.10 retrieving revision 1.11 diff -u -d -r1.10 -r1.11 --- graphio.mac 3 Apr 2010 08:05:51 -0000 1.10 +++ graphio.mac 21 Jun 2010 06:14:03 -0000 1.11 @@ -21,7 +21,7 @@ dimacs_export(gr, file, [comments]) := block( [fl, names:hash_table(), i:1], if not(is_graph_or_digraph(gr)) then error("dimacs_export: first argument is not a graph:", gr), - for v in vertices(gr) do ( + for v in sort(vertices(gr)) do ( set_hash(v, names, i), i:i+1), fl:openw(file), @@ -29,9 +29,9 @@ for c in comments do ( printf(fl, "c ~a~%", c)), if is_graph(gr) then - printf(fl, "p edges ~a ~a~%", graph_order(gr), graph_size(gr)) + printf(fl, "p edge ~a ~a~%", graph_order(gr), graph_size(gr)) else - printf(fl, "p arcs ~a ~a~%", graph_order(gr), graph_size(gr)), + printf(fl, "p arc ~a ~a~%", graph_order(gr), graph_size(gr)), for v in vertices(gr) do ( if get_vertex_label(v, gr)#false then printf(fl, "n ~a ~a~%", get_hash(v, names), get_vertex_label(v, gr))), Index: rtest_graphs.mac =================================================================== RCS file: /cvsroot/maxima/maxima/share/contrib/graphs/rtest_graphs.mac,v retrieving revision 1.1 retrieving revision 1.2 diff -u -d -r1.1 -r1.2 --- rtest_graphs.mac 21 Oct 2008 10:48:59 -0000 1.1 +++ rtest_graphs.mac 21 Jun 2010 06:14:03 -0000 1.2 @@ -226,6 +226,12 @@ edge_connectivity(g); 2; +(g: connect_vertices([5,6],[2,3,4], graph_union(complete_graph(5), complete_graph(5))), 0); +0; + +vertex_connectivity(g); +2; + vertex_connectivity(path_graph(2)); inf; |