DZone Snippets: path code

Dijkstra's Algorithm

scvalex (Alexandru Scvortov) — Sat, 01 Dec 2007 19:41:53 GMT

This is a simple O(n^2) implementation of Dijkstra's algorithm for finding the shortest paths from a single source to all nodes in a graph.

Further explanation is given here.



#include 



#define GRAPHSIZE 2048

#define INFINITY GRAPHSIZE*GRAPHSIZE

#define MAX(a, b) ((a > b) ? (a) : (b))



int e; /* The number of nonzero edges in the graph */

int n; /* The number of nodes in the graph */

long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */

long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */



void printD() {

	int i;

	for (i = 1; i <= n; ++i)

		printf("%10d", i);

	printf("\n");

	for (i = 1; i <= n; ++i) {

		printf("%10ld", d[i]);

	}

	printf("\n");

}



void dijkstra(int s) {

	int i, k, mini;

	int visited[GRAPHSIZE];



	for (i = 1; i <= n; ++i) {

		d[i] = INFINITY;

		visited[i] = 0; /* the i-th element has not yet been visited */

	}



	d[s] = 0;



	for (k = 1; k <= n; ++k) {

		mini = -1;

		for (i = 1; i <= n; ++i)

			if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))

				mini = i;



		visited[mini] = 1;



		for (i = 1; i <= n; ++i)

			if (dist[mini][i])

				if (d[mini] + dist[mini][i] < d[i]) 

					d[i] = d[mini] + dist[mini][i];

	}

}



int main(int argc, char *argv[]) {

	int i, j;

	int u, v, w;



	FILE *fin = fopen("dist.txt", "r");

	fscanf(fin, "%d", &e);

	for (i = 0; i < e; ++i)

		for (j = 0; j < e; ++j)

			dist[i][j] = 0;

	n = -1;

	for (i = 0; i < e; ++i) {

		fscanf(fin, "%d%d%d", &u, &v, &w);

		dist[u][v] = w;

		n = MAX(u, MAX(v, n));

	}

	fclose(fin);



	dijkstra(1);



	printD();



	return 0;

}

Bellman-Ford Algorithm

scvalex (Alexandru Scvortov) — Thu, 29 Nov 2007 14:55:34 GMT

This is a simple implementation of the Bellman-Ford algorithm for finding the shortest path from a single source in a graph.

A detailed explanation is given here.



#include 



typedef struct {

	int u, v, w;

} Edge;



int n; /* the number of nodes */

int e; /* the number of edges */

Edge edges[1024]; /* large enough for n <= 2^5=32 */

int d[32]; /* d[i] is the minimum distance from node s to node i */



#define INFINITY 10000



void printDist() {

	int i;



	printf("Distances:\n");



	for (i = 0; i < n; ++i)

		printf("to %d\t", i + 1);

	printf("\n");



	for (i = 0; i < n; ++i)

		printf("%d\t", d[i]);



	printf("\n\n");

}



void bellman_ford(int s) {

	int i, j;



	for (i = 0; i < n; ++i)

		d[i] = INFINITY;



	d[s] = 0;



	for (i = 0; i < n - 1; ++i)

		for (j = 0; j < e; ++j)

			if (d[edges[j].u] + edges[j].w < d[edges[j].v])

				d[edges[j].v] = d[edges[j].u] + edges[j].w;

}



int main(int argc, char *argv[]) {

	int i, j;

	int w;



	FILE *fin = fopen("dist.txt", "r");

	fscanf(fin, "%d", &n);

	e = 0;



	for (i = 0; i < n; ++i)

		for (j = 0; j < n; ++j) {

			fscanf(fin, "%d", &w);

			if (w != 0) {

				edges[e].u = i;

				edges[e].v = j;

				edges[e].w = w;

				++e;

			}

		}

	fclose(fin);



	/* printDist(); */



	bellman_ford(0);



	printDist();



	return 0;

}

add a folder to PATH, but not if it is already in PATH

jmcvetta (Jason McVetta) — Wed, 28 Nov 2007 18:38:16 GMT

Often times one uses a single .profile or .bashrc across several hosts. These hosts may be differently configured, with varying directory locations, and different initial PATH values from /etc/profile. In situations like this, setting PATH the traditional way -- "PATH=$PATH:/path/to/some/stuff" -- can result in a cumbersomely long PATH that includes inaccessible or duplicate folders.

The snippet below nicely handles this problem. It has been tested on Solaris and Linux.



AddPath ()

# Add argument to $PATH if:

# - it is not already present

# - it is a directory

# - we have execute permission on it

#

# This snippet is public domain; you may use it freely.  Death to copyright, patents, 

# and all other forms of intellectual monopoly.  

#

{

  _folder=$1

  echo " $PATH " | sed 's/:/ /g' | grep " $_folder " > /dev/null

  [ $? -ne 0 ] && [ -d $_folder ] && [ -x $_folder ] && PATH=$PATH:$_folder

  export PATH

}



# Add some common paths:

AddPath /usr/bin

AddPath /usr/local/bin

AddPath /opt/somepackage/bin

Printing out the full path of a resource on the classpath

Archanciel (Jean-Pierre Schnyder) — Tue, 04 Sep 2007 09:59:44 GMT

// displaying the full path of a resource found by the class loader on the classpath, here the log4j.xml file



String resourceName = "/log4j.xml"; // pay attention to the leading '/' !

URL location = AnyClass.class.getResource(resourceName);



if (location != null) {

    System.out.println(location.getPath());

} else {

    System.out.println(resourceName + " not found on the classpath");

}

Does a file have a path?

gregg.irwin (Gregg Irwin) — Thu, 05 Apr 2007 18:18:34 GMT



; You could use split-path for this, but it's a bit non-

; orthogonal in what it returns when there's no path.

has-path?: func [file [file!]] [find file #"/"]

Get the path a script was started in

gregg.irwin (Gregg Irwin) — Thu, 05 Apr 2007 18:13:29 GMT



boot-path:   does [system/options/path]

Add a jar file to Java load path at run time

mikewilsonuk (Mike Wilson) — Fri, 23 Feb 2007 15:24:18 GMT

Sometimes it is necessary to amend the class load path at run time. For example, dynamically adding jar files containing user-configurable JDBC data sources. The way this is done is truly monstrous -- the URL Path format was only revealed when a colleague looked into the Java library sources.



import java.net.URL;

import java.io.IOException;

import java.net.URLClassLoader;

import java.net.MalformedURLException;



public class JarFileLoader extends URLClassLoader

{

    public JarFileLoader (URL[] urls)

    {

        super (urls);

    }



    public void addFile (String path) throws MalformedURLException

    {

        String urlPath = "jar:file://" + path + "!/";

        addURL (new URL (urlPath));

    }



    public static void main (String args [])

    {

        try

        {

            System.out.println ("First attempt...");

            Class.forName ("org.gjt.mm.mysql.Driver");

        }

        catch (Exception ex)

        {

            System.out.println ("Failed.");

        }



        try

        {

            URL urls [] = {};



            JarFileLoader cl = new JarFileLoader (urls);

            cl.addFile ("/opt/mysql-connector-java-5.0.4/mysql-connector-java-5.0.4-bin.jar");

            System.out.println ("Second attempt...");

            cl.loadClass ("org.gjt.mm.mysql.Driver");

            System.out.println ("Success!");

        }

        catch (Exception ex)

        {

            System.out.println ("Failed.");

            ex.printStackTrace ();

        }

    }

}

absolute path to itself

heliix (Helena Handrkova) — Wed, 31 Jan 2007 01:43:44 GMT

// returns absolute path to the file from which the code was executed



require 'pathname'

puts(Pathname.new($0).realpath)

fix darwin ports shebang on rails

caffo () — Fri, 12 Jan 2007 01:23:01 GMT

ruby -i -pe 'gsub!("#!/opt/local/bin/ruby", "#!/usr/bin/env ruby")' public/dispatch.* script/*

Path parser //Pascal class

jonasraoni (Jonas Raoni Soares Silva) — Thu, 15 Jun 2006 18:40:23 GMT

An unit to get the special folders' path under windows and it also parses paths shortcuts in the form "$(shortcut)/folder/file.ext".



unit PathParser;



interface



uses

  Classes, SysUtils, TypInfo, SysUtils2, ShlObj, ShellApi, Registry, Windows;



type

  TSpecialFolder = ( sfDesktop, sfAppData, sfTemplates, sfPrograms,

    sfPersonal, sfFavorites, sfStartup, sfRecent, sfSendTo, sfStartMenu,

    sfFonts, sfHistory, sfCookies, sfInternetCache, sfCommonFavorites,

    sfCommonDesktop, sfCommonStartup, sfCommonPrograms, sfCommonStartMenu,

    sfProgramFiles, sfTemporary, sfWindows, sfSystem );



  TSpecialFolderSet = set of TSpecialFolder;



  TPathParser = class( TStringList )

  public

    constructor Create( const UseDefaultMap: Boolean = True );

    class function GetSpecialFolder( const Name: TSpecialFolder ): string;

    function Parse( Path: string ): string;

  end;





implementation



{ TPathParser }



uses Dialogs;



constructor TPathParser.Create(const UseDefaultMap: Boolean);

var

  I: TSpecialFolder;

begin

  CaseSensitive := False;

  if UseDefaultMap then begin

    for I := Low( TSpecialFolder ) to High( TSpecialFolder ) do

      Add( RemoveSlash( LowerCase( Copy( GetEnumName( TypeInfo( TSpecialFolder ),

        Ord( I ) ), 3, MAX_PATH ) ) + '=' + GetSpecialFolder( I ) ) );

    Add( RemoveSlash( Format( 'windowsvolume=%s', [ GetSpecialFolder( sfWindows )[1] ] ) ) );

  end;

end;



class function TPathParser.GetSpecialFolder(

  const Name: TSpecialFolder): string;

const

  FoldersMap: array[TSpecialFolder] of Cardinal = ( CSIDL_DESKTOP,

    CSIDL_APPDATA, CSIDL_TEMPLATES, CSIDL_PROGRAMS, CSIDL_PERSONAL,

    CSIDL_FAVORITES, CSIDL_STARTUP, CSIDL_RECENT, CSIDL_SENDTO, CSIDL_STARTMENU,

    CSIDL_FONTS, CSIDL_HISTORY, CSIDL_COOKIES, CSIDL_INTERNET_CACHE,

    CSIDL_COMMON_FAVORITES, CSIDL_COMMON_DESKTOPDIRECTORY, CSIDL_COMMON_STARTUP,

    CSIDL_COMMON_PROGRAMS, CSIDL_COMMON_STARTMENU, 0, 0, 0, 0 );

var

  Res: Bool;

  Path: array[0..MAX_PATH-1] of Char;

  Reg: TRegistry;

begin

  Result := '';

  case Name of

    sfWindows: GetWindowsDirectory( Path, MAX_PATH );

    sfTemporary: GetTempPath( MAX_PATH, Path );

    sfSystem: GetSystemDirectory( Path, MAX_PATH );

    sfProgramFiles:

    begin

      Reg := TRegistry.Create( KEY_READ );

      try

        Reg.RootKey := HKEY_LOCAL_MACHINE;

        Reg.OpenKey( 'SOFTWARE\Microsoft\Windows\CurrentVersion', False );

        Result := AddSlash( Reg.ReadString( 'ProgramFilesDir' ) );

      finally

        Reg.Free;

      end;

      Exit;

    end;

  else

    Res := ShGetSpecialFolderPath( 0, Path, FoldersMap[ Name ], False );

    if not Res then

      raise Exception.Create( ClassName + '.GetSpecialFolder: Error on ShGetSpecialFolderPath' );

  end;

  Result := AddSlash( Path );

end;



function TPathParser.Parse(Path: string): string;

var

  S: string;

  I, I2, Pos: Integer;

begin

  I := 1;

  while I <= Length( Path )-3 do

  begin

    if ( Path[I] = '$' ) and ( Path[I+1] = '(' ) then

    begin

      I2 := I + 2;

      while ( I2 <= Length( Path ) ) and ( Path[I2] <> ')' ) do

        Inc( I2 );

      if I2 > Length( Path ) then

        Break;

      S := Copy( Path, I + 2, I2 - ( I + 2 ) );

      System.Delete( Path, I, I2 - I + 1 );

      Pos := IndexOfName( S );

      if Pos > -1 then

      begin

        System.Insert( ValueFromIndex[Pos], Path, I );

        Inc( I, Length( ValueFromIndex[Pos] ) );

      end

      else

        raise Exception.CreateFmt( '%s.Parse: Variável "%s" inexistente', [ ClassName, S ] ); //I := I2 + 1;

    end

    else

      Inc( I );

  end;

  Result := Path;

end;



end.